英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

外文翻译

题 目 多目标进化优化的约束测试问题

作 者 Kalyanmoy Deb, Amrit Pratap, and T. Meyarivan

发表时间_____2001年_______

二Ｏ 一九 年 四 月 三十 日

摘要：在过去的几年里，研究人员已经开发了许多多目标进化算法（MOEAs）。尽管大多数研究都集中在求解无约束优化问题上，但也有一些研究将无约束优化问题推广到了求解约束优化问题上。随着约束处理方法的普及，需要开发能够很好地评价算法的测试问题。在本文中，我们回顾了一些文献中使用的测试问题，然后提出了一组可调整的约束处理测试问题。

导言

多目标进化算法（MOEAs）充分证明了使用基于人群的搜索算法来解决多目标优化问题的优点[1,14,8,5,6,11]。在复杂程度不同的多目标优化问题中，精英莫厄斯证明了他们在接近真正的帕累托最优战线和维持一套多样化解决方案方面的能力。尽管取得了这些进展，但似乎没有足够的研究集中处理制约因素的程序。约束处理是现实问题解决的重要组成部分，现在是研究约束多目标优化问题的时候了。

要评估任何算法，都需要对测试问题有很好的理解和可调整性。尽管在文献中存在一些约束处理程序，但它们都是在简单问题上尝试过的，特别是决策变量很少，非线性约束不充分。当算法在这些问题上表现良好时，评估它的真正价值就成了迷信，特别是在一般问题解决的背景下。

本文概述了文献中提出的几种约束处理方法。此后，我们回顾了一些流行的测试问题的程度，他们的二。然后，我们提出了一个具有六个参数的可调测试问题生成器，它可以被设置为得到所需的二进制度的约束测试问题。用NSGA-II [1]与约束控制原理和另外两种约束处理程序的仿真结果，揭示了NSGA-II在解决二进制约束优化问题中的优越性。试验问所证明的二元性，将使它们有资格作为今后几年的标准约束多目标试验问题。

受限的多目标进化算法

目前只有少数研究表明，一个特殊的设计用于处理约束。在所有方法中，通常的惩罚函数方法[11,2]，即在所有目标函数中增加与完全违反约束成正比的惩罚。当应用这个过程时，所有的约束和目标函数都必须归一化。

Jimenez等人[7]提出了一个程序，该程序仔细比较了二元锦标赛选择中的两个解决方案。如果一个方案可行，另一个方案不可行，则选择可行的方案。如果这两种解都可行，则使用霍恩等人的[6]精确法。另一方面，如果两个解都是不可行的，则更有可能选择更接近约束边界的解。

Ray等人[10]提出了一种更详细的约束处理技术，在这种技术中，对所有约束的约束违反行为并不是简单地归纳在一起，而是对约束违反行为进行非支配性检查。基于单独使用目标函数、单独使用约束违逆以及将目标函数和约束违逆放在一起对种群进行单独的非支配排序，算法需要很大的计算复杂度。

最近，deb等人[1]确立了约束支配原则，该原则在非支配排序过程中与可行的解决办法相区别：

定义1 如果下列任何一个条件成立，则称i约束支配一个解j：

1. 解决方案i是可行的，而解决方案j不是。
2. 解决方案i和j都是不可行的，但解决方案i有一个较小的总体约束违规。
3. 解i和j是可行的，解i支配解j。

这不需要额外的约束处理程序来使用MOEAs。由于该程序是通用的，上述约束支配原则可用于任何无约束的限制MOEAs。

过去的测试问题

在多目标优化的背景下，制约因素可能阻碍多目标的EA（MOEA）收敛到真正的帕累托最优区域，也可能在维持一组不同的帕累托最优解上造成二重性。直觉告诉我们，国际能源机构能否成功地解决这两个问题，在很大程度上取决于所使用的约束处理技术。本文首先介绍了文献中常用的一些测试问题，然后讨论了开发测试问题产生器的系统步骤。Veldhuizen[13]列举了一些研究人员使用的约束测试问题。我们在这里提出了研究人员经常使用的三个问题。

Srinivas和deb[11]使用了以下函数：              

SRN: （1）
图1显示了可行的决策变量空间和帕累托最优集。帕累托最优解[11]对应于，。可行的目标空间和帕累托最优解如图2所示。

图1.用于测试问题SM的决策变量空间 图2.测试问题的客观空间

在这个问题中引入的约束唯一的二进制是，它们消除了未约束的帕累托最优集合的一部分（如图1所示的虚线）。

Tanaka[12]提出了以下两个可变问题：

TNK: （2）

可行的决策变量空间如图3所示。由于和，可行的目标空间也与可行的

图3.TNK给出了可行决策变量和目标搜索空间 图4.测试问题的最优区域

决策变量空间相同。无约束决策变量空间由平方中的所有解组成。这样，唯一无约束的帕累托最优解是。但是，包含了有限约束使得这个解决方案是不可行的。约束的帕累托最优解位于约束的边界上。由于约束函数是周期性的，而第二个约束函数也必须满足，所以并不是所有边界上的解都是帕累托最优的。断开的帕累托最优集合显示在带粗实线的区域中。由于帕累托最优解位于非线性约束面上，因此优化算法可以在整个帕累托最优面上展开求解。

Osyczka和Kundu【9】使用了以下的六个变量测试问题：

OSY : (3)

