引用本文

封文清, 巩敦卫. 基于在线感知 Pareto 前沿划分目标空间的多目标进化优化. 自动化学报, 2020, 46(8): 1628−1643 doi: 10.16383/j.aas.2018.c180323

Feng Wen-Qing, Gong Dun-Wei. Multi-objective evolutionary optimization with objective space partition based on online perception of Pareto front. Acta Automatica Sinica, 2020, 46(8): 1628−1643 doi: 10.16383/j.aas.2018.c180323

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c180323

关键词

多目标进化优化，Pareto前沿，间断点，目标空间划分，MOEA/D 

摘要

多目标进化优化是求解多目标优化问题的可行方法.但是, 由于没有准确感知并充分利用问题的Pareto前沿, 已有方法难以高效求解复杂的多目标优化问题.本文提出一种基于在线感知Pareto前沿划分目标空间的多目标进化优化方法, 以利用感知的结果, 采用有针对性的进化优化方法求解多目标优化问题.首先, 根据个体之间的拥挤距离与给定阈值的关系感知优化问题的Pareto前沿上的间断点, 并基于此将目标空间划分为若干子空间; 然后, 在每一子空间中采用MOEA/D (Multi-objective evolutionary algorithm based on decomposition)得到一个外部保存集; 最后, 基于所有外部保存集生成问题的Pareto解集.将提出的方法应用于15个基准数值函数优化问题, 并与NSGA-Ⅱ、RPEA、MOEA/D、MOEA/DPBI、MOEA/D-STM和MOEA/D-ACD等比较.结果表明, 提出的方法能够产生收敛和分布性更优的Pareto解集, 是一种非常有竞争力的方法.

文章导读

优化是工程实践和科学研究中主要的问题形式之一, 其中, 仅有1个目标函数的优化问题, 称为单目标优化问题; 目标函数超过1个且存在冲突的最优化问题, 称为多目标优化问题(Multi-objective optimization problems, MOPs).与单目标优化问题相比, 多目标优化问题更加普遍地存在于科学研究和工程应用领域, 如半导体制造、工业调度以及控制系统[1-4].其特点在于, 优化问题不仅包含多个目标, 而且目标之间相互冲突, 从而难以得到使各目标都达到最优的解, 而只存在一个折衷解的集合, 称为Pareto最优解集(Pareto-optimal set)[5].针对多目标优化问题, 出现众多优异的多目标进化算法[6-9], 其中文献[10]在2009年提出基于分解的多目标进化算法(Multi-objective evolutionary algorithm based on decomposition, MOEA/D), 该算法首先将多目标优化问题分解成多个单目标子问题, 然后并行优化各子问题, 并基于聚合函数选择最优解, 提高了Pareto解集的选择压力, 并通过实验验证了所提方法对解决具有复杂Pareto前沿形状的问题有较好的效果.

针对多目标优化问题, 最初采用数学规划方法, 将多目标优化问题转化为单目标问题, 典型的方法包括:加权和法、切比雪夫法(Tchebycheff approach), 以及边界交集法等[11-12].多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的, 使得传统的数学规划方法求解效率偏低, 且对权值和目标的次序敏感. 20世纪80年代中期, 进化优化应用于求解多目标优化问题, 即多目标进化. 90年代中期, 多目标优化开始迅速发展, 大体分为两个阶段:

第一阶段主要采用基于Pareto占优的个体选择和适应值共享的多样性保持, 典型的方法有多目标遗传算法(Multi-objective genetic algorithms, MOGA)[13]、非支配排序遗传算法(Non-dominated sorting genetic algorithm, NSGA)[14]和小生境遗传算法(Niched Pareto genetic algorithm, NPGA)[15]. MOGA首先基于Pareto占优, 将种群中的个体划分不同的等级, 并基于此对个体排序; 然后通过适应度共享调整个体的适应值, 并基于调整后的适应值选择优势个体. MOGA大的选择压力, 导致种群往往早熟收敛. NSGA选择非被占优解之后共享一个虚拟适应值, 并选择后续的非被占优解. NSGA不但计算复杂度高, 而且需要预先设定共享参数的值.在NPGA中, 采用基于Pareto占优的锦标赛选择并辅以小生境技术, 生成子代种群.但是, 该算法中小生境半径的选取和调整困难, 且需要确定比较集的规模.

第二阶段主要以外部保存集用来存放进化过程中的非被占优个体, 保证了解集的分布性, 代表性的方法有强度Pareto进化算法(Strength Pareto evolutionary algorithm Ⅱ, SPEA-Ⅱ)[16]、非支配排序遗传算法Ⅱ (Non-dominated sorting genetic algorithm Ⅱ, NSGA-Ⅱ)[17]和Pareto包络选择算法Ⅱ (Pareto envelop-based selection algorithm-Ⅱ, PESA-Ⅱ)[18]. NSGA-Ⅱ基于序值的快速非被占优解排序, 降低了计算复杂度. PESA-Ⅱ基于网格选择个体, 使得解集具有好的收敛性, 特别适合于求解高维多目标优化问题.但是, 该算法执行一次选择操作只能选择一个个体, 导致计算消耗增多, 且解集的多样性不佳. SPEA约定适应度低的个体对应高的选择概率, 并设置除进化种群外的一个外部种群, 保存当前非被占优个体.当外部种群的个体数目超过设定值时, 采用聚类方法删减个体, 从进化种群和外部种群中选择个体进行交叉和变异操作.但是, 该算法的计算复杂度较高.

