一种改进的高维多目标调和进化算法

易高明,张永闯, 施武祖，赵 彬

(1.桂林航天工业学院 a.理学院;b.管理学院， 广西 桂林 541000;2.兰州工业学院 计算机与人工智能学院，甘肃 兰州 730050；3.天津师范大学 计算机与信息工程学院，天津 300380)

多目标进化方法可以有效求解2-3个目标的低维多目标优化问题(MOPs)[1]，当目标的维数(个数)超过3的时候，多目标优化问题转化为它的特殊形式，即高维多目标优化问题(LMOPs)[2]。LMOPs的定义虽然只是形式上增加了目标的个数，但是其计算的难度要远高于3个目标及以下的低维多目标优化问题，主要体现在目标优化问题的搜索空间急剧扩大和严格的Pareto占优机制下的精英选择策略失效[3]，从而导致难以对进化个体施加足够强的选择压力。收敛性不足且解集的分布性难以维护，进化种群中的Pareto非劣进化个体所占比例急剧上升，造成进化搜索的盲目和停滞不前[4]。

为了解决高维多目标优化的问题，国内外专家提出了以进化融合为标志的第三代高维多目标进化方法，如r支配[5]、模糊支配[6]、融入决策者偏好的支配[7]、K支配[8]和ε支配[9]等，以及降维法来提高进化个体的精英选择策略[10]，以上方法在求解高维多目标问题上仍然存在一定的不足，如降维法可能导致目标关键信息的丢失，从而不能达到真实的前沿面。

基于以上分析，本文将决策理论中的调和模型应用到多目标遗传算法中，替换Pareto占优关系，利用ELECTRE-I来产生进化个体的优劣偏好排序集并辅以双极偏好占优的策略，将该方法嵌入NSGA-II中，并用来求解典型高维多目标问题，与四个优秀的高维多目标进化方法做比对实验，实验仿真结果表明本文方法的有效性。

1 问题描述

高维多目标优化问题一般蕴含n个决策变量，不低于3个目标以及若干约束组成，其中x表示决策向量，y表示目标向量，X表示决策空间集合，Y表示目标空间集合。高维多目标问题数学模型表达式如下[11]，即

miny=F(x)=(f1(x),f2(x),...,fk(x))T,

s.te(x)=(e1(x),e2(x),...,em(x))≥0,

x=(x1,x2,...,xn)∈X,

y=(y1,y2,...,yk)∈Y.

(1)

定义1:(Pareto支配)xu=(u1,u2,…,un)，Pareto支配xv=(v1,v2,…,vn)：xu≻xv，当且仅当∀i=1,2,…,k，fi(xv)≥fi(xu)且∃j=1,2,…,k，有fj(xv)>fj(xu)。

定义2:(Pareto最优解集)，若P*∈{x∈X|┐∃x*∈X,x*≻x}，则P*即为Pareto最优解集。

定义3:(Pareto前沿)Pareto最优解对应的所有目标函数值的全体集合即为Pareto前沿，记为PF*={F(x)|x∈P*}。

2 调和模型

ELECTRE(Elimination et Choice Translating Reality，淘汰选择法)是多属性决策理论中的一种经典方法[12]，自法国人Roy在20世纪60年代提出以来，在决策科学领域得到成功使用。在之后的几十年，随着后继的研究者们将ELECTRE法不断地发展和改进，形成了处理不同功能的ELECTRE家族系列。ELECTRE法虽然在多属性决策领域取得了广泛的应用，但是很少将该方法应用在高维多目标进化优化中。

2.1 ELECTRE-I法

基本思想是决策者采用某种预先设定的偏好排序策略对决策方案集中的各个方案进行级别关系的排序和比较检验[13]，不断删除级别低的或者处于劣势的方案，让决策人从剩下的优势方案中挑选出级别高的优势方案，本质上是决策人在1组非劣解集中的偏好排序过程，而且这种排序策略是一种比Pareto策略更松弛的高级别关系排序方法。在实际的高维多目标进化算法操作中，每个遗传个体的分目标个数都超过了3(3个以上的属性值)，传统的基于Pareto选择优势个体的策略难以进行比较操作，针对高维多目标优化问题中的各个子目标都难以服从绝对优于关系的情况，现介绍一种经典的多属性决策模型方法ELECTRE-I法，主要分为级别高于关系的构造和优势方案集的挖掘[14]。

2.1.1 级别高于关系的构造

首先设立决策矩阵P=(fj(ai))m×n，对方案集中的任意一对方案ai,ak，不作规范化操作。为了检验方案间的级别高于关系的存在性，需要作和谐性以及非不和谐性两种检验，详细步骤如下：

步骤1：决策人为方案的所有属性分配权重w,w=(w1,w2,…wn)。

步骤2：属性序号分类。

