引用本文

刘元, 郑金华, 邹娟, 喻果. 基于邻域竞赛的多目标优化算法. 自动化学报, 2018, 44(7): 1304-1320. doi: 10.16383/j.aas.2017.c160315

LIU Yuan, ZHENG Jin-Hua, ZOU Juan, YU Guo. An Evolutionary Algorithm Through Neighborhood Competition for Multi-objective Optimization. ACTA AUTOMATICA SINICA, 2018, 44(7): 1304-1320. doi: 10.16383/j.aas.2017.c160315

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160315

关键词

多目标优化算法，Pareto支配关系，邻域竞赛机制，高维优化问题 

摘要

传统多目标优化算法（Multi-objective evolution algorithms，MOEAs）的基本框架大致分为两部分：首先是收敛性保持，采用Pareto支配方法将种群分成若干非支配层；其次是分布性保持，在临界层中，采用分布性保持机制维持种群的分布性.然而在处理高维优化问题（Many-objective optimization problems，MOPs）（目标维数大于3）时，随着目标维数的增加，种群的收敛性和分布性的冲突加剧，Pareto支配关系比较个体优劣的能力也迅速下降，此时传统的MOEA已不再适用于高维优化问题.鉴于此，本文提出了一种基于邻域竞赛的多目标优化算法（Evolutionary algorithm based on neighborhood competition for multi-objective optimization，NCEA）.NCEA首先将个体的各个目标之和作为个体的收敛性估计；然后，计算当前个体向量与收敛性最好的个体向量之间的夹角，并将其作为当前个体的邻域估计；最后，通过邻域竞赛方法将问题划分为若干个相互关联的子问题并逐步优化.为了验证NCEA的有效性，本文选取5个优秀的算法与NCEA进行对比实验.通过对比实验验证，NCEA具有较强的竞争力，能同时保持良好的收敛性和分布性.

文章导读

近几年, 因为多目标优化算法(Multi-objective evolution algorithms, MOEAs)能高效地解决NP难问题, 被广泛地运用到各个领域, 包括工程、经济、后勤等.但大部分多目标进化算法仅在处理2维和3维多目标优化问题(Multi-objective optimization problems, MOPs)时, 能得到收敛性和分布性均较好的非支配解集.然而现实问题中, 大部分优化问题都是高维多目标优化问题, 通常需要同时优化多个相互冲突的目标, 目标维数甚至达到10 ~ 15.因此, 在处理高维多目标优化问题时, 我们需要找到一组均衡收敛性和分布性的解集.

高维多目标优化是指对目标维数大于3的MOPs进行优化.对于维数较高的MOPs, 想要获得一组Pareto最优解集非常困难, 一些处理低维数目标时不会遇到的问题将凸显出来, 同时随着目标维数的增加, Pareto支配关系的优化效果会逐渐减弱[1].故而对于强调非支配解的优化算法, 如果种群中解的选择压力还是如低维目标一样, 那么种群进化速度将会减慢, 甚至停滞.因此在高维优化问题的研究中, 分布性保持机制将对算法的性能起决定性作用[2].

然而, 分布性主导的选择机制可能会对算法的收敛性能造成负面影响[3-4].目前大多数分布性保持机制, 如小生境(Niche)、聚集距离(Crowding Distance)、聚类(Clustering)等[5], 由于它们过于强调分布性, 种群在优化中可能会偏好支配抵抗解(Dominance resistant solutions, DRSs)[6].这些DRSs具有较好的分布性能, 但由于某一维或者几维上的收敛性远逊色于其他个体, 这些DRSs不仅不能增加种群向真实Pareto面逼近的选择压力, 反而在某种程度上阻碍了种群的进化搜索, 以致于没有分布性保持机制的算法反而在高维情况下能够表现出更好的收敛性[7].因此, 在处理高维优化问题中, 选择合适的分布性保持机制对基于Pareto支配关系的优化算法至关重要.

最近几年, 为了解决在处理高维优化问题时所面临的难题, 研究者们已提出了许多优秀的算法, 根据算法的收敛性和分布性的保持机制的不同, MOEAs大致可以分为以下5类.

1) 宽松Pareto支配关系的算法:此类算法的主要思想是将个体的Pareto支配区域进行适当的放大, 再与其他个体进行支配比较.而这类算法一般都需要一组参数来控制个体的支配需求, 故而参数的设置决定了此类算法性能.如ϵ-MOEA[8]、CDAS[9]、模糊支配[10]等.

