英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于指标的多目标搜索选择
摘要
本文讨论了如何将决策者的偏好一般地融入到多目标搜索中。主要思想是首先根据二元性能指标（指标）定义优化目标，然后在选择过程中直接使用该指标。为此，我们提出了一种基于指标的通用进化算法（IBEA），它可以与任意指标相结合。与现有的算法相比，IBEA可以适应用户的偏好并且不需要任何额外的分集保存机制，例如分享使用的适应度。它显示了几个连续和离散的基准问题，IBEA算法可以在两种流行算法（即NSGA-II和SPEA2）就不同的性能测量而产生的结果方面得到实质性的改进。
1动机
在多目标情景中，优化过程的目标往往是找到一组Pareto最优解的良好近似。然而，困难在于，关于Pareto集合的良好近似的定义并不是一般的定义。每个特定的定义代表了取决于用户的特定的偏好。例如，可以将目标形式化为最大化由所得近似值控制的客观空间的超体积（参见[11，18]）。在某些情况下，这个定义可能是适当的，而在另一些情况下，这可能是不合适的，因为对于每个决策者和问题，优化过程的目标可能不同。
根据这个讨论，我们可以重新考虑在过去十年中指导多目标进化算法（MOEAs）设计的标准。我们在这里做了两个观察：
1．大多数MOEAs的基础是假设存在两个相互冲突的目标：（i）最小化到Pareto最优集合的距离，以及（ii）在Pareto最优集合的近似范围内最大化多样性[3]。然而，最近的研究[10，18]表明，这种假设是有问题的；根据我们的最佳知识，对于两个单独的目标，这里没有一个正式的定义，一个用于收敛，一个用于多样性，那是符合Pareto支配关系的。此外，还有与[1]中讨论的这个问题有关的实际问题。
2．在最流行的MOEAs中，上述假设是通过客观空间中的附加密度信息对个体进行基于Pareto排序来实现的。然而，算法在各个方面有所不同，因此它们中的每一个实现了稍微不同的优化目标，通常没有明确定义。这意味着目前的方法并未针对所使用的预设设计灵活性；相反，他们直接实施一种特定类型的预设信息。
至于第一个方面，另一种选择是使用决策者预设的符合Pareto的形式化（参见[9，10，18]）。这又反过来导致了一个与第二个方面直接相关的问题：如何根据任意偏好设计MOEA？
将偏好整合到多目标搜索中的问题已经由不同的研究人员解决，参见[2]的概述。例如，Fonseca和Fleming [8]提出了一个扩展的支配关系，它将预先确定的优先级和目标相结合；然而，上述两个观察结果也适用于由它们引入的算法，类似于本文中使用的许多其他算法：实现隐含地编码未指定的预设信息的分集保存机制。相比之下，Knowles [11]提出了一种多目标爬山者，它可以与任意的一元性能指标相结合，并且不需要niching方法。尽管如此，这种方法取决于所使用的性能指标，其计算成本很高，如何将其扩展到实现交配和环境选择的基于群体的多目标优化器尚不清楚。
在本文中，我们扩展了Fonseca和Fleming [8]和Knowles [11]灵活整合偏好的思想，并提出了一种基于指标的通用进化算法，简称IBEA。主要思想是根据优势关系的连续概括来形式化预设，这导致了一个简单的算法概念。因此，IBEA不仅允许适应任意偏好和优化场景，而且不需要任何多样性保存技术，与[8]相反。与[11]相比，IBEA更通用，因为种群规模可以是任意的，并且更快，因为它只比较个体对而不是整个近似集。正如将要显示的那样，与显着的基于Pareto的MOEAs相比，所提出的方法可以相对于所考虑的优化目标显着提高生成的Pareto集近似的质量。
2预备知识
在下文中，我们考虑由决策空间X，目标空间Z和n个目标函数f1，f2，...，f n定义的一般优化问题，给每个决策向量xisin;X分配一个对应的目标向量z=(f1(x)，f2(x)，...，f n(x))isin;Z。不失一般性，假设所有目标函数将被最小化，Z sube; I Rn。此外，MOEA的结果被定义为一组不可比较的决策向量，即0决策向量不支配该集合中的任何其他决策向量。这样的一个网络也可以表示为Pareto集近似，并且所有Pareto集近似的整体用符号Omega;来表示，其中Omega;sube;2Z。所有Pareto最优解集合称为Sisin;Omega;的Pareto集合S。
图1为本文使用的两个二元质量指标的示意图，其中A和B分别包含一个决策向量。
我们假设决策者的偏好是根据二元质量指标I：Omega;times;Omega;→IR给出的。一般而言，质量指标是将k个Pareto集逼近映射为实数的函数；最常见的是一元质量指标，其中k= 1（参见[18]）。二元质量指标可以用来比较两个Pareto集合近似值相对于彼此的质量。例如，二元加性指标Iisin; [18]给出了Pareto集逼近需要或可以在客观空间中的每个维度上进行平移的最小距离，这样另一个近似值被弱支配。形式上，定义如下：
Iisin; (A, B) = minisin;{forall;x2isin;B exist;x1isin;A：fi(x1)- isin;le; fi(x2) for iisin;{1, . . . , n}}
我们在此考虑二元质量指标的原因是它们表示Pareto优势关系的自然延伸，因此可以直接用于类似于普通的基于Pareto的适应度分配方案的适应性计算。但是，一个要求是所考虑的指标I符合Pareto主导地位，定义如下。
定义1：如果(i)x1gt;x2rArr; I({x1}，{ x2}) lt; I({x2}，{ x1}) 并且 (ii) x1gt;x2rArr;I({x3}， { x1}) ge; I({x3}，{ x2})，其中x1，x2，x3isin;X，则二元质量指标I被表示为优势保存。
我们将在后面看到这些属性如何确保所提出的适应度分配方案也符合Pareto主导地位。请注意，Iisin; 指示器是支配性的；例如，当x1支配x2时指标值变为负值（参见[18]）。
现在给定一个任意优化问题和一个相应的二元质量指标I，我们可以定义最优化过程的目标为使Aisin;Omega;的I（A，S）最小化，其中S是Pareto集合。如果I是支配优势，那么对于A = S，I（A，S）是最小的；在加性指标的情况下，Iisin; （S，S）= 0。注意，这里我们并不要求S是已知的，它只是服务于优化目标的形式化。
3基于指标的选择
考虑到第2节中描述的场景，问题是如何将I集成到MOEA中以最小化I（A，S），其中A是生成的Pareto集近似。本节讨论这个问题。
3.1适应度分配
种群P表示决策空间的样本，并且适应度分配试图根据其对优化目标的有用性对种群成员进行排名。在利用P和I给出信息的不同方式中，一种可能性是简单地总结每个种群成员相对于其余种群的指标值，即：F(x1) = 。这个适应值F将被最大化，它是衡量“质量损失”的一个度量，如果x1从总体中移除。对于Iisin; ，例如，F(x1)除以种群大小N等于其他种群成员覆盖x1所需的平均值。然而，我们将在下文中使用稍微不同的方案，放大支配人口成员对支配人口的影响：
F(x1) =
我们在这里使用一个支配性保存指标的属性，即如果x1gt; x2，则I({x1}，{ x2}) lt; I({x2}，{ x1})。因此，小指标值的影响对总体适应性的贡献大于大值。参数k是取决于I和基本问题的比例因子；k需要大于0。下面的定理表明该适应度方案符合Pareto支配关系。
定理1，设置I为一个二元质量指标。 如果I是支配优势，那么它认为x1gt; x2rArr;F(x1)gt; F(x2)。
证明，从定义1和性质（i）遵循指标值I({x1}，{ x2}) lt; I({x2}，{ x1})。由于定义1的性质（ii），我们知道I({x3}，{ x1}) gt;=I({x3}，{ x2})，forall;x3不isin;{ x1，x2}。 由于，如果x lt;y并且kgt; 0，则遵循F(x1)gt; F(x2)。
3.2示例指标
现在我们已经看到了如何使用加性指标来为群体成员分配适应值。但是，可以定义许多其他支配优势保护指标来代替。例如，以下IHD指标基于超体积概念[17]：如果任意forall; x2isin;B存在x1isin;A ：x1gt; x2，则IHD(A，B)= IH(B)- IH(A)；否则，IHD(A，B)= IH(A B)- IH(A)。
这里，IH(A)给出了由A支配的客观空间的超体积，并且相应地IHD(A，B)相对于预定的参考点Z测量由B支配而不是由A支配的空间的体积。IHD(A，B)值的计算对于包含若干决策向量的近似值而言在计算上是昂贵的，如果比较两个决策向量，则其为O(n)。除了本文后面的Iisin; 指标外，IHD指标还将被使用。IHD的图形解释可以在图1的右侧找到。
Hansen和Jaszkiewicz的研究[9]描述了可用于此处的二元质量指标的其他示例。
3.3基本算法
基于上述适应性分配方案，我们提出了一种基于指标的通用进化算法（IBEA），该算法为交配选择执行二元锦标赛法，并通过迭代地从群体中去除最差个体并更新其余个体的适应度值来实现环境选择。其运行时间复杂度为O(alpha;2)与人口规模alpha;有关。该算法的细节在下面给出；注意它仅代表IBEA的基本版本（在下文中表示为B-IBEA），稍后将指定扩展版本。
算法1（基本IBEA）
输入：alpha;（人口规模）
N（最大代数）
k（适应比例因子）
输出：A（Pareto近似）
步骤1：初始化：生成大小为alpha;的初始种群P；将生成计数器设置
全文共7293字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15991]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
