应用精英反向学习的多目标烟花爆炸算法

谢承旺，许　雷，赵怀瑞，夏学文，魏　波

(1.华东交通大学软件学院，江西南昌 330013； 2.江西科技师范大学数学与计算机学院，江西南昌 330013；3.华东交通大学轨道交通学院，江西南昌 330013)



应用精英反向学习的多目标烟花爆炸算法

谢承旺1,2，许雷1，赵怀瑞3，夏学文1，魏波1

(1.华东交通大学软件学院，江西南昌 330013； 2.江西科技师范大学数学与计算机学院，江西南昌 330013；3.华东交通大学轨道交通学院，江西南昌 330013)

现实中的多目标优化问题越来越多，而且日益复杂.受混合多目标优化算法设计思想的启发，将烟花爆炸方法和精英反向学习机制引入至多目标优化领域，提出一种应用精英反向学习的多目标烟花爆炸算法(Multi-Objective Fireworks Optimization Algorithm Using Elite Opposition-Based Learning，MOFAEOL).该算法利用精英反向学习策略加强算法的全局搜索能力，利用烟花爆炸方法增强算法的局部搜索能力并提高求解的精度.这两种搜索机制相互协同以更好地平衡算法的全局勘探和局部开采的能力.MOFAEOL算法与另外5种代表性多目标优化算法一同在由ZDT系列和DTLZ系列组成的测试集上进行性能比较.实验表明，MOFAEOL算法在收敛性、多样性和稳定性方面均优于或部分优于其他对比算法.

烟花爆炸优化；精英反向学习；多目标优化算法

1　引言

科学研究与工程实践中存在着大量需要同时优化多个目标函数的优化问题，它们通常被称为多目标优化问题(Multi-objective Optimization Problem，MOP).MOP问题中各目标之间相互冲突，整体上一般不存在单个的最优解，而是一组Pareto解的集合.MOP问题的复杂性导致经典的数学规划方法等一般难以凑效.

有关MOP问题的研究得到了长足的发展并取得了丰富的成果，概括起来大致可分为3类：

(1)基于进化算法(Evolutionary Algorithm，EA)的多目标优化方法.其中代表性的算法包括NSGA-II[1]、SPEA2[2]、PAES[3]、PESA[4]和PESA-II[5]等.这类算法基于群体进化的方式实现了搜索的多向性和全局性，能够在一次运行中获得一组解；其次，EA算法可以处理诸如不连续、非凸以及多峰等复杂的目标函数和约束条件.

(2)基于新型进化机制的多目标优化算法.例如，基于粒子群优化(Particle Swarm Optimization，PSO)模型和新型占优机制的CMOPSO算法[6]和OMOPSO算法[7]等；基于分布估计算法提出的RM-MEDA算法[8]以及将传统的数学规划方法和进化算法相结合提出的MOEA/D算法[9]等.这些新型进化范例的引入提高了多目标优化算法解题的效率与效果，开辟了解决MOP问题的新途径.

(3)混合多目标优化算法.例如，Molina等[10]将分散搜索和禁忌搜索结合以解决非线性多目标优化问题；Soliman等[11]将协同进化与局部搜索的思想融入到多目标差分进化算法中，以指导搜索进程朝Pareto最优解逼近；谢承旺等[12]将多种不同策略融合到多目标粒子群优化算法，并在多目标基准测试实例中取得了不错的效果.这类算法一般根据算子(组件)和元启发式方法的特点有机结合，发挥多目标优化算法和元启发式方法的长处，进行优势互补，从而克服单个的多目标优化算法或元启发式方法所固有的局限性，可进一步增强算法在解空间搜索的效果.

上述不同种类的多目标优化算法虽然在解决一些MOP问题中表现出了较好的性能，也取得了不错的应用效果，但现实中的多目标优化问题正日益增多，而且也越来越复杂，迫切需要探索新的有效的进化机制应对这种局面，以更好地解决这些较难的MOP问题.

