软件学报  2020, Vol. 31 Issue (12): 3716-3732   PDF    
偏好向量引导的高维目标协同进化算法
王丽萍1 , 陈宏2 , 杜洁洁3 , 邱启仓4 , 邱飞岳2     
1. 浙江工业大学 计算机科学与技术学院, 浙江 杭州 310023;
2. 浙江工业大学 教育科学与技术学院, 浙江 杭州 310023;
3. 浙江工业大学 管理学院, 浙江 杭州 310023;
4. 之江实验室, 浙江 杭州 310023
摘要: 多偏好向量引导的协同进化算法(PICEA-g)是将目标向量作为偏好,个体支配目标向量的个数作为适应值,以有效降低高维目标空间中非支配解的比例.但PICEA-g所获解集是近似Pareto前沿,而不是决策者真正感兴趣部分的Pareto最优解,导致算法在处理高维优化问题时性能下降和计算资源的浪费.鉴于此,提出一种基于偏好向量引导的高维目标协同进化算法(ASF-PICEA-g):首先,利用ASF扩展函数将进化种群中的参考点映射至目标空间,并将其作为偏好向量引导种群进化的参考方向;然后,利用偏好区域选择策略获取两个临时参考点,进而构建决策者感兴趣区域(ROI),确定随机偏好集产生的上下界范围,通过协同进化机制引导种群朝偏好区域收敛.将ASF-PICEA-g与g-NSGA-II和r-NSGA-II在3-20维的WFG系列和DTLZ系列测试函数上进行仿真实验,实验结果表明:ASF-PICEA-g在WFG系列测试函数上表现出了良好的性能,所得解集整体上优于对比算法;在DTLZ系列测试函数上略优于对比算法,尤其在10维以上目标空间,ASF-PICEA-g表现出更好的稳定性,所获解集有较好的收敛性和分布性.
关键词: 高维目标优化    协同进化    ASF函数    偏好向量    
Preference Vector Guided Co-evolutionary Algorithm for Many-objective Optimization
WANG Li-Ping1 , CHEN Hong2 , DU Jie-Jie3 , QIU Qi-Cang4 , QIU Fei-Yue2     
1. School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China;
2. College of Education, Zhejiang University of Technology, Hangzhou 310023, China;
3. College of Business Administration, Zhejiang University of Technology, Hangzhou 310023, China;
4. Zhejiang Lab, Hangzhou 310023, China
Abstract: The preference-inspired co-evolutionary algorithm (PICEA-g) uses goal vectors as preferences, and uses the number of target vectors that the individual can dominated as fitness value, to effectively decrease the proportion of non-dominated solutions in high dimensional space. However, the obtained set is approximate Pareto frontier, not Pareto optimal solution that decision makers are really interested in. This leads to the performance degradation and computational resources waste when dealing with high-dimensional optimization problems. Therefore, a preference vector guided co-evolutionary algorithm for many-objective optimization is proposed in this study. Firstly, the ASF extension function is used to map the ideal point in the evolution population on the objective space, which is used as a preference vector to guide the evolution direction of the population. Then, two temporary points are obtained by preference region selection strategy in order to build region of preference for decision maker (ROI). The range of upper and lower bounds generated by random preference sets is determined, and the co-evolution mechanism is used to guide the population to converge towards the ROI. The ASF-PICEA-g is compared with g-NSGA-II and r-NSGA-II on WFG and DTLZ benchmark test functions based on 3 dimension to 20 dimension. The experimental results demonstrate that ASF-PICEA-g shows sound performance on the WFG series test function, and the obtained solution set is better than the comparison algorithm; it is slightly better than the comparison algorithm in the DTLZ series test function, especially in the 10 dimension or higher dimension. In addition, ASF-PICEA-g shows better stability, and the obtained solution set has better convergence and distribution.
Key words: many-objective optimization    co-evolutionary    ASF function    preference vector    

在诸多实际问题中, 需要同时考虑多个目标的优化, 但是各个目标的性能难以同时达到最优.譬如更轻薄的笔记本质量可能会导致电脑价格的提升, 所以需要在各个设计目标之间进行折中考虑, 以获得一组综合性能较好的解.多目标进化算法(multi-objective evolutionary algorithms, 简称MOEA)是解决这类问题的有效途径之一[1-3].近20年来, 国内外涌现出许多的研究成果, 代表性算法有Deb等人提出的非支配排序算法(NSGA-II)[4]、Zitzler等人提出的强的Pareto支配进化算法(SPEA2)[5]和Knowles等人提出的基于参考信息的进化算法(PAES)[6].然而, 随着实际问题的复杂化, 使得原本相对简单的两目标或三目标问题演变成高维目标问题.高维目标优化问题有个非常明显的特征:随着目标维数的增加, 种群中的非支配解比例迅速增加[7], 导致经典算法选择压力不够且覆盖到整个目标空间的解集数量呈指数增长, 导致算法性能急剧下降.传统的多目标优化算法是通过搜索获得分布在整个Pareto前沿上的最优非支配解集.但在高维目标优化实际问题时, 决策者通常只对Pareto前沿上部分解感兴趣, 并没有必要去搜索得到覆盖整个Pareto前沿的解.

