進(jìn)化信息引導(dǎo)的煙花差分混合多目標(biāo)算法*

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

湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411100

1 引言

受煙花在夜空爆炸這一自然現(xiàn)象啟發(fā)，Tan和Zhu于2010年提出煙花算法[1-2（]fireworks algorithm,FA），F(xiàn)A主要由爆炸算子、變異算子和選擇算子三大部分組成，主要應(yīng)用在單目標(biāo)優(yōu)化問題中，其具有良好的局部搜索能力和全局搜索能力調(diào)節(jié)機(jī)制，逐漸受到研究者的廣泛關(guān)注。近幾年，許多研究者為提高它的性能進(jìn)行了很多改進(jìn)。Zheng等對(duì)基本煙花算法的爆炸算子、變異算子、選擇算子和映射規(guī)則進(jìn)行了詳細(xì)的分析，針對(duì)其存在的缺陷進(jìn)行了改進(jìn)，提出增強(qiáng)型煙花算法[3（]enhanced fireworks algorithm,EFWA）。Li等在EFWA基礎(chǔ)上，依據(jù)當(dāng)前種群最優(yōu)個(gè)體與特殊個(gè)體間的距離自適應(yīng)調(diào)節(jié)爆炸半徑，提出了自適應(yīng)煙花算法[4（]adaptive fireworks algorithm,AFWA），大大提升了煙花算法性能。文獻(xiàn)[5]在AFWA基礎(chǔ)上提出一種基于最優(yōu)煙火更新信息引導(dǎo)的自適應(yīng)單目標(biāo)煙花算法，并取得很好的實(shí)驗(yàn)效果。差分進(jìn)化算法[6（]differential evolution,DE）是Storn和Price提出用于解決各種復(fù)雜優(yōu)化問題的群體智能算法，文獻(xiàn)[7]將煙花算法與差分進(jìn)化兩種算法的優(yōu)良性能結(jié)合，提出一種新型混合算法（hybrid fireworks optimization method with differential evolution operators,FWA-DE）。

在實(shí)際優(yōu)化問題中，絕大多數(shù)都是多目標(biāo)優(yōu)化問題（multi-objective optimization problems，MOPs），而傳統(tǒng)的FA和DE都不能直接應(yīng)用在求解MOPs，基于DE的各種優(yōu)良特性，許多學(xué)者將DE進(jìn)行擴(kuò)展。Li和Zhang提出一種基于分解的多目標(biāo)差分進(jìn)化算法[8]；Rakshit和Konar提出一種含噪多目標(biāo)差分算法[9]；為解決電力系統(tǒng)最優(yōu)潮流問題，Abaci和Yamacli提出一種差分搜索算法[10（]differential search algorithm,DSA）。Zheng等使用SPEA-II[11（]strength pareto evolutionary algorithm II）算法中適應(yīng)度的計(jì)算方法，在FWA-DE的基礎(chǔ)上首次提出多目標(biāo)煙花算法[12]（multiobjective fireworks optimization,MOFOA），并將其應(yīng)用到油料作物生產(chǎn)實(shí)踐中。但MOFOA中采用標(biāo)準(zhǔn)的FA，處于Pareto前沿?zé)熁ǖ谋ò霃綄⒔咏?，?dǎo)致大量資源浪費(fèi)。其次由于映射規(guī)則和高斯變異算法的本身缺陷，使得大量火花自主地映射到原點(diǎn)附近，造成搜索資源浪費(fèi)，各煙花個(gè)體間缺乏信息交流，導(dǎo)致大量有用信息流失。