2010年，Tan等[13]通过模拟烟花爆炸中炸点的扩散机制提出了一种新颖的烟花搜索算法(Fireworks Explosion Algorithm，FEA).由于烟花弹爆炸时，释放出的火星散布在以烟花弹(炸点)为中心的一个圆形邻域内，如果将该邻域看成是问题解空间的一个局部区域，炸出的火星看成是区域中的点，则一次爆炸就类似于对局部区域的一次探索，这种探索可看作是对空间中该炸点附近的一次局部搜索.FEA算法为智能优化领域提供了新思想，注入了新活力，并引起了研究者的重视.文献[14]在原始FEA算法的基础上，对爆炸点的方向和爆炸半径等参数进行改进，提高了算法的性能.文献[15]借鉴PSO算法引入了交流算子，实现种群内个体之间的交流，引导种群向全局最优解逼近.文献[16]将遗传算法思想引入FEA中，随机选择某炸点与当前最佳炸点位置进行信息交换，增加种群的多样性，克服算法早熟收敛.文献[17]将精英反向学习机制引入至FEA算法以指导种群向全局最优解所在的空间逼近，并取得了较好的求解精度和收敛速度.然而，上述对FEA算法及其变种的研究均局限于单目标优化.2013年，Zheng等[18]将多目标烟花爆炸算法(Multi-Objective Fireworks Optimization Algorithm，MOFA)用于解决精准农业中的施肥问题，但其沿用单目标优化模式生成火星的做法值得商榷.

鉴于FEA算法基于群体的搜索以及具有执行参数较少、求解速度快和较强的局部搜索能力等优势，而且有关多目标烟花爆炸方面的研究尚不多见，因此，开展多目标烟花爆炸算法的研究具有现实意义.但也应注意到：烟花爆炸优化采用了贪婪选择的方式，随着迭代的进行，所有个体逐渐向当前最优个体靠拢，而且其爆炸半径也逐渐缩小，种群的多样性也会逐渐降低，这对于多目标优化算法是不能接受的.因为保持群体的多样性是指导搜索朝Pareto前沿逼近，克服多目标优化算法早熟收敛的重要措施.基于此，本文将精英反向学习机制(Elite Opposition-based Learning，EOL)引入至多目标烟花爆炸算法，一方面利用精英个体包含了比普通个体更多的有益搜索信息；另一方面，通过精英反向学习产生的反向解能远离局部最优区域，扩大算法在精英反向解所在区域内的搜索，增强算法的全局搜索能力，有利于算法较快收敛于全局Pareto前沿.本文提出了应用精英反向学习的多目标烟花爆炸算法(Multi-Objective Fireworks Optimization Algorithm Using Elite Opposition-based Learning，MOFAEOL)，其中的精英反向学习机制与烟花爆炸优化方法相互协同，以期更好地平衡算法的全局探索能力和局部开采能力，并能有效地解决复杂的多目标优化问题.另外，MOFAEOL算法采用改进的k-最近邻方法[2]更新外部档案以保持解群的多样性.

2　相关概念

2.1多目标优化问题

根据优化的对偶理论，只需考虑最小化问题.不失一般性，一个具有n个决策变量，m个目标函数，(p+q)个约束的MOP问题可定义为：

(1)

其中，x=(x1,x2,…,xn)T∈X⊂Rn是n维决策向量，X为n维决策空间；y=(y1,y2,…,ym)∈Y⊂Rm为m维目标空间；目标函数F(x)定义了由决策空间X向目标空间Y映射的函数，g(x)定义了p个不等式约束，h(x)定义了q个等式约束.约束函数g(x)和h(x)共同确定决策向量x的可行域.在此基础上给出几个重要的定义.

定义1(可行解集)可行解集Xf为满足式(1)中约束函数g(x)和h(x)的决策向量x的集合，即Xf={x∈X|g(x)≥0且h(x)=0}.

定义2(Pareto支配)假设x1,x2∈Xf是上述MOP问题的可行解，称x1Pareto支配x2(记为x1x2)当且仅当∀i=1,2,…,m:fi(x1)≤fi(x2)∧∃j=1,2,…,m:fj(x1)

定义4(Pareto最优解集)Pareto最优解集(ParetoSet，PS)是所有Pareto最优解的集合，即PS={x*}={x∈Xf|∃x′∈Xf:fi(x′)≤fi(x*)，i=1,2,…,m}.

定义5(Pareto前沿)Pareto前沿(ParetoFront，PF)是Pareto最优解集在目标空间中的投影，即PF={F(x)|x∈PS}.

