英语原文共 23 页，剩余内容已隐藏，支付完成后下载完整资料
基于优势和分解的进化多目标优化算法
Ke Li, Student Member, IEEE, Kalyanmoy Deb, Fellow, IEEE,
Qingfu Zhang, Senior Member, IEEE, and Sam Kwong, Fellow, IEEE
摘要——实现收敛与多样性之间的平衡是进化多目标优化中的一个关键问题。大多数现有的方法论已经在涉及两个和三个目标的各种实际问题上展现出其特殊性，在多目标进化中面临着显着的挑战。本文提出了一个统一的范例，它将优势和基于分解的方法结合起来，用于多目标进化。我们的主要目的是利用基于支配和分解的方法的优点来平衡演化过程的趋同和多样性。 我们提出的方法的性能经过验证，并与四个最先进的算法进行比较，其中包含多达15个目标的无约束基准问题。 实证结果充分证明了我们提出的方法在所有考虑的测试实例上的优越性。 另外，我们扩展这种方法来解决具有大量目标的约束问题。 与其他两个最近提出的约束优化器相比，我们提出的方法在所有约束优化问题上显示出高度竞争的性能。
关键词 - 约束优化，分解，演化计算，多目标进化，帕累托最优，稳态。
I ，导言
多目标进化问题（MOP）可以表述为
手稿于2014年6月12日收到; 2014年10月3日修订; 2014年11月4日接受。出版日期2014年11月21日;目前版本的日期为2015年9月29日。这项工作得到了中国国家自然科学基金项目资助61473241和61272289的支持，部分由香港城市大学深圳研究院，中国深圳和香港香港研究资助局总研究基金拨款9042038。
K. Li曾在香港城市大学计算机科学系工作。他现在在美国密歇根州东兰辛密歇根州立大学电子与计算机工程系工作。 K. Deb是美国密歇根州东兰辛密歇根州立大学电子与计算机工程系MI 48824。
Q. Zhang是香港城市大学计算机科学系，香港城市大学深圳研究院，深圳5180057，以及中国大学电子工程与计算机科学学院Essex，Colchester CO4 3SQ，英国（电子邮件：qingfu.zhang@cityu.edu.hk; qzhang@essex.ac.uk）。
S. Kwong与香港城市大学计算机科学系以及香港城市大学深圳研究院合作，深圳5180057（电子邮件：cssamk@cityu.edu.hk） 。
本白皮书中一个或多个数据的彩色版本可在http://ieeexplore.ieee.org上在线获取。
数字对象标识符10.1109 / TEVC.2014.2373386
最小化 F(x) = (f1(x),···,fm(x))T
受gj(x) ge;0, j=1,···,J hk(x) =0, k=1,···,K xisin;Omega;约束
其中J和K分别是不平等和平等约束的数量。 是决策（可变）空间，是一个候选解决方案。构成m个冲突目标函数，Rm称为目标空间。可达到的目标集定义为⊙= {F（x）|xisin;Omega;，gj（x）ge;0，hk（x）= 0}，对于jisin;{1，...，J}和k isin;{ 1,...,K}.
当且仅当对于每个iisin;{1，...，m}和fj（x1）lt;fj（x2），fj（x1）le;fj（x2），x1被称为支配x2（表示为x1le; x2） 对于至少一个索引jisin;{1，...，m}。一个解x *是帕累托最优的（1）如果没有其他解xisin;Omega; 例如xle;x *。 F（x *）然后被称为帕累托最优（客观）向量。 换句话说，在一个目标中对帕累托最优向量的任何改进必须导致至少一个其他目标的恶化。 所有帕累托最优解的集合称为帕累托最优集（PS）。 因此，所有帕累托最优向量集合EF = {F（x）isin;Rm |xisin;PS}称为有效前沿（EF）[1]。
自20世纪90年代初以来，人们一直致力于开发针对具有两个和三个目标的问题的演化多目标进化（EMO）算法[2] - [9]。然而，许多现实世界的应用，如配水系统[10]，汽车发动机校准问题[11]和土地使用管理问题[12]，往往涉及四个或更多的目标。因此，处理大量目标（也称为多目标进化）已成为近年来EMO社区的主要研究课题之一，这并不奇怪。
如果没有来自决策者的进一步信息，EMO算法通常设计为满足两个常见但常常相互矛盾的目标：最小化解决方案和EF之间的距离（即收敛），并最大化沿EF解决方案的扩散（即分集） 。在多目标进化中，平衡收敛和多样性变得更加困难。一般来说，大量目标带来的挑战包括以下六个方面。首先，随着目标数量的增加，几乎所有人口中的解决方案都不会互相支配[13]。这一方面严重恶化了对EF的选择压力，并大大减缓了演化过程，因为EMO算法的大多数精英维护机制都采用帕累托优势作为主要选择标准。其次，随着客观空间的增加，融合与多样性之间的冲突加剧[14]。由于大多数当前的分集管理算子（见[15]，拥挤距离[16]和第k个最近距离[17]）更喜欢选择优势抗性解决方案[14]，它们不能加强对EF的选择压力，甚至在一定程度上阻碍了进化过程。第三，由于计算效率的考虑，EMO算法中使用的总体规模不能任意大。但是，在高维度的客观空间中，有限数量的解决方案可能彼此远离。这可能会导致后代的低效率，因为繁殖操作通常会在高维空间中产生远离其父母的后代。接下来，众所周知，计算一些性能指标的计算复杂性，例如超体积 [18]，随着目标数量的增加呈指数增长[19]。最后，最后两个挑战是权衡表面的表示和可视化。虽然这两个问题可能不会直接影响进化过程，但它们会造成严重的决策困难。
面对上述困难，目前大多数EMO算法的性能已经显示出它们在两个和三个客观问题上的能力，当涉及三个以上目标时，其性能显着恶化[20]。基于帕累托的EMO方法（见[16]，[17]，[21]），其基本思想是根据帕累托优势关系和密度估计比较解决方案，是首当其冲的。由于上述第一个挑战，大部分非支配性解决方案使得主要选择标准，即帕累托主导关系不能区分解决方案。相反，也称为积极的多样性促进[14]，二级选择标准，即密度估计，控制交配和环境选择。然而，根据上述第二个挑战，由于存在显性抗性解决方案[24]，积极的多样性促进会导致对EF收敛的不利影响[13]，[22]，[23]。在过去的几十年中，基于指标的EMO方法（见[25] - [27]）被认为是一种有前途的多目标进化方法。与基于Pareto的方法不同，它将收敛性和多样性整合到一个单一的指标中，例如超体积 [18]，以指导选择过程。这个特点放弃了前面提到的前两个挑战。但不幸的是，如第四项挑战所述，超体积计算[19]的指数增加的计算成本严重阻碍了基于指标的EMO方法在多目标进化方面的进一步发展。尽管已经做出了一些努力来补救计算问题（参见[28] - [30]），但它在实践中还远未得到广泛应用。
总的来说，有五种可行的方法可以缓解进化多目标优化带来的挑战。第一个也是最直接的一个是新的支配关系的发展，可以增加对EF的选择压力。在这个方向上进行了大量的研究，如进化多目标优化，如isin;-dominance，优势区域控制[32]，网格优势[33]，偏好排序[34]， k最优[35]和基于模糊的帕累托最优[36]。此外，一些非基于帕累托的方法，如平均等级[37]，L-最优[38]和等级优势[39]，也显示了他们处理大量目标问题的能力。
另一个途径是基于分解的方法，该方法将MOP分解为一组子问题，并以协作方式进行优化。请注意，分解概念非常普遍，可以使用聚合函数或更简单的MOP [40]来形成子问题。由于这些子问题的权重向量广泛分布，预计获得的解决方案在EF上具有广泛的分布。 MOEA / D在[41]中提出，是这种类型的代表。在MOEA / D中，每个解决方案都有相关的子问题，并且通过使用其邻居的信息来优化问题。在过去的几年中，MOEA / D作为设计EMO算法的主要框架产生了大量的研究工作，在繁殖中引入自适应机制[42]，与局部搜索进行杂交[43]，并在选择中引入稳定匹配[44]。然而，这些算法对于多目标进化的有效性和有效性尚待验证。在多目标情景下，大多数MOEA / D的研究主要集中在研究行为的研究上（见[45] - [49]）。值得注意的是，[50]中提出的细胞多目标遗传算法（C-MOGA）也可以被认为是MOEA / D的早期版本。它为遗传搜索提供了几个方向，并使用相同的邻域概念来进行交配限制.C-MOG从MADEA获取/为子代繁殖和更新内部种群补充解决方案，并且必须在每一代插入来自其外部种群的解决方案给其内部种群与nonconvex EFs [41]。此外，最近提出的NSGA-III [49]也采用了基于分解的思想来保持种群多样性，而收敛仍受帕累托优势的控制。
第三种方式是通过改善多样性管理机制来挽救选择压力的丧失。 虽然听起来相当直观，但令人惊讶的是，在这个方向上没有做太多的工作。 在[51]中，提出了一种多样性管理算子来控制NSGA-II中拥挤度量的激活和去激活[16]。 在[22]中，通过对NSGA-II中拥挤距离的分配进行简单的修改，已经看到了收敛性能的显着改进。 在文献[52]中，提出了一种基于偏移的密度估计策略，通过将高密度值分配到拥挤的区域，将低密度值分配给收敛不佳的解决方案。 在一定程度上，NSGA-III的小生境保存操作的本质也可以看作是一种改进的多样性管理方案，它可以弥补高维客观空间中非支配性解决方案的泛滥所引起的选择压力的损失。
最后两种可行的补救措施是基于多准则决策的EMO方法和客观的减少。 前者涉及从整个PS寻找解决方案的优选子集（参见[53] - [55]）。 因此，由于缩小的搜索空间，上述困难可以得到缓解。 基于多目标进化问题中存在冗余目标的假设，后者考虑采用一些降维技术，如主成分分析[56]来识别环境目标空间中的嵌入式EF。 因此，针对两个和三个客观情况提出的经典EMO方法可以很容易地应用于这个减少的客观空间。
正如[57]所强调的那样，关于进化多目标优化的研究仍处于起步阶段。在两个和三个客观的情况下，EMO算法可以被认为是多目标进化的有效工具，仍然需要很大的改进。最近在[58]中的研究表明，基于帕累托分解和分解的EMO方法的代表，即NSGA-II和MOEA / D分别适用于不同的问题。这一观察极大地激励我们利用这两种方法的优点进一步改进和更广泛的适用性。在本文中，我们提出了一个统一的范例，称为MOEA / DD，它结合了基于支配和分解的方法，以解决多目标进化中提出的前三个挑战。本文的主要贡献总结如下。
1）我们提出了一个系统的方法来在高维客观空间中生成广泛传播的权重向量。每个权向量不仅定义了子目标，而且还指定了目标空间中的特定子集。
2）为解决上述高维度客观空间多样性管理的挑战，人口密度通过一个次区域的当地利基数估算。
3）考虑前面提到的第三个挑战，提出一种交配限制方案，以最大限度地利用从相邻子区域选择的交配亲本。
4）继承MOEA / D的稳态选择方案的优点，每次只考虑一个后代来更新人口。
5）为了解决所提到的第一个挑战，人口更新以层次方式进行，依次取决于帕累托优势，局部密度估计和标量化函数。此外，为了进一步改善人口多样性，提供给最后一个非支配级别的最差解决方案第二次机会，以防与隔离的子区域相关联。
6）对于具有大量目标的约束优化问题，提议的MOEA / DD进一步扩展。
本文的其余部分安排如下。第二部分提供了本文的一些背景知识。第三节致力于描述我们提出的多目标进化算法。第四部分提供了实验设置和全面的实验。在第五部分中进行和分析。第六部分介绍了MOEA / DD用于处理高维客观空间约束的扩展。 最后，第七部分结束本文，并介绍了一些未来的研究问题。
图1. PBI方法的说明.
II，准备工作
在本节中，我们首先介绍关于MOEA / DD中使用的分解方法的一些基本知识。 然后，我们简要介绍与本文相关的MOEA / D和NSGA-III的一般机制。
- 分解方法
原则上，经典多目标进化[1]中的任何方法都可以应用于我们的算法中，将MOP分解为一组标量优化子问题。 其中，最受欢迎的是加权总和，加权Tchebycheff和边界相交法[1]。 在本文中，我们使用了基于惩罚的边界相交（PBI）方法[41]，这是因为它在[49]中报告的多目标进化方面具有良好的性能。 这种方法是法线边界相交法[59]的变体，其中等式约束由惩罚函数处理。 更正式地说，PBI方法的优化问题被定义为
zlowast; = (zlowast;1,..., zlowast; m)T是zlowast; i lt;min xisin;Omega; fi(x) 的理想的目标向量，iisin;{1，...，m}，theta;ge;0是一个用户定义的惩罚参数。 图1给出了一个简单的例子来说明解决方案x关于权重向量w =（0.5,0.5）T的d1和d2。在PBI方法中，d1用于评估x向EF的收敛性，d2是种群多样性的一种度量。 通过将d2乘以theta;的值与d1相加，gpbi（x | w，z *）作为x的收敛和多样性的综合度量。
图2.用不同的theta;和w设置PBI函数的轮廓图.
d1和d2之间的平衡由参数theta;控制，PBI方法的目标是将F（x）推到尽可能低的位置，以便它可以达到的边界。
图2给出了三个2-D情况下PBI函数
全文共6524字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12945]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