有六个约束，其中四个是线性的。由于这是一个六个变量的问题，显示可行的决策变量空间是不可接受的。然而，对约束和目标函数的仔细分析揭示了受限的帕累托最优面，如图4所示。多最优区域是五区域的串联。每个地区都处在某些制约因素的交汇点上。但对于整个帕累托最优区域，Xlowast;4=Xlowast;6=0。表1显示了每个区域的其他变量值。因为整个帕

表1.问题的最佳区域

累托-最优区域要求一个多种群保持在约束边界的不同交点上，这是一个需要解决的双重崇拜问题。                            

拟议的测试问题

虽然上面的测试问题（以及其他许多在别处讨论过的问题）在某种程度上测试了MOEA处理约束的多目标优化问题的能力，但它们有一些二元性：（一）它们有一些决策变量，（二）大多数目标函数和约束都不是足够的非线性的，（三）它们对于在约束优化中引入不同程度的复杂性是不可调节的。与可调谐无约束测试问题的情况一样，我们在这里也提出了一些可以控制约束搜索空间复杂性的测试问题。提出的测试问题是为了给多目标优化算法带来两种不同的可调性问题：

1. 靠近帕累托最优锋的难点；
2. 在整个搜索空间的难点。

我们将在下面的小节中讨论这些问题。

4.1、在帕累托-最佳战线附近的难点

在这个测试问题中，约束并不会使搜索区域的任何主要部分不可行，除非非常接近帕累托-最佳前端。约束的设计方式使得无约束的帕累托最优区域的某些部分变得不可行。这样，整个帕累托最优锋将构成无约束帕累托最优区的一部分和约束边界的一部分。在下面，我们提出了一个通用的测试问题：

  (4)

在这里，函数g(X)可以是一个复多变量函数。存在j不等式约束，参数必须以某种方式选择，使得部分无约束帕累托-最优区域是不可行的。我们描述了一个计算参数对j约束的过程：

Step 1 Set j = 0,. Also set and x = ∆.

Step 2 Calculate and .Increment x = x ∆ and j = j 1.

Step 3 If jlt;J, Go to Step 2, else Stop.

For J = 2 约束，则找到以下参数值：

图5显示了无约束的帕累托最优区域（在虚线中）和两个约束。有了这两种制约因素的存在，结果表明，原来的无约束最优区域的约三分之一现在是不可行的。受限帕累托最优区域的另外三分之二区域来自于这两个约束。

由于每个约束的约束边界的一部分现在构成帕累托最优区域，在帕累托最优解中的展

图5.有两个j=2约束的约束测试问题CTP1

需要决策变量(X)用等式符号来满足不等式约束。每个约束都是决策变量的隐式非线性函数。因此，在非线性约束边界上找到若干解决方案是不可能的。通过使用更多的约束和使用多模态或欺骗性的g函数，可以进一步提高测试问题的复杂性。

除了将相关的决策变量限制并保持在几个约束边界上外，还可能有其他的双曲线在最优边界附近。约束函数可以使得无约束的帕累托最优区域现在是不可行的，由此得到的帕累托最优集合是多个离散区域的集合。在极端情况下，帕累托最优区域可以成为一组离散解的集合。让我们先用数学的方法提出这样的函数，然后在每个例子中描述它们。

(5)

决策变量X1在[0,1]中受到限制，其他变量的边界依赖于选择的g(X)函数。约束有六个参数（,a,b,c,d,和e）。事实上，上述问题可以作为一个约束测试问题生成器，在这种情况下，具有复杂程度的约束测试问题将通过简单地调整这六个参数而演化。我们通过构造不同的测试问题来证明这一点，其中还讨论了每个参数的值。

首先，我们使用以下参数值：

=minus;0.2pi;, a =0 .2,b= 10,c=1,d=6,e=1

由此产生的可行目标空间如图6所示。从定义中可以清楚地看出，在约束存在的情况下，无约束的帕累托最优区域变得不可行。约束边界的周期性使得帕累托-最优区域不连续，具有多个互不相连的连续区域。优化算法的任务是尽可能多地找到这样的断开区域。可以通过增加参数B的值来控制断开区域的数目。还可以清楚地看到，随着断开区域数量的增加，算法将在所有断开区域中具有代表性的解。

图6.受限测试问题CTP2 图7.受限测试问题CTP3

利用d的小值可以使上述问题变得更加复杂，使得在每个断开的区域中只有一个帕累托最优解。图7显示了d=0.5和a=0.1的可行目标空间（而其他参数与以前的测试问题相同）。尽管大多数可行的搜索空间是连续的，但在帕累托最优区域附近，可行的搜索区域是断开的，最终每个次区域导致一个奇异可行的帕累托最优解决方案。

该问题通过增加参数a的值可以有不同形式的复杂性，它具有从连续的可行区域到远离帕累托最优区域的不连续可行区域的过渡的可能性。由于一个算法现在必须通过一条狭长可行的隧道来寻找隧道末端的唯一帕累托最优解，与前面的问题相比，这个问题将更加难以解决。图8显示了一个这样的问题，其参数a=0.75，其余参数与上一个测试问题相同。

图8.受限测试问题CTP4 图9.受限测试问题CTP5

在上述三个问题中，断开的区域在目标空间中平均分布。利用=1可以使离散的帕累托最优

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19661]，资料为PDF文档或Word文档，PDF文档可免费转换为Word