英语原文共 13 页

多目标优化方法：分析

摘要

基于分解的方法常被用于求解目标数量增加的多目标非凸优化问题。这些方法利用一个标量函数将多目标问题简化为一组单目标问题，在解的基础上得到一组良好逼近的最优解。这个集合通常称为Pareto前沿。在本文中，从概率的角度探讨了基于分解的方法与基于Pareto算法的区别。也就是说，我们研究使用基于分解的方法，例如使用切比雪夫标量函数是否比使用基于Pareto的算法有优势。我们发现，在目标函数条件温和的情况下，当我们考虑为遵循平衡轨迹算法找到最优解的概率时，切比雪夫标量函数与Pareto优势关系的效果几乎相同。我们提出这样一个假设:与现有的经验证据相比较，这个看似矛盾的结果表明基于Pareto和基于分解的方法之间的性能差异是由于前一类算法无法遵循平衡轨迹的结果。我们还将广义分解与本文的结果联系起来，展示了如何在Pareto前几何的前提下，获得给定问题的最优标量函数。

2014爱思唯尔公司保留所有权利

1. 介绍

在考虑非凸问题时，只有在穷举搜索的情况下才能保证所得到的解。也就是说，要探索目标函数的整个定义域。当然，这样的任务很容易变得难以管理。然而，一旦问题是非凸的事实成立，就可以使用几个元启发式来获得一个解决方案。在文献中经常被称为进化算法(EAs)的元启发式的例子有:遗传算法(GAs)[17,14,26]，进化策略(ES)[36]，差分进化(DE)[40]，粒子群优化(PSO)[8,31,43]和其他等[7,1,18,33,13]。

尽管上述方法产生的解决方案很可能不是最优的，但元启发式在实践中表现良好。因此，与使用随机搜索[30,39]相比，它具有渐进收敛性，EAs在实际应用中会更快地收敛到许多问题的最优解的邻域[50,48]。当然，这并不意味着EAs优于随机搜索所有问题。它的含义是如果利用领域知识，EAs可以非常有效地解决[35]问题，特别是考虑到即使是凸问题在最轻微的刺激下也会变成非凸问题，例如[5]。

本文主要研究多目标非凸问题。多目标问题的一个问题是，一个完整的排序不是唯一定义的，不是一个最优解，而是一组最优解[44,p113],[34,p61]。在进化多目标优化领域，有两种主要的方法来解决这个问题:基于Pareto的方法和基于分解的方法。在这两种方法论和假设中，都使用了后验偏好表达范式[34,p63]，但目标的相对重要性是未知的。如果决策者(DM)给出了偏好信息，则可以使用分解方法组合标量目标函数，见第4节。另一种选择是将决策者给出的偏好信息提取为效用函数，但这需要对问题结构有广泛的了解，并不能保证其解决方案是Pareto最优[44,p62]。基于Pareto的方法利用Pareto优势关系[34]在目标空间中诱导部分排序。

具有3个以上目标的多目标问题在实际应用中很常见。一些例子是控制和航空航天，见例[9]。然而，随着维数的增加，不可比拟的解的个数在总体中占主导地位，选择压力大大减小，导致对Pareto 前沿的收敛速度较差[24]。对于具有3个以上目标的多目标问题，使用基于Pareto的方法面临的另一个问题是，不清楚如何保持解决方案的多样性。

一些作者声称解决方案是使用基于分解的算法，因为，它们适用于大规模数据，与基于Pareto算法相比，它们具有更好的收敛速度[23],这种观点似乎获得支持[16,20],如在[47]中介绍的MOEA/D算法的出版物数量所示。然而，如果要考虑相对性能，基于分解的算法和基于Pareto的算法之间的差异并不显著。也就是说，基于分解的算法的性能在所选择的指标中通常与基于Pareto的算法具有相同的数量级，例如参见[47,32]。此外，基于分解的方法也有一定的困难。例如，在Pareto前沿上分布解决方案的简单方法似乎难以获得基于分解的方法。这一不足的原因在于文献中大多数结果只适用于凸优化问题，选取加权向量和标量函数并不容易[44,34]。然而，最近的研究结果表明，在一定的假设下，这些问题是有办法解决的[11,12]。基于分解的方法的另一个问题是并不是所有的标量函数都能保证所有的Pareto最优解都能得到[34,p99]。一个例外是切比雪夫标量函数，它可以用于凸或非凸问题，同时保证产生弱Pareto最优的解。此外，有一个定理适用于切比雪夫的标量化函数，该定理表明，对于某个权重向量，可以得到所有的Pareto最优解[34,p99]，也许这就是文献中越来越多地使用这种尺度函数的原因，参见[47,42]。

