一种快速优秀的非支配排序遗传算法 多目标优化算法：NSGA-II外文翻译资料

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

一种快速优秀的非支配排序遗传算法

多目标优化算法：NSGA-II

Kalyanmoy Deb，Samir Agrawal，Amrit Pratap， T meyarivan

遗传算法实验室（坎加尔） 坎普尔的印度技术学院 坎普尔，208针016，印度

摘要：多目标演化算法主要受到（i）计算复杂度（目标数量和种群规模），（ii）非精英方法和（iii）非主流方法进行分类和分配的多目标进化算法， 需要指定共享参数的制约。 在本文中，我们提出了一种非主导的排序多目标进化算法（我们称之为非主导排序GA-II或NSGA-II），可以缓解上述三种难题。 特别地，提出了一种具有计算复杂度的快速非主导排序方法。 第二，提出了选择算子，通过组合父代和子代群体并选择最佳（相对于完整性和传播）解决方案，创建交配池。仿真测试结果表明，与PAES相比，所提出的NSGA-II能够在所有问题上找到更好的解决方案。另外一种精英多目标EA，特别注意创建一个多样化的帕累托最优前沿。 由于NSGA-II的计算量低，精准的方法和无参数共享方法，NSGA-II应该在未来几年得到越来越多的应用。

1 介绍

在过去十年中，已经提出了一些多目标进化算法（MOEAs）[9,3,5,13]。 其主要原因是他们能够在一次运行中找到多个帕累托最优解。 由于问题具有多目标公式的主要原因是因为不可能拥有同时优化所有目标的单一解决方案，所以提供了大量替代解决方案的算法，该算法位于帕累托最优前沿或其附近， 具有很大的实用价值。 Srinivas和Deb [9]中提出的非主导排序遗传算法（NSGA）是第一个这样的进化算法之一。 多年来，NSGA方法的主要批评如下：

非主导排序的高计算复杂度：现在使用的非主导排序算法是，如果人口众多，则非常昂贵，特别是因为人口需要在每一代进行排序。

缺乏精英主义：最近的结果[12,8]清楚地表明，精英主义可以显着加快GA的表现，也有助于防止一旦找到好的解决方案就会失去效用。

需要指定共享参数：保证人口多样性的传统机制，以获得各种各样的等效解决方案，在很大程度上依赖于共享的概念。 共享的主要问题是它需要指定一个共享参数。 虽然共享参数的动态尺寸已经有一些工作[4]，但是无参数的多样性保存机制是可取的。

在本文中，我们解决了所有这些问题，并提出了NSGA-II的NSGA改进版本。 从仿真结果出发，我们发现NSGA-II在其优化解决方案中比PAES [6] - 其他精英多目标进化算法具有更好的传播。 这些结果鼓励NSGA-II应用于更复杂和真实世界的多目标优化问题。

2精英多目标进化算法

在Zitzler，Deb和Theile [12]的研究中，清楚地表明，精英主义有助于实现MOEAs更好的融合。 在现有的精英教育部门中，Zitzler和Thiele的[13]力量Pareto EA（SPEA），Knowles和Corne的帕累托存档进化策略（PAES）[6]以及鲁道夫[8]精英GA都是众所周知的。

Zitzler和Thiele [13]提出了一个精英主义的多标准EA，具有非统治性的概念，它们的实力是Pareto EA（SPEA）。他们建议在每一代保存外部人口，存储从初始人口开始发现的所有非主导解决方案。这种外部人口参与遗传操作。在每一代，首先构建了与外部和当前人口相结合的人口。综合人口中所有非主导的解决方案都以其主导的解决方案数量为基础，并将主导的解决方案的配置优于任何非主导解决方案的最差状态。这种功能的分配确保搜索针对非主导的解决方案。确定性聚类技术用于确保非主导解决方案之间的多样性。虽然[13]中提出的实现是，通过适当的记账，SPEA的复杂性可以降低到，这项研究和后续研究的一个重要方面[12,11]清楚地表明了在进化多标准优化中引入精英主义的重要性。

Knowles和Corne [6]提出了一个使用进化策略（ES）的简单MOEA。在一个父母和一个孩子的帕累托存档ES（PAES）中，将孩子与父母进行比较。 如果孩子占主导地位，则该孩子被接受为下一个父母，并且继续进行迭代。 另一方面，如果父母主导孩子，那么孩子被丢弃，并且找到了一个新的解决方案（一个新的子代）。然而，如果孩子和父母不相互控制，孩子和父母之间的选择就会考虑到在获得的解决方案之间保持多样性的第二个目标。为了保持多样性，保持非主导解决方案的档案。将该小孩与归档进行比较，以检查它是否支配档案的任何成员。如果是，该小孩被接受为新的父母，并且从归档中消除了主导的解决方案。如果孩子没有统治档案的任何成员，父母和孩子都会通过档案的解决方案来检查他们的亲近度。如果子进程驻留在归档成员之间的参数空间中拥挤不到的区域中，则将其接受为父级，并将其添加到归档文件中。后来，他们提出了一个与上述类似原则的多父母PAES。作者已经将评估的PAES的最坏情况的复杂度计算为，其中a是可达的长度。由于归档大小通常选择与群体大小成比例，所以算法的整体复杂度是。