為解決上述問題，加快算法的收斂速度，提高分布性和逼近性，本文提出一種基于粒子進(jìn)化信息引導(dǎo)的自適應(yīng)多目標(biāo)煙花差分混合進(jìn)化算法（multiobjective hybrid optimization algorithm of fireworks and differentialguided by evolution information,MOHFWDE）。利用Pareto前沿粒子進(jìn)化信息，引導(dǎo)種群下一代進(jìn)化方向，加快種群收斂速度，受AFWA啟示，該算法使用多目標(biāo)自適應(yīng)策略，動(dòng)態(tài)調(diào)整爆炸半徑及火花數(shù)目，引入最小半徑檢測(cè)機(jī)制，替換相應(yīng)映射方式，將高斯變異算子改為差分變異算子和差分交叉算子，增強(qiáng)粒子間信息交流，并與其他3種算法進(jìn)行了對(duì)比實(shí)驗(yàn)。

2 多目標(biāo)煙花算法爆炸機(jī)制

在煙花爆炸時(shí)，質(zhì)量好的煙花會(huì)在以其為中心的附近區(qū)域均勻釋放大量火花，而質(zhì)量差的煙花往往釋放的火花數(shù)量少且分散。在單目標(biāo)煙花算法中，質(zhì)量好的煙花意味著它更有可能接近最優(yōu)解，因而在其附近釋放更多火花。相反，質(zhì)量差的煙花往往離最優(yōu)解較遠(yuǎn)，此時(shí)的爆炸半徑應(yīng)該取得更大。因此，在FA中，相對(duì)質(zhì)量差的煙花，質(zhì)量好的煙花會(huì)產(chǎn)生更多火花，且其爆炸半徑相對(duì)較小，其爆炸半徑計(jì)算如下：

爆炸火花數(shù)目計(jì)算如下：

式中，常數(shù)m控制著種群火花釋放總數(shù)，ymax為種群中最大目標(biāo)函數(shù)值。

為避免處于當(dāng)前Pareto前沿個(gè)體爆炸半徑過小，造成資源浪費(fèi)，設(shè)定閾值爆炸半徑和閾值火花數(shù)，如式（3）、式（4）。

式中，Ainit為初始最小半徑，Afinal為終止最小半徑，gen為終止進(jìn)化代數(shù)，t為當(dāng)前進(jìn)化代數(shù)。

為保證超出搜索空間維度坐標(biāo)映射的任意性，按式（6）對(duì)超出搜索空間火花維度坐標(biāo)xm進(jìn)行映射。式中xm,min、xm,max分別為第m維上的最小值、最大值。煙花釋放火花分布如算法1所示。

算法1火花分布

在多目標(biāo)算法NSGA-II[13]中使用非支配排序準(zhǔn)則選擇子代，通過非支配排序，每個(gè)個(gè)體i都會(huì)得到兩個(gè)屬性：非支配等級(jí)irank和擁擠度idistance。為適用多目標(biāo)優(yōu)化問題，MOHFWDE爆炸算子中的爆炸半徑和火花數(shù)目不再使用單一的目標(biāo)函數(shù)值計(jì)算，轉(zhuǎn)而采用一種結(jié)合個(gè)體在種群中非支配等級(jí)和擁擠度的計(jì)算方式。非支配等級(jí)靠前的煙花意味著其各目標(biāo)適應(yīng)度均優(yōu)于其他個(gè)體，擁擠度大的煙花意味著其在相同支配等級(jí)下分布于更稀疏的區(qū)域。這些位置上的煙花質(zhì)量優(yōu)于其他煙花，故在這些煙花上分配更多的搜索資源，使得群體朝著理想Pareto最優(yōu)解集和分布稀疏的方向進(jìn)化。

MOHFWDE初始化后，具體的爆炸半徑和火花數(shù)目計(jì)算如下：對(duì)于擁擠度不為無窮大的個(gè)體，如果當(dāng)前種群所有個(gè)體具有相同的非支配等級(jí)，即所有個(gè)體非支配等級(jí)都處于第一級(jí)，則依據(jù)擁擠度計(jì)算爆炸半徑和火花數(shù)目，否則需結(jié)合非支配等級(jí)與擁擠度進(jìn)行計(jì)算，如式（7）、式（8）。

