黄辉先，胡 拚，丁 灿，张广炎，刘嘉婷

湘潭大学 信息工程学院，湖南 湘潭 411100

1 引言

受烟花在夜空爆炸这一自然现象启发，Tan和Zhu于2010年提出烟花算法[1-2（]fireworks algorithm,FA），FA主要由爆炸算子、变异算子和选择算子三大部分组成，主要应用在单目标优化问题中，其具有良好的局部搜索能力和全局搜索能力调节机制，逐渐受到研究者的广泛关注。近几年，许多研究者为提高它的性能进行了很多改进。Zheng等对基本烟花算法的爆炸算子、变异算子、选择算子和映射规则进行了详细的分析，针对其存在的缺陷进行了改进，提出增强型烟花算法[3（]enhanced fireworks algorithm,EFWA）。Li等在EFWA基础上，依据当前种群最优个体与特殊个体间的距离自适应调节爆炸半径，提出了自适应烟花算法[4（]adaptive fireworks algorithm,AFWA），大大提升了烟花算法性能。文献[5]在AFWA基础上提出一种基于最优烟火更新信息引导的自适应单目标烟花算法，并取得很好的实验效果。差分进化算法[6（]differential evolution,DE）是Storn和Price提出用于解决各种复杂优化问题的群体智能算法，文献[7]将烟花算法与差分进化两种算法的优良性能结合，提出一种新型混合算法（hybrid fireworks optimization method with differential evolution operators,FWA-DE）。

在实际优化问题中，绝大多数都是多目标优化问题（multi-objective optimization problems，MOPs），而传统的FA和DE都不能直接应用在求解MOPs，基于DE的各种优良特性，许多学者将DE进行扩展。Li和Zhang提出一种基于分解的多目标差分进化算法[8]；Rakshit和Konar提出一种含噪多目标差分算法[9]；为解决电力系统最优潮流问题，Abaci和Yamacli提出一种差分搜索算法[10（]differential search algorithm,DSA）。Zheng等使用SPEA-II[11（]strength pareto evolutionary algorithm II）算法中适应度的计算方法，在FWA-DE的基础上首次提出多目标烟花算法[12]（multiobjective fireworks optimization,MOFOA），并将其应用到油料作物生产实践中。但MOFOA中采用标准的FA，处于Pareto前沿烟花的爆炸半径将接近零，导致大量资源浪费。其次由于映射规则和高斯变异算法的本身缺陷，使得大量火花自主地映射到原点附近，造成搜索资源浪费，各烟花个体间缺乏信息交流，导致大量有用信息流失。

为解决上述问题，加快算法的收敛速度，提高分布性和逼近性，本文提出一种基于粒子进化信息引导的自适应多目标烟花差分混合进化算法（multiobjective hybrid optimization algorithm of fireworks and differentialguided by evolution information,MOHFWDE）。利用Pareto前沿粒子进化信息，引导种群下一代进化方向，加快种群收敛速度，受AFWA启示，该算法使用多目标自适应策略，动态调整爆炸半径及火花数目，引入最小半径检测机制，替换相应映射方式，将高斯变异算子改为差分变异算子和差分交叉算子，增强粒子间信息交流，并与其他3种算法进行了对比实验。

2 多目标烟花算法爆炸机制

在烟花爆炸时，质量好的烟花会在以其为中心的附近区域均匀释放大量火花，而质量差的烟花往往释放的火花数量少且分散。在单目标烟花算法中，质量好的烟花意味着它更有可能接近最优解，因而在其附近释放更多火花。相反，质量差的烟花往往离最优解较远，此时的爆炸半径应该取得更大。因此，在FA中，相对质量差的烟花，质量好的烟花会产生更多火花，且其爆炸半径相对较小，其爆炸半径计算如下：

爆炸火花数目计算如下：

式中，常数m控制着种群火花释放总数，ymax为种群中最大目标函数值。

为避免处于当前Pareto前沿个体爆炸半径过小，造成资源浪费，设定阈值爆炸半径和阈值火花数，如式（3）、式（4）。

式中，Ainit为初始最小半径，Afinal为终止最小半径，gen为终止进化代数，t为当前进化代数。

为保证超出搜索空间维度坐标映射的任意性，按式（6）对超出搜索空间火花维度坐标xm进行映射。式中xm,min、xm,max分别为第m维上的最小值、最大值。烟花释放火花分布如算法1所示。

算法1火花分布

