基于自适应反向学习的多目标分布估计算法

李二超，杨蓉蓉

（兰州理工大学电气工程与信息工程学院，兰州 730050）

0 引言

多目标优化问题（Multi-objective Optimization Problem，MOP）通常是指同时对多个相互作用又相互冲突的优化目标进行求解，因此该类问题在尽量满足决策者需求的情况下，只能求得多个折中解，即满意解。目前用于求解多目标问题的优化算法已经被广泛应用在车辆调度［1］、0-1背包问题［2］、个性化搜索问题［3］和指尖定位［4］等。

多目标优化进化算法的实现主要模拟生物进化特性，比如应用了自然进化中选择、交叉以及变异等操作的多目标遗传算法（Non-dominated Sorting Genetic Algorithms Ⅱ，NSGA-Ⅱ）［5］；模拟鸟群或鱼群群体行为的多目标粒子群优化算法［6］；模拟蚂蚁觅食行为的蚁群算法［7］等。而通过数学建模的方法来解决多目标优化问题的研究工作相对较少。Larrañga 等［8］提出了一种新的进化算法：基于数学建模和概率统计的分布估计算法（Estimation of Distribution Algorithm，EDA），该算法的提出主要解决遗传算法中交叉、变异操作破坏积木块的问题。在EDA 中没有选择、交叉以及变异等操作，只是从历史解中提取决策空间的信息并建立期望解的概率分布模型，对其进行采样从而产生新解。2008 年Zhang 等［9］提出基于规则模型的多目标分布估计算法（Regularity Model-based Multiobjective Estimation of Distribution Algorithm，RM-MEDA），该算法在建模初期，采用局部的主成分分析方法为被划分为多个不相交类别的种群建立对应的流形，以刻画种群分布；再对各个流形建模、采样，从而产生新解。RM-MEDA 在解决多目标优化问题时主要存在两个问题：一是在建立概率模型时，RM-MEDA 没有充分发掘各种不同类型多目标优化问题的特征，这使得所建立的概率模型不够准确，这也是EDA 普遍存在的问题；二是由于该算法在建模初期对种群进行聚类，不利于子代的搜索，使得RM-MEDA 的全局搜索能力较弱，很难快速收敛。

针对EDA 存在的全局搜索能力差问题，高尚等［10］将摸石头过河算法与分布估计算法的优点进行结合，首先以一个解为起点，向该起点附近邻域随机搜索若干个解，找出这些解中最好的一个解；并挑选部分优秀个体的中心与最好解进行交叉操作，以此解作为下次迭代的结果，然后以此点为起点，再向附近邻域随机搜索若干个解，以此类推，最终提高算法的收敛速度和精度。2017 年高尚等［11］提出一种基于正态分布的多目标分布估计算法，依据自然界中很多随机变量的概率分布都可以近似地用正态分布描述，进而将正态分布引入到分布估计算法中，使得算法有良好的收敛性和分布性，并且效果稳定。RM-MEDA 作为EDA 中的典型优化算法，很多学者对其进行了研究并给出改进的相关策略或方法。罗辞勇等［12］提出了两步训练法改进RM-MEDA，与原算法不同的是在建模初期依次采用均值聚类法和流形聚类法进行聚类，改进后的算法明显缩短了EDA 的寻优时间，但算法的收敛性和种群多样性并没有较大改进。为了提高RM-MEDA 的全局搜索能力，很多学者将RM-MEDA 与其他经典的多目标优化算法进行了结合。基于逆建模的多目标进化算法（Inverse Modeling based MultiObjectiveEvolutionary Algorithm，IM-MOEA）［13］是另一种基于连续多目标问题的规则属性的分布估计算法，王慧君［14］将RM-MOEA 与IM-MOEA 设计成一种混合算法，通过IM-MOEA 在算法前期充分挖掘帕累托解集和帕累托前沿的规则，以提高RM-MOEA 的收敛速度和种群的分布性。吴烨烨等［15］对RM-MEDA 的改进是：首先通过正交设计产生的初始种群使得个体均匀分布在可行解域，加快算法的收敛并提高种群的分布性，同时加入遗传算法来进化算法迭代中的种群。因此该算法初期使用分布估计算法进行快速的全局搜索，在算法后期主要利用遗传算法的交叉、变异进行局部寻优，增强算法的局部搜索能力。该算法还引入小生境技术和精英策略进行了算法优化，但是在提高算法性能的同时，由于引入多个策略，降低了算法的运行速度。以上对EDA 以及RM-MEDA 的研究，改进的方法适用性不强，有些改进甚至增加了算法的复杂性。

