基于多点非均匀变异的多目标极值优化算法研究

，， ，，

(1.国网浙江瑞安市供电有限责任公司，浙江 瑞安 325000；2.浙江九宏电力工程有限公司，浙江 苍南 325802；3.温州大学 电气数字化设计技术国家地方联合工程实验室，浙江 温州 325035)

0 引言

大量的实际工程优化问题都可以描述为典型的计及多个性能指标且满足多种约束条件的多目标优化问题[1]。传统的多目标优化方法往往将多个目标函数进行加权求和，整合成单目标优化问题，而这显然是违背多目标优化的基本思想。多目标进化算法因其在解决多个矛盾目标函数优化问题时的强大处理能力，正受到越来越多的研究与关注[2-4]。目前，多目标优化算法存在的主要问题包括：如何促使算法加快或更好地逼近问题的真实的Pareto解集(True Pareto)，这就是所谓的收敛性问题；另一个问题就是如何最获得更加均匀分布的最终的Pareto解集，这就是所谓的分布性问题[1,5]。以上两个问题可以说是多目标优化算法的核心问题所在。

极值动力学优化算法(Extremal optimization,EO)作为一种新颖的优化算法[6-7]，最早由Boettcher和Percus于1999年提出，起源于统计物理领域的自组织临界(Self-organized criticality,SOC)理论和Bark-Sneppen生物演化模型(BS模型)[8]。相比于遗传算法(GA)和粒子群算法(PSO)等传统优化算法而言，EO算法具有远离平衡态的动力学特征，从操作上看就是EO算法总是选择当前的最差组员和与其有关系的组员来进行变异。所以，算法的实质操作只有变异操作而不存在交叉等操作。EO算法自提出起来，在离散优化、连续优化以及各种工程优化问题中得到了较为成功的应用[9-16]，但有关多目标EO算法的研究却十分有限[17-21]。

本文将提出一种能够解决连续多目标优化问题的基于多点非均匀变异(Multi-non-uniform mutation,MNUM)的多目标极值优化算法，该算法以下简称为MOEO-MNUM。该算法的基本思想是将采用Pareto优化的基本原理引入到极值优化算法中，即在对当前个体逐个组员变异后所产生的个体中，利用Pareto优化的概念，选取其中一个非支配来无条件取代当前个体并进行外部存档，经逐代优化后获得最终的Pareto解集供决策者使用。通过对典型连续多目标优化测试函数的仿真测试实验从而验证本文提出算法相比其它经典多目标优化算法的有效性。

1 多目标优化问题

以目标函数均为最小化问题为例，连续多目标优化问题定义如下[1]：

min{f1(x),f2(x),...,fM(x)},x= (x1,x2,...,xN)

s.t.gj(x)≥0,j= 1,2,...,J;

hk(x) = 0,k= 1,2,...,K;

xiL≤xi≤xiU

(1)

定义1(Pareto支配,Pareto Dominance)决策向量xu∈X:若Pareto支配决策向量xv∈X，记为xu

1)∀i∈{1，…，m}满足fi(xu)≤fi(xv)；

2)∃j∈{1，…，m}满足fj(xu)≤fj(xv)；

此时，也称决策向量xvPareto支配于决策向量xu。若决策向量xu与决策向量xv不存在Pareto支配关系，则称它们非支配(Non-dominated)。

定义2 (Pareto最优解,Pareto Optimality)决策向量xu∈X称为X上的Pareto最优解，当且仅当∃xv∈X使得xv

定义3 (Pareto最优解集,Pareto Optimal Set，POS)对于给定的多目标优化问题f(x)，Pareto最优解集(ρ*)定义为：ρ* ={xu∈X|∃xv∈X，xv

定义4(Pareto前沿,Pareto Front,PF))对于给定的多目标优化问题f(x)和Pareto最优解集(ρ*)，Pareto前沿(ρf*)定义为：ρf*={f(xu) |xu∈ρ*}。显然算法得到的最优Pareto解集是逼近Pareto前沿。