在多目标算法NSGA-II[13]中使用非支配排序准则选择子代，通过非支配排序，每个个体i都会得到两个属性：非支配等级irank和拥挤度idistance。为适用多目标优化问题，MOHFWDE爆炸算子中的爆炸半径和火花数目不再使用单一的目标函数值计算，转而采用一种结合个体在种群中非支配等级和拥挤度的计算方式。非支配等级靠前的烟花意味着其各目标适应度均优于其他个体，拥挤度大的烟花意味着其在相同支配等级下分布于更稀疏的区域。这些位置上的烟花质量优于其他烟花，故在这些烟花上分配更多的搜索资源，使得群体朝着理想Pareto最优解集和分布稀疏的方向进化。

MOHFWDE初始化后，具体的爆炸半径和火花数目计算如下：对于拥挤度不为无穷大的个体，如果当前种群所有个体具有相同的非支配等级，即所有个体非支配等级都处于第一级，则依据拥挤度计算爆炸半径和火花数目，否则需结合非支配等级与拥挤度进行计算，如式（7）、式（8）。

对于拥挤度为无穷大的个体，如果非支配等级处于第一级，则爆炸半径设置为当代最小爆炸半径，火花数目设置为当代最大火花数目。否则将爆炸半径设置为上一级个体的最大爆炸半径，火花数目设置为上一级个体最小火花数目，如式（9）、式（10）。

式中，H={j|jrank=irank-1}为支配个体i的上一非支配级个体编号集合。

3 进化信息引导的多目标烟花差分算法

3.1 改进的多目标烟花算法

基于排序机制，算法进化过程中，选择出的新烟花子代与父代相应维度坐标一定存在不同，两代烟花不同维度距离通常不相等，因而在进化过程中，烟火每个维度呈现不同趋向最优解的趋势，对于那些坐标不发生改变的维度，可以认为解在该维度上已经到达一个相对较好的位置，在坐标发生改变的维度方向上加强搜索力度，使其获得更多的搜索资源，算法将更有可能找到最优解，加快寻优速度，为更好地描述，称这个方向为进化更新方向。根据上述分析，在以下三方面进行改进：

（1）拓展在进化更新方向上的爆炸半径。

假设第t-1代烟花数目为N，分别在N个烟花位置按相应的爆炸半径和火花数目释放烟花产生子代Pt，对父、子代进行一次非支配排序。对于处于当前Pareto前沿每个个体，如果仍然是原来的烟花炸点（ 即算法没有产生更优个体），则按式（7）～（10）计算爆炸半径和火花数目，每个维度按相同半径释放烟花，否则，利用最优火花在某些维度上的坐标变更信息，确定进化更新方向，把烟花爆炸范围由原来的规则圆形向进化更新方向拉伸，使得烟花在每个维度上都有其相应的爆炸范围，其爆炸半径大小rmt,i由式（11）、式（12）确定。

（2）增加在进化更新方向上的爆炸火花数目。

通过上述分析，最优解将更有可能分布在进化更新方向上，故增加在进化更新方向上的爆炸火花数目，可使算法更快地向真实Pareto前沿靠拢。需要注意的是，最优解并不一定就在进化更新的方向，如果过多地在进化更新方向分配资源，算法可能会陷入局部最优点，因此设置扩增概率η，使得火花以概率η直接设置在进化更新方向上，以1-η的概率随机设置，具体方法参照算法2。

算法2非支配解集的火花分布

（3）增加进化烟花的爆炸火花数目。

对所有未发生坐标更新和支配解仍按算法1释放火花。为加强取得更优解烟花的搜索能力，同时满足最大火花数目smax的限制，引入大于1的加强因子ω，如果父代烟花被子代烟花支配，则依式（13）计算子代烟花的火花数目。

在其他方向上，扩增因子减少了这些方向的爆炸火花数，增加了算法陷入局部最优解的可能性，但加强因子使得烟火爆炸出更多火花，弥补了这些方向的火花丧失，避免算法陷入局部最优，同时爆炸半径的压缩，使得算法可以更加细致地在这些方向进行局部搜索，提高算法收敛精度。

针对上述三方面的改进，图1给出了两维有无引导机制的爆炸示意图。无引导机制爆炸中，烟花根据式（7）、式（8）得到的爆炸半径和火花数目，在以其为圆心的圆形范围内均匀随机释放火花。烟花引导机制爆炸相对无引导机制爆炸会释放更多爆炸火花，在进化更新方向上，爆炸幅度相对较大，火花数目更多，使算法更有可能找到更优解，收敛速度得到提高，其他方向爆炸幅度相对较小，搜索更为细致，使算法具备更好的收敛精度。