考虑到RM-MEDA 在早期种群中个体分布还未呈现一定的规律时就进行建模，使得产生的新解很难快速收敛；同时，该算法采用随机的方法初始化种群，使得初始种群不能均匀地分布在可行解空间，影响了算法的寻优速度。本文提出基于自适应反向学习的多目标分布估计算法（Multi-objective Estimation of Distribution Algorithm with Adaptive Oppositionbased Learning，AOL-MEDA），它在RM-MEDA 基础上，通过自适应引入反向学习，一定程度地提高算法的收敛性和算法迭代中种群个体的多样性。

1 问题描述

一般的MOP 由N个决策变量参数、M个目标以及约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最优化目标一般可以描述如下：

其中：Ω代表决策空间，x=(x1，x2，…，xN)T∈Ω为N维决策变量；Θ代表目标空间，F(x)=(f1(x)，f2(x)，…，fM(x))T∈Θ为M个目标函数；gi(x) ≤0(i=1，2，…，p)为p个不等式约束条件；hi(x)=0(i=1，2，…，q)为q个等式约束条件。

多目标优化问题就是寻求x=(x1，x2，…，xN)T∈Ω，使得f(x)在满足约束条件的情况下达到最优。

个体支配关系 对于任意两个解x，y∈Ω，如果∀i∈{1，2，…，M}满足fi(x) ≤fi(y)，且∃j∈{1，2，…，M}满足fj(x) ＜fj(y)，则称x支配y（记为x≺y）。

Pareto 最优解（Pareto optimal solution） 如果x∈Ω，不存在y∈Ω使得y≺x成立，则称x是Pareto 最优解。所有Pareto最优解组成的解集为Pareto 最优解集。Pareto 最优解对应的目标函数值组成的解集称为Pareto 前沿（Pareto Front，PF），即：

2 AOL-MEDA

2.1 反向学习机制

反向学习（Opposition-Based Learning，OBL）的概念被Tizhoosh［16］在2005 年提出，通过概率证明了当前解有50%的概率比它的反向解更加远离全局最优解，其主要思想是在当前个体所在区域依据当前个体信息产生反向个体，并使反向个体与当前个体一起参与竞争，得到的优秀个体进入下一代繁殖。因此反向个体的引入对算法收敛性方面有很大的贡献，为反向学习机制的收敛性提供了理论上的依据，从而证实了反向学习是提高随机搜索算法搜索能力的一种有效方法。

定义1反向解。

其中：xij∈[aj，bj]，i=1，2，…，|Popsize|，j=1，2，…，D，|Popsize|为种群规模，D为搜索空间的维度。

定义2中的k可以取不同的实数，当k=0 时=-xij，称其为基于解对称的一般反向学习；当k=0.5 时，称其为基于区间对称的一般反向学习；当k=1 时，称其为一般反向学习或广义的反向学习；而当k为［0，1］区间内的随机数时，称其为基于随机的一般反向学习。

定义3动态的一般反向学习。

其中daj和dbj分别表示当前代中种群搜索空间中第j维上的最小值和最大值，即：

其中：Aj为种群中的个体在第j维上所有取值的集合；k∈[0，1]为一般化系数。

很多学者将反向学习与很多多目标进化算法结合，并设计成相应的混合算法，如与粒子群算法［17］、差分进化算法［18］以及和声搜索算法［19］等相结合。通过对混合算法性能的测试，验证了反向学习对原算法的性能有一定程度的提升，进而证明了反向学习在多目标优化算法中的适用性。

本文算法采用动态的一般反向学习策略产生反向种群，从当前种群和反向种群中选择较好的个体组成新的种群进行算法迭代。引入反向学习策略主要是提高种群中个体的多样性，扩大种群搜索范围，使得进化算法能较快地收敛到Pareto最优前沿上。