因此, 如何有效地将决策者偏好信息与多目标进化算法融合, 求得决策者感兴趣的偏好解[8], 是近年来多目标进化计算领域的一个研究热点.融合偏好信息的高维目标优化算法研究不仅能够提高算法性能、降低算法计算成本, 而且对决策者而言更具有实际意义.例如, Fleming等人[9]提出, 决策者在算法运行过程中不断提供偏好信息, 以缩小搜索区域, 降低算法复杂度; Deb等人提出, 用参考点[10]、参考方向[11]、光束搜索[12]等方法获得决策者的偏好信息, 并将其运用到NSGA-II算法中, 求解高维目标优化问题.受Deb参考点方法启发, Molina等人[13]提出, 基于参考点g-占优解集排序思想, 缩小需要进行排序的解集空间, 提高排序效率, 并提出参考点动态调整策略.但是在g-占优中, 当决策者给出的参考点离Pareto面上很近甚至直接落在前沿面上时, 整个种群会一直在参考点和最优点之间不断变化, 算法收敛性极差.进一步, Said等人[14]提出了一种r占优关系, 在非支配解中建立一组更为严格的偏序集, 但这种占优方法计算复杂度较高, 求解偏好解耗时过长, 尤其当参考点落在可行区域时, 严重影响算法的收敛性.Qiu等人提出双极偏好支配方法[15], 不仅在Pareto非支配解中定义了严格的偏序关系, 而且同时考虑决策者正、负偏好, 引导种群向正参考点的偏好区域靠近且远离负参考点的偏好区域收敛.但是, 当决策者的正参考点远离Pareto前沿时, 双极偏好占优机制容易陷入局部最优而丢失部分最优解.郑金华等人提出一种基于权重迭代的偏好多目标分解算法(MOEA/D-PRE)[16], 该算法主要是利用权重向量对偏好区域进行映射, 以减少参考点对算法的影响, 且易调整偏好区域的大小.Deb提出了基于偏好点的非支配排序算法(an evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, 简称NSGA-III)[17], 该算法的主要思想是:在非支配排序中, 结合分解思想设置参考点, 引导种群进化, 获取相对均匀的解集.上述方法都是解决有偏好信息的多目标优化问题的有效途径.

然而, 上述文献中所提及的偏好表达方式具有一定局限性.如g-NSGA-II, r-NSGA-II等基于占优关系的算法对于参考点选取较为敏感, 参考点的选取对种群的进化影响较大, 若参考点设置在Pareto前沿(PF)附近时, 可能存在所获得偏好区域内种群难以收敛、算法性能不稳定的情况[18].此外, 随着目标维度的增加, 基于占优关系的偏好算法其非支配解的数量急剧增长, 削弱了Pareto支配关系对种群的选择压力, 可能导致算法的收敛性恶化.同时, 在高维空间中, 决策者较难直接给定确切偏好信息, 难以获取偏好区域[19].因此, 本文提出基于偏好向量引导的高维目标协同进化算法:首先, 通过计算个体的收益标量扩展函数值, 将种群映射到目标空间; 随后, 根据偏好区域选择策略确定两个临时参考点, 分别获取距离两个临时参考点收益标量扩展函数值最小的个体, 从而确定偏好集(goal vectors)上下界, 构建偏好区域, 以此减少决策者认知负担以及主观影响; 最后, 利用协同进化机制中适应值截断选取机制增加选择压力, 引导种群向偏好区域收敛.本文提出的基于收益标量扩展函数的偏好区域选择策略具有较好移植性, 能与多种类型的多目标进化算法相结合.

1 相关工作 1.1 协同进化机制

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

Fig. 1 (μ+λ) elite selection framework 图 1 (μ+λ)精英选择框架

1.2 偏好信息的表达方法

关于决策者偏好信息的表达方式大致可分为以下几类[19, 21].

(1)   偏好参考点:在各个目标维度上由决策者的期望值构成的点, 其在每个维度上的值均由决策者事先给出.Wierzbicki等人[22]提出了参考点的设置方法:设定一个参考点r=[r1, r2, …, rM], 该参考点每一维的数值ri代表决策者在第i个目标上的期望值..通过修改参考点的占优机制来引入决策者偏好是一种常见的偏好设置方式, 这种方式改变了种群的支配优先级, 例如g-占优[13]、r-占优[14]、2p-占优[23].这种机制也存在一定的不足,需要决策者事先给出参考点, 且该类算法对参考点的位置较为敏感, 容易导致算法不收敛或陷入局部最优;

(2)   权重:权重以决策向量的方式给出, 代表决策者对于每个目标的偏好程度, 并对每个权重向量给出相应的数学表达[24].权重在一定程度上表达了决策者的期望搜索解集的方向, 即引导种群进化的方向;

(3)   效用函数:效用函数是一种综合了偏好参考点、决策向量和解集信息的函数, 更加直观地反映了算法带来的性能提升程度.但是当面对复杂函数时, 尤其是Pareto前沿信息及其数学特性未知的问题时, 决策者很难将每个目标上的期望值转换成可信赖的效用函数;

(4)   涂刷技术:Wang等人[25]提出一种涂刷技术(brushing technique)来表达决策者偏好信息, 在目标空间中涂刷一部分区域以作为偏好区域(ROI), 优势在于决策者不需要事先了解目标函数的先验信息.因而一定程度上克服了决策者需明确给出权重和期望值的缺陷, 此外, 涂刷技术是交互式的, 决策者可以在算法运行过程中调整偏好信息, 从而使种群逼近偏好区域;

(5)   角度信息:利用参考点r和偏好角度信息α确定目标空间中的偏好区域[26].其中, 参考点r的分量表示决策者在第i维目标上的的期望值, 将参考点r与目标空间中的一个点相连形成基准线,一般与坐标轴原点O或是膝盖点相连, 在基准线左右两边角度α范围内的个体均属于偏好解;

(6)   隐式偏好[27]:不要求决策者提供偏好信息, 而是在求解过程中根据解集的, 动态地给出相应的偏好, 譬如膝盖点区域, 结合机器学习的方法指导算法进化.该方法可以运用于求解先验信息未知的偏好多目标优化问题, 有效减少决策者的决策偏差;

(7)   随机偏好:Wang等人[20]提出一种多偏好驱动下的协同进化算法, 偏好集通过目标向量的形式给出, 通过当前种群的最优解和最差解决定随机偏好产生的范围, 进而引导种群的进化, 种群的迭代反过来以驱动偏好更新.

1.3 收益标量函数(achievement scalarizing functions, 简称ASF)

Wierzrzbicki[22]首次提出了ASF函数, 该函数可以将任意给定的参考点(在可行区域内或者可行区域外)映射到目标空间中, 通过ASF函数找到任意有效解.ASF函数有许多特性[23], 如:

(1)   ASF的最优解总是(弱)Pareto最优的;

(2)   通过改变参考点都可以获得Pareto最优解;