對(duì)于擁擠度為無窮大的個(gè)體，如果非支配等級(jí)處于第一級(jí)，則爆炸半徑設(shè)置為當(dāng)代最小爆炸半徑，火花數(shù)目設(shè)置為當(dāng)代最大火花數(shù)目。否則將爆炸半徑設(shè)置為上一級(jí)個(gè)體的最大爆炸半徑，火花數(shù)目設(shè)置為上一級(jí)個(gè)體最小火花數(shù)目，如式（9）、式（10）。

式中，H={j|jrank=irank-1}為支配個(gè)體i的上一非支配級(jí)個(gè)體編號(hào)集合。

3 進(jìn)化信息引導(dǎo)的多目標(biāo)煙花差分算法

3.1 改進(jìn)的多目標(biāo)煙花算法

基于排序機(jī)制，算法進(jìn)化過程中，選擇出的新煙花子代與父代相應(yīng)維度坐標(biāo)一定存在不同，兩代煙花不同維度距離通常不相等，因而在進(jìn)化過程中，煙火每個(gè)維度呈現(xiàn)不同趨向最優(yōu)解的趨勢(shì)，對(duì)于那些坐標(biāo)不發(fā)生改變的維度，可以認(rèn)為解在該維度上已經(jīng)到達(dá)一個(gè)相對(duì)較好的位置，在坐標(biāo)發(fā)生改變的維度方向上加強(qiáng)搜索力度，使其獲得更多的搜索資源，算法將更有可能找到最優(yōu)解，加快尋優(yōu)速度，為更好地描述，稱這個(gè)方向?yàn)檫M(jìn)化更新方向。根據(jù)上述分析，在以下三方面進(jìn)行改進(jìn)：

（1）拓展在進(jìn)化更新方向上的爆炸半徑。

假設(shè)第t-1代煙花數(shù)目為N，分別在N個(gè)煙花位置按相應(yīng)的爆炸半徑和火花數(shù)目釋放煙花產(chǎn)生子代Pt，對(duì)父、子代進(jìn)行一次非支配排序。對(duì)于處于當(dāng)前Pareto前沿每個(gè)個(gè)體，如果仍然是原來的煙花炸點(diǎn)（ 即算法沒有產(chǎn)生更優(yōu)個(gè)體），則按式（7）～（10）計(jì)算爆炸半徑和火花數(shù)目，每個(gè)維度按相同半徑釋放煙花，否則，利用最優(yōu)火花在某些維度上的坐標(biāo)變更信息，確定進(jìn)化更新方向，把煙花爆炸范圍由原來的規(guī)則圓形向進(jìn)化更新方向拉伸，使得煙花在每個(gè)維度上都有其相應(yīng)的爆炸范圍，其爆炸半徑大小rmt,i由式（11）、式（12）確定。

（2）增加在進(jìn)化更新方向上的爆炸火花數(shù)目。

通過上述分析，最優(yōu)解將更有可能分布在進(jìn)化更新方向上，故增加在進(jìn)化更新方向上的爆炸火花數(shù)目，可使算法更快地向真實(shí)Pareto前沿靠攏。需要注意的是，最優(yōu)解并不一定就在進(jìn)化更新的方向，如果過多地在進(jìn)化更新方向分配資源，算法可能會(huì)陷入局部最優(yōu)點(diǎn)，因此設(shè)置擴(kuò)增概率η，使得火花以概率η直接設(shè)置在進(jìn)化更新方向上，以1-η的概率隨機(jī)設(shè)置，具體方法參照算法2。

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

（3）增加進(jìn)化煙花的爆炸火花數(shù)目。

對(duì)所有未發(fā)生坐標(biāo)更新和支配解仍按算法1釋放火花。為加強(qiáng)取得更優(yōu)解煙花的搜索能力，同時(shí)滿足最大火花數(shù)目smax的限制，引入大于1的加強(qiáng)因子ω，如果父代煙花被子代煙花支配，則依式（13）計(jì)算子代煙花的火花數(shù)目。