定义6(当前种群的非劣解集NDS)假设Pop(t)为MOEA算法的第t代种群，个体x*∈Pop(t)为群体的非劣解，当且仅当∃x′∈Pop(t):x′x*.Pop(t)中所有非劣解x*组成的集合称为当前群体的非劣解集NDS，即NDS={x*}={x|x∈Pop(t)且∃x′∈Pop(t)，使x′x}.

2.2精英反向学习

Tizhoosh[19]于2005年提出了反向学习(Opposition-BasedLearning，OBL)的概念，并说明了反向解要比当前解有高近50%的概率靠近全局最优.其主要思想是通过在当前个体所在区域产生反向个体，并将反向个体与当前个体一起参与竞争，优秀个体进入下一代.

定义8(基于反向解的优化)设待优化问题为式(1)中的最小化多目标优化问题，若存在当前解X，其反向解为X′，对X和X′采用如下更新机制：①若XX′，则保留当前解X；②若X′X，则用X′替换X；③若X和X′彼此非支配，则随机选择其中某个个体保留.

多目标优化问题中的非支配解一般视为精英个体，这些个体通常包含了更多的引导种群向全局最优Pareto前沿收敛的有益信息.如果最终算法能够全局收敛，那么精英个体所形成的搜索区域必然会收敛到全局最优Pareto解集所形成的搜索区域.因此，加强精英个体所在空间邻域的搜索，将会提高算法的收敛速度，改善算法的全局收敛能力.

(2)

其中，|Pop|为当前群体的规模.

用搜索空间的动态边界代替固定边界有利于保存搜索经验，使得生成的反向解能够位于逐步缩小的搜索空间，促进算法较快收敛.由于精英反向解也可能跳出边界[ai,bi]而成为非可行解，这里采用文献[20]中的方法对越界值进行重置，如式(3)所示：

(3)

通过形成的精英反向解，可加强对精英个体邻域的探测，MOFAEOL算法在每一次迭代中，针对种群的精英个体执行反向学习，生成精英个体的反向种群，并参与进化竞争.

3　MOFAEOL算法

3.1烟花爆炸优化机制

FEA算法受烟花爆炸现象的启发，将寻优问题的搜索空间类比于烟花爆炸的空间，用炸点及其爆炸产生的火星的位置来表征优化问题的候选解.评估炸点和火星位置的优劣，并选择较优的位置保留至下一代，如此迭代进行，直至获得满意的结果或停机条件达到时为止.

基于烟花爆炸优化的搜索方式如下：首先在搜索空间中随机初始化N个炸点，即确定第一次爆炸的炸点位置，用以表征问题的初始解.例如，在n维搜索空间中的第i个炸点可表示为xi=(xi,1,xi,2,…,xi,n).炸点执行均匀爆炸操作时需预设最大爆炸半径r，即火星的最大散开区域.如果炸点爆炸层数为w，那么每一层的爆炸半径为j·r/w(j=1,2,…,w)，其中，r设置为随迭代次数的增加呈非线性递减的参数，以确保算法初期可以执行搜索空间的全局探索，算法末期能在全局最优前沿附近进行精确的局部搜索.考虑到算法在实际执行过程中由于时空资源的限制，同时也为了保证有足够的火星数目，这里规定火星与炸点之间的距离只有r/4,r/2,3r/4和r四种情况.烟花弹爆炸半径r的计算如式(4)所示，而对于炸点i，其爆炸产生的火星的迭代公式如式(5)所示.

(4)

(5)

这里在实施烟花爆炸的过程中对所有炸点和火星的位置边界进行限制，设xl(l=1,2,3,…,n)为n维搜索空间任一维决策变量，且xl∈[al,bl]，如果炸点x爆炸过程中产生的火星xj跳出边界[al,bl]成为非可行解，则将xj在第l维上的值按式(6)进行重置.

(6)

其中，rand(·)是区间[al,bl]上的均匀随机数.

3.2选择火星

这里从第二代起将当前种群中每一个个体都将视为一个炸点，这些炸点爆炸后将会产生大量的火星，这些火星与炸点一起进行评估以选择出较优的火星(炸点)参与下一次爆炸.为了保持每一代种群规模不变以及火星的多样性，这里根据文献[13]中基于距离的方法筛选出一定数目的解点.设xi∈M，M为当前炸点及其爆炸后产生火星的集合，则个体xi与M中其他个体的欧式距离之和定义为：