Fig.1 Exploding schematic with and without guidance图1 有无引导机制爆炸示意图

3.2 多目标烟花算法与差分算法的混合

在烟花算法中，各个烟花分别在其炸点释放火花，各个烟花之间缺乏信息交流机制，烟花群体中有用信息没有得到充分利用，因此在种群中建立一种信息交流机制，成为提高算法搜索效率的有效方法。差分算法作为一种结构简单、鲁棒性强、可调参数少的启发式智能搜索算法，其使用差分算子，利用不同个体各维度信息形成差分矢量，再使用交叉算子使得差分矢量各维度值按一定概率加载在另一个不同个体上，这为个体优秀维度信息在种群传播提供了途径。因此MOHFWDE依据拥挤度由高到低依次从精英存档集合中选取前NI个个体、每个目标适应值前NI个个体以及当前烟花群进行差分算法的变异和交叉操作，取代烟花算法中的高斯变异算子，并称之为差分算子。

标准的差分算法主要由变异算子、交叉算子和选择算子组成，最基本的变异成分是父代的差分矢量，对于每个父代，随机从其他父代中选取3个不同个体，把其中2个个体各个维度坐标相减得到差分矢量，将得到的差分矢量加到另一个随机选择的个体矢量上形成变异矢量vti+1，如式（14）。

在MOHFWDE中，采用标准差分算法变异、交叉操作，为避免算法在历代进化中有用信息流失，引入精英存档集合，保留历代优秀个体，并采用NSGA-II中非支配排序准则维护外部精英集合。

3.3 算法步骤及其复杂度分析

综上所述，MOHFWDE算法流程图如图2所示，具体步骤如下：

步骤1初始化算法参数，使用拉丁采样[14]方法初始化烟花位置，进行非支配排序。

步骤 2根据式（3）、（5）、（7）、（9）、（11）、（12）计算爆炸半径，根据式（4）、（8）、（10）、（13）计算火花数目。

Fig.2 Flow chart of MOHFWDE algorithm图2 MOHFWDE算法流程图

步骤3根据算法1、2释放火花，选择所有烟花并从外部存档集合中选取(1+a)×NI个个体执行差分变异、交叉操作，产生子代，a为目标数。

步骤4将父代和子代一起进行非支配排序，维护外部精英存档集合。

步骤5判断进化代数是否满足t≤gen，如果满足，则令t=t+1，依据非支配排序原则选择子代，返回步骤2；否则，终止算法，输出存档集合。

在时间复杂度方面，标准烟花爆炸半径计算、火花数目计算均为Ο(N)，释放火花时间复杂度为Ο(nN)，n为决策向量维数。MOHFWDE中，由进化更新方向的引入，爆炸半径计算时间复杂度为Ο((1+n)N)，增强因子的引入使火花数目计算时间复杂度为Ο(2N)，扩增概率的引入使释放火花的时间复杂度为Ο(3nN)，由以上三种因子的引入共使烟花算法增加的时间复杂度为Ο((1+3n)N)。执行差分算子的时间复杂度约为Ο((N+(1+a)NI)2)，a为目标数，由于子代选择和外部存档的维护均采用非支配排序 准则，时间复杂度约为Ο(aN2)，故MOHFWDE时间复杂度为Ο((N+(1+a)NI)2)+Ο(2aN2)+Ο((3+4n)N)≈Ο(N2)，算法主要的时间消耗在差分算子和非支配排序上。

4 实验与分析

4.1 性能指标

在多目标算法性能评估中，分别使用综合性 能指标反世代距离（inverted generational distance，IGD）[15]和Spacing[16]测度对算法性能进行评估。

式中，P*是均匀分布在真实Pareto前沿的点集，|P*|为P*的集合长度，Q为算法获得的近似Pareto前沿，d(v,Q)为P*中个体v到集合Q的最小欧几里德距离。IGD值越小，说明算法获得的近似Pareto前沿多样性、逼近性越好。

式中，di为近似前沿上个体i到相邻个体之间的最小欧几里德距离，为这些距离的平均值。Spacing值越小，说明所得Pareto前沿分布越均匀。

4.2 算法有效性分析

4.2.1 实验参数设定

