多目标群体智能算法指南

2023-11-26 理论教育版权反馈

【摘要】：鉴于此，一些研究者提出了设计多目标优化测试问题的系统方法和基本原则。为此，Deb等[20]提出了以下三种设计多目标优化测试问题集的方法:将单目标优化问题组合成多目标优化问题；采用自底向上的设计方法；对曲面进行约束设计。Deb详细阐述了构造多目标测试函数的系统方法及其特点，指出设计一个(组)测试函数的主要依据是基于多目标优化方法所期望的函数特征。

早期设计的多目标优化测试问题主要通过对单目标优化问题进行组合得到，相对比较简单，而且目标的维数不可缩放，目前已很少用于多目标优化算法的性能测试。早在1984年，Schaffer[12]引入了两个单决策变量的测试问题SCH1和SCH2。1990年，Kursawe[13]提出测试问题KUR，它的决策变量数目是可以缩放的。1996年，Viennet[14]提出测试问题VNT，该问题包含三个目标，有一个离散的Pareto前沿。1998年，Fonseca和Fleming[15]提出测试问题FON。由于这些测试问题比较简单，当现有的算法都能有效地解决它们时，使用它们就无法有效地区分算法的性能，而且有些问题的Pareto前沿是未知的，这样就不利于对算法的收敛性能进行精确的度量。

鉴于此，一些研究者提出了设计多目标优化测试问题的系统方法和基本原则。比如，1996年，Whitley等[16]提出多目标优化问题测试集的设计准则:

测试问题必须是简单的搜索方法无法解决或者不易解决的；

测试集中应该包括非线性耦合和非对称的问题；

测试集中应该包括规模可缩放的问题；

一些测试问题的评价代价应该具有可伸缩性；

测试问题的表达形式应该规范。

1999年，Deb[17]阐述了构建多目标优化测试问题的系统方法。该方法使用决策变量不重叠的函数来构造目标函数，从而可以控制收敛到最优解的难度以及在最优前沿上分布均匀的难度。他的方法可以用式(3.1)表示如下:

其中，函数f1是关于m(m<n)个决策变量的目标函数，f2是关于所有n个决策变量的目标函数，函数g是关于(n-m)个决策变量的函数，而这n-m个决策变量是未在函数f中出现的，函数h是关于f和g的函数。规定f、g必须满足f>0，g>0。

Deb[18]指出，函数f、g、h在测试多目标进化优化方法时具有如下作用:

函数f:用于控制Pareto最优解集中解点在最优前沿上的均匀分布情况。

函数g:控制多目标优化问题解的特征，是“多重最优前沿”还是单独的一个最优前沿。

函数h:控制Pareto最优前沿的特征，比如是凸的、凹的，抑或不连续等。

虽然函数g和h关于决策变量不能重叠的独立性限制了基因型的特征，但是这也使得构造包含多种特征的“表现型”函数变得容易。这里说指的特征包括图形呈曲线或曲面、凸的、凹的、连续的、离散的、不相交的、规模可变的和其他特征等。研究者可根据所需要的特征来构造不同的测试函数集。通过如非线性映射来构造出PFtrue的结构以及所期望的不同密度的PFknown。这样，就可以在构造好的多目标测试问题集上对多目标进化优化方法进行性能比较，如收敛性、分布性等。

通过上述的方法，Zitzler、Deb和Thiele[1]设计了一组多目标测试问题ZDT系列，这组测试问题的目标都只有两个，但是它们的决策变量的数目是可以缩放的，它们的Pareto最优前沿的表达形式是已知的，这样就可以方便准确地衡量算法的性能。而且由于它们在决策空间或者目标空间上具有不同的特征，难度会有所不同，很多的多目标优化算法都用该测试集来检验算法的性能。

Deb等[19]认为，一个能够充分检测多目标进化优化方法各方面能力的测试集应该包含以下特征:(www.chuimin.cn)

测试问题应该容易构造；

测试函数的决策变量和目标函数的个数应该是可以缩放的；

测试问题的Pareto最优前沿应该是易于理解的，其具体的形态和位置应该是已知的；

测试集必须能够提供可控的障碍以阻止收到真实的Pareto最优前沿和发现分布宽度广且均匀的Pareto最优解集。

按照上述的特征要求，如果只使用ZDT系列测试集来检验算法的性能显然是不够的。为此，Deb等[20]提出了以下三种设计多目标优化测试问题集的方法:

将单目标优化问题组合成多目标优化问题；

采用自底向上的设计方法；

对曲面进行约束设计。

Deb详细阐述了构造多目标测试函数的系统方法及其特点，指出设计一个(组)测试函数的主要依据是基于多目标优化方法所期望的函数特征。

Deb给出了两个基本的定义，即局部Pareto最优解(集)和全局Pareto最优解(集)。其中，全局Pareto最优解(集)即为Ptrue；利用这个术语也比较容易地得出局部Pareto最优解的定义，即Plocal。应该注意的是，Plocal是一个容易引起混淆的定义，以下是Deb给出的局部Pareto最优解(集)的定义。

局部Pareto最优解(集):给出Pareto最优解集P，对于∀x∈P¬∃x′:‖x′-x‖∞≤ε其中，ε是一个极小的正数(一般来说来，x′是对x进行很小的扰动而得到的)，并且F(x)≤F(x′)，那么P中的解构成了一个局部Pareto最优解集。

这个定义指出，对于已给出的Pareto最优解集中的每个解进行较小的扰动，并不会产生新的非支配解。Deb给出这个定义的用意在于指明PFlocal一般处于与其相关的PFtrue“之后”。从理论上说，任意一个Plocal的存在都与ε的取值有关，太大的ε将难以产生Plocal，而太小的ε将导致多重局部最优前沿。Deb也将这一概念扩展到多重最优前沿、欺骗问题、仅有一个最优解和带有噪声的多目标优化问题领域中。

一个潜在的问题是，使连续函数(或解空间)离散化，其结果的映射可能并没有反映出问题的真实性，因为离散的过程可能会导致发生“错误”。此外，均匀决策变量空间的离散化并不一定产生到目标空间的均匀映射。一般而言，在各种不同的多目标问题领域进行分析和比较多目标进化优化方法的性能时，不能轻易地得出结论，因为不同的多目标进化优化方法(包括参数和进化算子)会产生不同的表现效果[11]。

2006年，Huband等[21]对当时几种流行的测试问题集进行了总结和分析，并提出了一个可扩展的WFG测试问题工具包。该工具包不仅提供了多种问题特性(如欺骗、偏转、多模等)函数，还提供了一组包含多种几何结构的形状函数，研究者可以利用这些工具函数通过一种自底向上的方式构造具备多种特性、难度可控的测试问题。

多目标群体智能算法指南

相关推荐