(7)

则xi被选中的概率p(xi)如式(8)定义：

(8)

对p(x)值按非升序排列，依次遴选排在前列的一定数目的个体.

3.3维持档案群体的多样性

MOFAEOL算法在种群外部设置一个档案集合，用于保存算法在搜索过程中获得的非支配解.这里采用渐进方法对外部档案进行维护，初始时置档案为空，对每次迭代产生的非劣解执行算法1所示的操作.

在使用渐进方法决定解个体进入档案的过程中，档案成员的多样性不断增强，而渐进方法所采用的个体密度估计方法对档案的维护和解群的多样性保持都很重要.在目前已定义的密度估计方法中，SPEA2算法的k-最近邻方法[2]在保持解群多样性方面表现突出.这里将对k-最近邻方法做一定改进后用于更新外部档案并保持解群的多样性.

若多目标优化问题的目标数目为M，采用改进的k-最近邻方法维护外部档案的时间复杂度O(M(N+N′)2log(N+N′))，其复杂度则要优于原方法的复杂度O(M(N+N′)3)[2].

3.4MOFAEOL算法流程

在前面3.1至3.3小节描述的基础上，以下给出MOFAEOL算法的流程，如算法2所示.

假设待优化MOP问题的目标数目为M，搜索空间的维度为n，种群的规模为N，外部档案最大容量为N′，算法最大迭代次数为Tmax，则MOFAEOL算法的时间复杂度可估计如下：

Step1产生初始种群的时间复杂度为O(nN)，将种群中非支配解复制到外部档案集的时间为O(MN2)，因而Step1的时间复杂度为O(MN2).

算法从Step2开始便进入迭代循环过程.

循环体内，Step3至Step5为炸点产生火星的过程，其中一个炸点产生火星的时间复杂度为O(8n2/3)，N个炸点产生火星的时间则为O(8Nn2/3).

Step6执行精英反向学习的时间复杂度为O(MN′).

Step7利用归一化排序[21]构造非支配集NDS的时间复杂度为O(M(N+N′)log(N+N′)).

Step8利用算法1对外部档案进行多样性维护的时间复杂度为O(M(N+N′)2log(N+N′)).

Step9根据距离关系选择参与下一代繁殖的个体所需的时为O(nN2).

Step10的时间复杂度为O(1).基于上述分析，循环体内的时间复杂度应为O(8Nn2/3)+O(MN′)+O(M(N+N′)log(N+N′))+O(M(N+N′)2log(N+N′))+O(nN2)+O(1)=O(M(N+N′)2log(N+N′))，而整个循环迭代过程的时间复杂度则为O(TmaxM(N+N′)2log(N+N′)).

Step12输出算法求解结果所需要的时间为O(N′n).

综上，MOFAOL算法的时间复杂度为O(MN2)+O(TmaxM(N+N′)2log(N+N′))+O(N′n)=O(TmaxM(N+N′)2log(N+N′)).

4　实验与结果分析

4.1实验设置

(1)对等比较算法

为了测试MOFAEOL算法的性能，选取5个代表性多目标优化算法作为对等比较算法，它们分别是：①Deb等提出的改进型非劣分类遗传算法NSGA-II[1]；②Zitzler等提出的改进型强度Pareto进化算法SPEA2[2]；③Coello C等提出的多目标粒子群优化算法CMOPSO[6]；④Sierra等提出的改进型多目标粒子群算法OMOPSO[7]；⑤Zhang等提出的基于分解的多目标进化算法MOEA/D[9].

(2)多目标测试问题集

测试函数由ZDT[22]和DTLZ[23]两个系列共计12个函数组成.其中，ZDT系列是5个2-目标测试问题，由ZDT1～ZDT4以及ZDT6组成.由于ZDT5是布尔函数，需要二进制编码，本文省去了该测试函数.DTLZ系列是由DTLZ1～DTLZ7组成的一个可以改变搜索变量和优化目标个数的可扩展多目标测试问题集.这里选择DTLZ系列作为3-目标优化测试问题集.

(3)实验参数

