進化信息引導的煙花差分混合多目標算法*

黃輝先，胡 拚，丁 燦，張廣炎，劉嘉婷

湘潭大學 信息工程學院，湖南 湘潭 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如何解決帶約束多目標優化問題、結構的精簡、參數的自適應值得進一步研究。