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

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

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)是解决这类问题的有效途径之
[4]
一 [1−3] .近 20 年来,国内外涌现出许多的研究成果,代表性算法有 Deb 等人提出的非支配排序算法(NSGA-II) 、
[5]
Zitzler 等人提出的强的 Pareto 支配进化算法(SPEA2) 和 Knowles 等人提出的基于参考信息的进化算法
[6]
(PAES) .然而,随着实际问题的复杂化,使得原本相对简单的两目标或三目标问题演变成高维目标问题.高维目
[7]
标优化问题有个非常明显的特征:随着目标维数的增加,种群中的非支配解比例迅速增加 ,导致经典算法选择
压力不够且覆盖到整个目标空间的解集数量呈指数增长,导致算法性能急剧下降.传统的多目标优化算法是通
过搜索获得分布在整个 Pareto 前沿上的最优非支配解集.但在高维目标优化实际问题时,决策者通常只对
Pareto 前沿上部分解感兴趣,并没有必要去搜索得到覆盖整个 Pareto 前沿的解.
[8]
因此,如何有效地将决策者偏好信息与多目标进化算法融合,求得决策者感兴趣的偏好解 ,是近年来多目
标进化计算领域的一个研究热点.融合偏好信息的高维目标优化算法研究不仅能够提高算法性能、降低算法计
[9]
算成本,而且对决策者而言更具有实际意义.例如,Fleming 等人 提出,决策者在算法运行过程中不断提供偏好
信息,以缩小搜索区域,降低算法复杂度;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] .此外,随着目标维度的增加,基于占优关系的