根据文献[17]的研究，MOFAEOL算法中的半径递减指数α取值为5，初始爆炸半径rinitial=a·(xi,max-xi,min)，a∈[0.05,0.3]，rend取值为10-6.文献[20]的研究结果表明，一般化系数β=1时能获得较好效果，本文的实验参数β亦取值为1.本文选取的其他5个对比算法的实验参数都按照对应的参考文献设置.

比较实验中各算法在2-目标测试问题中的种群规模均设为N=100，外部档案集合的最大容量N′=100，所有测试函数的最大评估次数均设为50000次，所有算法的最大迭代次数Tmax=500；3-目标测试问题中种群的大小均设为N=200，外部档案集合的最大容量N′=200，所有测试函数的最大评估次数均为200000次，所有算法的最大迭代次数为Tmax=2000.

为减少性能分析中随机因素的影响，每种算法在所有的测试函数上均独立运行30次.本文的仿真实验在Think Pad X200笔记本电脑上运行，电脑配置5G内存和2.4GHz双核CPU，安装Windows 7 X64操作系统，算法运用C++编程实现，并利用Matlab 2010a环境出图.

(4)性能指标

为了评估算法获得的近似Pareto前沿的收敛性和均匀性，本文采用反转世代距离(Inverted Generational Distance，IGD)作为性能评估指标[9].IGD是度量真实Pareto前沿到算法获得的近似Pareto前沿之间的距离指标.该指标值越低，表明算法获得的近似Pareto前沿的收敛性和多样性越好，越接近真实Pareto前沿.令P为真实Pareto最优解集，A是进化算法获得的近似Pareto最优解集，则IGD可根据式(9)计算：

(9)

4.2实验结果与分析

实验1通过比较6个对等多目标优化算法在12个多目标测试问题上的IGD值来考察MOFAEOL算法的性能.表1列出了各算法在12个测试实例上的IGD性能对比结果.其中IGD的均值(mean)和标准差(std.)是同一算法在同一测试问题上独立运行30次的统计结果；t-test值是本文算法与其他对等算法在同一测试问题上进行t检验时的t值；“+”、“=”和“-”表示本文算法获得的IGD值在显著性水平为5%的双尾t检验中分别优于、等于和劣于对应列的对等算法在对应行的测试问题上的显著性区分结果；“Score”表示本文算法显著优于对应列的对等算法在12个测试问题中的净胜得分，即得“+”与得“-”的测试问题个数之差(下文同).同时，采用粗体字表示所有对比算法在每一个测试问题中的最小IGD均值.

从表1可以看出，MOFAEOL算法在12个测试函数上获得了4个最优的IGD均值，NSGA-II、CMOPSO和MOEA/D各获得2个最优的IGD均值，SPEA2和OMOPSO分别获得1个最优的IGD均值.这表明MOFAEOL算法在12个测试问题中总体上具有较好的IGD性能.而在MOFAEOL未能获得最优IGD均值的那些测试问题上，本文算法所获得的IGD值与那些在同一测试函数上获得的最优的IGD均值始终处在相同的数量级上，这也反映了MOFAEOL算法与那些在某些测试问题上表现最优的对等算法相比，它们在IGD性能上的差距很小.

表1　6种对等算法在12个测试实例上的IGD性能对比结果

在表1的t-检验结果中，MOFAEOL算法对比其他5种算法的净胜得分均为正数，其中，MOFAEOL对比OMOPSO的净胜得分为10，对比NSGA-II和SPEA2的净胜得分为8，对比MOEA/D的净胜得分为6，对比CMOPSO的净胜得分为2.这表明MOFAEOL算法在所有测试问题上获得的总体IGD性能要显著优于另5种对比算法.当然，根据没有免费午餐的定理，不能期望MOFAEOL算法在每一个测试问题上都能获得最好的IGD值.

由于IGD性能指标能够同时反映算法的收敛性和多样性，因此本文算法在所有对等比较算法中获得了最好的收敛性和多样性的折中效果，说明MOFAEOL算法的精英反向学习策略和烟花爆炸方法相互协同，较好地平衡了算法的勘探与开采的进化过程.

这里给出了6种对等比较算法在12个测试函数上的排名均值和排名方差，如图2所示.

