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

基于分解的多目标进化算法摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目标优化问题分解为一组？单目标优化问题并对它们同时优化。通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，这是的该算法比MOGLS和非支配排序遗传算法NSGA-相比有更低的计算复杂度。实验结果证明：在0-1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-表现的更加出色或者表现相近。实验也表明目标正态化的MOEA/D算法可以解决规模范围相异的多目标问题，同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。最后，MOEA/D在较小种群数量是的性能，还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。I. 介绍多目标优化问题可以用下面式子表示：Maximize F(x)=(f1x.fmx)Tsubject to x其中是决策空间，F：Rm，包含了m个实值目标方法，Rm被称为目标区间。对于可以得到的目标集合成为F(x)|x。如果xRm，并且所有的目标函数都是连续的，那么则可以用=xRn|hj(x)0, j=1m其中hj是连续的函数，我们可以称(1)为一个连续的多目标优化问题。如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义Pareto最优。令u, vRm，如果uivi对于任意的i，并且至少存在一个ujvj(i,j1.m)，那么u支配v。如果在决策空间中，没有一个点F(y)能够支配F(x)点，那么x就是Pareto最优，F(x)则被称为Pareto最优向量。换句话说，对于Pareto最优点在某一个目标函数上的提高，都会造成至少一个其余目标函数的退化。所有Pareto最优解的集合称为Pareto集合，所有最优向量的集合被称为Pareto前沿。在许多多目标优化的实际应用中，通过选择器选择一个接近Pareto最优前沿的解作为最后的解。大多数多目标优化问题都有许多甚至是无穷个Pareto最优向量，如果想要获得一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往往是获得一个均匀分布在Pareto最优前沿周围的最优解向量，这样就具有更好的代表性。许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。一般来说，在温和控制下多目标优化问题的Pareto最优解，可以看做是一个标量优化问题的最优解(其中目标函数是fi的集合)。因此，Pareto最优前沿的近似求解可以被分解为一组标量目标优化子问题。这个想法是建立在许多传统的对最优前沿求近似解的数学编程方法上的。现在有许多的聚合方法，最流行的是切比雪夫法和加权法。最近，边界交叉方法也引起了许多的关注。如今多目标进化算法并没有将分解这一概念引入当前的主要发展领域。这些算法将多目标优化问题看成一个整体。他们并没有通过任何特别的标量优化将每一个解相互联系在一起。在一个标量目标优化问题中，所有的解都可以通过他们的目标函数值进行对比，而挑战就是如果找到一个单独的最优解。但是在MOP中，支配关系并不能定义一个具有完整顺序的解集合，MOEA则是为了产生一组尽可能分散的可以代表整个PF的解集合。因此，那些常见的被设计在标量优化中使用的选择器，可能不能直接的在传统的MOEA中使用。可以认为，如果有一个可以为每个体分配相关适应度来反映供选择参考的效用的适应度分配表，那么标量优化进化算法就可以真正的使用在MOP中，但是其他技术：比如交配限制、多样性控制、许多MOP方法的属性和外部种群集合等仍然需要用来加强标量算法的性能。因为这个原因，适应度分配已经成为现在MOEA研究的一个主要议题。比较流行的适应度分配策略包括基于目标函数的适应度分配比如VRGA，还有基于支配关系的适应度分配比如SPRA-和NSGA-。分解这种想法在某种程度已经被应用在许多元启发式方法中用于解决MOP问题。例如，两相局部搜索方法被认为是一组标量优化问题，其中MOP中的多目标被通过聚合方法分解为一个个单目标问题，一个标量优化算法被应用到标量优化问题中通过一组聚合参数来完成，在之前问题中获得的一组解作为下一个问题的起始点因为聚合原因两者间的差别很小。多目标遗传局部搜索目标就是对用过使用甲醛算法或者切比雪夫算法的聚合进行同时优化。在每一代中，它对一个随机生成的聚合目标进行优化。在本篇文章中，我们提出了一个新的基于分解的多目标进化算法。MOEA/D将MOP分解为N个标量的子问题。它通过进化出一个解的种群来同时解决所有子问题。对于每一代种群，种群是从所有代中选出的每一个子问题的最优解的集合。相邻两个子问题键的关联程度是由它们的聚合系数向量间的距离所决定的。对于两个相邻子问题来说，最优解应该是非常相似的。对于每一个子问题来说，只是用与其相邻的子问题的信息来优化它。MOEA/D有以下特性：l MOEA/D提供了一个简单但是有效的方法，那就是将分解的方法引入到多目标进化计算中。对于常常在数学规划领域发展的分解方法，它可以真正的被并入到EA中，通过使用MOEA/D框架来解决MOP问题。l 因为MOEA/D算法是同时优化N标量子问题而不是直接将MOP问题作为一个整体来解决，那么对于传统的并不是基于分解的MOEA算法来说适应度分配和多样性控制的难度将在MOEA/D框架中得到降低。l MOEA/D算法有一个较低的计算复杂度相比于NSGA-和MOGLS。总体来说，在MOGLS和MOEA/D同时解决0-1背包问题测试样例中，两者使用相同的分解方法，MOEA/D在解的质量上表现更为出色。在一组连续的MOP样例测试中，使用了切比雪夫分解法的MOEA/D方法和NSGA-表现相近。在一个3目标的连续样例测试中，使用一个先进的分解方法的MOEA/D算法表现的比NSGA-出色许多。当MOEA/D算法使用一个小型种群时也可以产生一组种群数量少的分布均匀的解。l 因为在MOEA/D中每一个解都和标量优化问题有关，所以使用标量优化方法显得很自然。相反，对于传统的不是基于分解的MOEA算法的一个缺点就是很难找到一个简单的方法来冲分利用标量优化算法。本篇文章按如下组织。在第二部分介绍了三种分解方法。第三部分详细展示了MOEA/D算法。在第四和第五部分，对其和MOGLS和NSGA-算法进行了对比，对比结果表明MOEA/D算法表现的更为出色有时表现相近。在第六部分，展示了更多关于MOEA/D的实验数据。在第七部分对本文做了总结。II. 多目标优化中的分解算法如今有许多方法可以将对求Pareto前沿近似解的问题转换为一组标量优化问题的。在下面，我们将介绍三种我们试验中使用到的方法。1. 权重求和方法权重求和是最常见的聚合方法，假设待优化的多目标问题有m个总目标，该函数通过一个非负的权重向量=(1m)加权到每个目标上将MOP转化为单目标子问题，其数学表达式为：maximize gwsx=i=1mifi(x)subject to x其中，=(1m)是一组权重向量，对于所有的i=1,2,m，i0&i=1mi=1。聚集韩式可以是线性的，也可以是非线性的。由如上的定义可知，传统的加权方法利用均匀的权重向量够早了一个不同目标函数值的凸组合。根据凸组合的性质，当聚集函数呈线性时，无论如何调整权重系数，都难以搜索到非凸解。但是当聚集函数呈非线性时，可以很好地解决以上问题。在本文中，将加权求和聚合函数表达式记为上式是为了强调是这个目标函数的一个参数向量，X是待优化的变量。与传统的加权方法不同，加权求和聚合方法通过在上述标量优化问题中生成不同的权重向量来产生一组不同的Pareto最优解。然而，在最优Pareto面的形状为非凸面的情况下，这种方法并不能获得每一个Pareto最优向量。为了克服这些缺点，研究人员做出了一些努力，例如在此方法中引入了-约束。2. 切比雪夫聚合方法切比雪夫聚合方法的计算公式为：minimize gtex,z*=max1imi|fix-z*| 其中x，z*=(z1*,zi*)T为参考点，对于每一个i=1,m，有zi*=minfi(x)|x。对于每一个Pareto最优点x*总存在一个权重向量使得上式的解为一个Pareto最优解，该解对应着元多目标问题的Pareto最优解。并且通过修改权重向量可以获得Pareto最优面上的不同的解。这种方法的一个缺点就是处理连续多目标问题时聚合方法曲线不平滑。权重切比雪夫聚合方法是在权重求和和切比雪夫方法的基础上进行的改进，在该方法中添加了参数，将两种聚合方法组合在一起。通过调整控制两种聚合方法的比例，力图结合权重求和聚合方法收敛速度快和切比雪夫聚合方法分布性好的特点。mingATx,z*=maxi=1,2,mi|fix-z*|+j=1m|fjx-zj*|3. 边界交叉聚合方法几种常见的聚合方法如标准边界交叉方法和规范化标准约束方法可以归类为边界交叉方法。这些方法被设计用来处理连续多目标优化问题。在一定条件下，连续多目标优化问题的Pareto最优边界是其可行目标集的最右上边界的一部分。从几何角度来看，这些边界交叉方法旨在寻找到最上部的边界和一组线的交点。在某种意义上说，如果这组线均匀地分布，由此产生的交点可以看做是提供了对整个Pareto最优边界一个很好的近似。这些方法能够很好的处理Pareto最优边界为非凸面的问题。一般在试验中，通常取一组从参考点出发的射线。在数学意义上，定义如下形式的标量优化问题：mingbix,z*=d其中，和z*在第二个方法中介绍过，分别代表的是一个权重向量和参考点。如下图所示，约束条件z*-Fx=d确保了F(x)保持在直线L上，直线L的方向为且穿过点z*。边界交叉方法的目标是把F(x)推尽可能的远，这样算法能够搜索到可行目标空间的边界。上述方法的一个缺陷就是它必须处理等式约束。在实践中，通常采用惩罚的方法来处理约束。基于惩罚的边界交叉方法的详细定义为：mingbipx,z*=d1+d2d1=z*-FxT|d2=|Fx-(z*-d1)|其中x，0是一个预设的参数。理论上PBI聚合方法将个体向最优Pareto面的逼近分为与权重向量间的距离和沿权重向量与最优Pareto面的距离。假设y是F(x)在直线L上的阴影。如下图所示，d1是z*和y间的距离。d2是F(x)和L间的距离。如果参数设置的合适，上面两式的解将非常接近。在下文中，称这种方法为基于惩罚的边界交叉方法(PBI)。相对于切比雪夫聚合方法，PBI聚合方法及其通用的边界交叉方法举要有如下两个优势：在超过两个目标时，PBI聚合方法和切比雪夫聚合方法是用相同的均匀分布的权重向量，PBI的结果最优解应该比切比雪夫聚合方法获得的最优解分布更加均匀，特别是在目标较少的时候这种现象更加明显。如果x支配y，仍然有可能gtex,z*=gtey,z*。虽然对于gbip和其他边界交叉方法这种可能性非常小。然而这种优势需要一定的代价。其中之一是必须设定惩罚系数的值。众所周知，过大或者过小的惩罚系数将会减弱惩罚方法的性能。上述三种聚合方法可以用来将多目标精华算法对PF的逼近转为一组标量优化问题。足够大的均匀分布的权重向量通常会引导一组Pareto最优向量，这些解可能不是均匀分布的，但是能很好的逼近Pareto最优前沿。III. 基于分解的多目标进化算法的框架1. 总体框架本篇文章介绍的基于分解的多目标进化算法需要在有考虑的情况下进行正对性的分解。任何分解方法都能够应用在本算法中。在下面的描述中，我们使用了切比雪夫的分解法。对于定义下面MOEA/D算法，使用别的分解方法影响很小。令1,N为一组均匀分布的权重向量，z*为参考点。就像第二部分所说的，对PF的逼近问题可以通过切比雪夫为N个标量优化子问题，其中每一个子问题可以表示成：gtexj,z*=max1imijfix-zi*j=(1j,mj)T在一轮运行中，MOEA/D同时优化这N个目标方法。其中gte应该是连续的，如果j和i相邻那么gtexj,z*和gtexi,z*的值也应该非常接近。因此，通过权重向量任何gte与i相关的信息都应该有助于优化gtexi,z*。这就是MOEA/D的主要驱动力。在MOEA/D中，一个相邻的权重向量i定义为一组数个相邻的权重向量1,N。与第i个子问题的相邻是所有带有与i相邻的权重向量的子问题。每一代种群都在所有种群中挑选的最优解的集合。在MOEA/D中，只有相邻的子问题可以被用来优化彼此。对于第t代种群，使用切比雪夫的MOEA/D包含以下初始条件：l 大小为N的种群，x1,xN，其中xi是第i个子问题的当前解。l FV1,FVi，其中FVi是xi的目标函数值，FVi=F(xi)。l z=(z1zm)T，zi是目前搜索到的目标函数fi的最佳值(或者说最大值)。l 一个外部种群，是用来存储当前搜索到的非支配解。MOEA/D算法输入：多目标优化问题；算法终止条件；N：MOEA/D定义的种群大小；均匀分布的N个权重向量：1,N；T：每一个邻域中的权重向量的个数；输出：x1,xN和f(x1),f(xi)1. Step1：初始化2. Step1.1：计算任意两个权重向量间的欧式距离，查找每个权重向量最近的T个权重 向量。对于每个i=1,N，令Bi=i1,iT，i1,iT是i最近的T个权重向量。3. Step1.2：在可行空间中均匀随即采集产生初始种群x1,xN。4. Step1.3：初始化z=(z1zm)T，令zi=minfix1,fix2,fixN。5. Step1.4：设置EP为空。6. Step2：更新7. For i=1,N do8. Step2.1：基因重组：从B(i)中随机选取两个序号k,l，运用遗传算子由xk和xl产生一个新的解y。9. Step2.2：改进：对y运用基于测试问题的修复和改进启发产生y。10. Step2.3：更新z：11. For each j=1,m，if zifjy，令zi=fjy end for12. Step2.4：更新邻域解：For each jBi，if gteyj,zgtexjj,z，令xj=y，FVj=Fy end for13. Step2.5：更新EP：从EP中移除所有被Fy支配的向量，如果EP中的向量都不支配Fy，将Fy加入EP。14. End for 15. Step 3：终止条件：停止并输出EP，否则转Step2初始化，B(i)包含了,i的T个最接近的索引向量。使用任何两个权重向量之间的欧氏距离来衡量权重向量的接近程度。距离权重向量i最近的权重向量是其本身，因此，iBi。如果jBi，第j个子问题可以视为第i个子问题的邻近子问题。在Step2步骤中在第i次经过的循环中，考虑到第i个子问题的T个相邻的子问题。在步骤Step2.1中的第i个子问题的领域中，xk和xl是当前最好解，它们的子代个体y应该对第i个问题产生好的解有帮助。在步骤2.2中，y使所有的约束无效，在这种情况下针对特定问题的启发式方法用于修复y，并优化i个gte。因此，所得到的解y是可行的，并且很有可能有一个函数值是第i子问题的邻居中较低的。步骤2.4考虑到第i个所有的邻近子问题，如果y的性能比低i个子问题xj优秀，那个y取代xj。在步骤2.4中，计算gte时需要FVj。由于查找精确的参考点z*比较浪费时间，在进化过程中采用近似解z。在步骤1.4随着进化不断更新Z，保持Z为各个目标上的最小值。他在步骤2.3中被更新。EP在1.1中初始化，在2.5中被新的解y替代。2. 讨论在MOEA/D中为什么要考虑一个有限的子问题：MOEA/D中使用的权重向量是在N个预先选取的权重向量中的一个。对于N个子函数，MOEA/D花费了相同的时间来优化，但是MOGLS是在每一代中随机生成一个权重向量。之前说到选择器只需要一个有限数量的均匀分布的Pareto最优解级，只对选取的有限的子问题进行优化不仅更现实而且更恰当。因为计算资源总是有限的，优化所欲可能子问题函数是不实际的，还会浪费计算性能。MOEA/D如何控制种群的多样性：在I中提到，MOEA算法需要控制种群的多样性来产生出具有代表性的一组解。多数的不是基于分解的MOEA比如NSGA-和SPEA-使用拥挤距离来控制多样性。但是，在这些算法中想要产生一组均匀分布的Pareto最优目标向量是不容易的。在MOEA/D中，一个MOP问题被分解为一组标量优化子问题。在每一代种群中，每个子问题的解之间实现互联系的。这些子问题本身的多样性会很自然的导致当前解的多样性。当选择了正确的分解方法和权重向量后，这使得通过子问题合成的最优解均匀的分布在PF边缘，如果MOEA/D能够很好的优化所有这些子问题，那么很有机会获得一组均匀分布的Pareto解。交叉约束和MOEA/D中T的作用：T是相邻子问题的集合大小。在当代种群中，对于每个子问题，只有T个最相邻子问题被用来优化它。某种意义上来说，两个解只有在他们会为相邻子问题是可以交叉产生一个子代。这个被称为交叉约束。要注意对于T的设定，如果T数值过小，那么xk和xl会非常的接近因为他们是两个近似子问题的解，因此，在步骤2.2中产生的y将会和他们的父代xk和xl非常接近。因而，这个算法就会陷入局部最优的困局。另一方面，如果T的数值过大，xk和xl对于子问题来说可能有用性不大，那么他们的子代也是如此。因而，这个算法的精度就会变低。此外，T过大也会导致2.4步中的计算复杂度大大提升。3. MOEA/D的变种我们可以在MOEA/D中使用任何其他的分解方法。如果使用了权重求和方法，那么MOEA/D就不需要去控制z。在步骤2.2中允许MOEA/D很自然的使用标量优化算法。gteyj,z或者gwsx最为目标方法在步骤2.2的启发式算法中。如果步骤2.1能够产生一个可行的解，那么步骤2.2就不一定是必须的，这也是MOEA/D的一个主要特性。使用外部种群往往对改进算法非常有帮助，但是在MOEA/D中他也是一个可选项。有一种替代方法，如果没有EP的话，就将最终的内部种群作为一个PF的逼近解返回。当然，其他的用于更新EP的随即策略也可以很容易的运用在MOEA/D中。还可以限制EP的大小以避免可能产生的内存溢出问题。MOEA/D算法在处理组合问题时拥有一个外部种群，而在处理连续优化问题时没有。在产生新的子代时并没有使用外部种群。这就是说，外部种群在对MOEA/D的搜索能力没有影响。在MOEA/D中，这种只有更好才取代的策略应用到所有的个体中。这种取代策略可以看做是以一种保优策略。因此，在遗传算子产生新的子代时，即使不利用外部种群中的非支配解作为父代，MOEA/D仍然具有很高的搜索能力。外部种群通常变的非常大，特别是咋高维情况下，主要是因为高维问题中的解几乎变的互相不支配。结果，当目标较多是，外部种群的修剪通常需要比较高的时间复杂度。细胞多目标遗传算法cMOGA也可以看做是一个使用分解额多目标进化算法。大体上，它使用一个相同的邻近关系来控制交叉。cMOGA和MOEA/D在遗传操作中解的选取和更新内部种群上是不同的，因为cMOGA使用权重求和方法最为引导性方法，他没有一个机制用以确保到目前为止发现的每一个子问题的最优解咋当前内部种群中，所以他不得不在每一代内部种群中插入EP解来解决非凸PF问题。.和MOGLS算法的比较接下来,首先介绍MOGLS然后分析了MOGLS和MOEA/D算法的计算复杂度。同时也比较了两种算法在01多目标背包问题上的处理能力。之所以选择MOGLS这个方法来比较，是因为MOGLS这个算法在多目标01背包问题上的处理能力很突出。1. MOGLSMOGLS使用一个基于惩罚系数的切比雪夫权重聚合方法或者是完全的权重聚合方法来将MOP问题分解为同时解决多个子问题。在每一次迭代当中，MOGLS需要控制当前的种群数量(CS)，和F值；需要控制一个外部种群(EP)，用来存储费支配解。如果MOGLS使用基于切比雪夫权重聚合方法来分解多目标问题，那么还需要控制一个参考点z。在本问题中，z就是每一个子问题的最大值的集合。MOGLS需要控制参数K和S。K是当前临时精英种群的大小，S是初始种群的大小。输入：多目标优化问题；算法终止条件；K：当前精英种群的大小；S：初始种群的大小输出：EP1. Step1：初始化2. Step1.1：通过针对问题的修复方法，随即生成一组解作为初始种群x1,xS。3. Step1.2：初始化z=(z1zm)T，令zi=minfix1,fix2,fixN。4. Step1.3：设置EP为初始种群对应的F值。5. Step2：更新6. For i=1,N do7. Step2.1：从CS中取得K个最优解，通过比较他们的切比雪夫值以及权重向量，一次来形成一个临时的精英种群(TEP)。在TEP中随即获取两个解，然后生成新的解y。8. Step2.2：改进：对y运用基于测试问题的修复和改进启发产生y。9. Step2.3：更新z：10. For each j=1,m，if zifjy，令zi=fjy end for11. Step2.4：更新TEP：For each jBi，如果y的值比TEP中最差的解要好的话，那么就把这个它放入当CS中，如果CS的大小比K*S大的话，那么就去掉最旧的解。12. Step2.5：更新EP：从EP中移除所有被Fy支配的向量，如果EP中的向量都不支配Fy，将Fy加入EP。13. End for 14. Step 3：终止条件：停止并输出EP，否则转Step22. MOEA/D与MOGLS的复杂度比较。空间复杂度：在搜索中，MOEA/D需要控制他的内部大小为N的种群，和一个外部种群EP，同时MOGLS需要维持一个当前种群和一个外部种群。因为CS的大小会非常大，知道K*S大小。因此MOGLS相比MOEA/D来说，在空间复杂度上更高。计算复杂度：MOEA/D和MOGLS的主要计算成本都在第二步中。在STEP2.1中，MOGLS需要获得K个最优解，这个需要O(m*CS)和O(k*CS)的复杂度。而MOEA/D因为是随机选取两个值，所以这个复杂度要远远低于MOGLS。在STEP2.2和2.3中，两者的计算复杂度相似。在STEP2.4中，如果T和K的大小相似的话，那么计算复杂度也相似。因此MOEA/D的计算复杂度要比MOGLS小。3. 0-1多目标优化问题。0-1多目标优化问题是NP级难度问题，他可以模拟出复杂环境下应用对资源的分配情况。上面是该问题的表达式。4. 修复方法在随即生成解的同时，我们很有可能获得到一个没有完全符合解约束的解，这是我们就需要一个修复方法来修复这个解。上式是个修复方法，我们g为目标函数，如果对分母影响最大同时又对分子印象最小的y存在，那么我们将这个y从解中去掉。反复循环，知道当前的解是符合要求的。参