实际的多目标优化问题的Pareto前沿往往具有复杂的特征, 可能是长尾、多峰或不连续的.如果问题的Pareto前沿具有长尾, 那么, 获得好的分布性能的解集将非常困难; 多峰优化问题往往需要寻找多个极值点, 而已有方法主要求解优化问题的全局极值, 因此, 非常具有挑战性; 当优化问题的Pareto前沿不连续时, 间断边界搜索的不准确, 往往导致解集的分布范围非常有限.对于这些优化问题, 已有方法通常难以有效求解.

为了有效求解具有复杂Pareto前沿的优化问题, 文献[19-20]提出了新的非被占优解保留方法, 并且通过优化Pareto解集的评价指标, 代替优化原来的问题; 虽然在多种评价指标中, 超体积(Hypervolume)最为常用, 但是, 鉴于其计算耗时长, 因此, 利用蒙特卡洛方法估计超体积.文献[21-22]是MOEA/D的改进, 通过分析Tchebycheff聚合函数, 确定初始的方向向量, 且引入方向向量的自适应调整, 获得具有好的分布性的解集.文献[23]提出了一个参考向量引导的多目标优化算法, 采用角度惩罚距离的标量化方法, 平衡目标空间中解的收敛和多样性, 根据目标函数的尺度动态调整参考向量的分布.文献[24]针对规则和不规则POF的问题, 提出基于分解的参考向量自适应的g-DBEA算法, 采用学习期间积累的关于特定的参考矢量的非支配解的数量的信息, 引导参考矢量的适应.

需要指出的是, 这些工作假定优化问题的Pareto前沿形状可粗略估计, 并基于Pareto前沿形状, 设计有针对性的求解方法.对于实际的优化问题, 与该问题相关的数据往往难以获取, 从而难以估计问题的Pareto前沿.如果基于进化求解过程获取的数据, 在线感知问题的Pareto前沿, 那么, 在后续的求解过程中, 将能够基于感知的Pareto前沿, 设计有针对性的优化问题求解方法, 对于优化问题的解决, 是非常有帮助的.

鉴于此, 本文研究多目标优化问题Pareto前沿的在线感知问题, 并提出基于在线

感知Pareto前沿划分目标空间的多目标进化优化方法.首先, 基于拥挤距离, 感知优化问题的Pareto前沿是否存在间断点; 然后, 如果存在间断点, 那么, 将目标空间划分为若干子空间, 并在每一子空间上采用MOEA/D, 得到一系列外部保存集, 基于此, 生成问题的Pareto解集; 否则, 采用传统的MOEA/D, 生成问题的Pareto解集.

本文的贡献主要体现在如下3个方面: 1)提出了基于拥挤距离的优化问题Pareto前沿间断点感知方法; 2)提出了基于在线感知Pareto前沿划分目标空间的多目标进化优化方法; 3)将提出的方法应用于15基准数值函数优化问题, 并与NSGA-Ⅱ、基于参考点的进化算法(Reference points-based evolutionary algorithm, RPEA)[25]、MOEA/D、MOEA/D-PBI[26]、MOEA/D-STM[27]和MOEA/D-ACD[28]等比较, 验证了所提方法的有效性.

本文结构安排如下:第1节综述相关工作; 本文的方法在第2节提出; 第3节将提出的方法应用于基准数值函数优化问题, 并与已有方法对比; 最后, 第4节总结全文, 并指出需要进一步研究的问题.

图 1  总体框架

图 2  搜索间断点

图 3  网格的形成

具有复杂Pareto前沿的多目标优化问题是非常普遍的, 有效求解该问题的前提是及时准确地感知Pareto前沿.鉴于此, 本文提出一种基于在线感知Pareto前沿划分目标空间的多目标进化优化方法.基于种群进化的信息, 在线感知Pareto前沿的特性, 如果Pareto前沿是不连续的, 那么, 采用MOEA-PPF求解; 否则, 采用传统MOEA/D求解.将提出的方法分别应用于15个连续和不连续基准优化问题, 并与6个流行的多目标进化优化方法对比, 通过反世代距离和覆盖率等测度的实验结果表明, 本文方法的确是求解多目标优化问题的有效方法.

需要指出的是, 本文判定优化问题Pareto前沿的间断点时, 需要利用种群进化信息, 它们的质量直接影响间断点判定的准确性, 从而影响后续种群的进化方向.因此, 如何提高用于判定间断点的进化种群的质量, 是今后需要研究的问题.此外, 本文仅针对Pareto前沿不连续的优化问题, 给出了MOEA-PPF求解方法.实际的复杂优化问题, Pareto前沿会有更多的表现特性, 如在某些区域分布密集, 而另一些区域分布稀疏、Pareto前沿分段个数多等.对这些问题, 本文方法的求解性能往往难以令人满意.需要在Pareto前沿感知和进化求解等方面, 研究有针对性方法, 这也是今后需要进一步研究的问题.最后, 本文提出的方法能否成功应用于实际的优化问题, 需要进一步验证, 不但有利于方法的改进与完善, 也有助于实际问题的解决.

作者简介

封文清

中国矿业大学信息与控制工程学院博士研究生. 2013年获得黑龙江大学硕士学位.主要研究方向为多目标进化优化与应用. E-mail: fwq_cumt@163.com

巩敦卫

中国矿业大学信息与控制工程学院教授. 1999年获得中国矿业大学博士学位.主要研究方向为进化计算与应用.本文通信作者. E-mail: dwgong@vip.163.com