搜索
1一种基于参考点的非支配排序多目标优化算法，第一部分：解决箱约束问题KalyanmoyDeb,Fellow,IEEEandHimanshuJain摘要：利用进化优化方法，开发了多目标优化算法，并证明了它们各自的生态位，涉及多个和三个目标的各种实际问题，现在是一个多目标优化的进化发展的成长需要（EMO）处理多目标算法（有四个或更多的目标）的优化问题。在本文章中，我们认识到最近的一些努力和讨论了开发一个潜在的EMO算法求解多目标优化问题的一些可行的方向。此后，我们建议一种基于参考点的多目标算法（我们叫它nsga-iii），强调群体成员而非支配但接近一组提供的参点。该nsga-iii应用于许多许多客观测试的问题有两个到15个目标与最近提出的EMO算法（MOEA/D两版本相比）。而每种MOEA/D方法适用于不同类别的问题，提出了nsga-iii被发现在所有研究中考虑的问题均得到了满意的结果。本文对无约束问题的结果在处理许多目标优化问题时，环境管理系统和续集文件考虑了限制和其他专业。指数条款，多目标优化，进化计算，大尺寸，nsga-iii，非支配排序、多准则优化。一、引言自90年代初，进化多目标优化（EMO）的方法学已经充分证明他们的利基找到一套很好的融合及多元化的非支配解在不同的两个还是比较佩服目的优化问题。然而，在大多数现实世界中的问题，涉及多个股权持有人和功能，往往存在许多优化问题这涉及四个或更多的目标，有时要求有10至15个目标[1]，[2]。因此，这是不足为奇的，处理大量的目标一直是主要的研究活动的情绪在过去的几年里。许多目的问题的任何优化算法，提出了一系列的挑战，包括情绪。首先，比例在一个随机选择的非支配解客观的向量呈指数大的增加目标数。自非支配解占据人口最多的插槽，任何精英保留情绪面孔容纳足够数量的困难人口的新解决方案。这减缓了搜索过程相当[3]，[4]。其次，实施的一个多样性保护经营者（如拥挤距离算子[5]或聚类算子[6]）计算昂贵的操作。第三，可视化一个大尺寸的前面成为一个艰巨的任务，从而造成困难，在随后的决策任务和一种算法的性能评价。为了这个目的，性能指标（如超体积测量[7]或其他指标[3]，[8]）是计算过于昂贵或可能没有意义。一个很重要的问题便是‘有用的多目标优化问题简单吗？'。虽然上述第三个难度与可视化和性能指标以上不能应避免的一些算法改变现有的EMO算法可以解决第一个问题。在本文中，我们回顾了一些过去的努力[9]，[10]，[11]，[12]，[13]在设计多目标EMOS[14]和大纲设计高效的多目的EMO方法的一些可行的方向。然后，我们提出了一个新的方法，采用NSGA-II算法框架程序[5]，但与一组提供或预定义的参考点的工作，并展示其在解决2至15个目标优化问题的有效性。在本文中，我们介绍了框架和限制解决不受约束的各种各样的问题，如有归一化，缩放，凸，凹，脱节，和聚焦论帕累托最优前沿的一部分。实践可以提供存在的问题的这样的属性的数目。因此，对这些事件的一个算法充分的测试仍然是一个重要的任务。我们比较了NSGA-Ⅱ算法的性能—随着现有的许多客观情绪两版本（MOEA/D[10]），该方法有点类似的方法。关于MOEA/D与NSGA版本工作有趣的见解—一揭示了。该nsga-iii也对其他一些有趣的多目标优化使用决策任务。在本文的续集，我们建议处理多目标约束优化问题和其他一些特殊和艰难的nsga-iii延期了许多客观问题。2在本文的其余部分，我们首先讨论在求解多目标优化问题的困难，然后尝试回答上面提出的关于EMO算法的有用性在处理多目标问题。此后，在第三节中，我们提出一些对多目标优化包括最近提出的方法MOEA/D[10]过去的研究综述。然后，在第四节中，我们列出了我们所提出的nsga-iii程序详细。结果归一化DTLZ测试问题多达15个目标使用nsga-iii和MOEA/D两版本在部分v-a.结果放大版并在这里建议DTLZ问题旁边显示。此后，在随后的章节中，nsga-iii程序对不同类型的多目标优化问题的测试。最后，nsga-iii应用于两个实际问题涉及三个和九个目标的问题在第七。这项广泛研究的结论是：第八节。二、many-objective问题不严格的说，许多目标问题被定义为有四个或多个目标的问题。两个和三个目标问题分为不同的阶级所得到的帕累托最优前沿，在大多数情况下，在整体上可以全面使用可视化的图形方式。虽然一个严格的上限，对一个多目标优化问题的目标是不那么明确，除了几次[15]，大多数从业者都感兴趣的最大10至15个目标。在这一部分中，首先，我们讨论的困难，现有的EMO算法可能面临在处理许多客观存在的问题和研究的EMO算法是有用的在处理大量的目标。A.在处理许多目标的困难它已在别处讨论[4]、[16]，目前最先进的EMO算法工作支配[17]可能面临以下困难的原则下：1)一大部分的人口是非占主导地位：它是众所周知的[3]，[16]，随着数量的增加，越来越多的人口比例越来越大，成为非支配。由于大多数EMO算法强调的非劣解在一个群体中，在处理多目标问题，没有太多的一代创造新的解空间。这会减慢搜索过程，因此整体的EMO算法效率低下。2)多样性测度的评价变得计算昂贵：确定解决方案在一个人口拥挤程度，对邻居的识别变得昂贵的计算在大尺寸空间。任何妥协或近似的多样性估计，使计算更快可能会导致一个不可接受的解决方案在最后分配。3)重组操作可能是低效的：在一个许多目标问题，如果只有极少数的解决方案被发现在一个大的空间，解决方案很可能是彼此遥远的。在这样一个群体，重组算子的效果（这是一个情绪的一个关键搜索算子）变得可疑。两家遥远的父母解决方案很可能会产生后代的解决方案，也远离父母。因此，特殊的重组运营商（配合限制或其他计划）可能是必要的，有效地处理许多客观问题。4)表示的权衡表面是困难的：它是直观的，以实现这代表一个更高的尺寸的权衡表面，指数更高的点是必要的。因此，一个大的人口规模是必要的，以代表所产生的帕累托最优前沿。这会导致一个决策者难以理解和作出足够的决定选择一个最佳的解决方案。5)性能指标是计算昂贵的计算：由于高维点集进行相互比较，建立一对一的算法的性能研究，需要一个更大的计算工作量。例如，计算超体积度量需要成倍的计算与目标[18]数，[19]。6)可视化是困难的：最后，虽然这是一个不相关的问题，最终的一个更高维度的权衡面前化可能对许多目的是困难的问题。第一三困难只能通过现有的EMO方法缓解一定的修改。第四，第五，和第六的困难都是多目标优化问题的一般的问题，我们不解决他们在这里。B.处理多目标问题的EMO的方法在我们讨论可能的补救措施三上述的困难，在这里我们强调多目标问题的两个不同的类的方法学存在的情绪仍然可以使用。首先，现有的EMO算法仍可能找到一个最佳的解决方案的子集是有用的（部分）从完整的帕累托最优集。虽然首选的子集仍然是许多暗淡维，因为有针对性的解决方案都集中在帕累托最优前沿的一个小区域，最上面的困难将由这个原理缓解。基于多目标决策的EMO方法数技术已经发明了10目的问题上表现良好，大的这个目的和结果[20]，[21]、[22]、[23]。其次，实践中的许多问题，尽管有许多目标，往往退化到一个低维帕累托最优前[4]，[11]，[25]，[24]。在这类问题中，冗余的目标识别可以用一个EMO找到帕累托最优前沿，低维集成。由于最终的前两或三维低，现有的EMO方法应该在处理这样的问题的工作。先前的研究NSGA-II算法与主成分分析（基于主成分分析法的程序[4]是能够解决大到50个客观问题，有一二个客观的帕累托最优前沿。3C.对于许多目的情绪的两个想法牢记第一三困难与控制为基础的EMO程序有关，两种不同的策略可以考虑减轻困难：1)采用专用的控制原理：上面提到的第一个困难是可以通过使用特殊的控制原理，将自适应离散化的帕累托最优前找到缓解一个分布均匀的点集。例如，对∈-使用控制原理[26]，[27]将使所有的点在∈距离的一组帕累托最优的点∈占据统治地位，因此过程中会产生有限数量的帕累托最优为目标。这样的考虑，也将缓解二难的多样性保护。第三难度可以照顾到使用一个交配方案或限制在一个特殊的重组方案接近母方案强调（如SBX大量分布指数[28]）。其他特殊控制原则[29]，[30]也可以用于这个目的。阿吉雷和田中[31]和Sato等人。[32]建议使用一个子集的目标为优势检查和使用不同的组合每一代人的目标。使用固定的锥支配[33]，[34]或可变锥支配[35]的原则，也可以尝试。这些研究是在低维公共关系的背景下进行的他们在解决问题和多目标优化的成功尚未建立。2)使用一个预定义的多目标搜索：它已经越来越清楚，这是太多的期望从一个单一的人口为基础的优化算法，其人口的收敛耳朵的帕累托最优前沿的同时，其分布均匀在整个前面的一个大尺寸的问题。处理这类多目标优化问题的一个方法是通过一些外部手段帮助多样性的维护问题。这一原理可以直接解决上述二个难点。而不是寻找帕累托优化整个搜索空间误的解决方案，多个预定义的有针对性的搜索，可以通过一个算法。由于最佳的点被发现对应于每个目标搜索任务，第一个困难的处理一个大的非支配集也缓解。重组的问题可以通过使用一个交配约束方案，从邻近目标的两个解决方案参与回收处理应用操作。我们提出的算法（nsga-iii）是基于这样的原则，因此我们讨论这方面的一些更详细的。我们建议执行预定义的多的两种不同的方式多目标搜索原理：a)一组预定义的搜索方向，跨越整个帕累托最优前可以预先指定，并可以进行多个搜索沿每个方向。由于搜索方向是广泛分布，得到的最佳点也有可能被广泛分布在大多数问题上的帕累托最优前沿。最近提出的MOEA/D程序[10]利用这个概念。b)多个预先定义的参考点，而不是多个搜索方向，可以指定为这个目的。此后，对应于每一个参考点的点，可以强调找到设置帕累托最优点的分布广泛分布。最近提出了一些这样的实现[36]，[37]，[38]，[14]，本文提出了另一种扩展和完善的方法并提出在第一参考[36]。三、现有的many-objective优化算法加尔萨法布尔，Pulido和基于[16]建议三单目标措施，通过使用两个竞争的父母和个人目标值之间的差异表明，在5到50目的DTLZ1，DTLZ3和dtlz6问题收敛性可以得到比一些现有的方法包括基于EMO方法通常的帕累托优势增强。purshouse和弗莱明[39]表明，附近的帕累托最优前多样性保护和实现收敛是两个相互矛盾的目标，通常的遗传算子是不足以达到目的的同时，特别是许多客观存在的问题。同时，特别对许多客观存在的问题。另一项研究[40]延伸NSGA-II加入多样性控制运营商解决六到20目的DTLZ2问题。Koppen和吉田[41]针对其创意NSGA-II程序不适合多目标优化问题，提出了一些指标，有可能取代NSGA-II的拥挤距离操作性能更好的人。基于对二到15目的DTLZ2仿真研究，DTLZ2,DTLZ3和DTLZ6问题，他们建议用一种替代分配距离测度作为最佳战略。Hadka和Reed[42]建议为基础的EMO程序使用一个合适的重组算子从一组八到10个不同的预定义的运算符基于代明智的成功率问题的自适应选择。它也使用∈-优势概念和自适应的人口规模的方法，是解决了八个目标测试成功。巴德一DZitzler[43]表明样品的超体积计算的快速程序，设计了一个以最大化的超体积找到一套折中解算法。越来越多的文学关于近似超体积计算[44]，[18]，[45]可以使这样的方法解决许多客观问题。上述研究分析和扩展先前建议的进化多目标优化算法，其适用于解决许多客观问题。在大多数情况下，结果是有希望的，所提出的算法必须进行其他更具挑战性的问题比通常的标准测试问题如DTLZ问题。他们也必须尝试在真实—世界的问题。在下面的文章中，我们描述了最近提出的算法，非常适合我们的一个多目标优化算法在第II-C给予描述和密切与我们所提出的算法相匹配。4MOEA/D[10]使用一组预定义的权重向量保持多样化的