Rudolph[8]提出，但没有模拟一个简单的精英多目标EA，基于来自亲代和后代人群的个体的系统比较。将后代人口的非主导解决方案与母体解决方案进行比较，形成一个整体非主导的解决方案，成为下一代的母亲群体。如果这个集合的大小不大于所需的人口数量，则包括来自后代人群的其他个体。通过该策略，他已经能够证明该算法与帕累托最优前沿的收敛。虽然这本身就是一个重要的成就，但算法缺乏维持帕累托最优解的多样性的第二个任务的动机。必须添加明确的多样性保存机制，使其在实践中更加可用。由于第一个非主导前沿的确定性是 ，Rudolph算法的整体复杂度也是 。

3精英主义非主导排序遗传算法（NSGA-II）

Srinivas和Deb在1994年提出的非主导排序GA（NSGA）被应用于各种问题[10,7]。 然而，如前所述，对NSGA有许多批评。 在本节中，我们修改NSGA方法以减轻上述所有困难。我们首先介绍一些构成NSGA-II的不同模块。

3.1快速非主导排序方法

为了根据非统治水平对大小N进行排序，每个解决方案必须与人口中的每个其他解决方案进行比较，以确定其是否主导。这需要每个解决方案的比较，目标数量在哪里。当这个过程继续发现所有人口成员的第一个非主导阶层的成员时，总的复杂度是。在这个阶段，发现了第一个非主导阵线的所有人。为了找到下一代个人的个人，第一前线的解决方案暂时被打折扣，并重复上述步骤。在最坏的情况下，第二面的任务也要求计算。重复该过程以查找次序前沿。可以看出，最差的情况（每个前端只存在一个解决方案），这个算法的复杂度是。在下文中，我们描述了一种快速非主导排序方法，最多需要计算。

首先，对于每个解决方案，我们计算两个实体：（i），主导解的解的数量，以及（ii）解决方案占主导地位的一组解。 这两个实体的计算需要比较。我们识别所有这些点，它们有=0，并将它们放在一个集合.我们称之为当前的。 现在，对于当前前台的每个解决方案，我们访问它的集合中的每个member（j），并将它的count减1。 在这样做时，如果任何成员j的计数变为零，我们将其放在单独的列表中。 当前正面的所有成员都被检查过后，我们将列表中的成员声明为第一前线的成员。 然后，我们使用新确定的前端作为我们当前的前沿继续此过程。

每个这样的迭代都需要计算。 这一过程一直持续到所有方面都得到确认。 由于最多可以有N个，这个循环的最坏情况是复杂的是现在算法的整体复杂度是或者这里值得一提的是，尽管计算负担减少了通过执行系统的书面保存，从到，在最坏的情况下，存储从增加到。应用于人口的快速非主导排序过程返回非主导集合F。

3.2密度估计

为了估计人口中特定点周围的解决方案的密度，我们沿着每个目标的这一点的两侧的两点的平均距离。 这个数量作为包围点的最大长方体的大小的估计，而不包括人口中的任何其他点（我们将其称为拥挤距离）在图1中，第i个解决方案的拥挤距离 在前面（用实心圆标记）是长方体的平均长度（用虚线框示出）。以下算法用于计算集合中每个点的拥挤距离：

图1显示拥挤距离计算

这里表示集合TT中第m个人的第m个目标函数值。 该过程的复杂性由排序算法控制。 在最坏的情况下（所有解决方案都在前面），排序需要计算.

3.3拥挤比较运算符

拥挤的比较运算符（）指导在算法的各个阶段的选择过程，以均匀分布的帕累托最优前沿。 让我们假设人口中的每个人都有两个属性。

1.非支配排序（）

2.本地拥挤距离()

我们现在定义一部分顺序（）

if()or(()and( ))

也就是说，在具有不同非统治级别的两种解决方案之间，我们更喜欢具有较低等级的点。 否则，如果两个点都属于相同的前沿，则我们更喜欢位于具有较少点数的区域中的点（长方体的长度大于其）。

3.4主循环

最初，创建一个随机父母群体p0。 人口按非统治地位排序。 每个解决方案被赋予等于其非控制级别（1是最佳级别）的等级。 因此，假设最小化固定度。 二进制竞赛选择，重组和变异算子用于创建一个大小为N的子群体Q0。 从第一代起，程序是不同的。 精英程序为对于特定一代，显示如下：

首先，组合人口形成。 种群的大小为2N。 然后，种群按非统治地分类。 新的父代种群 通过添加第一个前端的解决方案，直到大小超过N。 此后，最后接受的前线的解决方案按照进行排序，并选择第一个点N。 这是我们如何构建大小N的种群数量。 这个大小N的种群现在被用于选择，交叉和突变，以创建一个大小的新人口。 重要的是要注意，我们使用二进制比赛选择算子，但是选择标准现在是基于比较运算符。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[25590]，资料为PDF文档或Word文档，PDF文档可免费转换为Word