一种快速的优秀的基于多目标的遗传算法

一种快速的优秀的基于多目标的遗传算法 摘要——多目标进化算法（EAS），使用非支配排序和共享的方法，关键主要表现为：1）O（ MN3）计算复杂度线索（其中M是目标数目和N是种群数目）;2）非线性方法;3）需要指定一个共享参数。在本文中，我们提出一个非支配基于多目标排序EA （MOEA） ，称为非支配排序遗传算法（NSGA –II），这既减轻了上述三个困难。具体来说 ，一个快速的非支配方式O （ MN2）计算复杂度的排序方法被提上了纸面。此外，选择运作器，创建一个交配池相结合的父母和后代人口选择最好的（健康和传播方面）的N个解决方案。困难测试问题上的仿真结果表明，所使用的NSGA- II ，在大多数问题上，是能够找到很多更好的解决方案和更好的收敛接近真正的帕累托最优前，这是相比于帕累托归档的演变算法和强度帕累托EA- 这两种特别注意创造一个不同的帕累托最优前的算法。此外，我们修改支配地位的定义，以有效地解决约束多目标问题。一些测试问题如五目标七约束的非线性问题， 相比与其他约束多目标优化和仿真结果的约束表明NSGA- II能有更好的功效。

索引——约束处理，优选，遗传算法，多标准决策，多目标优化，帕累托最优的解。

1.简介

一个多目标优化问题的存在，在原则上是产生一组最佳的解决方案（主要是被称为Pareto最优的解决方案），而不是一个单一的最佳的解决方案。在没有任何进一步的条件下，其中的一个帕累托最优的解决方案不能说是比其他的优化解决方案好。这就要求用户能够找到尽可能多的帕累托最优的解决方案。经典的优化方法（包括多标准决策方法）建议将多目标优化问题转通过单独强调一个帕雷托优化解化为单目标优化问题。当使用这样的一种方法时，它需要被应用了很多次，希望在每次模拟运行寻找不同的解决方案。

在过去的十几年中，出现了许多运用面向多对象的遗传算法的例子出现。主要的原因是他们能够找到多个帕累托最优的解决方案，而只使用一次模拟运行。由于进化算法（ EAS ）是处理一个种群的解决方案，所以进化算法可以扩展到保持一组不同的多样化的解决方案。随着逐渐找到帕累托最优的地区， EA可以找到多个帕累托最优的解决方案，仅仅在一次模拟运行中。

非支配排序遗传算法（NSGA）[20 ]是进化算法的一种。多年来，主要批评NSGA方法如下所示。

1）高的计算复杂的非支配排序：目前所使用的非支配排序算法具有计算复杂度为O （MN3 ） （其中，M是目标数N的数量是种群规模） 。这NSGA计算对于种群规模较大的计算花费较大。这家大型的复杂性的产生是因为复杂性在非支配排序发生在每一代中 。

（2）缺乏精英主义：最近的研究结果[25]， [18]可以加快的GA的性能，这也可以帮助防止优化解的损失。

（3）3）需要指定共享参数QST ，分别是：传统的确保人口的多样性，使以获得等效各种各样的解决方案的机制已依赖对共享的概念。它的的主要问题共享是，它需要一个共享的规范参数（QSR ） 。虽然已经有一些关于动态共享参数大小[ 10 ]的工作，一个无参数的多样性的保护机制是可取的。

在本文中，我们为解决了所有这些问题提出了一种改进的版本，我们称之为NSGA NSGA- II 。从仿真结果所解决的一系列困难问题 ，我们发现NSGA- II在收敛的累托最优集附近发现一组不同的解系方面优于其他两个当代MOEAs ：帕累托存档的进化策略（ PAES） [14]和加强帕累托EA （SPEA） [24]。

约束多的优化是非常重要的解决实际问题的方法，但没有太多的关注EA的研究人员在这方面已经的付出。在本文中，我们提出一个简单的使用NSGA-I的约束处理策略，它适合任何EA问题。在我们从文献中选择四个问题中，一直比较NSGA-II和另一个最近提出的约束处理策略。这些比较鼓励NSGA- II应用到更复杂的和现实世界的多目标优化问题中去。

