论文部分内容阅读
摘 要：为了提高MOEA/D算法求解大规模高维多目标优化问题的能力，本文提出一种基于自适应信息反馈机制改进的MOEA/D算法，其基本思想是根据信息反馈原理，将当前代第k个个体与用MOEA/D算法求得的第i个个体加权平均后作为下一代第i个个体。k的选取有指定和随机两种方式，可以根据目标函数的梯度自适应地选择。采用标准的测试函数来评测改进后的算法的性能。结果表明，改进后的MOEA/D算法在收敛性方面有明显的提高。
关键词：大规模高维多目标优化;MOEA/D;信息反馈;自适应;目标函数梯度
中图分类号：TP391 文献标识码：A 文章编号：1673-260X（2021）04-0025-04
当多目标优化问题中的目标函数的个数有二至三个时，此类优化问题被称为多目标优化问题（Multi-objective Optimization Problems，MOP）;当优化问题中的目标函数的个数达到4个以上时，此类优化问题则被称为高维多目标优化问题[1]（Many-objective Optimization Problems，MaOP）。多目标进化算法（Multi-objective Evolutionary Algorithm，MOEA）是求解MOP非常经典的优化算法，但是在用于求解MaOP时，算法的性能就会有一定程度地下降，不足之处主要表现在随着目标函数个数的增加，进而导致算法的收敛性不足，Pareto最优前沿不能完美地逼近真实的Pareto前沿，并且解的分布性和均匀性也欠佳。
基于分解的MOEAs根据分解的形式可分为基于聚合函数的MOEAs和基于参考向量分解的MOEAs[2]。基于分解的多目标进化算法中具代表性的算法是MOEA/D。Zhang提出了基于多目标分解的MOEA/D[3];为了改善计算资源的分配，Zhang提出了改进的MOEA/D，称为MOEA/D-DRA[4];在MOEA/D-DRA的基础上，Zhou和Zhang提出了MOEA/D-GRA[5];Ryoji[6]分析了MOEA/D的控制参数;Dong[7]提出了自适应权重MOEA/D。Zhang和Wang[8]提出了一种基于信息反馈的改进MOEA/D。
Zhang和Wang将信息反馈模型中参数k的两种选择方式对应为两种不同的算法，分别研究了这两种算法对MOEA/D的改进[8]。考虑到参数k的两种选择方式的优缺点，本文提出了一种针对参数k选择方式的不同来进行自适应地确定参数k选择方式的算法，具体做法就是利用目標函数的梯度，来构建自适应性选择，从而确定参数k的选择方式。对改进后算法的性能，一般用标准化测试函数对其进行评测，并将改进后算法得出的结果和MOEA/D算法产生的结果相比较。
1 MOEA/D算法
在MOEA/D算法中，权重向量的生成方式是多种多样的，可以根据自己的需求预先设置权重向量，再利用权重向量将复杂的多目标优化问题转换成一个一个的单目标问题，每个子问题进化所需要的参考信息是由相邻的子问题来提供，子问题与其相邻的子问题依据参考信息相互协同进化。MOEA/D主要用于求解MaOP。该算法采用Tchebycheff分解法，MOEA/D的基本步骤如下。
步骤1 初始化：
（1）设EP=？椎。
（3）根据权重向量生成初始种群x1，x2，…，xN。令FVi=F（xi）。
（4）采用基于问题的特定方法初始化z=（z1*，z2*，…，zm*）。
步骤2 更新：
（1）从B（i）中随机选取两个序号k，l，运用遗传算子由xk和xl产生一个新的解y。
（2）对y运用基于测试问题的修复和改进启发产生y′。
（3）若zj<fj（y′），则zj=fj（y′），j=1，2，…，m。
（4）若gte（y′|u，zu*）≤gte（xu|u，zu*），u∈B（i），若xu=y′，FVu=F（y′）。
（5）剔除EP中受y′支配所有的向量，并且在EP中向量都不支配y′时，令EP=EP∪{f（y）}。
步骤3 终止条件：如果满足终止条件，则停止并输出EP，否则转步骤2。
其中，N是子问题的个数;？姿1，？姿2，…，？姿N是权向量;T是每个权重向量的邻域中含有权重向量的个数;EP是最优解的集合，？椎是空集。
2 信息反馈MOEA/D算法
数值实验表明，MOEA/D算法在求解大规模高维多目标优化问题时，会面临比较复杂的Pareto最优解，会导致算法收敛速率慢，并且在同等评价次数情况下，求解质量不高[8]。
Wang[9]提出信息反馈机制策略，并将其引入启发类算法中，从而提高算法的收敛性。Zhang[8]年研究如何将信息反馈机制引入到MOEA/D算法中，来改善算法在求解大规模高维多目标优化问题时性能不佳等状况。
信息反馈机制的原理类似于求解线性方程组数值解法中的超松弛法，本质是第t代个体经过MOEA/D算法后，产生的个体是不能作为第t+1代的个体，只能是作为一个中间个体。将此中间个体与第t代中的若干个体，按一定的规律进行加权平均后得到新的个体，才能作为第t+1代的个体。在信息反馈机制中，由于中间个体可以和第t代若干个体进行组合，那么到底从第t代中选取多少个个体以及怎样选取个体，这会产生多种信息反馈模型。
为了避免增加算法的复杂性，从第t代中选取个体的数目一般不要超过3个，并且从第t代选取个体有两种选取方式，即固定方式和随机方式，因此产生6种信息反馈模型。
虽然信息反馈模型有不同的形式，但是它们的结构基本上是相似的，而本文只研究从第t代选取个体的数目为1时的情形。 当从第t代选取个体的数目为1时，此时信息反馈模型可以按如下的方式定义[8]：
其中，xkt是第t代种群中的第k个个体，uit+1是用MOEA/D算法求出的中间个体，xit+1是第t+1代种群中的第i个个体，f表示个体对应的适应度。
很明显，xit+1就是由xkt和uit+1加权平均生成的，并且权重？兹1和？兹2与适应度相关。有两种方法可以对k进行确定：第一种是固定方式，即令k=i;第二种是随机方式，即k=rand（1，2，…，N）。固定方法即为数值计算中的松弛法，可以起到对算法进行加速的作用。
在MOEA/D中，利用信息反馈模型来对种群进行更新，即可得到信息反馈MOEA/D算法。
3 自适应信息反馈模型改进的MOEA/D算法
Zhang和Wang提出了6种信息反馈模型[8]，并且利用这些模型对MOEA/D算法进行改进，得到6种改进后的MOEA/D算法，而MOEA/D1算法（固定方式选取第t代中一个个体）相较剩下5种算法而言，属于模型改进后效果最好的算法，让其产生的结果与其他相关算法产生的结果做了比较。
下面对种群的更新方式加以分析，信息反馈模型中的参数k的两种选取方式各有优劣。固定方式是最符合常理，也是最自然的方式。采用此方式的算法，其收敛速度是比较快的，但是会面临一些问题。比如当uit+1与xkt接近时，算法会陷入局部最优，非常容易导致算法早熟。此时，要想使算法跳出局部最优，只有靠随机方式。因此在改进MOEA/D算法时，最佳方案是将固定和随机这两种方式根据具体情况进行自适应地结合，这样既能够保证算法收敛速度加快，又能尽量避免算法陷入局部最优。
基于上述的讨论，本文提出了自适应信息反馈模型，将其应用在MOEA/D算法中。而构造自适应信息反馈模型的关键就在参数k的选取方式上，让参数k根据算法自身收敛的状况，来自行确定参数 的选取方式，即自适应性选择。自适应的构造如下：
在进化的前期和中期，？滓值是控制算法过早收敛重要因素。因为当公式（3）计算出的？籽ab值小于预先设定的临界值？滓（？滓的取值是10-2）时，算法可能会陷入局部最优的状况。这时让信息反馈机制中的参数k按照随机的方式进行选取，这样能使算法跳出局部最优状况。如果算法没有陷入局部最优状况，那么信息反馈机制参数k的选取就用固定的方式。在进化后期，为了避免算法的收敛性遭到破坏，要根据算法收敛的情况，适当地放弃随机性的选择方式，直接采用固定的方式进行选择。另外，要在程序中将总进化代数的后20%为设置为进化后期。
将自适应信息反馈模型应用到MOEA/D算法中，得到自适应信息反馈MOEA/D算法（MOEA/D based on adaptive information feedback， MOEA/D-AIF），简记为MOEA/D-AIF。此间具体步骤如下：
步骤1 初始化种群。
步骤2 种群更新。
（1）将父代种群Pt，经过MOEA/D算法得到个体uit+1。
（2）根据目标函数梯度自适应来确定信息反馈方法，即自适应地确定k的选取方式，再根据公式（1）和（2）生成子种群Qt。
（3）将Pt和Qt合并，记为Dt。
（4）对Dt再利用MOEA/D算法，生成下一代父代种群Pt+1。
步骤3 达到设定值时，停止此循环并输出结果EP。否则循环回到步骤2。
4 数值实验与算法性能评测
为了评测本文提出的基于自适应信息反馈机制的MOEA/D算法的性能，用此算法对两个标准测试函数DTLZ1和DTLZ2进行数值实验，并将实验结果与经典的MOEA/D算法的优化结果进行了比较。
4.1 DTLZ1测试函数
M=3时两者的PF如图4所示。
为了更准确、定量地衡量本文算法的性能，下面给出基于自适应信息反馈机制的MOEA/D算法和常规MOEA/D算法的世代距离（GD）和分散性（SP）两个指标的对比数据。其中，GD指标反映的是算法的收敛性，而SP指标则描述了解的分布性。由于计算结果有随机性，表1、表2中数据为GD指标数据和SP指标数据计算结果的平均值。
5 结论
图3-6直观显示，基于自适应信息反馈机制的MOEA/D算法的解明显优于常规MOEA/D算法的解。表1和表2中的指标进一步表明，MOEA/D-AIF算法与常规MOEA/D算法相比，SP指标相差不大，但GD指标明显占优。
综上，可以得出明确的结论：基于自适应信息反馈机制的MOEA/D算法较常规MOEA/D算法在收敛性方面有明显提高，分布性和均匀性也有一定程度的改进。
参考文献：
〔1〕孔維健.高维多目标进化算法研究综述[J].控制与决策，2010，25（03）：321-326.
〔2〕袁源.基于分解的多目标进化算法及其应用[D].清华大学，2015.
〔3〕Zhang Q. F Li H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on. Evolutionary Computation.， 2007，11（06）：712-731.
〔4〕Zhang Q， Liu W， Li H. The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances [A]. Evolutionary Computation， 2009[C]. 2009， 203-208.
〔5〕Zhou A， Zhang Q. Are All the Subproblems Equally Important？ Resource Allocation in Decomposition-Based Multiobjective Evolutionary Algorithms [J]. IEEE Transactions on Evolutionary Computation， 2016， 20（01）： 52-64.
〔6〕Ryoji Tanabe， Hisao Ishibuchi. An analysis of control parameters of MOEA/D under two different optimization scenarios [J]. Applied Soft Computing， 2018， 70： 22-40.
〔7〕Zhiming Dong， Xianpeng Wang， Lixin Tang. MOEA/D with a self-adaptive weight vector adjustment strategy based on chain segmentation [J]. Information Sciences， 2020， 521： 209- 230.
〔8〕Yin Zhang， Gai-Ge Wang， Keqin Li. Enhancing MOEA/D with information feedback models for large-scale many-objective optimization [J]. Information Sciences， 2020， 522： 1-16.
〔9〕G. Wang， Y. Tan， Improving metaheuristic algorithms with information feedback models [J]. IEEE Trans. Cybern.， 2019， 49（2）： 542-555.
关键词：大规模高维多目标优化;MOEA/D;信息反馈;自适应;目标函数梯度
中图分类号：TP391 文献标识码：A 文章编号：1673-260X（2021）04-0025-04
当多目标优化问题中的目标函数的个数有二至三个时，此类优化问题被称为多目标优化问题（Multi-objective Optimization Problems，MOP）;当优化问题中的目标函数的个数达到4个以上时，此类优化问题则被称为高维多目标优化问题[1]（Many-objective Optimization Problems，MaOP）。多目标进化算法（Multi-objective Evolutionary Algorithm，MOEA）是求解MOP非常经典的优化算法，但是在用于求解MaOP时，算法的性能就会有一定程度地下降，不足之处主要表现在随着目标函数个数的增加，进而导致算法的收敛性不足，Pareto最优前沿不能完美地逼近真实的Pareto前沿，并且解的分布性和均匀性也欠佳。
基于分解的MOEAs根据分解的形式可分为基于聚合函数的MOEAs和基于参考向量分解的MOEAs[2]。基于分解的多目标进化算法中具代表性的算法是MOEA/D。Zhang提出了基于多目标分解的MOEA/D[3];为了改善计算资源的分配，Zhang提出了改进的MOEA/D，称为MOEA/D-DRA[4];在MOEA/D-DRA的基础上，Zhou和Zhang提出了MOEA/D-GRA[5];Ryoji[6]分析了MOEA/D的控制参数;Dong[7]提出了自适应权重MOEA/D。Zhang和Wang[8]提出了一种基于信息反馈的改进MOEA/D。
Zhang和Wang将信息反馈模型中参数k的两种选择方式对应为两种不同的算法，分别研究了这两种算法对MOEA/D的改进[8]。考虑到参数k的两种选择方式的优缺点，本文提出了一种针对参数k选择方式的不同来进行自适应地确定参数k选择方式的算法，具体做法就是利用目標函数的梯度，来构建自适应性选择，从而确定参数k的选择方式。对改进后算法的性能，一般用标准化测试函数对其进行评测，并将改进后算法得出的结果和MOEA/D算法产生的结果相比较。
1 MOEA/D算法
在MOEA/D算法中，权重向量的生成方式是多种多样的，可以根据自己的需求预先设置权重向量，再利用权重向量将复杂的多目标优化问题转换成一个一个的单目标问题，每个子问题进化所需要的参考信息是由相邻的子问题来提供，子问题与其相邻的子问题依据参考信息相互协同进化。MOEA/D主要用于求解MaOP。该算法采用Tchebycheff分解法，MOEA/D的基本步骤如下。
步骤1 初始化：
（1）设EP=？椎。
（3）根据权重向量生成初始种群x1，x2，…，xN。令FVi=F（xi）。
（4）采用基于问题的特定方法初始化z=（z1*，z2*，…，zm*）。
步骤2 更新：
（1）从B（i）中随机选取两个序号k，l，运用遗传算子由xk和xl产生一个新的解y。
（2）对y运用基于测试问题的修复和改进启发产生y′。
（3）若zj<fj（y′），则zj=fj（y′），j=1，2，…，m。
（4）若gte（y′|u，zu*）≤gte（xu|u，zu*），u∈B（i），若xu=y′，FVu=F（y′）。
（5）剔除EP中受y′支配所有的向量，并且在EP中向量都不支配y′时，令EP=EP∪{f（y）}。
步骤3 终止条件：如果满足终止条件，则停止并输出EP，否则转步骤2。
其中，N是子问题的个数;？姿1，？姿2，…，？姿N是权向量;T是每个权重向量的邻域中含有权重向量的个数;EP是最优解的集合，？椎是空集。
2 信息反馈MOEA/D算法
数值实验表明，MOEA/D算法在求解大规模高维多目标优化问题时，会面临比较复杂的Pareto最优解，会导致算法收敛速率慢，并且在同等评价次数情况下，求解质量不高[8]。
Wang[9]提出信息反馈机制策略，并将其引入启发类算法中，从而提高算法的收敛性。Zhang[8]年研究如何将信息反馈机制引入到MOEA/D算法中，来改善算法在求解大规模高维多目标优化问题时性能不佳等状况。
信息反馈机制的原理类似于求解线性方程组数值解法中的超松弛法，本质是第t代个体经过MOEA/D算法后，产生的个体是不能作为第t+1代的个体，只能是作为一个中间个体。将此中间个体与第t代中的若干个体，按一定的规律进行加权平均后得到新的个体，才能作为第t+1代的个体。在信息反馈机制中，由于中间个体可以和第t代若干个体进行组合，那么到底从第t代中选取多少个个体以及怎样选取个体，这会产生多种信息反馈模型。
为了避免增加算法的复杂性，从第t代中选取个体的数目一般不要超过3个，并且从第t代选取个体有两种选取方式，即固定方式和随机方式，因此产生6种信息反馈模型。
虽然信息反馈模型有不同的形式，但是它们的结构基本上是相似的，而本文只研究从第t代选取个体的数目为1时的情形。 当从第t代选取个体的数目为1时，此时信息反馈模型可以按如下的方式定义[8]：
其中，xkt是第t代种群中的第k个个体，uit+1是用MOEA/D算法求出的中间个体，xit+1是第t+1代种群中的第i个个体，f表示个体对应的适应度。
很明显，xit+1就是由xkt和uit+1加权平均生成的，并且权重？兹1和？兹2与适应度相关。有两种方法可以对k进行确定：第一种是固定方式，即令k=i;第二种是随机方式，即k=rand（1，2，…，N）。固定方法即为数值计算中的松弛法，可以起到对算法进行加速的作用。
在MOEA/D中，利用信息反馈模型来对种群进行更新，即可得到信息反馈MOEA/D算法。
3 自适应信息反馈模型改进的MOEA/D算法
Zhang和Wang提出了6种信息反馈模型[8]，并且利用这些模型对MOEA/D算法进行改进，得到6种改进后的MOEA/D算法，而MOEA/D1算法（固定方式选取第t代中一个个体）相较剩下5种算法而言，属于模型改进后效果最好的算法，让其产生的结果与其他相关算法产生的结果做了比较。
下面对种群的更新方式加以分析，信息反馈模型中的参数k的两种选取方式各有优劣。固定方式是最符合常理，也是最自然的方式。采用此方式的算法，其收敛速度是比较快的，但是会面临一些问题。比如当uit+1与xkt接近时，算法会陷入局部最优，非常容易导致算法早熟。此时，要想使算法跳出局部最优，只有靠随机方式。因此在改进MOEA/D算法时，最佳方案是将固定和随机这两种方式根据具体情况进行自适应地结合，这样既能够保证算法收敛速度加快，又能尽量避免算法陷入局部最优。
基于上述的讨论，本文提出了自适应信息反馈模型，将其应用在MOEA/D算法中。而构造自适应信息反馈模型的关键就在参数k的选取方式上，让参数k根据算法自身收敛的状况，来自行确定参数 的选取方式，即自适应性选择。自适应的构造如下：
在进化的前期和中期，？滓值是控制算法过早收敛重要因素。因为当公式（3）计算出的？籽ab值小于预先设定的临界值？滓（？滓的取值是10-2）时，算法可能会陷入局部最优的状况。这时让信息反馈机制中的参数k按照随机的方式进行选取，这样能使算法跳出局部最优状况。如果算法没有陷入局部最优状况，那么信息反馈机制参数k的选取就用固定的方式。在进化后期，为了避免算法的收敛性遭到破坏，要根据算法收敛的情况，适当地放弃随机性的选择方式，直接采用固定的方式进行选择。另外，要在程序中将总进化代数的后20%为设置为进化后期。
将自适应信息反馈模型应用到MOEA/D算法中，得到自适应信息反馈MOEA/D算法（MOEA/D based on adaptive information feedback， MOEA/D-AIF），简记为MOEA/D-AIF。此间具体步骤如下：
步骤1 初始化种群。
步骤2 种群更新。
（1）将父代种群Pt，经过MOEA/D算法得到个体uit+1。
（2）根据目标函数梯度自适应来确定信息反馈方法，即自适应地确定k的选取方式，再根据公式（1）和（2）生成子种群Qt。
（3）将Pt和Qt合并，记为Dt。
（4）对Dt再利用MOEA/D算法，生成下一代父代种群Pt+1。
步骤3 达到设定值时，停止此循环并输出结果EP。否则循环回到步骤2。
4 数值实验与算法性能评测
为了评测本文提出的基于自适应信息反馈机制的MOEA/D算法的性能，用此算法对两个标准测试函数DTLZ1和DTLZ2进行数值实验，并将实验结果与经典的MOEA/D算法的优化结果进行了比较。
4.1 DTLZ1测试函数
M=3时两者的PF如图4所示。
为了更准确、定量地衡量本文算法的性能，下面给出基于自适应信息反馈机制的MOEA/D算法和常规MOEA/D算法的世代距离（GD）和分散性（SP）两个指标的对比数据。其中，GD指标反映的是算法的收敛性，而SP指标则描述了解的分布性。由于计算结果有随机性，表1、表2中数据为GD指标数据和SP指标数据计算结果的平均值。
5 结论
图3-6直观显示，基于自适应信息反馈机制的MOEA/D算法的解明显优于常规MOEA/D算法的解。表1和表2中的指标进一步表明，MOEA/D-AIF算法与常规MOEA/D算法相比，SP指标相差不大，但GD指标明显占优。
综上，可以得出明确的结论：基于自适应信息反馈机制的MOEA/D算法较常规MOEA/D算法在收敛性方面有明显提高，分布性和均匀性也有一定程度的改进。
参考文献：
〔1〕孔維健.高维多目标进化算法研究综述[J].控制与决策，2010，25（03）：321-326.
〔2〕袁源.基于分解的多目标进化算法及其应用[D].清华大学，2015.
〔3〕Zhang Q. F Li H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on. Evolutionary Computation.， 2007，11（06）：712-731.
〔4〕Zhang Q， Liu W， Li H. The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances [A]. Evolutionary Computation， 2009[C]. 2009， 203-208.
〔5〕Zhou A， Zhang Q. Are All the Subproblems Equally Important？ Resource Allocation in Decomposition-Based Multiobjective Evolutionary Algorithms [J]. IEEE Transactions on Evolutionary Computation， 2016， 20（01）： 52-64.
〔6〕Ryoji Tanabe， Hisao Ishibuchi. An analysis of control parameters of MOEA/D under two different optimization scenarios [J]. Applied Soft Computing， 2018， 70： 22-40.
〔7〕Zhiming Dong， Xianpeng Wang， Lixin Tang. MOEA/D with a self-adaptive weight vector adjustment strategy based on chain segmentation [J]. Information Sciences， 2020， 521： 209- 230.
〔8〕Yin Zhang， Gai-Ge Wang， Keqin Li. Enhancing MOEA/D with information feedback models for large-scale many-objective optimization [J]. Information Sciences， 2020， 522： 1-16.
〔9〕G. Wang， Y. Tan， Improving metaheuristic algorithms with information feedback models [J]. IEEE Trans. Cybern.， 2019， 49（2）： 542-555.