在其他方向上，擴(kuò)增因子減少了這些方向的爆炸火花數(shù)，增加了算法陷入局部最優(yōu)解的可能性，但加強(qiáng)因子使得煙火爆炸出更多火花，彌補(bǔ)了這些方向的火花喪失，避免算法陷入局部最優(yōu)，同時(shí)爆炸半徑的壓縮，使得算法可以更加細(xì)致地在這些方向進(jìn)行局部搜索，提高算法收斂精度。

針對(duì)上述三方面的改進(jìn)，圖1給出了兩維有無引導(dǎo)機(jī)制的爆炸示意圖。無引導(dǎo)機(jī)制爆炸中，煙花根據(jù)式（7）、式（8）得到的爆炸半徑和火花數(shù)目，在以其為圓心的圓形范圍內(nèi)均勻隨機(jī)釋放火花。煙花引導(dǎo)機(jī)制爆炸相對(duì)無引導(dǎo)機(jī)制爆炸會(huì)釋放更多爆炸火花，在進(jìn)化更新方向上，爆炸幅度相對(duì)較大，火花數(shù)目更多，使算法更有可能找到更優(yōu)解，收斂速度得到提高，其他方向爆炸幅度相對(duì)較小，搜索更為細(xì)致，使算法具備更好的收斂精度。

Fig.1 Exploding schematic with and without guidance圖1 有無引導(dǎo)機(jī)制爆炸示意圖

3.2 多目標(biāo)煙花算法與差分算法的混合

在煙花算法中，各個(gè)煙花分別在其炸點(diǎn)釋放火花，各個(gè)煙花之間缺乏信息交流機(jī)制，煙花群體中有用信息沒有得到充分利用，因此在種群中建立一種信息交流機(jī)制，成為提高算法搜索效率的有效方法。差分算法作為一種結(jié)構(gòu)簡單、魯棒性強(qiáng)、可調(diào)參數(shù)少的啟發(fā)式智能搜索算法，其使用差分算子，利用不同個(gè)體各維度信息形成差分矢量，再使用交叉算子使得差分矢量各維度值按一定概率加載在另一個(gè)不同個(gè)體上，這為個(gè)體優(yōu)秀維度信息在種群傳播提供了途徑。因此MOHFWDE依據(jù)擁擠度由高到低依次從精英存檔集合中選取前NI個(gè)個(gè)體、每個(gè)目標(biāo)適應(yīng)值前NI個(gè)個(gè)體以及當(dāng)前煙花群進(jìn)行差分算法的變異和交叉操作，取代煙花算法中的高斯變異算子，并稱之為差分算子。

標(biāo)準(zhǔn)的差分算法主要由變異算子、交叉算子和選擇算子組成，最基本的變異成分是父代的差分矢量，對(duì)于每個(gè)父代，隨機(jī)從其他父代中選取3個(gè)不同個(gè)體，把其中2個(gè)個(gè)體各個(gè)維度坐標(biāo)相減得到差分矢量，將得到的差分矢量加到另一個(gè)隨機(jī)選擇的個(gè)體矢量上形成變異矢量vti+1，如式（14）。

在MOHFWDE中，采用標(biāo)準(zhǔn)差分算法變異、交叉操作，為避免算法在歷代進(jìn)化中有用信息流失，引入精英存檔集合，保留歷代優(yōu)秀個(gè)體，并采用NSGA-II中非支配排序準(zhǔn)則維護(hù)外部精英集合。

3.3 算法步驟及其復(fù)雜度分析

綜上所述，MOHFWDE算法流程圖如圖2所示，具體步驟如下：

步驟1初始化算法參數(shù)，使用拉丁采樣[14]方法初始化煙花位置，進(jìn)行非支配排序。

步驟 2根據(jù)式（3）、（5）、（7）、（9）、（11）、（12）計(jì)算爆炸半徑，根據(jù)式（4）、（8）、（10）、（13）計(jì)算火花數(shù)目。

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