从图2可以看出，MOFAEOL算法的排名均值和排名方差确定的点位于左下角，即本文算法的排名均值和排名方差占优了其他5种对比算法，这也表明了MOFAEOL算法在所有对比算法中具有最好的准确性和稳定性.

表1和图2的实验结果反映出MOFAEOL算法总体上具有最好的多样性和收敛性.究其原因，该算法采用精英反向学习策略加强算法的全局搜索能力，利用烟花爆炸方法增强算法局部搜索能力，并利用简化的k-最近邻策略保持解群的多样性，这些策略相互协同，较好地解决了复杂MOP问题.

实验2为检验MOFAEOL算法中烟花爆炸优化方法有效性，这里将MOFAEOL算法与剔除了烟花爆炸优化方法的MOFAEOL算法(简记为MOEOL算法)一起在ZDT4、ZDT6、DTLZ1、DTLZ6和DTLZ7测试实例上进行对比实验，两算法取相同的实验参数.表2给出了MOFAEOL算法与MOEOL算法在IGD性能指标上的实验结果.

表2　MOFAEOL与MOEOL在6个测试实例上的IGD性能对比结果

从表2可以看出，MOFAEOL在6个测试问题上获得了全部最优的IGD均值，而去除烟花爆炸优化方法的MOEOL算法在6个测试问题上无一能获得最优的IGD均值.表2的t-检验结果中，MOFAEOL对比MOEOL在IGD性能上的净胜得分为6.

由此可见，采用了烟花爆炸方法的MOFAEOL算法与未使用烟花爆炸方法的MOEOL算法相比，在收敛性和多样性方面具有显著性的优势，这也表明烟花爆炸优化方法在增强算法局部搜索能力，提高解的精度方面发挥了重要的作用.实验2的结果表明了烟花爆炸优化方法是有效的.

实验3为检验MOFAEOL算法中精英反向学习机制的作用，这里将MOFAEOL算法与去除精英反向学习机制的MOFAEOL算法(简记为MOFA算法)一同在ZDT4、ZDT6、DTLZ1、DTLZ3、DTLZ6和DTLZ7测试函数上进行比较实验，两算法的执行参数取相同的值.表3给出了MOFAEOL算法与MOFA算法在IGD性能指标上的实验结果.

表3　MOFAEOL与MOFA在6个测试实例上的IGD性能对比结果

从表3可以看出，MOFAEOL算法在6个测试函数上获得了全部最优的IGD均值，而MOFA算法无一能获得最优的IGD均值.从表3的t-检验结果来看，MOFAEOL算法对比MOFA算法在IGD性能上的净胜得分为6.由此可见，采用了精英反向学习策略的MOFAEOL算法较之未使用精英反向学习方法的MOFA算法具有显著性的IGD性能优势.这也表明精英反向学习策略在防止种群陷入局部最优，促进群体在更广的区域内搜索发挥了重要的作用.实验3的结果表明了精英反向学习策略的有效性.

5　结论

为更好地解决现实中日益复杂的多目标优化问题，将精英反向学习策略和烟花爆炸优化方法引入至多目标优化算法中，提出了一种应用精英反向学习的多目标烟花爆炸算法MOFAEOL.该算法与另5种代表性多目标优化算法NSGA-II、SPEA2、OMOPSO、CMOPSO和MOEA/D一起在12个基准多目标测试函数集上进行IGD性能的比较实验，并分别就精英反向学习和烟花爆炸方法在多目标优化算法中的有效性进行了测试.实验结果表明MOFAEOL算法较之其他几种对比算法在总体上具有显著性的收敛性、多样性、准确性以及稳定性方面的优势，其中的精英反向学习和烟花爆炸方法在多目标优化算法中是有效的，二者相互协同，有利于MOFAEOL算法较好地解决一些复杂的MOP问题.

[1]Deb K,Pratap A,Agarwal S,Meyarivan T.A fast and elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[2]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm[A].Giannakoglou K,Tsahalis DT,Periaux J,Papailious KD,Fogarty T,eds.Evolutionary Methods for Design,Optimization and Control with Applications to Industrial Problems[C].Berlin:Springer-Verlag,2002.95-100.

[3]Knowles J D,Corne D W.Approximating the non-dominated front using the pareto archived evolution strategy[J].Evolutionary Computation,2000,8(2):149-172.

