MOEAD(基于分解的多目标进化算法).doc

《MOEAD(基于分解的多目标进化算法).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于分解的多目标进化算法摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目标优化问题分解为一组？？？单目标优化问题并对它们同时优化。通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，这是的该算法比MOGLS和非支配排序遗传算法NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在0-1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现的更加出色或者表现相近。实验也表明目标正态化的MOEA/D算法可以解决

2、规模范围相异的多目标问题，同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。最后，MOEA/D在较小种群数量是的性能，还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。I.介绍多目标优化问题可以用下面式子表示：MaximizeF(x)=((f1x…...fmx)Tsubjecttox∈Ω其中Ω是决策空间，F：Ω→Rm，包含了m个实值目标方法，Rm被称为目标区间。对于可以得到的目标集合成为{F(x)

3、x∈Ω}。如果x∈Rm，并且所有的目标函数都是连续的，那么Ω则可以用Ω={x∈Rn

4、hj(x)≤0,j=1…

5、…m}其中hj是连续的函数，我们可以称(1)为一个连续的多目标优化问题。如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义Pareto最优。令u,v∈Rm，如果ui≥vi对于任意的i，并且至少存在一个uj≥vj(i,j∈{1…..m})，那么u支配v。如果在决策空间中，没有一个点F(y)能够支配F(x)点，那么x就是Pareto最优，F(x)则被称为Pareto最优向量。换句话说，对于Pareto最优点在某一个目标函数上的提高，都会造成至少一个其余目标函数的退化。所

6、有Pareto最优解的集合称为Pareto集合，所有最优向量的集合被称为Pareto前沿。在许多多目标优化的实际应用中，通过选择器选择一个接近Pareto最优前沿的解作为最后的解。大多数多目标优化问题都有许多甚至是无穷个Pareto最优向量，如果想要获得一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往往是获得一个均匀分布在Pareto最优前沿周围的最优解向量，这样就具有更好的代表性。许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。一般来说，

7、在温和控制下多目标优化问题的Pareto最优解，可以看做是一个标量优化问题的最优解(其中目标函数是fi的集合)。因此，Pareto最优前沿的近似求解可以被分解为一组标量目标优化子问题。这个想法是建立在许多传统的对最优前沿求近似解的数学编程方法上的。现在有许多的聚合方法，最流行的是切比雪夫法和加权法。最近，边界交叉方法也引起了许多的关注。如今多目标进化算法并没有将分解这一概念引入当前的主要发展领域。这些算法将多目标优化问题看成一个整体。他们并没有通过任何特别的标量优化将每一个解相互联系在一起。在一个标量目标优化问题中，所有的解都可以通过他们的目标函数值进行对比，

8、而挑战就是如果找到一个单独的最优解。但是在MOP中，支配关系并不能定义一个具有完整顺序的解集合，MOEA则是为了产生一组尽可能分散的可以代表整个PF的解集合。因此，那些常见的被设计在标量优化中使用的选择器，可能不能直接的在传统的MOEA中使用。可以认为，如果有一个可以为每个体分配相关适应度来反映供选择参考的效用的适应度分配表，那么标量优化进化算法就可以真正的使用在MOP中，但是其他技术：比如交配限制、多样性控制、许多MOP方法的属性和外部种群集合等仍然需要用来加强标量算法的性能。因为这个原因，适应度分配已经成为现在MOEA研究的一个主要议题。比较流行的适应度分

9、配策略包括基于目标函数的适应度分配比如VRGA，还有基于支配关系的适应度分配比如SPRA-Ⅱ和NSGA-Ⅱ。分解这种想法在某种程度已经被应用在许多元启发式方法中用于解决MOP问题。例如，两相局部搜索方法被认为是一组标量优化问题，其中MOP中的多目标被通过聚合方法分解为一个个单目标问题，一个标量优化算法被应用到标量优化问题中通过一组聚合参数来完成，在之前问题中获得的一组解作为下一个问题的起始点因为聚合原因两者间的差别很小。多目标遗传局部搜索目标就是对用过使用甲醛算法或者切比雪夫算法的聚合进行同时优化。在每一代中，它对一个随机生成的聚合目标进行优化。在本篇文章中，

10、我们提出了一个新的基于分解的多目标进化