2 MOEO-MNUM算法设计

MOEO-MNUM算法的主要部分包括：随机产生单个个体，利用MNUM变异来更新后代，基于非支配排序的Pareto适应度评价准则和一个外部存档更新机制。我们首先给出MOEO-MNUM的主要算法流程，其后在给出流程中使用的细节模块。

2.1 主要算法流程

输入：一个连续多目标优化测试问题，MOEO-MNUM算法的可调整参数：最大迭代次数Imax、外部存档最大个数Amax和MNUM变异的参数b。

输出：MOEO-PLM算法优化后的最终Pareto解集。

步骤1：随机产生一个个体SC，并令外部存档A为空。

步骤2：通过当前个体SC逐个组员进行MNUM变异，并保持其它组员不变，产生N个子代个体{Si,i=1,2,…,N}，其中N为变量个数即组员个数。MNUM变异具体实现如下方程所示：

(2)

(3)

其中:r和r1表示0～1范围内的随机数，t表示算法运行的当前迭代次数。

步骤3：对这N个子代个体{Si,i=1,2,…,N}使用基于非支配排序的Pareto适应度评价准则进行排序。

步骤4：如果只存在一个非支配个体，令该个体为Snd；如果存在多个则随机选择一个个体作为Snd。

步骤5：启用基于拥挤度距离的外部存档更新机制Update_Achieve(Snd,Achieve)，用Snd来更新外部存档。

步骤6：将当前个体SC无条件替代为Snd。

步骤7：不断重复步骤2～7，直至满足停止条件或达到最大迭代次数。

步骤8：将外部存档作为到目前为止最优化的Pareto解集输出。

2.2 基于非支配排序的Pareto适应度评价准则

MOEO-MNUM利用Pareto支配的概念来定义变异后个体的适应度值。具体适应度赋值准则为：个体适应度值=解集中支配该个体的其他个体的个数。显然，适应度值为0的个体为解集中的非支配个体，适应度值越小该个体越优。

以两目标优化问题为例，目标函数分别为f1和f2，假设当前个体为S=(x1,x2,x3,x4,x5)，通过当前个体S逐个组员变异并保持其它组员不变的基于MNUM变异方式，产生5个子代个体，分别为SA=(xm1,x2,x3,x4,x5),SB=(x1,xm2,x3,x4,x5),SC=(x1,x2,xm3,x4,x5),SD=(x1,x2,x3,xm4,x5)和SE=(x1,x2,x3,x4,xm5)且如图1所示。由Pareto适应度评价准则知，以上5个解的Pareto适应度值分别为f(SA)=0，f(SB)=f(SC)=f(SD)=1，f(SE)=4。

图1 Pareto适应度评价准则示意图

2.3 外部存档更新机制Update_Achieve

MOEO-MNUM为了不丢失历代寻优过程中的优秀非支配解，引入外部存档更新机制来保存这些优秀个体。MOEO-MNUM的外部存档的保存的最大个数是一定的，有用户自行设置。因此，当外部存档达到最大个数时，新的个体若要进入外部存档就需要进行甄别选择，达到真正存优的目的。

假设新产生的个体为Snd，则MOEO-MNUM外部存档更新机制如下[17]：

1)如果外部存档中至少有一个体能够支配个体Snd，则个体Snd不能加入外部存档。

2)如果个体Snd能够支配外部存档中的某些个体，则将这些个体移除，并将个体Snd加入外部存档。

3)如果外部存档中的个体与个体Snd互不支配时，若外部存档个数未达到最大个数Amax，则将个体Snd加入外部存档；若外部存档个数达到最大个数Amax，则若个体Snd位于外部存档最拥挤的地方(由下面的拥挤距离准则判断得出)，则不加入外部存档；否则个体S将替代掉位于外部存档最拥挤的地方的个体而加入外部存档。