2.2 自适应调用机制

将反向学习引入RM-MEDA 的出发点是想在RM-MEDA陷入局部收敛时，利用反向学习摆脱早熟的困境。反向学习与其他算法设计的混合算法中，引入反向学习的反向学习概率需要通过大量实验数据来确定其值，这样得到的概率值不能很好地处理任意问题，从而在处理不同测试问题时不能充分改善算法的全局收敛性，甚至影响算法本身的性能。

本文采用一种自适应机制［20］来调用反向学习，具体方法为：

Xp、Xc分别表示父代和子代个体。

rij是目标函数的离散相对变化率。当rij的模小于预定的阈值ε，即rij很小时，认为此时算法陷入局部收敛，则在RMMEDA中引入反向学习；否则执行RM-MEDA。

2.3 AOL-MEDA步骤

下面给出基于自适应反向学习的多目标分布估计算法的具体步骤：

输入 聚类数目K，种群规模N，最大运行代数T；阈值ε。

输出 算法得到的新种群Pop(t)和每个个体对应的目标函数值。

步骤1 初始化：在决策空间随机生成初始化种群Pop(0)，计算种群Pop(0)中每个个体的目标函数值；t=0。

步骤2 停止条件：如果t＞T，则终止算法并输出Pop(t)和它们对应目标函数值；否则执行步骤3。

步骤3 当rij＜ε时，转至步骤4；否则执行步骤6。

步骤4 反向学习。对Pop(t)中的个体进行动态反向学习并生成反向种群P，评价P中每个解的目标函数值。

步骤5 选择：采用NSGA-Ⅱ非支配排序的选择操作，从P∪Pop(t)中选择N个优秀解作为新的种群Pop(t)。

步骤6 RM-MEDA进化产生新种群Q。

1）建模：对Pop(t)中的解进行训练，获得分段的流形并建模。

2）采样：在每个流形的模型中产生新解，新解组成种群Q，并计算Q中每个个体的目标函数值。

步骤7 选择：采用非支配排序的选择操作，从Q∪Pop(t)中选择N个优秀个体作为下一代种群Pop(t+1)。

步骤8 令t=t+1，跳转到步骤2。

3 实验与结果分析

3.1 参数设置

在本文实验中，算法种群规模N设为100，维度D为30，AOL-MEDA、RM-MEDA两种算法簇数K都为5，簇的扩展系数均为0.25。摸石头过河算法与分布估计混合算法（Hybrid Wading across Stream Algorithm-Estimation Distribution Algorithm，HWSA-EDA）［10］中邻域半径L=0.1，α=0.5，其中：α为1 时，混合算法是摸石头过河算法；而α为0 时，混合算法是分布估计算法。IM-MOEA中的参考向量为15，模型数为3。每组实验独立运行10次。

AOL-MEDA中需要设置的一个重要参数是目标函数的离散变化率rij的阈值ε，它主要用来判断算法在迭代过程中是否陷入局部最优，算法中在依据式（6）计算rij时，∇f未包含差值的最大值和最小值，因此rij的取值范围为（0，1），rij越小，表明父代和子代个体相对变化小。本文阈值ε的取值决定反向学习策略是否被引入到算法中，为了反向学习在算法中引入的合理性，ε的取值参考文献［20］，即ε为1× 10-2。

3.2 多目标测试和评价指标

本文将4 种算法分别在两目标ZDT 测试问题和三目标DTLZ测试问题中进行性能测试，其中两目标优化测试函数为ZDT1～ZDT3、ZDT6；三目标优化测试函数为DTLZ2、DTLZ2.1［8］、DTLZ4 和DTLZ7，DTLZ2.1 比DTLZ2 中的约束条件复杂一些。DTLZ4可以测试算法维持一个良好的分布解集的能力；DTLZ7是不连续多模态问题，这一测试函数可以很好地体现算法处理局部最优的能力。

为了更精确地比较4 种算法的性能优劣，对算法做定量对比，本文选用了反世代距离（Inverted Generational Distance，IGD）［21］、收敛性指标γ［5］和超体积（HyperVolume，HV）［22］作为性能评估指标。