(3)   当参考点就是Pareto最优解时, ASF函数的最优值为0.

s(f(x), zr)表示个体x的收益标量函数值:Rm×RmR, 它是一个标量值.最优化问题可以被写成以下形式: minimize s(f(x), zr), 将最小化标量化函数作为搜索的目标函数.ASF函数通常使用参考点及加权向量表示对目标的偏好, 表现形式如下:

$ s(f(x), {z^r}) = \mathop {\max }\limits_{i \in \{ 1, 2, ..., m\} } \{ {\omega _i}({f_i}(x) - z_i^r)\} $ (1)

研究表明:使权重向量固定, 移动参考点zr, 可以找到(弱)Pareto最优解; 使参考点zr固定, 改变权重向量, 可以找到不同Pareto最优解.但是可能会产生弱Pareto最优解, 因此, 本文使用切比雪夫增广ASF函数表示[29]:

$ s(f(x), {z^r}) = \mathop {\max }\limits_{i \in \{ 1, 2, ..., m\} } \{ {f_i}(x) - z_i^r\} + \rho \sum\limits_{i = 1}^m {({f_i}(x) - z_i^r)} $ (2)

其中, ρ > 0, ρ是一个很小的正数, 称为放大系数; zir为参考点.ASF可以将多目标问题转换成单目标问题, 并且获得一个满足决策者偏好的参考点, 决策者通过交互式过程不断改变ASF函数求得的参考点, 以获得决策者最想要的偏好解.

2 基于偏好向量引导的高维目标协同进化算法

针对大多数偏好多目标进化算法需要决策者人为给定偏好信息, 给决策者带来巨大认知负担的问题[29], 本文提出一种基于偏好向量引导的高维目标协同进化算法(ASF-PICEA-g).在种群进化过程中, 利用ASF函数将参考点映射到目标空间中, 将映射点作为决策者偏好信息, 利用协同进化机制和区域选择策略引导种群朝偏好区域逼近.本文提出的区域选择策略可以和多种多目标进化算法结合, 具有较强的可移植性.

2.1 PICEA框架

多偏好协同进化算法是多目标优化领域的一类新的计算框架, 旨在利用偏好和种群协同进化求解多目标优化问题[9]. PICEA-g算法把目标向量作为偏好集, 将个体支配目标向量的个数作为适应值, 降低高维目标空间中非支配解的比例.在PICEA-g算法中, 候选解s的适应值Fs以及目标向量g的适应值Fg的计算如公式(3)~公式(5)所示:

$ {{F}_{s}}=0+\sum\limits_{g\in G\cup Gc|s\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\prec }g}{\frac{1}{{{n}_{g}}}} $ (3)

其中, ng是满足目标向量g的解的个数, 并且:

$ {F_g} = \frac{1}{{1 + \alpha }} $ (4)
$ \alpha = \left\{ {\begin{array}{*{20}{l}} {1\;, {\rm{ }}{n_g} = 0}\\ {\frac{{{n_g} - 1}}{{2N - 1}}, {\rm{ otherwise}}} \end{array}} \right. $ (5)

其中, N是候选解个数.

根据适应值赋值法的定义可知, 偏好集的产生范围依赖于两个参数:上界值(goalUpper)和下界值(goalLower).更通俗来说, 种群中最优个体与最差个体的差值, 会决定偏好集的范围.如果偏好集只产生在某个区域, 则在此区域内的候选解具有较大可能性被选作父代来产生子代.这主要是由于这些候选解能够支配更多的偏好集, 从而并获得更高的适应值; 反之亦然.由此可知, 候选解会向该区域内部的Pareto前沿逼近.因此, 我们能够通过设定偏好集的上界和下界, 引导候选解朝着决策者感兴趣的区域进化.

图 2(a)所示, 假设存在S1, S2和S3个体, 将偏好集产生区域划分为G1, G2和G3区域.我们发现:位于G3区域的Goal Vectors分别被3个个体所支配, 位于G2区域的Goal Vectors分别被3个个体所支配, 位于G1区域的Goal Vectors只被1个个体所支配.位于G3区域内的Goal Vectors适应值> 位于G2区域内的Goal Vectors适应值> 位于G1区域内的Goal Vectors适应值.Goal Vectors适应值越高, 说明它被解个体支配的可能性越大, 在进化过程中的贡献越小.也就是说, 位于G1区域内的Goal Vectors数量越多, 种群的选择能力越强, 进化速度越快.候选解应当努力支配位于G1区域内的Goal Vectors以获取更高的适应值, 更有可能被保留下来进入下一代遗传变异.

Fig. 2 Analysis of different GoalUpper 图 2 不同GoalUpper设置分析

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

2.2 偏好区域选择策略

受第2.1节启发, 偏好区域依赖于偏好集的产生范围, 因此我们要做的就是如何确定偏好集的上下界, 使候选解集朝向偏好区域进化.本文所提算法确定偏好区域的思想是:在算法进化前期, 获取当前种群的参考点, 利用ASF扩展函数, 找到两个临时参考点, 再分别计算两个临时参考点与每个个体之间的ASF值, 找到离临时参考点最近的两个个体, 由此确定偏好区域, 修改偏好集的goalUpper, 将更多的搜索资源用于决策者感兴趣区域内(ROI)的解集.

值得注意的是:在算法进化前期, 让种群尽可能地在整个目标空间中搜索; 然后, 进行ASF扩展函数计算时, 应该逐渐缩小搜索空间, 直到决策者获得其满意的候选解, 其目的是为了避免算法陷入局部最优.

该策略的特点是:

(1)   不需要决策者事先给偏好信息, 减少决策者的认知负担;

(2)   不依赖于特别给定的参数来调节偏好区域大小.在算法前期, ROI范围大, 此时种群离参考点较远; 随着进化代数的增加, 种群越来越靠近Pareto前沿, ROI范围越来越小;

(3)   根据ASF扩展函数值确定参考点, 并将其映射到目标空间中, 动态地控制偏好集和种群协同进化, 使解集朝偏好区域逼近.

以二维目标举例说明, 如图 3(a)所示.该策略的具体步骤如下:

Fig. 3 Preference area selection strategy 图 3 偏好区域选择策略示意图

Step 1  在当前代数为t的种群P(t)中, 将参考点记为z*, 计算每个个体与参考点z*的ASF值, 找到ASF值最小的个体, 记为Smin;

Step 2  对向量$\overrightarrow {{z^*}{s_{\min }}} $进行正交分解, 得到两个临时参考点(坐标轴上的两个黑色五角星), 分别记为:

$ z_{aux, 1}^* = {z^*} + {e_1}{s_{\min }}, z_{aux, 2}^* = {z^*} + {e_2}{s_{\min }} $

Step 3  分别计算当前种群中每个个体到$z_{aux, i}^*$的ASF值, 找到离临时参考点$z_{aux, i}^*$最近的两个个体, 记为xcloset, I;

Step 4  根据公式fi(y)≤fi(xclosest, i), ∀i=1, 2, …, myROI, 在当前种群中确定哪一些是偏好解, 如图 3(b)所示, 不属于该区域的种群个体将被剔除, 从而确定偏好区域大小.

图 3(b)中, 位于虚线框中的圆圈就代表偏好解, 位于该虚线外的个体被剔除, 从而实现对偏好区域的搜索.

图 3(c)表示随迭代次数的增加, 虚线框中的偏好解趋近于Pareto面, 从而使确定的偏好区域更小.

以二维空间为例, 将偏好选择策略应用于WFG2, WFG3, 并分别在前沿面可行域与不可行域随机选择参考点z=[0.5, 3.5], [1, 1], [1, 2], 其结果如图 4所示.由切比雪夫增广ASF函数的特性[21, 27, 28]可知, 通过该函数可以将任意参考点映射到偏好区间, 且ASF的最优解总是Pareto最优的.因此, 本文通过将参考点z*映射到目标空间, 获得ASF函数最优解, 即函数值最小的个体.然后, 利用偏好区域选择策略获取临时参考点, 从而构建偏好区域.该区域可以通过决策者所给定β值选择偏好区域大小, 从而确定决策者满意的偏好区域.

Fig. 4 Preference area leaded by idea points on WFG2 and WFG3 functions 图 4 在WFG2和WFG3函数上参考点引导的偏好区域

偏好区域确定后, 在该偏好区域内随机产生目标向量, 通过计算目标向量和种群的适应值进行截断选取, 选择适应值大的个体, 即优秀个体.由公式(3)可知:当ng越大时, s的适应值Fs的值为0.即:当候选解s没有满足任何的目标向量g, 则s的适应值Fs的值为0.因此, 偏好区域外的解集所能支配的目标向量少, 其适应值随种群进化而变小; 同时, 由于协同进化算法中偏好向量与解集的适应值截断选取机制, 选择适应值大的个体, 即偏好区域内个体被优先保留, 偏好区域外个体由目标向量引导朝偏好区域收敛.

但是, 当β=1且参考点z*与标准前沿设置较近时, z*所对应的ASF函数值最小的个体Smin距离z*较近, 对$\overrightarrow {{z^*}{s_{\min }}} $进行正交分解后获得临时参考点, 可能导致两个临时参考点所对应的ASF函数值最小的个体相同, 从而使得该策略仅获得一个偏好点, 而非偏好区域.因此在仿真实验中, 若参考点与前沿较近时, β应大于1.

2.3 算法步骤

算法中所用参数如下:进化种群P的规模为N, 偏好G的规模为Ngoal, 最大进化代数为MaxGen.图 5为算法流程图.首先, 初始化种群及目标向量并确定初始参数, 通过交叉变异获得子代种群, 将父代种群与子代种群放入交配池S+Sc, 从而将父子代种群函数值的最大最小值作为子代偏好向量产生的上下界, 从而得到混合目标向量G+Gc; 然后, 利用适应值赋值法对个体及目标向量进行评价, 截断选择产生新子代种群和新子代目标向量, 如Step 1, Step 2所示.在进化前期, 使算法在目标空间中尽可能搜索, 不对种群进行偏好区域的设置, 避免陷入局部最优; 在进化中后期, 利用偏好选择策略确定偏好区域并对偏好区域内个体进行适应值评价, 如Step 3, Step 4所示.在此过程中, 决策者可通过修正参考点及β值修改偏好区域的位置及大小.其具体步骤如下所示.

Fig. 5 Algorithm flowchart 图 5 算法流程图

Step 1  设置初始参数, 产生初始种群P=(P1, P2, …, PN)和初始化偏好集$G = ({G_1}, {G_2}, ..., {G_{{N_{goal}}}}), $偏好集上界$goalUpper = 1.2 \times \mathop {\max }\limits_{1 \le i \le 2N} {f_j}({x^i}), $偏好集下界$goalLower = \mathop {\min }\limits_{1 \le i \le 2N} {f_j}({x^i});$

Step 2  对进化种群P进行交叉变异产生新的子代种群Pc, 更新偏好集G的上下界, 并随机产生新的偏好Gc, 更新外部集合Qt, 将种群PPc、偏好向量GGc混合, 并通过适应值计算公式分别计算其各自适应值, 截断选择产生新子种群和新偏好向量集;

Step 3  利用ASF扩展函数将进化种群中的参考点映射至目标空间, 并将其作为偏好向量引导种群进化的参考方向, 然后利用偏好区域选择策略获取两个临时参考点进而构建ROI区域, 确定随机偏好向量集产生的上下界范围;

Step 4  利用协同进化机制对目标函数进行优化, 在ROI区域内的候选解中选择适应值最大的N个候选解进入下一代进化, 引导种群朝偏好区域收敛;

Step 5  判断是否满足终止条件:若否, 返回Step 2;否则, 算法终止运行.

在ASF-PICEA-g中包含两个竞争主体:一个竞争主体是偏好向量集, 另一个竞争主体是候选解集.协同进化框架的主要思想是:基于(μ+λ)精英选择框架, 利用偏好向量集和候选解协同进化.若偏好向量集被越少的候选解支配, 则其适应值越高; 若候选解所支配的偏好向量个量越多, 则其适应值越高.评分的目的是选择出性能较好的候选解和偏好向量集进行交叉变异操作, 以此有利于种群进化.在合作协同机制的运作下, 偏好向量集不断通过择优的方式选择出父代, 并且引导种群向Pareto前沿逼近.

3 实验结果与分析 3.1 参数分析实验

在仿真实验中, 目标向量产生区域的大小对解集质量会产生较大影响, 而目标向量产生区域大小由β值控制:当β值大于2时, 目标向量产生区域过大, 导致资源浪费, 不利于种群收敛, 如图 6(e)所示; 当β值小于1时, 目标向量产生在不可行域, 不利于目标向量和解集的适应值计算, 可能导致种群中优秀个体的丢失, 如图 6(a)所示.由此可见, 合适的β值对于种群进化至关重要.因此, 本文将β值分别设为0.5, 1, 1.5, 2和4, 并选取8个二维WFG系列(WFG2~WFG9)测试函数进行仿真实验.种群规模和偏好规模均为100, 距离参数L=14, 位置参数L=18.在此次仿真实验中, 每个算法迭代次数均为250代, 且在相同环境下运行20次.所有实验在笔记本电脑上运行, 电脑配置4GB内存, 32位Windows 7操作系统, 处理器为Intel(R)Core(TM)i3-2310M CPU.

Fig. 6 Simulation diagram of different β values on WFG3 function 图 6 在WFG3函数上不同β值仿真图

图 7(a)~图 7(h)是二维WFG测试函数在不同β取值下的HV指标值盒图.从实验结果看:当β值为0.5时, 除测试函数WFG3外, 在其他测试函数上的HV指标值均等于或低于其他β值.原因在于:β值为0.5时, 偏好集产生范围上界从当前种群中的最差值缩小至原来的0.5倍, 位于边界区域的解很难搜索进化, 最终产生的解集整体质量很差.当β值为1时, 在WFG2测试函数上, 所求得的HV指标值高于β值为1.5和β值为4所求得的HV指标值; 在WFG3测试函数上, 所求得的HV指标值皆低于其他β值所求得的HV指标值, 解集整体质量较差; 在WFG4~WFG6和WFG8测试函数上, 所求得的HV指标值等于或低于β值为1.5、β值为2和β值为4所求得的HV指标值; 在WFG7测试函数上, 所求得的HV指标值高于其他β值所求得的HV指标值, 相较于其他对比情况, 解集整体质量高; 在WFG9测试函数上, 所求的HV指标值高于β值为0.5和β值为4所求得的HV指标值, 但低于或等于β值为1.5和β值为2所求得的HV指标值.当β值为1.5时, 在WFG2测试函数上, 所求解集质量最差; 在WFG3, WFG5和WFG9测试函数上, 所求解集质量最好; 在WFG4, WFG6~WFG8测试函数上, 所求解集整体质量低于β值为2和β值为4所求得的解集质量; 当β值为2时, 在WFG2, WFG4~WFG8测试函数上, 所求解集的HV指标值等于或高于其他β值所求得的HV指标值; 在WFG3和WFG9测试函数上, 所求解集的HV指标值并没有明显优势.当β值为4时, 在WFG系列测试函数上, 与其他β值所求得的HV指标值相比没有明显优势, 在WFG2, WFG7和WFG9测试函数上表现较差.

Fig. 7 Box plots of HV results for algorithms with different β value on WFG test function 图 7 WFG测试函数上的β值盒图

从上述实验结果分析可得:基于5种不同的β取值在WFG系列测试函数上的表现, 总体来说, 当β取值为1, 1.5和2时, 大部分测试函数的解集整体质量较高.对于WFG7和WFG9测试函数, β取值区间为[1, 2]时, 解集质量最高.原因可能在于, 这两个测试函数都是凹的且有偏的, 偏好集产生的区域放大倍数不宜太大, 否则容易造成算法收敛性较差.针对性质为凹且多峰的测试函数(如WFG4和WFG9)或者性质为凹且不可分解的测试函数(如WFG6, WFG8和WFG9), β的取值最好为1.5或者2, 偏好集产生的范围太大和太小皆会导致所求解集质量的下降.通过上述分析, 我们可以认为, 将β取值设在区间[1, 2]内较为合理.

3.2 性能指标评价

本文从收敛性、综合性两个方面对该算法进行性能评价.通常使用收敛性衡量所获解集与真实Pareto前沿之间的逼近程度, 使用综合性表示解集尽可能地分布在整个Pareto前沿.目前文献中所提及的指标多达十几种, 本文使用时代距离来表示收敛性, 使用反向时代距离表示综合性.

(1)  世代距离(GD)[30]是一种评价所求近似Pareto解集和理想Pareto前沿间距离的方法, 公式如下:

$ GD \buildrel \Delta \over = \frac{{{{\left( {\sum\limits_{i = 1}^n {d_i^p} } \right)}^{1/p}}}}{n} $ (6)

其中, n表示所求近似Pareto解集向量个数.GD的值越小, 则说明解集收敛性越好.

(2)  反向世代距离指标(IGD)[31]是计算标准Pareto前沿到个体的平均欧式距离.设解集P*是一组真实Pareto前沿, 解集P是一组近似解集, IGD定义公式如下:

$ IGD(P, {P^*}) = \frac{1}{{|{P^*}|}}\sum\limits_{x \in {P^*}} {\mathop {\min }\limits_{y \in P} d(x, y)} $ (7)

其中, P*表示真实前沿, P表示算法求得的近似Pareto解集, min d(x, y)为解x与解y之间的欧几里得距离.近似Pareto解集越逼近真实前沿, 则所得的IGD值就越小, 算法的性能也就越优.若P*中参考点足够多且能够描绘出完整Pareto前沿, 那么IGD指标在衡量所获解集收敛性的同时, 也可以衡量其多样性.

(3)  超体积指标(hyper volume, 简称HV)[32]是一种能够在某种程度上同时衡量算法收敛性和多样性的综合性评价指标, 计算公式如下所示:

$ HV(P, r) = volume\left( {\bigcup\limits_{f \in P} {[{f_{1, }}{r_1}] \times ... \times [{f_{m, }}{r_m}]} } \right) $ (8)

其中, P表示近似解集:r表示参考点, 该参考点r被近似解集P中的所有个体支配.HV值越大, 表明算法所求解集质量越高.

3.3 ASF-PICEA-g算法与其他算法的性能对比实验

表 1表示g-NSGA-II[13], r-NSGA-II[14]和ASF-PICEA-g在DTLZ测试函数上所求解集的GD值和IGD值.其中, 数字加粗表示该算法GD值, 即收敛性最优; 数字加下划线表示IGD值最小, 即综合性最优.目标个数分别扩展至3, 5, 7, 10, 15和20维.

Table 1 GD index value and IGD index value on DTLZ test function 表 1 DTLZ测试函数GD指标值和IGD指标值表

从GD指标上看, r-NSGA-II算法在DTLZ1和DTLZ3测试函数上表现优于对比算法, ASF-PICEA-g在DTLZ2和DTLZ4测试函数上表现优于对比算法, 在10维的DTLZ4测试函数上, g-NSGA-II算法略优于其他算法, 在其他维度的测试函数表现最差.原因在于DTLZ2和DTLZ4函数性质为简单连续且单模态, 其初始种群离真实Pareto前沿较近, ASF-PICEA-g能够有效搜索到Pareto前沿, 展现出良好的收敛性, 并且随着目标数量的增加, 算法收敛性没有出现严重的衰退.而DTLZ1和DTLZ3函数性质为复杂且多模态, 并且产生的初始种群远离真实Pareto前沿, 对于3种算法的收敛搜索都带来巨大的挑战.实验结果表明:在这类复杂性质的测试函数上, 3种算法所求解集的GD指标值较大, 导致算法不收敛.

从IGD指标上看, ASF-PICEA-g在10维DTLZ1, DTLZ2和3维DTLZ4测试函数上的IGD指标优于对比算法, r-NSGA-II算法在5维DTLZ1和DTLZ3测试函数上的IGD指标优于对比算法, 在7维DTLZ1和5维、7维、10维DTLZ4测试函数上, g-NSGA-II算法表现较优.IGD指标实验结果表明:在大多数测试函数上, r-NSGA- II和ASF-PICEA-g所求解集的整体质量较高.原因在于:g-NSGA-II算法采用的Flag分区严格限制了种群的搜索路径, 导致算法难以收敛到Pareto前沿上的偏好区域.另外, 在15维与20维的结果上, 可知ASF-PICEA-g在DTLZ1-4测试函数上GD值及IGD值要明显优于对比算法, 且与5维、7维、10维数据相差不大, 而g-NSGA-II与r-NSGA-II算法在15维与20维上, GD值与IGD值急剧增加.原因在于:基于支配关系的算法随维度增加, 其非支配解个数呈指数级增长, 导致算法对种群的选择压力急剧下降, 使得算法性能急剧恶化.而ASF-PICEA-g使用的协同进化算法框架, 在通过ASF扩展函数所获得的偏好区域内, 目标向量与个体协同进化, 一方面合理利用计算资源, 另一方面通过适应值截断选取机制增加了选择压力, 使得算法性能保持在较稳定状态.

综上所述, 伴随着目标维度的增加, 在解集空间中, 非支配解的比例呈现迅猛增长的态势, 而ASF-PICEA-g算法通过偏好选择策略和协同进化机制, 较有效地解决算法在高维目标优化问题中的非支配解比例过高的问题, 加快种群逼近Pareto前沿的收敛速度, 提高算法整体性能.

表 2表示g-NSGA-II, r-NSGA-II和ASF-PICEA-g在WFG测试函数上所求解集的GD指标值, 其中:加粗表示该算法GD值最小, 即收敛性能最优; 下划线表示20次运行后GD方差值最小, 方差值越小, 则算法稳定性越好.

Table 2 GD index value on WFG test function 表 2 WFG测试函数上的GD指标值表

除了2维和3维的WFG2测试函数、2维和5维的WFG3和WFG5测试函数外, ASF-PICEA-g所求解集的GD值均小于对比算法.ASF-PICEA-g是基于偏好集与种群协同进化框架, 能有效减少高维目标中非支配解的比例, 提高选择压力.相比于对比算法, 在5维和7维的WFG2-WFG5测试函数上, g-NSGA-II的GD指标值较大, 说明g-NSGA-II在高维WFG2-WFG5测试函数的算法收敛性较差, 难以收敛到Pareto前沿上的ROI区域.从5维上看, 在WFG2和WFG4测试函数上, ASF-PICEA-g优于g-NSGA-II和r-NSGA-II; 从7维上看, ASF- PICEA-g在WFG2-WFG4测试函数上均优于g-NSGA-II和r-NSGA-II.原因在于:随着目标维数的增加, g-NSGA- II和r-NSGA-II的选择个体机制是基于Pareto占优的, 选择能力急剧下降, 而协同进化机制能有效克服这一缺陷, 减少目标空间中非支配解得比例, 加快种群收敛速度.从指标方差看, 3种算法所求解集质量较稳定.

图 8分别表示ASF-PICEA-g算法在WFG2~WFG5二维测试函数上的Pareto前沿图.从图 8中可以发现, ASF-PICEA-g算法以偏好向量引导的偏好区域中的解集在前沿上分布较为集中.ASF-PICEA-g在大多数的WFG测试函数上表现较好, 但在WEG5测试函数上, 可以发现其收敛性较差, 如图 8(d)所示.

Fig. 8 Attainment surface of ASF-PICEA-g for WFG2~WFG5 图 8 ASF-PICEA-g算法在WFG2~WFG5测试函数上的前沿图

图 9~图 12分别表示g-NSGA-II, r-NSGA-II和ASF-PICEA-g算法在DTLZ1~DTLZ4的3维测试函数上的Pareto前沿图.

Fig. 9 Attainment surface of the algrithms for DTLZ1 图 9 g-NSGA-II, r-NSGA-II和ASF-PICEA-g在DTLZ1测试函数上的前沿图

Fig. 10 Attainment surface of the algrithms for DTLZ2 图 10 g-NSGA-II, r-NSGA-II和ASF-PICEA-g在DTLZ2测试函数上的前沿图

Fig. 11 Attainment surface of the algrithms for DTLZ3 图 11 g-NSGA-II, r-NSGA-II和ASF-PICEA-g在DTLZ3测试函数上的前沿图

Fig. 12 Attainment surface of the algrithms for DTLZ4 图 12 g-NSGA-II、r-NSGA-II和ASF-PICEA-g在DTLZ4测试函数上的前沿图

在DTLZ1和DTLZ3上, g-NSGA-II完全没有收敛到标准前沿, 原因在于g-NSGA-II受到参考点位置的影响, 当参考点位于可行区域或Pareto面上时, 容易陷入局部搜索, 最终导致算法不收敛.而r-NSGA-II在DTLZ1和DTLZ3上均能够收敛到标准Pareto前沿, 但从图 9(b)图 9(c)图 11(b)图 11(c)可知:r-NSGA-II所求偏好区域较为分散; 而ASF-PICEA-g所获偏好区域较为集中, 更有利于决策者做出选择.在DTLZ2和DTLZ4测试函数上, g-NSGA-II和r-NSGA-II所求解集在前沿上分布均较为分散, 没有完全收敛到偏好区域.反观ASF-PICEA-g所求解集在前沿上的分布情况, 候选解都较好地收敛到参考点附近.

图 13表示10维DTLZ2测试函数在g-NSGA-II, r-NSGA-II和ASF-PICEA-g算法上的前沿图.从10维上看, g-NSGA-II所求的解集比较散乱, 虽然靠近参考点, 但是收敛效果较差.原因在于:g-NSGA-II机制是一种放松的Pareto占优机制, 造成高维目标空间中非支配解比例过大.r-NSGA-II所求解集均匀分布在参考点附近, 收敛效果比g-NSGA-II要好.同样的, 本算法所求解集也均匀分布在参考点附近, 体现出了偏好信息的引导作用.上述分析可得:在10维的DTLZ2测试函数上, 所求得的偏好集能够很好地满足决策者的偏好, 并且能很好地收敛到前沿上.随着目标维数的增加, ASF-PICEA-g算法性能并未明显衰减, 所求解集仍然集中在决策者感兴趣区域.

Fig. 13 Attainment surface of the algrithms with 10 objects for DTLZ2 图 13 g-NSGA-II, r-NSGA-II和ASF-PICEA-g在10维DTLZ2测试函数上的测试结果

4 总结与展望

为了减少决策者在处理高维目标问题的认知负担, 本文利用ASF扩展函数将参考点映射到目标空间, 将映射点作为决策者偏好表达的一种方式, 同时利用偏好区域选择策略和协同进化机制, 构建决策者感兴趣区域, 进而提出基于多偏好引导的协同进化多目标优化算法(ASF-PICEA-g).实验结果表明:ASF-PICEA-g在WFG系列测试函数上整体优于对比算法; 在DTLZ1, DTLZ3这类复杂多模态测试函数上, 本文所提算法略优于其他对比算法, 在简单连续单模态的DTLZ2, DTLZ4测试函数上优于对比算法, 尤其在10维以上目标空间中, ASF- PICEA-g表现出更好的稳定性, 能够有效引导种群朝偏好区域快速收敛, 所求解集质量更高.对于高维目标优化算法而言, 如何正确有效表达决策者的偏好信息仍存在较大的研究空间.未来我们将继续在高维目标优化算法中, 进一步探索如何有效地融入决策者的信息, 在提高算法精度的同时, 也进一步提高算法基于偏好信息求解的收敛速度.

参考文献
[1]
Zhou A, Qu BY, Li H, et al. Multiobjective evolutionary algorithms:A survey of the state of the art. Swarm and Evolutionary Computation, 2011, 1(1): 32-49. [doi:10.1016/j.swevo.2011.03.001]
[2]
Giagkiozis I, Purshouse RC, Fleming PJ. An overview of population-based algorithms for multi-objective optimisa-tion optimisation. Int'l Journal of Systems Science, 2015, 46(9): 1572-1599. [doi:10.1080/00207721.2013.823526]
[3]
Coello Coello CA. Twenty years of evolutionary multi-objective optimization:A historical view of the field. IEEE Computational Intelligence Magazine, 2006, 1(1): 28-36.
[4]
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2002, 6(2): 182-197. [doi:10.1109/4235.996017]
[5]
Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Proc. of the Eurogen 2001 Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, 2001.
[6]
Knowles JD, Corne DW. Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation, 2006, 8(2): 149-172.
[7]
Kong WJ, Ding JL, Chai TY. Survey on large-dimensional multi-objective evolutionary algorithm. Control and Decision, 2010, 25(3): 321-326(in Chinese with English abstract).
[8]
Trivedi A, Srinivasan D, Sanyal K, et al. A survey of multi-objective evolutionary algorithms based on decomposition. IEEE Trans. on Evolutionary Computation, 2017, 21(3): 440-462.
[9]
Fleming PJ, Purshouse RC, Lygoe RJ. Many-objective optimization:An engineering design perspective. LNCS, 2005, 3410: 14-32.
[10]
Deb K, Sundar J. Reference point based multi-objective optimization using evolutionary algorithms. Int'l Journal of Computational Intelligence Research, 2006, 2(3): 635-642. http://www.ams.org/mathscinet-getitem?mr=2300926
[11]
Deb K, Kumar A. Interactive evolutionary multi-objective optimization and decision-making using reference direction method. In: Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2007). London, 2007. 788-802.
[12]
Deb K, Kumar A. Light beam search based multi-objective optimization using evolutionary algorithms. In: Proc. of the IEEE Congress on Evolutionary Computation. 2007. 2125-2132.
[13]
Molina J, Santana LV, Hernández-Díaz AG, et al. g-dominance:Reference point based dominance for multiobjective metaheuristics. European Journal of Operational Research, 2009, 197(2): 685-692. [doi:10.1016/j.ejor.2008.07.015]
[14]
Said LB, Bechikh S, Dira K. The r-dominance:A new dominance relation for interactive evolutionary multicriteria decision making. IEEE Trans. on Evolutionary Computation, 2010, 14(5): 801-818. [doi:10.1109/TEVC.2010.2041060]
[15]
Qiu FY, Wu YS, Qiu QC, Wang LP. Many-Objective evolutionary algorithm based on bipolar preferences dominance. Ruan Jian Xue Bao/Journal of Software, 2013, 24(3): 476-489(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/24/476.htm [doi:10.3724/SP.J.1001.2013.04273]
[16]
Zheng JH, Yu G, Jia Y. Research on moea/d based on user-pereference and alternate weight to solve the effect of reference point on multi-objective algorithms. Acta Electronica Sinica, 2016, 44(1): 67-76(in Chinese with English abstract).
[17]
Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I:Solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2014, 18(4): 577-601. [doi:10.1109/TEVC.2013.2281535]
[18]
Wang LP, Feng ML, Qiu QC, Zhang ML, Qiu FY. Survey on preference-based multi-objective evolutionary algorithms. Chinese Journal of Computers, 2019, 42(6): 1289-1315(in Chinese with English abstract).
[19]
Du JJ. Research on many objective evolutionary algorithm based on multi preference of coevolution[MS. Thesis]. 2018(in Chinese with English abstract).
[20]
Wang R, Purshouse RC, Fleming PJ. Preference-Inspired coevolutionary algorithms for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2013, 17(4): 474-494. [doi:10.1109/TEVC.2012.2204264]
[21]
Coello CAC. Evolutionary multi-objective optimization:A historical view of the field. IEEE Computational Intelligence Magazine, 2006, 1(1): 28-36. [doi:10.1109/MCI.2006.1597059]
[22]
Wierzbicki AP. The use of reference objectives in multiobjective optimization. In: Proc. of the Multiple Criteria Decision Making Theory and Application. Berlin, Heidelberg: Springer-Verlag, 1980. 468-486.
[23]
Qiu FY, Wu YS, Qiu QC, Wang LP. Many-Objective evolutionary algorithm based on bipolar preferences dominance. Ruan Jian Xue Bao/Journal of Software, 2013, 24(3): 476-489(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4273.htm [doi:10.3724/SP.J.1001.2013.04273]
[24]
Guo JW, Pu XQ, Gao X, Zhang Y. Improved method on weights determination of indexes in multi-objective decision. Journal of Xidian University, 2014, 41(6): 118-125(in Chinese with English abstract).
[25]
Wang R, Purshouse RC, Giagkiozis I, et al. The iPICEA-g:A new hybrid evolutionary multi-criteria decision making approach using the brushing technique. European Journal of Operational Research, 2014, 243(2): 442-453.
[26]
Zheng JH, Lai N, Guo GQ. ε-Pareto dominance strategy based on angle preference in MOEA. Pattern Recognition and Artificial Intelligence, 2014, 27(6): 569-575(in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTotal-MSSB201406013.htm
[27]
Das I. On characterizing the "kne" of the Pareto curve based on normal-boundary intersection. Structural & Multidisciplinary Optimization, 1999, 18(2-3): 107-115.
[28]
Goulart F, Campelo F. Preference-Guided evolutionary algorithms for many-objective optimization. Information Sciences, 2016, 329: 236-255. [doi:10.1016/j.ins.2015.09.015]
[29]
Sindhya K, Deb K, Miettinen K. Improving convergence of evolutionary multi-objective optimization with local search:A concurrent-hybrid algorithm. Natural Computing, 2011, 10(4): 1407-1430. [doi:10.1007/s11047-011-9250-4]
[30]
Coello CAC, Lamont GB, Veldhuizen DAV. Evolutionary Algorithms for Solving Multi-Objective Problems. New York:Springer-Verlag, 2002.
[31]
Yu GY, Li P, He Z, et al. Advanced evolutionary algorithm used in multi-objective constrained optimization problem. Computer Integrated Manufacturing Systems, 2009, 15(6): 1172-1178.
[32]
Zitzler E, Thiele L. Multiobjective optimization using evolutionary algorithms-A comparative case study. In: Proc. of the Parallel Problem Solving from Nature (PPSN V). Berlin, 1998. 292-301.
[7]
孔维健, 丁进良, 柴天佑. 高维多目标进化算法研究综述. 控制与决策, 2010, 25(3): 321-326.
[15]
邱飞岳, 吴裕市, 邱启仓, 王丽萍. 基于双极偏好占优的高维目标进化算法. 软件学报, 2013, 24(3): 476-489. http://www.jos.org.cn/1000-9825/24/476.htm [doi:10.3724/SP.J.1001.2013.04273]
[16]
郑金华, 喻果, 贾月. 基于权重迭代的偏好多目标分解算法解决参考点对算法影响的研究. 电子学报, 2016, 44(1): 67-76.
[18]
王丽萍, 丰美玲, 邱启仓, 章鸣雷, 邱飞岳. 偏好多目标进化算法研究综述. 计算机学报, 2019, 42(6): 1289-1315.
[19]
杜洁洁.基于多偏好协同的高维目标进化算法研究[硕士学位论文].杭州: 浙江工业大学, 2018.
[23]
邱飞岳, 吴裕市, 邱启仓, 王丽萍. 基于双极偏好占优的高维目标进化算法. 软件学报, 2013, 24(3): 476-489. http://www.jos.org.cn/1000-9825/4273.htm [doi:10.3724/SP.J.1001.2013.04273]
[24]
郭金维, 蒲绪强, 高祥, 等.一种改进的多目标决策指标权重计算方法.西安电子科技大学学报, 2014, 41(6): 118-125.
[26]
郑金华, 赖念, 郭观七. 多目标进化算法中基于角度偏好的ε-Pareto支配策略. 模式识别与人工智能, 2014, 27(6): 569-575. http://www.cnki.com.cn/Article/CJFDTotal-MSSB201406013.htm