Page 55 - 《软件学报》2020年第12期

王丽萍 等:偏好向量引导的高维目标协同进化算法 3721

如图 2(b)~图 2(d)所示,虚线区域为偏好集产生区域,偏好集产生区域与最优 Pareto 前沿的重合部分就是
ROI 区域.根据实验结果可知,在进化过程中设置不同偏好集的上界,对种群进化方向会产生巨大的影响.可以说
明:偏好集的不同设置,能够引导不同的候选解向决策者感兴趣区域搜索进化.

2.2 偏好区域选择策略
受第 2.1 节启发,偏好区域依赖于偏好集的产生范围,因此我们要做的就是如何确定偏好集的上下界,使候
选解集朝向偏好区域进化.本文所提算法确定偏好区域的思想是:在算法进化前期,获取当前种群的参考点,利
用 ASF 扩展函数,找到两个临时参考点,再分别计算两个临时参考点与每个个体之间的 ASF 值,找到离临时参考
点最近的两个个体,由此确定偏好区域,修改偏好集的 goalUpper,将更多的搜索资源用于决策者感兴趣区域内
(ROI)的解集.
值得注意的是:在算法进化前期,让种群尽可能地在整个目标空间中搜索;然后,进行 ASF 扩展函数计算时,
应该逐渐缩小搜索空间,直到决策者获得其满意的候选解,其目的是为了避免算法陷入局部最优.
该策略的特点是:
(1) 不需要决策者事先给偏好信息,减少决策者的认知负担;
(2) 不依赖于特别给定的参数来调节偏好区域大小.在算法前期,ROI 范围大,此时种群离参考点较远;随
着进化代数的增加,种群越来越靠近 Pareto 前沿,ROI 范围越来越小;
(3) 根据 ASF 扩展函数值确定参考点,并将其映射到目标空间中,动态地控制偏好集和种群协同进化,使
解集朝偏好区域逼近.
以二维目标举例说明,如图 3(a)所示.该策略的具体步骤如下:
*
*
Step 1 在当前代数为 t 的种群 P(t)中,将参考点记为 z ,计算每个个体与参考点 z 的 ASF 值,找到 ASF
值最小的个体,记为 S min ;

*
Step 2 对向量 zs min 进行正交分解,得到两个临时参考点(坐标轴上的两个黑色五角星),分别记为:
z * aux ,1 = z + * e s , z * aux ,2 = z + * e s ;
1 min
2 min
Step 3 分别计算当前种群中每个个体到 z * aux ,i 的 ASF 值,找到离临时参考点 z * aux ,i 最近的两个个体,记为
x closet,I ;
Step 4 根据公式 f i (y)≤f i (x closest,i ),∀i=1,2,…,m⇒y∈ROI,在当前种群中确定哪一些是偏好解,如图 3(b)所
示,不属于该区域的种群个体将被剔除,从而确定偏好区域大小.
图 3(b)中,位于虚线框中的圆圈就代表偏好解,位于该虚线外的个体被剔除,从而实现对偏好区域的搜索.
图 3(c)表示随迭代次数的增加,虚线框中的偏好解趋近于 Pareto 面,从而使确定的偏好区域更小.

真实 临时参考点 真实 临时参考点
*
F 2 Z 理想解 F 2 Pareto F 2
候选解个体 偏好区域内的个体 Pareto 偏好区域内的个体
临时参考点 前沿 偏好区域外的个体 前沿 偏好区域外的个体
*
Z +S min*e 2
S min
ROI
ROI
区域 区域
*
Z +S min*e 1
Z * F 1 Z * F 1 Z * F 2
(a) 临时参考点 (b) 偏好区域 (c) 种群进化
Fig.3 Preference area selection strategy
图 3 偏好区域选择策略示意图
以二维空间为例,将偏好选择策略应用于 WFG2,WFG3,并分别在前沿面可行域与不可行域随机选择参考