1）反世代距离（IGD）。

IGD 指标兼顾了近似最优解集的收敛性和多样性，是一个综合评价的性能指标。计算公式如下：

其中：P是优化算法求出的一组近似最优解集；P*为Pareto 真实前沿上均匀采样得到的一组参考点；|P*|表示P*的基数，即解集P*中解的个数；d(v，P)表示v∈P*到P中所有解的最小欧氏距离。IGD 值越小，则最优解集P能很好地逼近Pareto前沿，并且更均匀地分布在Pareto最优前沿上。

2）收敛性指标γ。

收敛性指标γ是计算算法所获得的所有最优解与Pareto真实前沿上的最优解之间的最近距离，这些距离的平均值就是收敛性指标γ。公式如下：

其中：|P|表示非支配解集PS中解的数量，d(Pi，P*)表示第i个非支配解与理论Pareto 前沿之间的最小欧氏距离。算法所求解和理论最优解之间的最小距离越小，γ就越小，即算法求得的解越逼近理论最优解，算法的收敛性越好。

3）超体积指标（HV）。

超体积HV 不需要Pareto 真实前沿，而是通过在目标空间设定一个参考点来求得。假设Zr=为目标空间中被所有的Pareto 最优解支配的一个参考点，则超体积表示目标空间中以Zr为边界被最优解集P中的解所支配的区域的大小，HV指标的计算公式如下：

其中，VOL(·)表示勒贝格计量。HV用来同时评估所得近似最优解集的收敛性和多样性，HV 越大说明最优前沿P的性能越好。

表1 给出了算法在各个测试函数测试时的迭代次数以及IGD、γ指标计算所需的Pareto真实前沿上的参考点数目。

表1 各个测试函数所用的参数Tab.1 Parameters used by test functions

3.3 实验结果与分析

为了测试AOL-MEDA 的性能，选择RM-MEDA、HWSAEDA 和IM-MOEA 作为对比算法。本文算法是基于RMMEDA 进行改进的，与它对比能够体现改进后的算法在收敛性方面的提高。HWSA-EDA 是EDA 中搜索速度快、全局搜索能力好的一种算法。IM-MOEA 是一种根据个体解在目标空间中的分布信息采用高斯过程建立逆模型的算法，该算法充分利用了Pareto解集和Pareto前沿的规则属性，使得算法能够获得高质量的解。

表2、图1～4 为4 种算法在两目标测试问题下的实验数据及结果；表3、图5～8为三目标测试问题下的实验数据和结果。在表2、3中将最好的值加粗表示。

表2 4种算法在ZDT测试集上的IGD、γ和HV的均值及方差Tab.2 Means and variances of IGD，γ and HV for four algorithms on ZDT test set

图1 不同算法在ZDT1上获得的最终Pareto前沿Fig.1 Final Pareto fronts obtained by different algorithms on ZDT1

从表2 中的数据及图1～4 可以看出，在两目标测试问题中，AOL-MEDA 与RM-MEDA、HWSA-EDA 以及IM-MOEA 相比，在收敛性和多样性方面都有很大的提升。表2 中数据表明，在相同进化代数下，不论是处理凸函数ZDT1 还是凹函数ZDT2，AOL-MEDA 的性能比对比算法更好；且从图1 和图2可以看到AOL-MEDA 获得的Pareto 解更靠近真实Pareto 前沿，解的分布也较均匀。RM-MEDA 主要处理连续多目标优化问题，但表2 及图3、4 表明，改进后的AOL-MEDA 相较于对比算法，在处理非连续问题ZDT3 以及非均匀的ZDT6 测试问题时，仍可以很快收敛到Pareto 前沿上，且得到的解集有良好的分布性。从表2 中IGD、HV 的均值可以看到AOL-MEDA 解集的多样性和分布性优于对比算法，在ZDT1 和ZDT2 中表现更为明显。

