基于指标的多目标局部搜索_multiobjective function optimization using nondomi

基于指标的多目标局部搜索

【注：个人博客地址转移至：点此跳转】
【注：个人博客地址转移至：点此跳转】
【注：个人博客地址转移至：点此跳转】

参考文献
《M. Basseur and E. K. Burke，Indicator-Based Multi-Objective Local Search》

要点

提出了一种简单通用的基于指标的多目标局部搜索方法。优化目标是根据定义选择算子的二元指标来定义的。本文提出的方法是为了易于适应和尽可能与参数无关而定义的。

一、介绍

本文把基于指标的选择原理推广到多目标局部搜索。决策者将定义一个二元指标，用于定义哪个邻居好，哪个不好。然后，提出了一个简单通用的基于指标的多目标局部搜索(IBMOLS)，它可以很容易地适应决策者的偏好。

为什么说IBMOLS简单通用？(1)提出的算法只有几个参数；(2)不需要多样性保护机制，种群的多样性应该通过决策者定义的二元指标来控制和优化；(3)局部搜索处理固定的种群规模，这使得它能够在一次运行中找到多个非支配解，而没有任何专用于在多目标局部搜索期间控制非支配解的数量的特定机制。

二、基于指标的优化

如果R表示帕累托最优解集(或任何其他参考集)，则总体优化目标可以表述为

（1）

其中M(X)是目标向量集的空间。由于R是固定的，I实际上代表一元函数，它给每个帕累托集近似赋值一个实数；数字越小，近似值越好。

首先建议使用以下两个指标:ε指标(Iε)和超体积指标(IHD)。

（2）

（3）

Iε(x1，x2)，x1∈ X和x2∈ X，表示执行x1的最小平移，以使其支配x2。

H(x1)表示由x1支配的空间体积。IHD(x1，x2)代表由x2支配但不由x1支配的空间体积。

为了根据总体P和二元指标I评估解的质量，可以定义几种不同的方法：

（4）

（5）

（6）

为了被认为是帕累托支配概念的自然延伸，所定义的指标必须符合帕累托支配关系。

Bentley和Wakefield提出的排名方法近似对应于等式（7）中定义的二元指标。在这个等式中，只保留了Bentley和Wakefield提出的原始方法中的帕累托支配关系部分，因为本文的一个目标是评估Iε和IHD。通过使用指标值的相加组合，得到方程（8），其近似对应于Bentley和Wakefield的排名方法。《P . J. Bentley and J. P . Wakefield. Finding acceptable solutions in the pareto-optimal range using multiobjective genetic algorithms. Soft Computing in Engineering Design and Manufacturing, 5:231–340, 1997.》

（7）

（8）

Fonseca和Flemming的排序方法(等式（9）和（10）)可以以相同的方式进行调整，我们获得了与原始的排序方法类似的公式。《C. M. Fonseca and P . J. Flemming. Genetic algorithms for multiobjective optimization: Formulation discussion and generalization. In Fifth International Conference on Genetic Algorithms (ICGA’93), pages 416–423, San Mateo, USA, 1993.》

（9）

（10）

最后，由Srinivas和Deb在NSGA-II中提出的众所周知的排序方法由方程（11）和（12）描述。让我们注意这个指标使用的是最小组合方法，我们认为x1的适应度是已知的。《N. Srinivas and K. Deb. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 2(3):221–248, 1994.》

（11）

（12）

我们将应用所有这些指标作为IBMOLS算法的选择操作符。

三、IBMOLS

A、算法描述

局部搜索方法通常以迭代的方式使用，以增加找到好的局部最优解的机会。迭代局部搜索算法意味着对每个局部搜索使用一个解初始化函数。算法2中概述的整个执行过程如下：维护一个帕累托近似集PO，并用IBMOLS找到的解实现。每次局部搜索后，都会为下一次IBMOLS执行创建一个新的初始种群。

B、参数

为了设计一个通用的元启发式算法，必须尽可能减少对所处理问题敏感的参数数量。IBMOLS算法仅由三个必须固定的主要参数定义，在搜索过程中动态定义或根据所考虑的实例进行修正。这些参数是种群大小、二元指标和种群初始化函数。