基于分布估计的分解多目标进化算法

摘要：分解多目标进化算法具有较好的分布性，但群体数量会随着目标数的增加而急剧增加，严重影响算法效率。提出一种基于分布估计的分解多目标进化算法，基本思想：首先将多目标分解为若干单目标，然后根据分布估计的思想对各个单目标建立概率模型，通过采样产生解。数值分析和实验表明，新算法的解不仅具有较好的多样性和均匀性，而且算法的计算复杂度明显低于分解多目标进化算法，尤其是对于三目标优化问题。

关键词：多目标优化；进化算法；分解策略；分布估计

中图分类号：TP301.6文献标识码：A文章编号：1672-7800（2012）010-0039-03

基金项目：安徽省教育厅自然科学基金项目（2010kb236）

作者简介：赵晶晶（1988-），女，安徽理工大学理学院硕士研究生，研究方向为智能计算；许峰（1963-），男，安徽理工大学教授，研究方向为波谱学和智能计算。

0引言

目前，新型占优机制、新型进化机制、高维多目标优化问题及多目标优化测试问题是进化多目标优化算法的研究热点。

本文根据分布估计原理和分解多目标进化算法的特点，对分解多目标进化算法做了改进研究，提出了一种基于分布估计的分解多目标进化算法，并对该改进算法进行了性能分析和数值模拟。

1分解多目标进化算法与分布估计算法

传统优化算法求解多目标优化问题的基本思路是：将各个子目标加权组合后转化为单目标优化问题。多目标进化算法是将所有目标看成一个整体，通过适当的进化方法，寻找尽可能多的有代表性的、分布均匀的Pareto最优解。

Zhang和Li将传统多目标优化算法思想引入多目标进化算法，提出了分解多目标进化算法MOEA/D。分解多目标进化算法将多目标优化问题分解为若干单目标优化问题，并将它们作为一个群体同时进化，进化的每一代群体由当前各个子目标的最优解组成。在MOEA/D中，各个子目标的优化只需用到它周围的邻居个体信息，子目标间的邻居关系由各个目标函数的权向量之间的距离决定。权向量距离相近的两个子目标，它们的解也必然近似。由此可见，各个目标函数的权向量能否充满整个空间，分布是否均匀是MOEA/D中的关键问题。

分布估计算法是进化计算领域新兴的分支，它是进化算法和统计学习的有机结合。该算法使用统计学习的手段构建解空间内个体分布概率模型，然后运用进化的思想进化该模型。分布估计算法没有交叉和变异操作，取而代之的是估计解空间的概率模型和由概率模型采样生成新的群体。分布估计算法从宏观上把握群体进化的方向，能够有效解决高维的多目标优化问题，在初始阶段能够很有效地降低时间的复杂性。在多目标优化问题中，不可能使多个目标同时达到最优，所以，优化的目的就是要找到Pareto最优解集，分布估计算法本身存在并行性，适合解决这样的问题。而多目标优化问题与单目标优化问题根本的区别在于寻优过程中要同时考虑多个目标的影响，从而使整个群体向多个目标函数值不增的方向进化。在用分布估计算法求解单目标优化问题时，概率向量的更新是依据适应值最高的一部分主体的分布进行的，那么在多目标优化问题中概率向量的更新就应该同时考虑到多个目标的适应值情况。因此，可以根据各个目标函数的适应值分别排序，选出多个子群体，分别作为不同目标适应性最好的代表，就像“各行各业的劳模代表团”，然后根据各子群体更新概率向量。

随着分布估计算法的发展以及该算法在解决一些问题时所表现出来的优越性能，一些基于分布估计思想的多目标优化算法相继被提出来。Khan将NSGA-II中的选择策略和贝叶斯优化算法（BOA）结合起来，提出了多目标贝叶斯优化算法（mBOA），取得了比NSGA-II更好的效果。Laumanns等学者把SPEA2和BOA结合起来，用于解决多目标背包问题。Zhang和Zhou等学者提出了RM-MEDA，该算法是比较经典的用分布估计算法求解多目标优化问题的算法。

分布估计算法和分解多目标进化算法的算法流程如图1。

2基于分布估计的分解多目标进化算法

考虑到分布估计算法能从宏观上把握群体进化的方向，且没有交叉和变异操作，在初始阶段能够很有效地降低时间的复杂性，本文提出一种基于分布估计的分解多目标进化算法DE-MOEA/D。DE-MOEA/D在MOEA/D算法框架的基础上，使用了概率模型来进化群体。