在余下的篇幅里，我们将在第二部分简要的介绍存在的精选MOEA算法，接下来在第三部分，我们将详细讨论NSGA –II。第四部分介绍NSGA –II的一些模拟运算结果，以及与其他多目标遗传算法的比较。在第五部分，我们着重强调参数的相互作用问题，这个问题在进化计算的研究方面很重要。接下去的单元，我们介绍NSGA-II的约束处理，以及和其他几种常用约束处理的比较。最后，我们得出结论。

2.精选多对象进化算法

在1993年至1995年期间，一些不同的精华算法，提出了并解决多目标优化问题。其中， Fonseca和Fleming的MOGA [7]， SRINIVAS和Deb的NSGA[20]， Horn等享有更多的关注。这些遗传算法演算了这些必要的操作算子，将一个简单的进化算法演变为非支配排序遗传算法。所有得分三种算子两种常见的特征如下：i）基于非支配排序将适应度值分配给总体中的每个个体ii ）维持具有相同非支配解的解决方案的多样性。尽管它们已找到多个非支配解决方案，研究人员意识到有需要引入更多的有用的算子（在单目标EA 中有很大的用处），以解决更好的多目标优化问题。特别的，对于精选算法能有效的提高MOEA的收敛性，所以给以了大量的研究。我们描述这些在简短的途径。有关详细信息，鼓励读者参考原来的研究。

Zitzler和Thiele [26 ]提出了精选多标准 EA与在基于其SPEA的非支配概念。他们表明，保持在每一代的外来人口的非支配性取决于最初的人口。这个外来人口参与在所有的遗传操作。在每一代，结合首先是人口与外部和目前的人口构建。适应度值的分配是根据个体所含解得多少来分配的，并且支配解所分到的适应度值小于非支配解。这种适应度值的分配保证了研究是朝找到非支配解的方向进行。一个确定的聚类技术被用来确保多样性，虽然执行建议在[26 ]是O（ MN3 ），适当处理运算复杂性， SPEA可以降低到O（ MNZ）。

诺尔斯和角膜[14]提出了一个简单MOEA单亲单后代EA （1 +1）演化方式二进制字符串被 使用并且逐位突变的才出现来繁殖后代。在他们的PAES理论中 ，一个父母有一个后代，后代只与自己的母代相比较。如果子代可以支配母代，那么子代就可以替代母代并如此反复进行。另一方面，如果父辈支配后代，那么子代就被丢弃，新的子代生成。当然，如果父代和子代互不支配，选择他们的方式是比较他们，看谁是更好的解决方案。子代在与以前的比较，看能否支配以前的，如果是的话，子代就可以变为父代。那么，所有被支配的解系就会从存档里消除。如果后代不支配存档中的任何成员，父母和后代进行检查，他们的亲近的归档解决方案。如果后代居属于一个最不拥挤的地区成员之间的存档空间，它被接受作为家长和副本的加入到存档。为了避免拥挤，通过划分整个确定的搜索空间在做子空间，其中，d是

深度参数和n是决策变量的数目，并通过动态更新的子空间。研究人员已经计算了最坏情况下的复杂性PAES的N评估为O（ AMN） ，其中一个是归档的长度。由于档案大小通常选择成比例的人口规模N，整体算法的复杂度是O（ MN2）。

下面，我们介绍非支配排序GA的方法，它采用了快速非支配排序过程中，精英保留的做法，和一个无参数算子。

3.精选非支配排序算法

为了清楚起见，我们首先描述一个简单的和缓慢的一个成不同的种群的排序程序的水平。此后，我们描述了一种快捷的方法。

一个简单的方法，以确定解决方案的第一个非支配前的人口规模N，每个解决方案可与所有其他解决方案的人口相比较，来检验它是否是支配的。这个过程需要O（ MN）次比较。其中M是目标的数目。当此过程继续查找第一级别的非支配所有成员，总的复杂度是O（ MNZ）。在这个阶 …… 此处隐藏：11224字，全部文档内容请下载后查看。喜欢就下载吧 ……