搜索
一个快速和精英机制的多目标遗传算法KalyanmoyDeb,AssociateMember,IEEE,AmritPratap,SameerAgarwal,T.Meyarivan摘要:应用非支配排序的多目标进化算法被广为评判，主要是因为：1）3()OMN计算复杂度（其中M代表目标个数，N代表种群个数）2）非精英机制方法；还有3）需要指定一个共享参数。本文中，我们提出了一个基于非支配排序的多目标进化算法（MOEA），称为第二代非支配排序进化算法（NSGA-II），它缓解了以上三个难点。特别要明确指出的是，一个计算复杂度只有2()OMN的快速非支配排序方法被提出。还有，一个通过结合父代和子代种群以及选择最佳解决方法（根据适应度和扩展性）创建交配池的选择算子被提出。对不同的测试问题进行的模拟仿真结果表明所提出的NSGA-II，在大多数问题中，与其他进化策略和强性Pareto进化算法——两个注重创造具有多样性Pareto占优前沿面的精英机制的多目标进化算法——相比能找到相对扩展性较好的解以及更能收敛于实际Pareto占优的前沿面。另外，为了高效解决约束多目标优化问题，我们修改了支配的定义。对一些测试问题，包括5目标、7约束的非线性问题，将约束NSGA-II算法的模拟仿真结果与另一个约束多目标优化算法相比，NSGA-II的性能明显更好。索引词—约束处理，精英机制，遗传算法，多重判据决策，多目标优化，Pareto占优法I.引言原则上，在一个问题中存在多个目标会产生一个最优解集合（广范知晓的是Pareto占优解法），而不仅仅是一个最优解。没有任何进一步的信息，不可以认为一个Pareto占优的解法会比其它解法好。这需要用户找到尽可能多Pareto占优的解。经典优化方法（包括多重判据决策方法）建议通过每次强调一个特有的Pareto占优解将多目标优化问题转化为单目标优化问题。当这种方法被用来寻找多个解时，在每次模拟运行时它必须运行多次才有希望找到不同的解。在过去几年，一些多目标进化算法(MOEAs)被相继提出[1],[7],[13],[20],[26].其主要原因是它们能够在一次单一的模拟运行中找到多个Pareto占优解。因为进化算法(EAs)以种群方式运行，所以一个简单的进化算法可以被扩展到保持不同解的集合。以向Pareto占优区域移动为重点，那么在一次单一模拟运行下一个进化算法可以被用来找到多个Pareto占优解。非支配排序遗传算法(NSGA)[20]正是首批基于这种思想的算法之一。多年来，对NSGA方法的主要批判有如下几点。1）支配排序的高计算复杂度：当前使用的支配排序算的计算复杂度为3()OMN（其中M代表目标函数的数目，N代表种群的数目）。对大的种群数目会使得NSGA的计算非常昂贵。这种大复杂度的起因是由于在每一子代中都包含非支配排序程序。)2）缺少精英机制：近来结果[25],[18]表明精英机制能够很大程度上提高遗传算法的性能，同时还能够防止较优解一旦被发现后丢失的情况。3）需要指定共享参数：传统的种群多样性保存机制为了得到多种多样等价的解则非常依赖共享的概念。共享的主要问题是它需要指定共享参数(share)。即使已经存在一些共享参数动态大小调整的工作[10]，但是一种无参的多样性保持机制仍然很需要。本文中，我们致力于所有这些问题并提出了一个NSGA的改进版本，我们称之为NSGA-II。从对一些困难测试问题的仿真结果上看，就找到一个多样性解的集合以及收敛于真实Pareto最优解集合的性能来看，我们能够发现NSGA-II优于同时期的其他两个多目标优化算法MOEAs：Pareto归档进化策略(PAES)[14]和强化Pareto进化算法(SPEA)[24]。约束多目标优化对实际要解决的问题来说是非常重要的，但是至今在进化算法领域并没有得到足够的重视。本文中，我们根据NSGA-II提出了一个适合任何遗传算法的简单约束处理策略。在文献中选择出来的四个问题测试，NGSA-II被用来和另一个当前提出的约束处理策略做对比。实验结果表明NSGA-II可以被鼓励应用于更多复杂的以及现实世界中的多目标优化问题。在文章的剩余部分，在第二章节我们简略地提到一些存在精英机制的多目标进化算法。然后，在第三章节，我们详细描述了所提出的NSGA-II算法。第四章节展示了NSGA-II的仿真结果并与其它两种多目标优化算法(PAES和SPEA)对比。在第五章节，我们重点强调了参数相互作用的问题，它是在进化计算方向非常重要的问题。下一章节将NSGA-II扩展到处理约束问题并将结果与当前另一个提出的约束处理方法做对比。最后，我们概括了本文的结论。II.精英机制的多目标进化算法1993-1995年期间，一些不同的进化算法被提出用来解决多目标优化问题。在它们之中，Fonseca和Fleming的MOGA[7],Srinivas和Deb的NSGA[20],以及Hornetal.的NPGA[13]得到了更多的关注。这些算法展示了将EA转化为MOEA的附加算子。以上三个算子有如下两个共同特征：i）基于非支配排序给种群成员指定适应度ii)在同一支配前沿面的解中保持多样性。即使他们已经被证明在很多测试问题以及一些工程设计问题上可以找到多个非支配解，研究者发现需要引进更多有用的算子（在单目标进化算法上已被证明有用）来更好地解决多目标优化问题。特别地，这种想法致使精英机制被引进用来提高MOEA的收敛性能。文献[25]表明经营机制能帮助MOEAs实现更好地收敛性能。在已经存在的精英机制MOEAs，Zitzler和Thiele的SPEA[26],Knowles和Corne的Pareto归档PAES[14],以及Rudolph的精英机制GA[18]得到充分地研究。我们简单描述了这些方法。细节部分，读者可自行参考原研究。Zitzler和Thiele在他们的SPEA中提出了一个带有非支配概念的精英机制多重判据进化算法。他们建议在每一子代中维持一个外部种群用于保存所有从开始至今找到的非支配解。这个外部种群参加每一次的遗传操作。在每一子代中，一个由外部和当前种群合成的种群首先被构造出来。在合成种群中所有非支配解都会根据他们所支配的解的数目被指派一个适应度值，并且被支配的解会被指派一个比当前最坏适应度值更坏的值作为适应度。这种适应度的分配保证搜索是直接朝向非支配解的。一种确定性的聚类技术被用来在非支配解中保证多样性。即使在文献[26]中提出的方法实现需要3()OMN，但是通过合适的保存方法SPEA的复杂度就会较少到2()OMN。Knowles和Corne[14]提出了一个使用与(1+1)-进化策略相似的单父代单子代进化算法的简单的MOEA。相反不使用实参，而是使用二进制串和按位变异来产生子代。在他们只有一个父代和一个子代的PAES中，子代被用来与父代比较。如果子代支配父代，那么子代就被接受作为下一次父代并且迭代继续。另一方面，如果父代支配子代，那么子代被抛弃并且一个新的变异解（新子代）被找到。然而，如果子代和父代都不互相支配，那么通过比较他们的目前找到最优解的存档来决定选择父代或子代。将子代与存档对比来检查它是否支配存档中的成员。如果存在支配情况，那么子代就被接受作为新的父代并且将所有的支配解从存档中剔除掉。如果子代没有支配存档中的成员，那么检查父代和子代与存档中其他解的接近程度。如果子代在存档的成员中处于目标空间最不拥挤的区域，那它就被接受作为父代，并拷贝加入存档中。通过将整个搜索空间准确划分为md子空间（其中d是深度参数，n是决策变量的数目）以及动态更新子空间来保持拥挤度。研究者已经计算出PAES最坏的复杂度为()OMN对N个评估来说，其中是存档的长度。由于存档大小经常按种群大小N的比例选择，所以总体上算法的复杂度为2()OMN。Rudolph[18]提出了，但是并没有仿真，一个基于系统的来自父代与子代种群个体比较的简单精英机制MOEA。将子代非支配解通过与父代解对比建立总体非支配解的集合，并将它作为下一次迭代的父代种群。如果这个集合的大小不比期望的种群大，那么来自子代种群的其他个体就被包括进来。通过这个策略，他证明了这个算法对Pareto最优前沿面的收敛性。即使对它自己来说这是一个重要的成功，但是算法缺少对第二个保持Pareto多样性解任务的推动性。一个明确的多样性保留机制一定是更加实用的。由于第一个非支配前沿面的确定需要2()OMN，所以Rudolph算法整体的复杂度也为2()OMN。接下来，我们展示了所提出的非支配排序GA方法，它使用了快速非支配排序步骤，精英保留方法以及一个无参小生境算子。III.精英机制的非支配排序遗传算法A.快速非支配排序方法由于描述清楚的缘故，我们首先描述了一个将种群排序为不同支配等级的简单并且缓慢的步骤。然后，我们描述了一个快速的方法。在这个简单的方法中，为了能在大小为N的种群中确定第一非支配前沿面的解，每一个解都被用来和其它种群中的解来对比来判断它是否被支配。对每个解需要()OMN次比较，其中M是目标的个数。持续这个程序直到找到种群中所有第一支配等级的成员，全部复杂度为2()OMN。现阶段所有在第一非支配前沿面的个体都被找到。为了找到下一支配前沿面的个体，第一前沿面的解被暂时打折并且以上程序被重复进行。在最坏的情况下，找到第二前沿面同样需要2()OMN次比较，特别当()ON个解属于第二或者更高的非支配等级。这个证据对找到第三和更高等级的非支配面同样正确。因此，最坏的情况是有N个前沿面并且每一个前沿面只有一个解。这总共需要3()OMN次比较。要注意的是程序需要()ON的储存空间。在接下来的段落和页底所示的方程中，我们描述了一个只需要2()OMN比较的快速非支配排序方法。首先，对每一个解我门计算两个实体：1）支配计数np，即支配着解的解的数量，还有2）Sp，解所支配的解的集合，这需要2()OMN次比较。所有第一非支配前沿面解的支配计数都为零。现在，对每一个解p都有0np，我们访问每一成员（q）和他的集合Sq并且减少逐一减少支配计数。通过这样，如果任何成员q的支配计数达到0，我们就把它放进一个单独集合Q。这些成员属于第二非支配前沿面。现在，以上程序应用Q中的每一成员继续执行直到第三前沿面被确定。这一过程持续到所有前沿面被确定。对每一个在第二或更高非支配等级的解p来说，支配计数np最多为N-1。因此，每一个解p在它的支配计数达到零时最多被访问N-1次。基于这一点，一个被指定非支配等级的解不会被再次访问。由于存在最多这样的解有N-1个，所以全部复杂度为2()ON。因此整体的程序复杂度为2()OMN。另一种计算复杂度的方法，第一内部循环的整体（对每一个ipF）被执行N次同时每一个体之多成为一个前沿面的成员，在第二层内循环中（对每一qSp）对每一个体来说被最多执行（N-1）次（每一个体最多支配(N-1)个体并且每次支配检查需要至多M比较)。这样的结果就是整体需要2()OMN次比较。需要注意的是虽然时间复杂度减少到了2()OMN，但存储空间需要增加到2()ON。）B.保留多样性我们之前提到，EA有收敛于Pareto占有集合的性能，在已获得解的集合中保持很好的扩展性也是EA所需要的。NSGA原型使用了著名的共享函数方法，这种方法已经被证明在相关参数设定合理的情况下能够在种群中找到很好的多样性。共享函数的方法包括一个共享参数share，它用来设置一个问题中要求的共享程度。这个参数与被选择计算两个种群成员的接近程度的距离度量标准相关。这个参数share表明在任意两个解间最大的距离测度会共享它们的适应度值。这个参数通常由用户来设置，即使在文献[4]中有一些指导方法，但是共享函数方法仍存在两个难点。1）共享函数方法在维持解的传播性能上过分依赖于share值的选择。图1拥挤距离计算。实心点代表同一非支配前沿面的解2）由于每个解必须与种群中其它所有解比较，共享函数方法的总体复杂度为2()ON。在所提出的NSGA-II中，我们用拥挤比较的方法替换了共享函数方法，它在一