步驟3根據(jù)算法1、2釋放火花，選擇所有煙花并從外部存檔集合中選取(1+a)×NI個(gè)個(gè)體執(zhí)行差分變異、交叉操作，產(chǎn)生子代，a為目標(biāo)數(shù)。

步驟4將父代和子代一起進(jìn)行非支配排序，維護(hù)外部精英存檔集合。

步驟5判斷進(jìn)化代數(shù)是否滿足t≤gen，如果滿足，則令t=t+1，依據(jù)非支配排序原則選擇子代，返回步驟2；否則，終止算法，輸出存檔集合。

在時(shí)間復(fù)雜度方面，標(biāo)準(zhǔn)煙花爆炸半徑計(jì)算、火花數(shù)目計(jì)算均為Ο(N)，釋放火花時(shí)間復(fù)雜度為Ο(nN)，n為決策向量維數(shù)。MOHFWDE中，由進(jìn)化更新方向的引入，爆炸半徑計(jì)算時(shí)間復(fù)雜度為Ο((1+n)N)，增強(qiáng)因子的引入使火花數(shù)目計(jì)算時(shí)間復(fù)雜度為Ο(2N)，擴(kuò)增概率的引入使釋放火花的時(shí)間復(fù)雜度為Ο(3nN)，由以上三種因子的引入共使煙花算法增加的時(shí)間復(fù)雜度為Ο((1+3n)N)。執(zhí)行差分算子的時(shí)間復(fù)雜度約為Ο((N+(1+a)NI)2)，a為目標(biāo)數(shù)，由于子代選擇和外部存檔的維護(hù)均采用非支配排序 準(zhǔn)則，時(shí)間復(fù)雜度約為Ο(aN2)，故MOHFWDE時(shí)間復(fù)雜度為Ο((N+(1+a)NI)2)+Ο(2aN2)+Ο((3+4n)N)≈Ο(N2)，算法主要的時(shí)間消耗在差分算子和非支配排序上。

4 實(shí)驗(yàn)與分析

4.1 性能指標(biāo)

在多目標(biāo)算法性能評(píng)估中，分別使用綜合性 能指標(biāo)反世代距離（inverted generational distance，IGD）[15]和Spacing[16]測(cè)度對(duì)算法性能進(jìn)行評(píng)估。

式中，P*是均勻分布在真實(shí)Pareto前沿的點(diǎn)集，|P*|為P*的集合長度，Q為算法獲得的近似Pareto前沿，d(v,Q)為P*中個(gè)體v到集合Q的最小歐幾里德距離。IGD值越小，說明算法獲得的近似Pareto前沿多樣性、逼近性越好。

式中，di為近似前沿上個(gè)體i到相鄰個(gè)體之間的最小歐幾里德距離，為這些距離的平均值。Spacing值越小，說明所得Pareto前沿分布越均勻。

4.2 算法有效性分析

4.2.1 實(shí)驗(yàn)參數(shù)設(shè)定

為驗(yàn)證該文所提算法的有效性，選取兩目標(biāo)ZDT1～4、ZDT6[17]、WGF1～9[18]和三目標(biāo) DTLZ1～7[19]系列多目標(biāo)測(cè)試函數(shù)進(jìn)行性能測(cè)試，ZDT、DTLZ決策向量為30維，WFG決策向量為31維。設(shè)置MODERMO[20（]multi-objective differential evolution with rankingbased mutation operator）、dMOPSO[21（]decompositionbased multi-objective particle swarm optimizer）、NSGA-II三種多目標(biāo)對(duì)比算法，各算法實(shí)驗(yàn)參數(shù)設(shè)置如下：

Table 1 IGD values of each algorithm表1 各算法IGD指標(biāo)