到目前为止，还没有理论证据支持上述观点，即对于具有3个以上目标的问题，基于分解的方法优于基于Pareto的方法。文献中已有一些研究，例如[38,41]，但假设目标函数为单峰函数，即凸函数或拟凸函数。这种假设限制了这些工作的范围，因为进化算法(EAs)适用于非凸问题。在这项工作中，我们试图揭示基于Pareto的EAs似乎不适用于目标数量增加的问题的基本原因，而不是基于分解的优化算法。此外，与[38]相比，我们之前关于问题结构的假设更加宽松和现实。这项工作的主要贡献可以总结如下:

·从理论角度研究了Pareto优势方法的效果，并解释了几种基于Pareto的算法所面临的困难。

·并且研究了基于分解的方法，阐明了它们与优势度方法的关系。一个主要的结果是在某些假设下基于切比雪夫标量函数的方法与基于Pareto优势的方法是等价的，而这些假设在基于分解的算法中通常易于满足的。

·最后，给出了关于Pareto前几何的一些先验信息，确定了最优标量函数。最优是指在给定起始点z_c的情况下，通过这个标量函数找到更好的解的概率比其他标量函数的下降速度要慢，同时可以由切比雪夫标量函数提供的类似保证给出。

本文的其余部分结构如下。第2节给出了多目标优化问题的定义。在第3节中，我们讨论了基于Pareto的方法，并探讨了优势关系对这类问题的影响。此外，在第4节中，我们对一类基于加权度量标量函数的分解方法进行了与基于Pareto的方法相似的分析。在第5节中，我们证明对于满足p lt;infin;的基于norm的分解函数，可以给出与切比雪夫标量函数提供的类似的保证。此外，在第6节中，我们反思了所提出结果在这项工作中的后果以及目前的背景，在这些背景下，我们的结果可以建设性地用于改进解决大量目标问题的算法。最后在第7节中对这项工作进行了总结和总结。

2. 问题定义

多目标优化问题定义为:

(1)

其中k是标量目标函数的个数，x是具有定义域的决策向量, 而Z是目标空间并且为映射F下的S的前向图像。当目标k大于3时，(1)定义的问题在进化多目标优化社区被称为多目标问题。这种区别的原因在于，对于非凸多目标问题，目标数量的增加会对算法在Pareto前沿附近寻找解的能力产生深远影响，而对于凸问题，这通常不是问题。但是，为了避免混淆，在本文中我们只是简单地将这些问题称为多目标问题。有关多目标优化的更多详细信息，请参阅[44,34]。

3.Pareto法

3.1 概述

在数学规划中，Pareto优势关系主要用于理论目的。然而，在进化算法中，它们被大量用于适应度分配。适应度分配与梯度搜索中的负梯度有相似的功能，它指明了一个有可能的搜索方向。因此，如果EA无法获得这样的方向，那么继续搜索将变得越来越困难，因为没有迹象表明正在生成更好的解决方案。

具体来说，在最小化中，如果没有其他决策向量使得，那么对于所有的i ,决策向量 被称为Pareto最优，至少有一个i = 1,hellip;,k。也就是说，不存在映射到一个明显优越的目标向量的其他的决策向量。类似地，如果没有其他决策向量使得对于所有的i = 1,hellip;,k满足，则认为决策向量是弱Pareto最优的。最后，由二元关系，引起的排序之所以被称为部分是因为存在以下可能：，但是并且，在这种情况下，向量x和 y是不可比较的。

大多数多目标问题求解者试图确定一组Pareto最优解。该集合是Pareto最优集(PS)的子集，也被称为Pareto前沿。Pareto最优集的定义如下:，即它是在可行目标空间中不受任何目标向量支配的目标向量集合。目标函数的前向图像为集合的决策向量也称为Pareto集合，记为，即。也就是说，根据应用于目标空间的部分排序隐式排序决策空间。

3.2 目标函数中的偏差

在本文的以下部分中，我们假设目标函数不偏向Pareto前沿。这个术语与WFG工具包[19]的作者所称的目标函数中的偏差有关。对于在S中均匀分布的决策向量，目标函数被认为是无偏的，在目标空间中得到的分布也是均匀的或者是接近均匀的。在这项工作中，我们使用了同样的偏差概念，但是我们也提供了一个定义，该定义说明了陈述的基本假设：“目标函数没有偏差”，或“目标函数偏向Pareto前沿”等。在这项工作中，我们考虑以下形式的目标函数:

（2）

其中h为目标空间中的概率密度函数，B为距Pareto前沿距离r或更小的所有可行目标向量的集合，R_i为的元素。同时,当在均匀分布U下对决策空间进行采样时，目标向量z位于集合B中的概率。在前两种情况下，即R₁和R₂，以及对于某些r gt; 0，我们说目标函数分别偏向于Pareto前沿并远离Pareto前沿。当R₃对所有的r gt; 0成立时，目标函数没有偏差。

图1 第3.4节中描述的实验的轨迹比较分解和基于Pareto的方法。M_P为可行目标空间的上界，L_P为Pareto前沿和可行目标空间的下界。此外，V_F是Pareto前沿下方的体积，V_Z是可行目标空间的体积，V_P是包含当前解决方案z_c的优质解决方案的区域的体积。最后，z_s和z_e为初始和目标向量，z_e为Pareto最优。左图说明了上述z_c = z_s的量，右图说明了随着z_c沿(z_e - z_s)向z_e移动时，上述量是如何变化的。结果如图2所示。

3.3 多目标问题的Pareto优势

在[24]中，Ishibuchi等人提供了实证结果，试图解释基于Pareto优势算法应用于多目标问题上时性能不佳的原因。他们的主要观点是，非支配个体与种群大小的比值接近1，这意味着几乎整个种群都是非支配的，因此算法的选择机制没有提供有用的信息。接下来我们进一步阐述这一论点，证明在多目标问题中可以预期这种行为，并且我们在一定程度上揭示了造成这种困难的根本原因。

考虑最简单的多目标情况，即两个目标问题。目标空间中的每个点都定义了4个区域，(i)一个区域包含的解决方案明显更好，记作S; (ii)一个区域包含的解决方案明显更差，在和(iii, iv)两个区域中，解决方案是无法比拟的问题。在一般情况下，对于k维问题，总有1个区域的解决方案明显更好，1个区域的解决方案明显更差，还有2^k - 2个区域包含不可解决的问题。此外，假设问题(目标函数)没有对这些区域的任何一个区域的偏差，随机过程(算法)在这些区域中任意一个区域生成解的概率与这些区域的体积除以目标空间中整个可行集的体积Z成正比。然而，随着维数的增加，对于目标空间中的任何一点，在区域内生成解决方案的可能性都会大大降低。

虽然这个没有偏差的假设问题似乎限制了上述论点的普遍性，但这并不完全正确。为了说明这一点，我们在优化的背景下考虑目标函数中偏差的相对方向。这种偏差可以是:(i)偏向于Pareto前沿，即PF附近比在任何其他区域更容易获得解决方案，(ii)偏向于包含明显更差的解决方案的区域，以及（iii）偏向包含不可比解的任何区域。只有在(i)的情况下，与无偏解相比，优化问题的解决才变得更容易。然而，这种有利的情况在实践中很少遇到。假设目标函数没有偏差，我们计算的所有概率在最坏情况下都是集合S中解的概率的上界。换句话说，本文报告中的概率代表关于目标向量的位置的可获得的最佳概率。我们将在第6节中进一步阐述这一点。

为了更好地理解多目标优化算法在这类问题上面临的困难的原因，我们在更具体的基础上构建了上述示例。假设目标空间Z由如图1所示的超平面有从上方围起来的，具体来说，上界是点集。选择具有这种特定几何结构的可行目标区域的原因将在下面的内容中解释清楚。另外,让Pareto前沿变成(k – 1)单纯形，即Pareto最优目标向量为集合的一部分 ，显然我们必须选择L lt; M为最小化问题因为L gt; M意味着z = {empty;}。如果我们也假设这个问题没有偏差，那么对于给定的目标向量，就可以计算出目标空间中任何点获得更好的解的概率。这些信息在许多方面都很有用，我们将在第6节详细介绍这些信息。

现在，给定目标空间中的一个点z_c，其中下标是当前点的缩写，我们可以用下面的关系计算得到更好解的概率，

（3）

其中,对于基于Pareto的方法，是可行的目标空间的体积，它等于M_P, L_P和象限之间的板块体积，参见图1。此外,是在给定目标向量z_c的情况下找到更好的目标向量z_n的概率。(3)中的表达式仅适用于给定一组

资料编号：[3440]