为验证该文所提算法的有效性，选取两目标ZDT1～4、ZDT6[17]、WGF1～9[18]和三目标 DTLZ1～7[19]系列多目标测试函数进行性能测试，ZDT、DTLZ决策向量为30维，WFG决策向量为31维。设置MODERMO[20（]multi-objective differential evolution with rankingbased mutation operator）、dMOPSO[21（]decompositionbased multi-objective particle swarm optimizer）、NSGA-II三种多目标对比算法，各算法实验参数设置如下：

Table 1 IGD values of each algorithm表1 各算法IGD指标

根据文献[13]设置NSGA-II参数pc=0.9，pm=1/N，ηc=ηm=20，根据文献[18]设置MODE-RMO参数F=0.5，CR=0.3，根据文献[19]设置dMOPSO参数Ta=2，θ=5，ω=0.729，c1=1.2，c2=1.5。在ZDT、WFG系列测试函数中，最高评价次数FEAS=50 000，设置MOHFWDE精英集大小NP=100，gen=300，MODERMO、dMOPSO、NSGA-II种群大小N=100。在DTLZ测试函数中，最高评价次数FEAS=80 000，设置NP=200，gen=500，MODE-RMO、dMOPSO、NSGA-II种群大小为200。4种算法分别进行20次独立实验。

4.2.2 收敛精度分析

在ZDT系列测试函数中，结合表1中IGD性能统计和图3近似前沿，MODE-RMO求解ZDT6的近似前沿与真实前沿存在较大差距，NSGA-II求解ZDT3-4、ZDT6测试函数时没有找到真实前沿，并在求解ZDT4时陷入局部最优，dMOPSO和MOHFWDE求解5个测试函数的逼近性和分布性均取得较好效果，在t检验中结合5个测试函数二者并无明显差异，表现出良好的求解能力。

DTLZ系列测试函数中，除DTLZ5外，NSGA-II对其他6个测试函数的求解效果均不理想。dMOPSO除DTLZ5-6外，对其他DTLZ测试函数的求解效果较差。MODE-RMO对求解DTLZ2、DTLZ4～6均表现出较好效果，但对求解DTLZ1、DTLZ3、DTLZ7效果不理想。MOHFWDE 7种测试函数前沿均取得良好逼近性和分布性，除了DTLZ4与MODE-RMO无显著差异外，其他6种测试函数IGD指标均显著优于其他3种算法。

Fig.3 Pareto optimal front of some test functions图3 部分测试函数求解近似前沿

WFG系列测试函数是一组变量关联测试函数，其中WFG1、WFG8求解难度较大。MODE-RMO对WFG系列求解近似前沿均与真实前沿距离较大。dMOPSO除求解WFG5-6取得较好结果外，对WFG系列其他测试函数求解效果均不理想。NSGA-II在求解除WFG1、WFG5、WFG8外的其他WFG系列测试函数时，均表现出相对较好求解能力，其中WFG4取得最优求解效果。MOHFWDE求解WFG系列9种测试函数时8种取得最优求解效果，其中WFG1～3、WFG5求解效果与NSGA-II无显著差别。

为验证该文所提策略有效性，去除MOHFWDE中进化信息引导机制，对各测试函数进行20次独立实验。其在15种测试函数上的平均终值IGD差于MOHFWDE，6种无显著差异，说明MOHFWDE中进化信息引导机制很好地保持了种群多样性，提高了算法精度，验证了所提策略的有效性。

4.2.3 收敛速度及前沿分布性分析

Fig.4 Averaged evolution of IGD for each test function图4 各测试函数均值IGD指标变化趋势

根据图4给出的20次实验均值IGD变化趋势，ZDT系列ZDT1、3、4中MOHFWDE收敛速度最快，ZDT2、ZDT6中处于次优，但与最快的dMOPSO差距不大。在DTLZ系列测试函数中，MODE-RMO在DTLZ6上收敛速度最快，MOHFWDE在DTLZ7上收敛速度最快，且在DTLZ1～5中收敛速度显著优于其他3种算法。WFG系列中，MODE-RMO对9种测试函数求解能力均较弱，dMOPSO在前期均表现出较快收敛速度，其中WFG6中表现出较好收敛精度，但后期易显搜索疲态，NSGA-II对9种测试函数均表现出较快收敛速度。MOHFWDE收敛速度快于dMOPSO，远快于MODE-RMO，这可以说明烟花、差分算法混合策略的有效性。