从表3 中的数据及图5～8 可以看出，在三目标测试问题中，AOL-MEDA 与RM-MEDA、HWSA-EDA 以及IM-MOEA 相比，收敛性均有一定程度的提升。从表3 可以看出：在DTLZ2测试函数上进行算法性能测试时，AOL-MEDA比IM-MOEA稍微差一些，但比RM-MEDA 较好。在较为复杂的DTLZ2.1 中，AOL-MEDA 的结果明显比对比算法好。从表3 还可以看出，本文算法在解决DTLZ4 测试问题时比对比算法更好，表明了该算法保持了解的良好的分布性，在图7中也得以证实。表3中DTLZ7数据及图8结果表明，改进算法在处理多模问题时，相较于对比算法，可以很好地收敛到Pareto 前沿上，且解集分布更均匀。

图2 不同算法在ZDT2上获得的最终Pareto前沿Fig.2 Final Pareto fronts obtained by different algorithms on ZDT2

图3 不同算法在ZDT3上获得的最终Pareto前沿Fig.3 Final Pareto fronts obtained by different algorithms on ZDT3

图4 不同算法在ZDT6上获得的最终Pareto前沿Fig.4 Final Pareto fronts obtained by different algorithms on ZDT6

表3 4种算法在DTLZ测试集上的IGD、γ和HV的均值及方差Tab.3 Means and variances of IGD，γ and HV for four algorithms on DTLZ test set

图5 不同算法在DTLZ2上获得的最终Pareto前沿Fig.5 Final Pareto fronts obtained by different algorithms on DTLZ2

在处理两目标优化问题时，AOL-MEDA 相较RM-MEDA、HWSA-EDA 和IM-MOEA 在算法收敛性和解集的多样性上有很大的提升，而处理三目标优化问题DTLZ2 时，AOL-MEDA、RM-MEDA 与IM-MOEA 的IGD、γ和HV 的均值和方差相差不多，其中原因可能是EDA 是基于模型的算法，三目标优化问题测试中的种群规模与两目标优化问题的种群规模都为100，导致三种算法在算法迭代过程中不能建立准确的模型，从而使得算法不能更快地收敛。其中AOL-MEDA 中的反向学习因为种群个数的限制，使得生成的反向个体与当前个体竞争压力增大。IM-MOEA 作为挖掘Pareto 解集和Pareto 前沿的规则属性的多目标分布估计算法，在种群个数少以及算法迭代次数少的情况下，使得建立的高斯逆模型不准确，因此该算法在DTLZ4 以及DTLZ7 测试问题中很难像AOL-MEDA 和RM-MEDA 一样更快收敛到Pareto 前沿上。HWSA-EDA 虽然有较好的全局搜索能力，但因为该算法对解的特征没有进行分析，使得在本文设置较少迭代次数时，算法性能较差，且收敛速度慢。

图6 不同算法在DTLZ2.1上获得的最终Pareto前沿Fig.6 Final Pareto fronts obtained by different algorithms on DTLZ2.1

图7 不同算法在DTLZ4上获得的最终Pareto前沿Fig.7 Final Pareto fronts obtained by different algorithms on DTLZ4

图8 不同算法在DTLZ7上获得的最终Pareto前沿Fig.8 Final Pareto fronts obtained by different algorithms on DTLZ7

本文将4 种算法分别在两目标、三目标测试问题中进行测试，通过IGD、γ以及HV 指标的均值和方差进行了定量对比，其均值表明本文算法在处理问题时优于对比算法，表中各个指标的方差表明了AOL-MEDA 相较于对比算法，在解决测试问题时有较好的鲁棒性。

4 结语

本文将反向学习策略自适应地引入到RM-MEDA 中，在尽量减少算法运行时间的同时，提高了该算法的收敛性以及算法迭代中种群的多样性。理论分析及实验结果表明，AOLMEDA 通过自适应引入反向学习，提高了原算法RM-MEDA的收敛性和多样性，也有效避免了算法陷入局部最优。在处理两目标优化问题时，AOL-MEDA 相较对比算法在收敛性和多样性上有很大提高。但在处理三目标优化问题时效果不是很明显：一方面是因为算法在三目标优化测试问题中种群个数少；另一方面是因为AOL-MEDA 对陷入局部最优的判断可能不准确。因此本文所提算法在判断算法是否陷入局部最优方面还需要进一步研究。