有多种方法可以将多目标优化问题转换为一系列的接近PF的优化子问题，如边界交集法、Tchebycheff分解法、权重和法等。本算法采用的是Tchebycheff分解法。

3数值实验

下面用DE-MOEA/D算法对两个标准测试函数DTLZ1和DTLZ2进行数值计算，并与NSGA-II算法进行对比分析，从而检验DE-MOEA/D算法的性能。

从图4和图5中可以很清楚地看出，DE-MOEA/D在Pareto最优解的分布性和均匀性方面均明显优于NSGA-II，这表明DE-MOEA/D充分继承了MOEA/D在分布性和均匀性方面的优点。

为测试DE-MOEA/D的收敛性能，下面给出DE-MOEA/D和MOEA/D两种算法运行20次时最后一代种群的IGD数据的平均值。

4结语

数值分析与实验结果表明，新算法在Pareto解的分布性和均匀性与MOEA/D相当而明显优于NSGA-II；对于三目标优化问题，新算法的计算复杂度要低于MOEA/D，这主要是由于新算法没有使用传统的交叉、变异操作，而是利用概率模型产生进化解。

新算法在优化四目标问题时出现了一些问题，优化效果不甚理想。如何进一步提高基于分布估计的分解多目标进化算法的性能，将其能够解决更高维的多目标优化问题，是今后进一步的研究工作。

参考文献：

[1]SCHAFFERJD.Multipleobjectiveoptimizationwithvectorevaluatedgeneticalgorithms[C].In：GrefenstetteJJ，ed.Proc.oftheInt’lConf.onGeneticAlgorithmsandTheirApplications.Hillsdale：L.ErlbaumAssociates，Inc.，1985.

[2]FONSECACM，FLEMINGPJ.Geneticalgorithmformultiobjectiveoptimization：Formulation，discussionandgeneration[C].In：ForrestS，ed.Proc.ofthe5thInt’lConf.onGeneticAlgorithms.SanMateo：MorganKauffmanPublishers，1993.

[3]DEBK，PRATAPA，AGARWALS，etal.Afastandelitistmulti-objectivegeneticalgorithm：NSGA-II[J].IEEETrans.onEvolutionaryComputation，2002（2）.

[4]ZITZLERE，LAUMANNSM，THIELEL.SPEA2：ImprovingthestrengthParetoevolutionaryalgorithm[C].In：GiannakoglouK，TsahalisDT，PériauxJ，PapailiouKD，FogartyT，eds.EvolutionaryMethodsforDesign，OptimizationandControlwithApplicationstoIndustrialProblems.Berlin：Springer-Verlag，2002.

[5]ERICKSONM，MAYERA，HORNJ.ThenichedParetogeneticalgorithm2appliedtothedesignofgroundwaterremediationsystem[C].In：ZitzlerE，DebK，ThieleL，CoelloCoelloCA，CorneD，eds.Proc.ofthe1stInt’lConf.onEvolutionaryMulti-CriterionOptimization，EMO2001.Berlin：Springer-Verlag，2001.

[6]LAUMANNSM，THIELEL，DEBK，biningconvergenceanddiversityinevolutionarymulti-objectiveoptimization[J].EvolutionaryComputation，2002（3）.

[7]HERNNDEZ-DAZAG，SANTANA-QUINTEROLV，COELLOCOELLOCA，etal.Pareto-adaptiveε-dominance[J].EvolutionaryComputation，2007（4）.

[8]ZHANGQF，ZHOUAM，JINY.RM-MEDA：Aregularitymodelbasedmultiobjectiveestimationofdistributionalgorithm[J].IEEETrans.onEvolutionaryComputation，2007（1）.

[9]ZHANGQF，LIH.MOEA/D：Amultiobjectiveevolutionaryalgorithmbasedondecomposition[J].IEEETrans.onEvolutionaryComputation，2007（6）.

[10]KHANN，GOLDBERGDE，PELIKANM.Multi-Oobjectivebayesianoptimizationalgorithm[R].TechnicalReport，No.2002009，UniversityofIllinoisatUrbana-Champaign，2002.

[11]LAUMANNSM，OCENASEKJ.Bayesianoptimizationalgorithmsformulti-objectiveoptimization[C].In：MereloJJ，AdamidisP，BeyerHG，eds.Proc.ofthe7thInt’lConf.onParallelProblemSolvingfromNature.London：Springer-Verlag，2002.

[12]MIETTINENK.NonlinearMultiobjectiveOptimization.Norwell[M].MA：Kluwer，1999.