根據(jù)文獻(xiàn)[13]設(shè)置NSGA-II參數(shù)pc=0.9，pm=1/N，ηc=ηm=20，根據(jù)文獻(xiàn)[18]設(shè)置MODE-RMO參數(shù)F=0.5，CR=0.3，根據(jù)文獻(xiàn)[19]設(shè)置dMOPSO參數(shù)Ta=2，θ=5，ω=0.729，c1=1.2，c2=1.5。在ZDT、WFG系列測(cè)試函數(shù)中，最高評(píng)價(jià)次數(shù)FEAS=50 000，設(shè)置MOHFWDE精英集大小NP=100，gen=300，MODERMO、dMOPSO、NSGA-II種群大小N=100。在DTLZ測(cè)試函數(shù)中，最高評(píng)價(jià)次數(shù)FEAS=80 000，設(shè)置NP=200，gen=500，MODE-RMO、dMOPSO、NSGA-II種群大小為200。4種算法分別進(jìn)行20次獨(dú)立實(shí)驗(yàn)。

4.2.2 收斂精度分析

在ZDT系列測(cè)試函數(shù)中，結(jié)合表1中IGD性能統(tǒng)計(jì)和圖3近似前沿，MODE-RMO求解ZDT6的近似前沿與真實(shí)前沿存在較大差距，NSGA-II求解ZDT3-4、ZDT6測(cè)試函數(shù)時(shí)沒有找到真實(shí)前沿，并在求解ZDT4時(shí)陷入局部最優(yōu)，dMOPSO和MOHFWDE求解5個(gè)測(cè)試函數(shù)的逼近性和分布性均取得較好效果，在t檢驗(yàn)中結(jié)合5個(gè)測(cè)試函數(shù)二者并無明顯差異，表現(xiàn)出良好的求解能力。

DTLZ系列測(cè)試函數(shù)中，除DTLZ5外，NSGA-II對(duì)其他6個(gè)測(cè)試函數(shù)的求解效果均不理想。dMOPSO除DTLZ5-6外，對(duì)其他DTLZ測(cè)試函數(shù)的求解效果較差。MODE-RMO對(duì)求解DTLZ2、DTLZ4～6均表現(xiàn)出較好效果，但對(duì)求解DTLZ1、DTLZ3、DTLZ7效果不理想。MOHFWDE 7種測(cè)試函數(shù)前沿均取得良好逼近性和分布性，除了DTLZ4與MODE-RMO無顯著差異外，其他6種測(cè)試函數(shù)IGD指標(biāo)均顯著優(yōu)于其他3種算法。

Fig.3 Pareto optimal front of some test functions圖3 部分測(cè)試函數(shù)求解近似前沿

WFG系列測(cè)試函數(shù)是一組變量關(guān)聯(lián)測(cè)試函數(shù)，其中WFG1、WFG8求解難度較大。MODE-RMO對(duì)WFG系列求解近似前沿均與真實(shí)前沿距離較大。dMOPSO除求解WFG5-6取得較好結(jié)果外，對(duì)WFG系列其他測(cè)試函數(shù)求解效果均不理想。NSGA-II在求解除WFG1、WFG5、WFG8外的其他WFG系列測(cè)試函數(shù)時(shí)，均表現(xiàn)出相對(duì)較好求解能力，其中WFG4取得最優(yōu)求解效果。MOHFWDE求解WFG系列9種測(cè)試函數(shù)時(shí)8種取得最優(yōu)求解效果，其中WFG1～3、WFG5求解效果與NSGA-II無顯著差別。

為驗(yàn)證該文所提策略有效性，去除MOHFWDE中進(jìn)化信息引導(dǎo)機(jī)制，對(duì)各測(cè)試函數(shù)進(jìn)行20次獨(dú)立實(shí)驗(yàn)。其在15種測(cè)試函數(shù)上的平均終值IGD差于MOHFWDE，6種無顯著差異，說明MOHFWDE中進(jìn)化信息引導(dǎo)機(jī)制很好地保持了種群多樣性，提高了算法精度，驗(yàn)證了所提策略的有效性。

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