为了便于统一说明，这里假定每个属性fj，j=1,…,n,属性取值越大则越优。

对于某个属性j有ai绝对优于ak，并记为ai≻jak；令ai≻jak所对应的属性j的集合表示为J+(ai,ak)，数学集合为：

J+(ai,ak)={j|1≤j≤n,fj(ai)>fj(ak)}

(2)

与之相似，同样可以定义符合ai～jak对应的属性集合J=(ai,ak)以及aijak对应的属性集合,有

J=(ai,ak)={j|1≤j≤n,fj(ai)=fj(ak)}，

(3)

J-(ai,ak)={j|1≤j≤n,fj(ai)

(4)

计算和谐性指数,

(5)

式中：Iik表示方案ai不劣于方案ak所对应的属性的权重和。

(6)

(7)

步骤4：非不和谐性检验。定义不和谐性指数

(8)

通过非不和谐性检验当且仅当βik≤β0，其中β0是最大不和谐值，一般情况下应由决策者给出，在这里约定最大不和谐性指数取不和谐性指数的均值。

(9)

2.1.2 优势方案集的挖掘

在给出所有方案间的级别高于关系后，下一步的关键就是利用第一步的级别高于关系信息的优势，对方案集的优势集进行挖掘以获得一组符合决策者偏好的调和解集。具体的思路是在已经构建的每对方案的级别高于关系的基础上，建立指向图来完成。筛选的步骤如下：

步骤1：若某个方案(指向图上的节点)位于有向弧的箭线终点，且该有向弧又不是某个闭环回路的一环，那么该节点即为相对应整个目标集中的至少一个，是级别高于关系里劣的一方，也是首先删除的对象方案。

步骤2：指向图中若是存在闭合回路，则该回路中的全部节点方案都应该是无差异的。

步骤3：在以上基础上，删除掉箭线所指的方案和所有闭合回路上的最少一个方案，于是剩下的没有被删除的子方案集则为最小优势子集，记为A1，使得

∀ai∈AA1,∃ak∈A1akSai.

(10)

若A1集合中不存在级别高于关系，即在有向图中节点之间没有箭线连接，那么该最小优势子集又称作方案集A的核，记为A0，且有A0⊆A1。在得到最小优势子集或者核后，如果它已经足够小，能让决策者可以简易的从中挑选出自己满意的解方案，则ELECTRE-I法完成，否则，决策者可以根据偏好需要，动态调整最低和谐值a和最大不和谐值β0来重新构造一个更强的级别高于关系，进一步压缩最小优势集中的方案个数，供决策者决策时使用。

2.2 TOPSIS法

TOPSIS是一种不断收敛到理想解的排序法，该方法借用决策理论中的绝对理想解和绝对最差解的概念来对目标进行排序操作。其中绝对理想解的目标向量的各个子属性目标值是该属性目标中的最好值，也就是说，绝对理想解是所有子目标的最优值综合得到的。而绝对最差解的每个子目标都是来源于最劣的子目标值。TOPSIS的基本思想是建立在上述两个虚拟解、理想解和最差解定义的欧式距离关系上，一般认为最好的方案都有这样一个特征：逼近绝对理想解的同时远离绝对最差解。因此依据这样的思想，来给出方案的优劣排序，TOPSIS评价指数量化了该方案的优劣性，又称作排队值，排队值越大，方案越优。综合评价指数如式(11),即

(11)

(12)

TOPSIS法的个体排序规则如图1所示，图中的理想解即为绝对理想解，厌恶解就是绝对最差解，图中最优前沿面的最优点一定符合这样的一个特征：靠近理想解的同时远离厌恶解，此时最优点的综合评价指数也就相对较大。

图1 TOPSIS法对进化个体的排序

3 进化个体的适应值评价

本文设计一种全新的基于ELECTRE-I法的高维多目标调和进化算法的进化个体优劣排序规则，规则分为3层：第1层为Pareto非劣分层操作，第2层为级别高于关系的优势子集生成操作，第3层为双极偏好占优的排序操作和拥挤距离机制的优势子集内进化个体排序操作。在高维问题上定义一种全新的锦标赛选择算子ELET-Dominznce。

定义4:(ELET-Dominance)决策目标空间中任意的2个决策向量X，Y，有X个体 ELET-Dominance支配个体Y，当且仅当满足如下条件之一：①X支配Y;②X，Y互不支配且都属于优势子集Q，Xd>Yd;③X，Y互不支配且X属于优势子集，Y不属于优势子集;④X，Y互不支配且都不属于优势子集Q，CX>CY。其中Q是ELECTRE-I生成的优势子集，Xd,Yd是决策向量X,Y的拥挤度，CX,CY是决策向量X,Y综合评价指数。

该锦标赛选择算子1遵循传统的严格的帕累托支配策略。算子2、3和4给出了互不支配个体下的比较策略，当这两个个体同属一个优势子集下，则依据拥挤度来进一步判断优劣。相反，如果都不在优势子集中，则需要采用排队值进行判别。

4 基于ELECTRE-I的高维多目标调和进化方法

采用一种新的调和模型和多目标群体的进化思想互相结合的方法，由于高维中出现进化群体的维数灾难现象，提出一种全新的锦标赛选择算子ELET-Dominance算子，本算子包含2个关键技术：ELECTRE-I生成调和集的策略与双极偏好占优的策略。其中ELECTRE-I法是宽松的排序技术，借助ELECTRE-I法，决策者可以发现若干个相对不那么差的个体集合，并且定义了这种锦标赛选择算子下的各个进化个体的优劣比较，最后实现所有进化个体的排序并且在NSGA-II方法框架下实施遗传操作，最后逼近满意解，具体步骤及流程如图2所示。

5 实验仿真及结果分析

为了验证本文提出的基于ELECTRE-I的优化方法，我们将该方法与4个目前比较流行的多目标进化优化算法做比较，它们分别是NSGA-II、NSGA-III、α-NSGA-II和HV-NSGA-II。通过求解4个DTLZ的高维多目标测试集函数，来进行横向与纵向的不同维度比较，计算机配置条件为Core i5，内存4GB。初始群体试验设置为100，设置迭代次数上限为250代。

图2 本文算法流程

5.1 实验参数及性能指标

本实验中遗传算子的交叉概率为0.9，变异概率为1/n。

5.2 仿真结果与分析

在进行DTLZ系列的高维测试集实验分析前，先看基于ELECTRE-I的多目标调和进化算法在处理3目标DTLZ1和2目标ZDT3的实验结果，如图3、4所示。黑色实心为最终进化个体解。

图3 DTLZ1仿真

从仿真结果可以看到，不管是2目标问题还是3目标测试问题，本文提出的方法都可以让1组初始群体收敛到目标函数的真实Pareto前沿面，而且可以保持较好的分布性和延展度，该实验可以验证本文提出的方法在低维多目标上同样具有很好的收敛性。

图4 ZDT3仿真

由于高维多目标问题难以可视化，为了更直观的表现出本算法较其它4类方法性能优势，图5给出每种多目标进化方法在8目标DTLZ系列函数上的反世代距离IGD值的箱图。从图5的4组箱图可以看出，本文方法和NSGA-III在8目标的DTLZ系列问题上都表现出了比其它3种方法更显著的收敛和分布性能。此外，在DTLZ2系列问题上，NSGA-III的进化表现能力也比较突出，但是综合几个测试函数的最终结果来看，本文方法提出的算法较其他方法具有更强的稳定性。

图6给出了5类多目标进化方法处理8目标DTLZ测试问题的反世代距离值,从多目标进化代数的变化情况可以发现，无论在哪一个DTLZ系列的测试问题，本文提出的方法和NSGA-III法都随着进化迭代次数的增加，可以获得较小的IGD值，即较好的进化解和表现出更好的收敛性能。本文方法在DTLZ1、DTLZ3和DTLZ7上表现出最好的收敛性能，而NSGA-III只在DTLZ2问题上表现出比本文方法稍微好点的性能。此外，α-NSGA-II在DTLZ1上也表现出一定程度上的收敛能力，但是在其他3个测试函数上，并没有显示出较好的收敛能力，在DTLZ7上甚至是表现最差的一种方法。HV-NSGA-II在DTLZ1和DTLZ3上的IGD进化能力表现最差，但是在DTLZ7问题上也显现出一定的进化能力，在DTLZ2问题上，HV-NSGA-II和α-NSGA-II的IGD进化能力比较接近。整体而言，本文方法获得反世代距离的能力是最稳定的也是最好的。

(a) DTLZ1法

(b) DTLZ2法

(c) DTLZ3法

(d) DTLZ7法图5 8目标的DTLZ测试函数IGD箱图

(a) DTLZ1法

(b) DTLZ2法

(c) DTLZ3法

(d) DTLZ7法图6 8目标的DTLZ测试函数IGD折线

6 结语

针对高维多目标优化问题中Pareto支配失效的难题，本文提出了一种基于ELECTRE-I的多目标调和进化算法。通过引入多目标决策理论中的调和模型和ELECTRE-I法，重新定义进化个体中的优劣排序规则，在非优势子集中采用TOPSIS法进行同一层非劣个体的比较。在以上工作的基础上，提出一种新的锦标赛选择算子，最后在高维多目标问题DTLZ上进行进化仿真实验，并运用性能指标反世代距离评价进化解的质量，结果表明本文算法可以求得一组收敛性良好且延展度较大的解集。