英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料
（下文翻译的是an evolutionary many-objective optimizaiton algorithm ... 对应部分）
III. 现有的多目标优化算法
Garza-Fabre等人[16]研究了两个竞争的父代个体之间的差异，并基于这一差异提出了三种单目标优化的方法，这项研究表明，与常规的Pareto支配EMO方法相比，该方法在五目标到50目标之间的DTLZ1，DTLZ3和DTLZ6问题收敛性更强。 Purshouse和Fleming [39]的研究表明，在Pareto最优前沿附近，多样性和收敛性是两个不可兼得的目标，特别是对于许多多目标优化问题，一般的遗传算子根本不足以同时实现两个目标。另一项研究[40]又在NSGA-II算法中添加了分集控制算子，以此来解决6到20目标优化的DTLZ2问题。 Koppen和Yoshida [41]声称NSGA-II过程的独创性并不适用于多目标优化问题，并提出了许多可以取代NSGA-II拥挤距离算子以获得更好性能的指标。基于双目标到15目标DTLZ2，DTLZ3和DTLZ6问题的仿真研究，他们提出以替代指配距离度量作为最佳策略。 Hadka和Reed [42]提出了一种基于集合的EMO程序，该程序从8到10个不同的预定义算子中选择出来一个合适的重组算子（这些算子即问题中各代群体的成功率）。它还涉及了E-支配性的概念以及一种自适应的种群规模调整方法，据称可以成功解决八目标优化问题。Bader和Zitzler [43]提出了一种计算基于样本的超容量的快速程序，并设计了一种算法来找到一组使得超容量最大化的解决方案。越来越多的关于近似超容量计算的文献[18]，[44]，[45]使得这种方法在解决多目标问题时实用化。
上述研究分析和扩展了先前提出的进化多目标优化算法，以及他们在解决多目标优化问题时的性能。在大多数情况下，结果是都是相对可靠的，并且所提出的算法必须在比通常的标准化测试问题（如DTLZ问题）更具挑战性的问题上进行测试。另外，我们还必须在现实的场景下对他们进行测试。在下面的篇幅中，我们来描述一个最近提出的算法，它与我们在第II-C节给出的多目标优化算法的描述非常契合，并与我们提出的算法非常吻合。
MOEA / D [10]使用一组预定义的权重向量来维护一组不同的权衡解决方案。对于每个权重向量，所产生的问题称为子问题。首先，每个群体成员（该种群的规模与权重向量的规模相同）随机地与权重向量相关联。此后，将通过生态位参数（T）定义的相邻权重向量的两个解匹配，并创建后代解。然后基于性能度量将后代与一个或多个权重向量相关联。研究中提出了两项性能度量指标。从理想点到一个点的惩罚距离度量由参考方向的加权总和（权重theta;是另一个算法参数）和形成沿着参考方向的距离（d1）
（1）
我们将这个过程称为MOEA / D-PBI。第二种方法是使用Tchebycheff度量、理想点z *和权重向量w来表示
（2）
在之前的模拟[10]中，理想点被记为z *，而零权重的情况则是通过量级较小的数字来处理的。我们称此过程为MOEA / D-TCH。外部种群维持非支配性解决方案。前面提到的前两个困难是通过使用一组明确的权重向量来寻找目标点，第三个困难通过使用匹配限制方案来缓解。仿真结果仅针对双目标和三目标测试问题，而得出的结论是在三目标优化中，MOEA / D-PBI比MOEA / D-TCH更好，并且MOEA / D-TCH的性能通过使用人口最小和最大客观值的客观标准化过程得到了改进。两个版本的MOEA / D都需要设置一个生态位参数（T）。基于双目标和三目标问题的一些模拟结果，笔者建议使用种群的大部分成员作为T。另外，MOEA / D-PBI需要适当地设置额外的惩罚参数theta;，笔者建议其值为5。
MOEA / D的开发者在稍后的研究中使用差异进化（DE）取代遗传重组和变异操作。 此外，他们还进行了进一步的修改，定义了特定解决方案的邻域，并用相应的后代解决方案取代了给定邻域中的父代[46]。这里我们称这种方法为MOEA / D-DE。与其他算法相比，该算法主要在二目标规划和三目标规划相关问题的解决[47]上性能更佳。如前所述，MOEA / D是一种很有前景的多目标优化方法，因为它解决了上面提到的一些问题，但研究者们并没有探讨它们解决大量目标规划问题的适用性。在本文中，我们使用它来解决具有多达15个目标的问题，并评估它们对真正的多目标优化问题的适用性，并揭示这些算法一些有趣的特性。
另一项最近进行的研究[14]引用了我们对多目标优化程序的描述。该研究扩展了NSGA-II程序，以提出用于处理三目标和四目标问题的混合NSGA-II（HN算法）。该研究的研究者将混合后的群体成员投影到超平面上，并且在超平面上执行聚类操作，以此选择期望数量的群集（该群集由用户定义）。此后，根据种群的多样性，使用随机群成员上的局部搜索操作使得解靠近Pareto最优前沿，或使用分集增强算子从所有群中选择群体成员。由于没有使用有针对性的分布式搜索，这种方法比MOEA / D或本文建议的算法过程更通用。然而，HN算法的效率在四个以上目标的问题尚未得到研究，因此其在多目标问题解决中的总体性能尚不明确。下文我们将描述我们提出的算法。
IV. 提出算法： NSGA-III
本文所提出的多目标的基本框架NSGA-II(或NSGA-III)与最初的NSGA-II算法[5]一样，在选择算子中进行了显著改进。但是，不同于NSGA-II的是，NSGA-III中的种群成员多样性是通过提供和适用性地更新大量传播良好的参考点来保持的。为了本文的完整性，我们首先要简略地介绍一下最初的NSGA-II算法。
考虑一下NSGA-II算法的第t代。假设该代中父母群体是Pt，群体规模为N，其产生的子代群体是Qt，群体规模是N。第一步将父母群体和子代群体混合得到Rt=Ptcup;Qt（混合群体规模为2N），并从中挑选出最佳的N个种群成员，这样我们便能够保留下父代中的最优个体。这样我们就需要根据不同的非支配层级（F1,F2等）对混合种群Rt进行排序。然后，从F1开始，每次从各非支配层级中挑选出一个最优个体来组成St种群，直到St种群的规模等于或首次超过N为止。假设最后一个包含的层级为第l层。那么，Rt中l 1层及以上的所有解都会被拒绝进入St种群。在大多数情况下，最后接受的一个层级，即第l层中，之后一部分个体会被接受进入St种群。在这种情况下，我们只选择Rt种群中差异性最大的个体集合进入St种群。在NSGA-II算法中，该选择过程是通过一个有效率计算的，但是是大体上的，小生境保存的算子来计算每个级别成员的拥挤距离，并以此作为两个相邻的解的目标导向的归一化距离之和。然后，选择出有更大的拥挤距离值的解。而在NSGA-III算法中，我们用以下方法来代替拥挤距离算子。（IV-A–IV-E部分）
A.将种群划分为各非支配级别
以上用常规支配准则来识别非支配前线的步骤仍然适用于NSGA-III算法。所有从非支配层级1到层级l的种群成员都首先进入St。如果|St | = N，那么就无需进行任何操作，下一代种群便为Pt 1=St；但如果|St | gt; N，从非支配层级1到层级l-1的成员已经被选定，即，而剩下的种群个体便从中选择出来。我们将在下一个小部分阐述剩下的选择过程。
B.超平面上参考点的确定
如前所述，NSGA-III使用了预定义的参考点集合以确保获得的解决方案的多样性。选择的参考点可以在结构化方式中预定义或由用户优先提供。我们将在稍后的结果部分中给出这两种方法的结果。在没有任何偏好信息的情况下，任何预定义的结构化的参考点放置都可采纳，但是，在本文中，我们使用Das和Dennis[48]的系统化方法，在标准化的超平面—一个M-1维度的单位单层—上放置点，这相当于对所有目标轴有一定斜率和截距。如果说对于每一个目标轴有p个分支，那么在一个M个目标函数优化的问题中参考点（H）的总数可以由下式给出
例如，在一个三目标优化的问题(M = 3)中，参考点是在一个顶点为(1,0,0)，(0,1,0)和(0,0,1)
的三角形上创建的。如果对于每个目标轴选择4个分支，即，那么便会产生15个参考点。这些参考点的分布如图1所示。在NSGA-III算法中，除了强调非主流的解决方案外，我们也强调在某种程度上和每个参考点联系的种群成员。因为以上产生的参考
点在整个归一化超平面上分布广泛，所以得到的解也很可能是在Pareto最优集合上或临近Pareto最优集合处广泛分布的。在用户自己给定优先参考点集合的情况下，最理想情况是用户能够在归一化的超平面上标记H点或者指出所有与此目标对应的H和M维度矢量。本文中的NSGA-III算法很可能会发现近似于pareto -最优解的解集，这些解对应与所给定的参考点，这样就使得该方法从综合运用决策和多目标优化角度来看更加常用。这一过程在算法1中有详细阐述。
图1 p=4时的三目标优化问题中，15个结构化参考点在一个标准化参考平面上的分布图
算法1
C.人口成员的适应性标准化
首先，种群St的理想点是通过确定在中的每个目标函数的最小值，以及通过构建理想点来决定的。然后St中每个目标函数的值减去，从而使得转换后的种群的理想点成为零向量。我们将转换后的目标函数记为。然后，通过找到使对应的成就标量函数（通过和接近第i个目标函数轴的权重矢量来构建）取得最小值的解（）来确定每一个目标函数轴上的极值点。
图2. 三目标优化问题中计算截距以及通过极值点形成超平面的过程
然后用这M个极值矢量构建一个M维的超平面。然后便可以计算出第i个目标函数轴上的截距和线性超平面（如图2）。对于退化情况和非负截距的处理应当给予特别的关注。然后目标函数可以归一化为
（4）
注意到每个标准化目标函数轴上的截距现在是，而用这些截距点构建的超平面将会使得。
在构建参考点的情况中，使用Das和Dennis[48]的方法计算的初始参考点已经处于这些标准化超平面上了。而在用户指定优先参考点的情况中，参考点只是被简单放置在上述（4）式所构建的标准化超平面上了。因为每一代中标准化过程和超平面的产生已经使用先前找到的极值点完成，NSGA-III算法过程便可以保持每一代中限定空间的分散度。这使NSGA-III能够解决目标函数值可能会差异化分散的Pareto最优化集合的问题。这一过程在算法2中有详细阐述。
D.关联操作
在对基于目标函数空间中成员范围中的每一个目标函数做了适应性的标准化后，我们还需要将每一个种群成员和参考点关联起来。为此，我们超平面上每一个参考点的参考线定义为从原点到该参考点的连线。然后，我们计算每一个种群成员到参考线的垂直距离。在标准化的目标函数空间里参考线到种群成员最近的参考点便与种群成员联接起来，如图3所示。这一过程在算法3中有详细阐述。
算法2
图3. 种群成员和参考点的连接图
算法3
E.小生境保持操作
值得注意的是参考点可能有一个或多个或者不需要与之相关的种群成员。我们计算与每个参考点相关的来自Pt 1 = St/Fl的种群成员的数量。我们使用第个参考点的来定义小生境数量。我们现在设计如下所示的新的小生境保存操作。首先，我们记参考点集合Jmin = {j : argminjrho;j}的最小值为。在有多个这种参考点的情况下，我们随机选取一个(macr;j isin; Jmin)。
如果（这表示参考点没有相关的成员），那么对于集合中的便有两种解决方案。第一种方案，在层中存在一个或多个与参考点相关的成员。在这种情况下，与参考线的垂直距离最短的哪一个将被添加到。然后参考点上的的计数值便增加1。第二种方案，在层中不存在任何与参考点相关的成员。在这种情况下,
参考点被排除在当前代进一步考虑的范围之外。
在（即已经有一个与参考点相关的成员存在于之中）的情况下，便从与参考点相关的层中随机选择一个种群成员添加到中。然后的计数值加一。在小生境数量更新之后，该过程重复次来填补中空缺的种群位置。该过程在算法4中有详细阐述。
算法4
F.创造子代种群的遗传操作
在Pt 1种群形成后，通常利用常规的遗传算子来创建一个新的子代Qt 1。在NSGA-III中，我们已经对解决方案进行了细致的最优选择，并试图通过筛选出最接近每个参考点的参考线的解来保持解决方案的多样性。同样，正如我们将在第五节中描述的，对于一个快速计算的过程，我们已经将N设置为几乎等于H，从而期望在每个参考点对应的pareto -最优前沿进化出一个种群成员。出于所有这些原因，我们不使用任何与NSGA-III的显式复制操作来处理只包含框约束的问题。种群Qt 1是通过随机选取
全文共6281字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15994]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