Fig.4 Averaged evolution of IGD for each test function圖4 各測(cè)試函數(shù)均值IGD指標(biāo)變化趨勢(shì)

根據(jù)圖4給出的20次實(shí)驗(yàn)均值IGD變化趨勢(shì)，ZDT系列ZDT1、3、4中MOHFWDE收斂速度最快，ZDT2、ZDT6中處于次優(yōu)，但與最快的dMOPSO差距不大。在DTLZ系列測(cè)試函數(shù)中，MODE-RMO在DTLZ6上收斂速度最快，MOHFWDE在DTLZ7上收斂速度最快，且在DTLZ1～5中收斂速度顯著優(yōu)于其他3種算法。WFG系列中，MODE-RMO對(duì)9種測(cè)試函數(shù)求解能力均較弱，dMOPSO在前期均表現(xiàn)出較快收斂速度，其中WFG6中表現(xiàn)出較好收斂精度，但后期易顯搜索疲態(tài)，NSGA-II對(duì)9種測(cè)試函數(shù)均表現(xiàn)出較快收斂速度。MOHFWDE收斂速度快于dMOPSO，遠(yuǎn)快于MODE-RMO，這可以說明煙花、差分算法混合策略的有效性。

表2給出了各算法Spacing測(cè)度值，MOHFWDE在ZDT、DTLZ系列12種測(cè)試函數(shù)中8種取得最優(yōu)前沿分布，WFG系列中6種取得最優(yōu)前沿分布，3種取得次優(yōu)分布，算法整體前沿分布性優(yōu)于其他3種對(duì)比算法。

4.2.4 算法耗時(shí)

結(jié)合3.3節(jié)中算法復(fù)雜度分析，表3給出了4種算法在3種測(cè)試函數(shù)上20次獨(dú)立實(shí)驗(yàn)的平均耗時(shí)。MODE-RMO每次選擇個(gè)體進(jìn)行變異時(shí)都會(huì)進(jìn)行一次非支配排序，使得其總耗時(shí)遠(yuǎn)大于其他3種算法，在兩目標(biāo)優(yōu)化中MOHFWDE用時(shí)少于其他3種算法。在三目標(biāo)優(yōu)化中，由于dMOPSO、NSGA-II種群大小設(shè)置為200，而MOHFWDE在該實(shí)驗(yàn)參數(shù)下每代評(píng)價(jià)次數(shù)約為100，這就使得在相同的評(píng)價(jià)次數(shù)下MOHFWDE將進(jìn)行更多次精英存檔集的維護(hù)，因此MOHFWDE算法耗時(shí)跟算法參數(shù)有直接關(guān)系。

Table 2 Spacing values of each algorithm表2 各算法Spacing測(cè)度

Tab.3 Average CPU time of 20 independent experiments表3 20次獨(dú)立實(shí)驗(yàn)的平均耗時(shí) s

4.3 算法參數(shù)敏感性分析

MOHFWDE新引入了擴(kuò)增概率和加強(qiáng)因子，為分析這兩種參數(shù)的敏感性，取測(cè)試函數(shù)中MODERMO收斂精度較差的DTLZ3、WFG1、WFG3進(jìn)行策略對(duì)比實(shí)驗(yàn)，以增加實(shí)驗(yàn)的說明性。

在實(shí)際參數(shù)調(diào)試過程中，較小的擴(kuò)增概率對(duì)算法火花分布影響不明顯，為有效分析擴(kuò)增概率敏感性，使η在區(qū)間[0,1.0]均勻取0、0.3、0.6、0.8、1.0，在其他參數(shù)相同條件下對(duì)3種測(cè)試函數(shù)進(jìn)行20次獨(dú)立實(shí)驗(yàn)，圖5給出了3種測(cè)試函數(shù)在不同擴(kuò)增概率下平均IGD變化趨勢(shì)。DTLZ3中，擴(kuò)增概率非零條件下收斂速度和終值IGD優(yōu)于為零情況。WFG1中，η=0時(shí)IGD下降速率最慢，IGD終值最大，η=1.0時(shí)IGD下降速率和終值IGD優(yōu)于η=0.3，劣于η=0.6、η=0.8，在η=0.6時(shí)的IGD指標(biāo)下降速率，終值IGD明顯優(yōu)于其他4種情況。WFG3中，前期η=0、η=0.3、η=0.8、η=1.0收斂速度無明顯差別，后期明顯分化，終值IGD指標(biāo)有IGDη=0.8