MOEO-MNUM利用由Deb等人[2]在NSGA-II中提出的拥挤距离准则来选择出外部存档中处于最拥挤的地方的个体。我们首先将新产生的个体Snd连同外部存档中的所有个体联合在一起计算每个个体的拥挤距离。需要注意的是为保护每个目标的极端值，将所在个体的拥挤距离赋值为无穷大。

3 实验测试与分析

采用国际上通用的6个经典多目标标准测试函数[2]来验证本文所设计的MOEO-MNUM算法的性能。表1列出了本文所用的测试函数SCH、ZDT1、ZDT2、ZDT3、ZDT4和ZDT6，包括测试函数的表达式、变量维数、变量界限、Pareto前沿特点。

表1 典型的连续多目标优化测试问题

利用文献[2]中的两个性能指标来衡量不同算法的性能。第一个指标是收敛性指标γ，衡量的是算法优化后得到的Pareto解集与真实Pareto解集的间的逼近程度。第二个指标是分布性指标Δ，衡量的是算法优化后得到的Pareto解集的分布均匀性。计算公式如下：

(4)

式中，df和dl是算法优化后的Pareto前沿的边界点和真实Pareto前沿的边界点的欧氏距离，而di是算法优化后的Pareto前沿中两个连续点之间的欧氏距离，dm是所有di(1,2,…,N-1)的平均值。显然一个越好的算法它的收敛性指标越小，分布性指标越小。

MOEO-MNUM算法的参数设置为Imax=6 000，Amax

=100，b=2。所有实验基于MATLAB2012b软件进行，运行环境为3.10 GHz,i5-2400的2 GB RAM的PC机，每个测试函数独立运行30次。

表2列出了MOEO-MNUM与NSGA-II[2]、PAES[22]、SPEA[23]和SPEA2[24]等经典多目标进化算法的性能比较数据，包括收敛性指标γ的平均值和方差，分布性指标Δ的平均值和方差及其两个指标的排名。为了便于读者对比分析，表格中采用粗体对获得的最好性能指标进行了标记。

从表2可以看出，在收敛性方面，尽管MOEO-MNUM在求解SCH问题时稍逊于PAES，在其它5各测试问题的性能排名第1，但综合来看MOEO-PLM在收敛性上面还是令人满意的；在分布性方面，MOEO-MNUM占据很大优势，在各个测试问题上都排名第1，体现出MOEO-MNUM的独特性能即具有优秀的分布性能。

更进一步地，MOEO-MNUM算法求解6个典型测试问题获得的最优Pareto前沿如图2所示。不难看出，针对每个测试问题，MOEO-MNUM获得的最优Pareto前沿都与真实Pareto前沿基本重合。换句话说，MOEO-MNUM算法具有求解多目标优化问题最优Pareto前沿的潜力。

表2 MOEO-MNUM与其它经典优化算法的性能比较

4 结语

图2 MOEO-MNUM求解6个典型测试问题获得的最优Pareto前沿

本文提出了一种高效解决连续多目标优化问题的基于多点非均匀变异的多目标极值优化算法，简称为MOEO-MNUM。通过对国际上通用的6个多目标标准测试函数(包括SCH、ZDT1、ZDT2、ZDT3、ZDT4和ZDT6)的仿真实验，从而验证了本文所设计的MOEO-MNUM算法相比与NSGA-II[2]、PAES[22]、SPEA[23]和SPEA2[24]等经典多目标进化算法在多样性和分布性方面都具有明显的优势。另外，本文也对比了MOEO-MNUM求解6个典型测试问题获得的最优Pareto前沿与真实Pareto前沿，更进一步地验证了MOEO-MNUM算法具有求解多目标优化问题最优Pareto前沿的潜力。

本文提出的多目标极值优化算法进一步深入研究方向包括：1)通过设计更有效的变异操作因子或引入更高效的外部存档更新机制对算法进行改进；2)将本文提出算法推广应用到复杂控制系统优化设计、智能电网多目标规划和能量管理等实际工程优化问题中。