Page 155 - 《软件学报》2021年第12期

孙哲人 等:面向多目标优化的多样性代理辅助进化算法 3819

解 x 与参考向量 w 的角度θ的计算如下:
⎛ ˆ ⋅ yw ⎞
θ = arccos ⎜ ⎟ (11)
|| ⎝ ˆ || || ⋅ w || ⎠ y
其中, ˆ y 是目标函数值,w∈W 为参考向量,||⋅||是向量的模.
*
*
最小相关解集的具体算法见算法 2,其中,d(x,z )为解 x 到理想点 z 的距离.对于解集 X 中的每个解 x,其相关
参考向量是与 x 相差角度最小的参考向量.对于一个参考向量 w,其相关解为所有相关参考向量为 w 的解,可能
*
没有也可能很多个.参考向量 w 的最小相关解为 w 的相关解中距离理想点 z 最近的一个.所有参考向量的最小
*
相关解组成的集合即为解集 X 的最小相关解集.其中,z =(min(f 1 ),...,min(f m )),min(f i )为种群 P 中的解在第 i 个目
标上的最小值.
算法 2. 最小相关解集 MCS.
输入:X:解集;
W:参考向量集;
输出:C:每个参考向量 w 的最小相关解的集合.
1. for 每个 x∈X do
2. 找到与 x 角度相差最小参考向量 w∈W;
*
*
3. if isempty(C w )||d(x,z )<d(C w ,z ) then
4. 把 x 设置为 w 的最小相关解 C w =x;
5. end
6. end
2.4 候选解生成算子
候选解生成算子是在模型评估下迭代优化候选解,以得到在现有模型下表现较为优秀的候选解,具体见算
法 3.为了充分利用现有条件,候选解生成算子使用训练集 A 作为初始解,而不是重新随机采样.每次生成子代解
之前,如果|X|小于|A|,就从训练集 A 中随机选择|A|−|X|个解加入 X.这样可以使 X 中解的数量不会太少,以提高算
法的探索能力和解的多样性,从而更大机会搜索到更多有希望的候选解.在得到初始父代解后,候选解生成算子
使用模拟二进制交叉(simulated binary crossover) [27] 和多项式突变(polynomial mutation) [28] 算子生成子代解,并
使用 Kriging 模型评估其函数值.然后计算父代解和子代解并集的最小相关解集,把最小相关解集中的解作为下
一代父代解继续迭代优化.当达到最大迭代次数时,输出候选解集.
算法 3. 候选解生成算子 Candidates.
输入:A:训练集 A;
W:参考向量集;
model:Kriging 模型;
w max :最大评估次数;
输出:X:候选解集.
1. X=A;
2. while w max >0 do
3. if |X|<|A| then
4. 从 A 中随机选择|A|−|X|个解添加到 X;
5. end
6. 生成子代解 off,并使用 model 评估 off;
7. X=X∪off;
8. X=MCS(X); //计算 X 的最小相关解集,见算法 2
9. w max =w max −|off|;