根據(jù)上述實(shí)驗(yàn)結(jié)果可以說明擴(kuò)增機(jī)制的引入加快了算法收斂速度，驗(yàn)證了引導(dǎo)機(jī)制的有效性。對(duì)于多峰優(yōu)化，過高的擴(kuò)增概率會(huì)使得大量搜索資源盲目地分配在進(jìn)化更新方向，反而不利于種群進(jìn)化搜索。通過大量實(shí)驗(yàn)，MOHFWDE在擴(kuò)增概率η=0.6時(shí)，對(duì)各種測(cè)試函數(shù)均能取得較好效果。

在最大火花數(shù)目限制下，過大的加強(qiáng)因子往往火花數(shù)目不能增加到預(yù)期數(shù)，根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)，ω超過1.5時(shí)往往會(huì)被最大火花數(shù)目截止。其他參數(shù)相同條件下，在區(qū)間[1.0,1.5]加強(qiáng)因子均勻取1.0、7/6、5/4、4/3、3/2，對(duì)3種測(cè)試函數(shù)進(jìn)行20次獨(dú)立實(shí)驗(yàn)，圖6給出3種測(cè)試函數(shù)在不同加強(qiáng)因子條件下平均IGD變化趨勢(shì)。DTLZ3中，前期ω=1.0時(shí)算法收斂速度明顯慢于其他4種情況，ω=7/6時(shí)算法收斂速度、群體分布性和逼近性均優(yōu)于其他4種情況。WFG1中，5種條件下算法收斂速度無明顯區(qū)別，ω=7/6時(shí)取得最優(yōu)終值IGD。WFG3中，在ω=1.0時(shí)后期收斂速度快于ω=3/2，慢于其他3種情況，ω=7/6時(shí)算法收斂速度、群體分布性和逼近性均取得最優(yōu)。

根據(jù)上述實(shí)驗(yàn)結(jié)果說明，加強(qiáng)因子的引入能有效地提高算法收斂速度和收斂精度，但過大的加強(qiáng)因子由于爆炸半徑的限制，使得過多搜索資源消耗在小區(qū)域內(nèi)，不利于種群的快速收斂。通過實(shí)驗(yàn)驗(yàn)證加強(qiáng)因子ω=7/6在各種算法中取得較好效果。

Fig.5 Averaged evolution of IGD for differentη圖5 不同擴(kuò)增概率下均值IGD變化趨勢(shì)

Fig.6 Averaged evolution of IGD for differentω圖6 不同加強(qiáng)因子下均值IGD變化趨勢(shì)

5 結(jié)束語

與其他3種算法的對(duì)比實(shí)驗(yàn)分析，表明本文所提MOHFWDE具有良好的收斂性、逼近性和分布性，自身參數(shù)對(duì)比實(shí)驗(yàn)驗(yàn)證了本文所提策略的有效性。但MOHFWDE并不能直接用于解決現(xiàn)實(shí)世界中帶約束的多目標(biāo)優(yōu)化問題，此外，在MOHFWDE取得較好求解效果的同時(shí)，也引入了一部分參數(shù)，在一定程度上增加了算法的復(fù)雜性和靈活性，因而就MOHFWDE如何解決帶約束多目標(biāo)優(yōu)化問題、結(jié)構(gòu)的精簡、參數(shù)的自適應(yīng)值得進(jìn)一步研究。