[4]Corne D W,Knowles J D,Oates M J.The Pareto-envelope based selection algorithm for multi-objective optimization[A].Proceedings of the 6th International Conference on Parallel Problem Solving from Nature[C].Berlin:Springer,2000:869-878.

[5]Corne D W,Jerram N R,Knowles J D,et al.PESA-II:Region-based selection in evolutionary multi-objective optimization[A].Proceedings of the Genetic and Evolutionary Computation Conference[C].San Francisco:Morgan Kaufmann Publishers,2001.283-290.

[6]Coello C A,Pulido G T,Lechuga M S.Handling multiple objectives with particles swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.

[7]Sierra M R,Coello C A.Improving PSO-based multi-objective optimization using crowding,mutation and e-dominance[A].Proceedings of 3rd International Conference on Evolutionary Multi-criterion Optimization[C].Berlin:Springer,2005.505-519.

[8]Zhang QF,Zhou AM,Jin Y.RM-MEDA:A regularity model based multi-objective estimation of distribution algorithm[J].IEEE Transactions on Evolutionary Computations,2007,12(1):1-23.

[9]Zhang QF,Li H.MOEA/D:A multi-objective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.

[10]Molina J,Laguna M,Marti R,Caballero R.SSPMO:A scatter tabu search procedure for non-linear multi-objective optimization[J].Informs Journal Computing,2007,19(1):91-100.

[11]Soliman O,Bui L T,Abbass H.A Memetic Coevolutionary Multi-Objective Differential Evolution Algorithm in Multi-Objective Memetic Algorithm[M].Berlin,Germany:Springer,2009,369-388.

[12]谢承旺,邹秀芬,夏学文,等.一种多策略融合的多目标粒子群优化算法[J].电子学报,2015,43(8):1538-1544.

XIE Cheng-wang,ZOU Xiu-fen,XIA Xue-wen,et al.A multi-objective particle swarm optimization algorithm integrating multiply strategies[J].Acta Electronica Sinica,2015,43(8):1538-1544.(in Chinese)

[13]TAN Y,ZHU Y.Fireworks algorithms for optimization[A].Proceedings of International Conference on Swarm Intelligence[C].Piscataway:IEEE Press,2010.355-364.

[14]曹炬,贾红,李婷婷.烟花爆炸优化算法[J].计算机工程与科学,2011,33(1):138-142.

CAO Ju,JIA Hong,LI Ting-ting.A fireworks explosion optimization algorithm[J].Computer Engineering & Science,2011,33(1):138-142.(in Chinese)

[15]曹炬,季艳芳.改进的烟花爆炸优化算法及其收敛性分析[J].计算机工程与科学,2012,34(1):90-93.

CAO Ju,JI Yan-fang.An improved fireworks explosion optimization algorithm and its convergence analysis[J].Computer Engineering & Science,2012,34(1):90-93.(in Chinese)

[16]曹炬,李婷婷,贾红.带有遗传算子的烟花爆炸优化算法[J].计算机工程,2010,36(23):149-151.

CAO Ju,LI Ting-ting,JIA Hong.Fireworks explosion optimization algorithm with genetic operators[J].Computer Engineering,2010,36(23):149-151.(in Chinese)

[17]王培崇,高文超,钱旭,等.应用精英反向学习的混合烟花爆炸优化算法[J].计算机应用,2014,34(10):2886-2890.

WANG Pei-chong,GAO Wen-chao,QIAN Xu,et al.Hybrid fireworks explosion algorithm using elite opposition-based learning[J].Journal of Computer Applications,2014,34(10):2886-2890.(in Chinese)

[18]Zheng Yu-Jun,Song Qin,Chen Sheng-Yong.Multi-objective fireworks optimization for variable-rate fertilization in oil crop production[J].Applied Soft Computing,2013,13(11):4253-4263.

[19]Tizhoosh H R.Opposition-based learning:A new scheme for machine intelligence[A].Proceedings of International Conference on Computational Intelligence for Modeling Control and Automation[C].USA:IEEE,2005.695-701.

[20]周新宇,吴志健,王晖,等.一种精英反向学习的粒子群优化算法[J].电子学报,2013,41(8):1647-1652.

