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

3718 Journal of Software 软件学报 Vol.31, No.12, December 2020

偏好算法其非支配解的数量急剧增长,削弱了 Pareto 支配关系对种群的选择压力,可能导致算法的收敛性恶化.
同时,在高维空间中,决策者较难直接给定确切偏好信息,难以获取偏好区域 [19] .因此,本文提出基于偏好向量引
导的高维目标协同进化算法:首先,通过计算个体的收益标量扩展函数值,将种群映射到目标空间;随后,根据偏
好区域选择策略确定两个临时参考点,分别获取距离两个临时参考点收益标量扩展函数值最小的个体,从而确
定偏好集(goal vectors)上下界,构建偏好区域,以此减少决策者认知负担以及主观影响;最后,利用协同进化机制
中适应值截断选取机制增加选择压力,引导种群向偏好区域收敛.本文提出的基于收益标量扩展函数的偏好区
域选择策略具有较好移植性,能与多种类型的多目标进化算法相结合.
1 相关工作

1.1 协同进化机制
Fleming 等人提出一种多偏好驱动下的协同进化算法
父代种群, (preference-inspired co-evolutionary algorithms for many-
父代目标向量 [20]
适应值赋值 objective optimization,简称 PICEA) ,该算法的主要思想是:将
截断选择
多目标进化算法与协同机制结合,利用适应度截选机制提高种
遗传变异 μ+λ精英选择 混合种群, 群选择压力,实现偏好与种群协同进化,如图 1 所示 [20] .需要说明
操作 混合目标向量
的是:随机偏好不是由决策者提供的参考信息,而是用来和候选
解集比较的一种方式.这是经典的(μ+λ)精英选择框架,S 是含有
子代种群, 父子代混合 N 个候选解的集合,G 是含有 N Goal 个目标向量的集合.首先,初始
子代目标向量
化种群及目标向量,通过交叉变异产生子代种群,并根据种群范
Fig.1 (μ+λ) elite selection framework 围内随机产生子代目标向量;然后,将父代种群与子代种群合并,
图 1 (μ+λ)精英选择框架 父代目标向量与子代目标向量合并,形成混合种群及混合目标

向量,并计算目标向量与个体各自的适应度值,按照适应度值截
断选择,形成新的父代种群及父代目标向量混合种群及混合
目标.
1.2 偏好信息的表达方法

关于决策者偏好信息的表达方式大致可分为以下几类 [19,21] .
(1) 偏好参考点:在各个目标维度上由决策者的期望值构成的点,其在每个维度上的值均由决策者事先给
出.Wierzbicki 等人 [22] 提出了参考点的设置方法:设定一个参考点 r=[r 1 ,r 2 ,…,r M ],该参考点每一维的数
值 r i 代表决策者在第 i 个目标上的期望值..通过修改参考点的占优机制来引入决策者偏好是一种常
见的偏好设置方式,这种方式改变了种群的支配优先级,例如 g-占优 [13] 、r-占优 [14] 、2p-占优 [23] .这种
机制也存在一定的不足，需要决策者事先给出参考点,且该类算法对参考点的位置较为敏感,容易导
致算法不收敛或陷入局部最优;
(2) 权重:权重以决策向量的方式给出,代表决策者对于每个目标的偏好程度,并对每个权重向量给出相
应的数学表达 [24] .权重在一定程度上表达了决策者的期望搜索解集的方向,即引导种群进化的方向;
(3) 效用函数:效用函数是一种综合了偏好参考点、决策向量和解集信息的函数,更加直观地反映了算法
带来的性能提升程度.但是当面对复杂函数时,尤其是 Pareto 前沿信息及其数学特性未知的问题时,决
策者很难将每个目标上的期望值转换成可信赖的效用函数;
(4) 涂刷技术:Wang 等人 [25] 提出一种涂刷技术(brushing technique)来表达决策者偏好信息,在目标空间中
涂刷一部分区域以作为偏好区域(ROI),优势在于决策者不需要事先了解目标函数的先验信息.因而
一定程度上克服了决策者需明确给出权重和期望值的缺陷,此外,涂刷技术是交互式的,决策者可以
在算法运行过程中调整偏好信息,从而使种群逼近偏好区域;