2) 基于评价指标的算法:此类算法借鉴了评价指标的思想, 对评价指标稍加修改, 在个体之间两两比较, 从而帮助选择机制找到更好的个体.如IBEA[11]、SMS-EMOA[12]等.

3) 基于聚合的算法:此类算法通过设计一组均匀的权重系数将高维多目标优化问题转化为单目标优化问题, 再进行逐个优化, 而权重的均匀性决定了种群的分布性.如MSOPS (Multiple single objective pareto sampling)[13]、MOEA/D[14]、NSGA (Non-dominated sorting genetic algorithm)-Ⅲ[15], 基于目标分解的高维多目标并行进化算法[16]等.

4) 基于排列的算法:此类算法通过定义新的排列方法来区分个体之间的好坏, 使个体间形成全序关系.因此基于排序的算法不会受到目标空间维数的影响.如AR + DMO[17]等.

5) 基于密度估计的算法:此类算法通过改进分布性保持机制来提高收敛性.其主要思想是为种群中的每个个体设置密度估计信息, 使收敛性差的个体获得更高的密度值, 使分布性保持机制能在维持种群均匀分布的同时提高收敛性.如SDE[3] (计算平移后个体的聚集距离作为个体的密度估计, 值越小, 表示个体越密集), GrEA[18] (GrEA中引入了网格聚集距离GCD来表示个体的密度估计, 当GCD值越大表示个体的密度估计越大)等.

以上介绍的5类算法利用不同的策略提高了算法在高维多目标优化问题上的性能, 同时为解决高维多目标优化问题提供了新的选择和思路.本文提出一种基于邻域竞赛的多目标算法(Neighborhood competition-based multi-objective evolutionary algorithms, NCEA)求解高维多目标优化问题. NCEA在邻域竞赛机制中同时为个体设计了收敛信息和分布信息, 首先, 根据收敛信息保留收敛性好的个体; 然后, 通过竞赛机制将分布性差的个体淘汰掉.因此, 在临界层选择过程中, 不会因为分布性保持而破坏种群的收敛能力.

为了检验本文算法的性能, 将算法与其他5种经典算法ϵ-MOEA[8]、MSOPS[15]、NSGA-Ⅲ[17]、GrEA (Grid-based evolutionary algorithm)[18]、AR + DMO[17]分别在相同条件下优化DTLZ系列测试问题[19]并进行性能比较.实验结果表明, 在收敛性和分布性上, NCEA与其他5种算法相比能够获得更好的性能.

图 1  邻域竞赛机制示意图

图 3  收敛信息对不同类型问题的影响

图 4  分布信息示意图

本文提出了一种基于邻域竞赛机制的高维多目标算法NCEA:首先, 通过收敛信息选择优秀个体; 然后通过分布信息以竞赛模式淘汰分布性差的个体. NCEA一方面提高了种群的收敛性能, 另一方面确保了种群的分布性.同时, 为了证实算法在处理高维问题的有效性, 本文选择5种优秀的算法进行了大量的对比实验.实验结果表明, NCEA在7个测试问题的不同维度上(3, 4, 5, 6, 8, 10)整体性能(收敛性以及分布性)最佳.它在保证种群能快速地收敛到最优Pareto面上的同时还兼顾了种群的分布性能, 使得种群能铺满整个最优Pareto面上.

本文已经通过大量的分析验证了NCEA能够很好地求解高维优化问题, 但是需要指出的是, NCEA的性能在一定程度上依赖于角度参数α的设置.因此, 在后续的工作中, 需要根据不同问题自适应的产生合适的角度参数, 这样可以大大提高NCEA算法在实际优化问题上的适用性, 减少不必要的时间开销.另外, 为了检验算法的有效性, 引进更多的实际问题检测NECA的性能也是今后的研究重点.

作者简介

刘元

湘潭大学信息工程学院硕士研究生.主要研究方向为高维多目标进化算法.E-mail:liu3yuan@gmail.com

郑金华

湘潭大学信息工程学院教授.2000年获得中南大学控制理论与控制工程专业博士学位.主要研究方向为进化计算, 多目标遗传算法, 机器学习.E-mail:jhzheng@xtu.edu.com

喻果  

湘潭大学信息工程学院硕士研究生.主要研究方向为偏好多目标优化算法.E-mail:yuguo0801@126.com

邹娟  

湘潭大学信息工程学院副教授.2014年获得湘潭大学应用与数学专业博士学位.主要研究方向为人工智能, 优化算法设计, 进化计算.本文通信作者.E-mail:zoujuan@xtu.edu.com