ZHOU Xin-yu,WU Zhi-jian,WANG Hui,et al.Elite opposition-based particle swarm optimization[J].Acta Electronica Sinica,2013,41(8):1647-1652.(in Chinese)

[21]鲍培明,朱庆保.用于多目标进化的归一化排序非支配集构造方法[J].电子学报,2009,37(9):2010-2015.

BAO Pei-ming,ZHU Qing-bao.A technique of building non-dominated set based on normalized sort in evolutionary multi-objective optimization[J].Acta Electronica Sinica,2009,37(9):2010-2015.(in Chinese)

[22]Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results.Evolutionary Computation,2000,8(2):173-195.

[23]Deb K,Thiele L,Laumanns M,Zitzler E.Scalable multi-objective optimization test problems[A].Fogel DB,eds.Proceedings of the IEEE Congress on Evolutionary Computation (CEC)[C].Piscataway:IEEE Service Center,2002.825-830.

[24]Chow CK,Yuen SY.A multi-objective evolutionary algorithm that diversifies population by its density[J].IEEE Transactions on Evolutionary Computation,2012,16(2):149-172.

[25]胡旺,Yen GG,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014,25(5):1025-1050.

Hu W,Yen GG,Zhang X.Multiobjective particle swarm optimization based on Pareto entropy[J].Journal of Software,2014,25(5):1025-1050.(in Chinese)

谢承旺男，1974年10月出生，湖北武汉人，副教授、硕士生导师、中国计算机学会高级会员.2005年、2010年分别在武汉理工大学、武汉大学获得工学硕士和工学博士学位，2015年从武汉大学数学博士后流动站出站.现主要从事智能计算与智能信息处理方面的研究工作.

E-mail:chengwangxie@163.com

许雷男，1989年1月出生，湖北咸宁人，硕士研究生.主要从事智能计算方面的研究.

E-mail：13077911256@163.com

赵怀瑞男，1977年11月出生，山东临沂人，博士、讲师.2007年、2012年分别在大连交通大学、北京交通大学获得硕士和博士学位.主要从事车辆结构优化方面的研究工作.

夏学文男，1974年8月出生，湖北孝感人，博士、副教授、硕生导师.主要从事智能计算及其应用方面的研究.

魏波男，1983年1月出生，湖北天门人，博士、讲师.主要从事演化计算方面的研究.

Multi-objective Fireworks Optimization Algorithm Using Elite Opposition-Based Learning

XIE Cheng-wang1,2,XU Lei1，ZHAO Huai-rui3，XIA Xue-wen1，WEI Bo1

(1.SchoolofSoftware,EastChinaJiaotongUniversity,Nanchang,Jiangxi330013,China; 2.SchoolofMathematicsandComputerScience,JiangxiScienceandTechnologyNormalUniversity,Nanchang,Jiangxi330013,China; 3.SchoolofRailwayTracksandTransportation,EastChinaJiaotongUniversity,Nanchang,Jiangxi330013,China)

More and more complex multi-objective optimization problems have emerged in the real world.Inspired by the idea of hybrid components of multi-objective optimization algorithms,a method of fireworks explosion optimization and a strategy of elite opposition-based learning were introduced into the field of multi-objective optimization.A multi-objective fireworks optimization algorithm using elite opposition-based learning (MOFAEOL) was proposed in the paper.The MOFAEOL utilized the elite opposition-based learning strategy to strengthen the global search ability,and adopted the fireworks explosion optimization approach to improve the local search ability and the accuracy of the algorithm.These two learning mechanisms collaborated to balance the global exploration and the local exploitation,in order to solve some hard multi-objective optimization problems efficiently.The MOFAEOL was compared with other five typical multi-objective optimization algorithms on a benchmark test set including 12 multi-objective optimization test problems composed by ZDT and DTLZ series functions.Experimental results show that the MOFAEOL is superior or competitive to the other peer algorithms in convergence,diversity and stability.

fireworks explosion optimization;elite opposition-based learning;multi-objective evolutionary algorithm

2015-09-11；

2015-11-20；责任编辑：孙瑶

国家自然科学基金(No.61165004)；江西省自然科学基金(No.20114BAB201025，No.20151BAB207022)；江西省教育厅科技项目(No.GJJ12307，No.GJJ14373)

TP301

A

0372-2112 (2016)05-1180-09

电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.024