表2给出了各算法Spacing测度值，MOHFWDE在ZDT、DTLZ系列12种测试函数中8种取得最优前沿分布，WFG系列中6种取得最优前沿分布，3种取得次优分布，算法整体前沿分布性优于其他3种对比算法。

4.2.4 算法耗时

结合3.3节中算法复杂度分析，表3给出了4种算法在3种测试函数上20次独立实验的平均耗时。MODE-RMO每次选择个体进行变异时都会进行一次非支配排序，使得其总耗时远大于其他3种算法，在两目标优化中MOHFWDE用时少于其他3种算法。在三目标优化中，由于dMOPSO、NSGA-II种群大小设置为200，而MOHFWDE在该实验参数下每代评价次数约为100，这就使得在相同的评价次数下MOHFWDE将进行更多次精英存档集的维护，因此MOHFWDE算法耗时跟算法参数有直接关系。

Table 2 Spacing values of each algorithm表2 各算法Spacing测度

Tab.3 Average CPU time of 20 independent experiments表3 20次独立实验的平均耗时 s

4.3 算法参数敏感性分析

MOHFWDE新引入了扩增概率和加强因子，为分析这两种参数的敏感性，取测试函数中MODERMO收敛精度较差的DTLZ3、WFG1、WFG3进行策略对比实验，以增加实验的说明性。

在实际参数调试过程中，较小的扩增概率对算法火花分布影响不明显，为有效分析扩增概率敏感性，使η在区间[0,1.0]均匀取0、0.3、0.6、0.8、1.0，在其他参数相同条件下对3种测试函数进行20次独立实验，图5给出了3种测试函数在不同扩增概率下平均IGD变化趋势。DTLZ3中，扩增概率非零条件下收敛速度和终值IGD优于为零情况。WFG1中，η=0时IGD下降速率最慢，IGD终值最大，η=1.0时IGD下降速率和终值IGD优于η=0.3，劣于η=0.6、η=0.8，在η=0.6时的IGD指标下降速率，终值IGD明显优于其他4种情况。WFG3中，前期η=0、η=0.3、η=0.8、η=1.0收敛速度无明显差别，后期明显分化，终值IGD指标有IGDη=0.8

根据上述实验结果可以说明扩增机制的引入加快了算法收敛速度，验证了引导机制的有效性。对于多峰优化，过高的扩增概率会使得大量搜索资源盲目地分配在进化更新方向，反而不利于种群进化搜索。通过大量实验，MOHFWDE在扩增概率η=0.6时，对各种测试函数均能取得较好效果。

在最大火花数目限制下，过大的加强因子往往火花数目不能增加到预期数，根据实验经验，ω超过1.5时往往会被最大火花数目截止。其他参数相同条件下，在区间[1.0,1.5]加强因子均匀取1.0、7/6、5/4、4/3、3/2，对3种测试函数进行20次独立实验，图6给出3种测试函数在不同加强因子条件下平均IGD变化趋势。DTLZ3中，前期ω=1.0时算法收敛速度明显慢于其他4种情况，ω=7/6时算法收敛速度、群体分布性和逼近性均优于其他4种情况。WFG1中，5种条件下算法收敛速度无明显区别，ω=7/6时取得最优终值IGD。WFG3中，在ω=1.0时后期收敛速度快于ω=3/2，慢于其他3种情况，ω=7/6时算法收敛速度、群体分布性和逼近性均取得最优。

根据上述实验结果说明，加强因子的引入能有效地提高算法收敛速度和收敛精度，但过大的加强因子由于爆炸半径的限制，使得过多搜索资源消耗在小区域内，不利于种群的快速收敛。通过实验验证加强因子ω=7/6在各种算法中取得较好效果。

Fig.5 Averaged evolution of IGD for differentη图5 不同扩增概率下均值IGD变化趋势

Fig.6 Averaged evolution of IGD for differentω图6 不同加强因子下均值IGD变化趋势

5 结束语

与其他3种算法的对比实验分析，表明本文所提MOHFWDE具有良好的收敛性、逼近性和分布性，自身参数对比实验验证了本文所提策略的有效性。但MOHFWDE并不能直接用于解决现实世界中带约束的多目标优化问题，此外，在MOHFWDE取得较好求解效果的同时，也引入了一部分参数，在一定程度上增加了算法的复杂性和灵活性，因而就MOHFWDE如何解决带约束多目标优化问题、结构的精简、参数的自适应值得进一步研究。