差分準(zhǔn)對(duì)立學(xué)習(xí)多目標(biāo)蟻獅算法

王亞?wèn)|，石 全，尤志鋒，宋衛(wèi)星

陸軍工程大學(xué) 裝備指揮與管理系，石家莊 050003

1 引言

在工程領(lǐng)域以及軍事領(lǐng)域常遇到多目標(biāo)優(yōu)化問(wèn)題（Multi-objective Optimization Problem，MOP），所求得的最優(yōu)解集需要滿足多個(gè)互相沖突的目標(biāo)。為解決多目標(biāo)優(yōu)化問(wèn)題，很多學(xué)者提出了一系列優(yōu)化方法，從精確算法發(fā)展到啟發(fā)式算法，再發(fā)展到元啟發(fā)式算法，近些年又提出了超啟發(fā)式算法。由此可見(jiàn)多目標(biāo)優(yōu)化問(wèn)題一直是研究的熱點(diǎn)和難點(diǎn)問(wèn)題。

智能優(yōu)化算法作為元啟發(fā)式算法，對(duì)解決多目標(biāo)問(wèn)題具有很強(qiáng)的魯棒性和適用性。常見(jiàn)的智能優(yōu)化算法有PSO[1]、蟻群算法[2]、狼群算法[3]等仿生群體智能算法，以及NSGA[4]、差分進(jìn)化[5]、基于分解的進(jìn)化算法[6]等多目標(biāo)進(jìn)化算法。其中，Mirjalili 提出的蟻獅算法（ALO）是一種群體智能優(yōu)化算法，它通過(guò)模擬蟻獅捕食螞蟻的過(guò)程以獲取問(wèn)題的最優(yōu)解[7]。為利用蟻獅算法求解多目標(biāo)問(wèn)題，Mirjalili 又提出了多目標(biāo)蟻獅算法。算法利用不同個(gè)體的Pareto支配關(guān)系尋求最優(yōu)解，該算法相對(duì)于MOPSO 和NSGA-II 等經(jīng)典算法的優(yōu)越性已得到了驗(yàn)證[8]。由于蟻獅算法的優(yōu)越性，該算法很快得到了應(yīng)用和推廣。趙世杰等人對(duì)蟻獅算法進(jìn)行了改進(jìn)，用于優(yōu)化SVM 的參數(shù)[9]；Yao 等人利用蟻獅算法解決路徑規(guī)劃問(wèn)題[10]；Zawbaa 等人將蟻獅算法用于特征選擇[11]。

但是，在原始的蟻獅算法中螞蟻個(gè)體的位置更新過(guò)分依賴精英蟻獅的信息。導(dǎo)致算法在求解多目標(biāo)問(wèn)題時(shí)容易過(guò)早收斂，不利于尋求全局最優(yōu)解。而差分進(jìn)化算法擁有較為成熟的進(jìn)化策略，為提升算法性能目前已經(jīng)出現(xiàn)了大量改進(jìn)的變異、交叉以及選擇算子[12]。因此本文利用差分進(jìn)化的思想，提出一種能夠同時(shí)充分利用當(dāng)前種群和精英個(gè)體信息的變異策略。同時(shí)，還提出準(zhǔn)對(duì)立學(xué)習(xí)策略以改善種群的特性，提高個(gè)體在整個(gè)解空間內(nèi)的探索能力（exploration）和局部開(kāi)發(fā)能力（exploitation）。

2 相關(guān)研究

2.1 蟻獅算法

蟻獅算法是模擬自然界中蟻獅建造陷阱捕食螞蟻的過(guò)程來(lái)尋求最優(yōu)解集，因此在蟻獅算法中有兩個(gè)種群，即蟻獅和螞蟻。蟻獅捕食過(guò)程主要由五個(gè)基本步驟組成：螞蟻的隨機(jī)游走、螞蟻落入陷阱、螞蟻滑向蟻獅、蟻獅捕獲螞蟻以及蟻獅重構(gòu)陷阱。蟻獅算法的基本步驟正是模擬以上過(guò)程，其數(shù)學(xué)描述和模型如下所示。

（1）隨機(jī)游走機(jī)制，公式如下：

其中，cumsum為累積和，t是迭代次數(shù)，n是最大迭代次數(shù)。是與t相關(guān)的隨機(jī)函數(shù)，rand滿足[0，1]均勻分布。

為了保證個(gè)體在搜索空間內(nèi)隨機(jī)移動(dòng)，防止其超出邊界，需要對(duì)個(gè)體的位置進(jìn)行規(guī)范化處理：

（2）通過(guò)改變蟻獅周圍的隨機(jī)游動(dòng)來(lái)模擬螞蟻掉入陷阱的過(guò)程，公式如下：

其中，ct和dt分別是第t次迭代時(shí)所有變量的最小值和最大值；是第j個(gè)蟻獅在第t次迭代時(shí)的位置。

（3）通過(guò)適應(yīng)性地縮小螞蟻隨機(jī)游走的范圍模擬螞蟻向蟻獅滑落的過(guò)程，其公式如下：

其中，系數(shù)I滿足，隨著迭代次數(shù)的增加而逐漸增大。t是迭代次數(shù)，T是最大迭代次數(shù)，ω是隨迭代次數(shù)而動(dòng)態(tài)調(diào)整的參數(shù)。

（4）模擬蟻獅捕獲螞蟻的過(guò)程如下：

選擇并儲(chǔ)存適應(yīng)度值最優(yōu)的蟻獅作為精英個(gè)體，精英是唯一影響螞蟻位置蟻獅。即螞蟻向著隨機(jī)選擇的蟻獅以及精英蟻獅進(jìn)行隨機(jī)移動(dòng)，其移動(dòng)公式如下：

（5）重構(gòu)陷阱。采用一個(gè)外部存檔（Archive），來(lái)存儲(chǔ)Pareto 支配解集。采用小生境技術(shù)衡量存檔中解的分布，每個(gè)解的鄰域均為給定的半徑。用每個(gè)解鄰域內(nèi)的其他解的個(gè)數(shù)衡量該解的分布性，鄰域內(nèi)解越多則表示越密集，解越少則越稀疏。

2.2 差分進(jìn)化策略

差分進(jìn)化算法（Differential Evolution，DE）是在遺傳算法等基礎(chǔ)上提出的，通過(guò)模擬基因遺傳學(xué)中的變異、交叉和選擇來(lái)不斷更新個(gè)體，逐步找到最優(yōu)的個(gè)體種群。與遺傳算法不同的是，差分進(jìn)化算法的變異個(gè)體是由父代差分個(gè)體生成，并與其他父代個(gè)體交叉生成新個(gè)體，直接與其父代個(gè)體進(jìn)行選擇。目前常用的差分進(jìn)化變異策略如下[13]所示。

（1）DE/rand/1策略：

（2）DE/rand/2策略：

（3）DE/best/1策略：

（4）DE/best/2策略：

（5）DE/current-to-best/1策略：

（6）DE/current-to-rand/1策略：

其中，F(xiàn)i是控制參數(shù)為定值；xri為種群中隨機(jī)選取的個(gè)體，xi為發(fā)生變異的個(gè)體，xbest為適應(yīng)度最優(yōu)的個(gè)體，且滿足xi≠xbest≠xri。

以上變異策略能夠利用父代種群的信息產(chǎn)生新的個(gè)體，其中策略（3）、（4）、（5）還利用了種群中最優(yōu)個(gè)體的信息優(yōu)化個(gè)體的變異方向。但是，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)（見(jiàn)本文實(shí)驗(yàn)部分），單純將這些變異策略引入蟻獅算法并沒(méi)有很好的改善蟻獅算法的性能。因此需要借用差分進(jìn)化思想，提出與蟻獅算法相適應(yīng)的變異策略。

2.3 準(zhǔn)對(duì)立學(xué)習(xí)策略

傳統(tǒng)元啟發(fā)式算法通常對(duì)一組隨機(jī)的初始解進(jìn)行尋優(yōu)，而隨機(jī)產(chǎn)生的初始解可能距離最優(yōu)解很遠(yuǎn)，因此算法需要很長(zhǎng)時(shí)間去向最優(yōu)解收斂。反向?qū)W習(xí)策略是機(jī)器學(xué)習(xí)中的一種優(yōu)化策略，它要求在每次優(yōu)化時(shí)同時(shí)對(duì)當(dāng)前解和其對(duì)應(yīng)的對(duì)立解進(jìn)行檢驗(yàn)并擇優(yōu)作為新的解。在黑盒優(yōu)化中，反向?qū)W習(xí)策略得到的很好的應(yīng)用，其優(yōu)化結(jié)果通常更加接近優(yōu)化問(wèn)題的最優(yōu)解。

對(duì)于一個(gè)可行域?yàn)閇a,b]的實(shí)數(shù)x，定義其對(duì)立數(shù)ox如下：

但是，反向?qū)W習(xí)僅考慮某個(gè)解的對(duì)立數(shù)，而為了增加種群的多樣性，保證全局尋優(yōu)能力，本文采用（Quasi-Opposition Based Learning，QOBL）策略對(duì)初始種群進(jìn)行優(yōu)化[14]。定義x的準(zhǔn)對(duì)立數(shù)qox如下：

則對(duì)于D維螞蟻個(gè)體，其準(zhǔn)對(duì)立個(gè)體中第i維變量的值為。

在得到準(zhǔn)對(duì)立種群后，將其與原種群個(gè)體混合，并擇優(yōu)作為新的種群。

3 改進(jìn)多目標(biāo)蟻獅算法

要想將傳統(tǒng)差分進(jìn)化思想應(yīng)用到多目標(biāo)蟻獅優(yōu)化算法中，需要克服兩方面的問(wèn)題。首先，傳統(tǒng)差分進(jìn)化的變異策略都是針對(duì)單目標(biāo)優(yōu)化問(wèn)題，因此要解決由單目標(biāo)向多目標(biāo)的轉(zhuǎn)化。在單目標(biāo)優(yōu)化問(wèn)題中，通過(guò)單純比較適應(yīng)度函數(shù)值即可對(duì)個(gè)體的優(yōu)劣進(jìn)行排序。而多目標(biāo)優(yōu)化中需要同時(shí)考慮個(gè)體的多個(gè)目標(biāo)，因此不能通過(guò)比較適應(yīng)度值大小確定最優(yōu)個(gè)體xbest。本文引入非支配排序思想，首先根據(jù)螞蟻個(gè)體的Pareto支配關(guān)系找出非支配解，將非支配個(gè)體放入外部存檔中作為蟻獅種群。其次利用小生境技術(shù)（Niche）對(duì)存檔中的蟻獅種群進(jìn)行排序，選出精英蟻獅個(gè)體。則精英蟻獅的優(yōu)于其他蟻獅個(gè)體，所有的蟻獅個(gè)體優(yōu)于螞蟻個(gè)體。

其次，原蟻獅算法中螞蟻位置更新公式僅使用了外部存檔中蟻獅的信息，拋棄了螞蟻種群的信息。這可能導(dǎo)致算法過(guò)早收斂，不利于全局探索。而傳統(tǒng)差分進(jìn)化的變異策略則強(qiáng)調(diào)了螞蟻種群的信息，沒(méi)有充分發(fā)揮蟻獅信息的作用，不利于算法的收斂。因此要考慮如何全面利用種群和蟻獅的位置信息。因此，本文提出了一種新的螞蟻位置更新公式：

公式（9）可以充分利用當(dāng)前種群的信息，以及蟻獅的位置信息，保證種群向精英蟻獅移動(dòng)。針對(duì)求目標(biāo)函數(shù)最小值的多目標(biāo)優(yōu)化問(wèn)題，圖1 給出了其幾何解釋。圖中的紅點(diǎn)分別表示螞蟻個(gè)體以及從外部存檔中選出的精英蟻獅和隨機(jī)蟻獅，藍(lán)點(diǎn)表示的位置。由精英蟻獅和隨機(jī)蟻獅構(gòu)成的邊為(Antlionelite-Antlionrand)、(Antlionelite-Anti)和 (Antlionrand-Anti)三個(gè)向量。按照的三個(gè)向量方向（圖中藍(lán)線）運(yùn)動(dòng)至新的位置即更新后的螞蟻個(gè)體（圖中黑點(diǎn)）。從圖中可以看出通過(guò)式（9）的矢量變換，原螞蟻個(gè)體Anti將有效地向真實(shí)Pareto前沿面移動(dòng)，算法的收斂性得到了提升。

圖1 位置更新公式的幾何解釋

在每次迭代結(jié)束產(chǎn)生新的螞蟻種群后，求其準(zhǔn)對(duì)立個(gè)體，并將兩個(gè)種群混合后根據(jù)支配關(guān)系擇優(yōu)作為新的種群進(jìn)入下次迭代。偽代碼如下：

算法準(zhǔn)對(duì)立差分多目標(biāo)蟻獅算法

2. 設(shè)置種群規(guī)模，外部存檔規(guī)模，產(chǎn)生初始種群

3. While (t

4. fori=1∶n

5. 計(jì)算螞蟻種群個(gè)體適應(yīng)度函數(shù)

6. 根據(jù)個(gè)體支配關(guān)系，更新外部存檔（蟻獅種群）

7. 計(jì)算存檔中蟻獅個(gè)體的擁擠度，選出精英蟻獅和隨機(jī)蟻獅

8. 根據(jù)公式（9），更新螞蟻的位置

9. end for

10. fori=1∶n

11. forj=1∶d

12. 根據(jù)公式（7）和（8）計(jì)算個(gè)體向量的準(zhǔn)對(duì)立向量

13.Mi,j=(aj+bj)/2

14. If (Anti,j

15.

16. else

17.

18. end if else

19. end for

20. end for

21. 將準(zhǔn)對(duì)立種群與原種群混合，根據(jù)支配關(guān)系和擁擠度擇優(yōu)產(chǎn)生新的種群

22. end while

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

對(duì)于多目標(biāo)優(yōu)化算法，其算法的性能主要體現(xiàn)在收斂性（conversation）以及分布性（distribution）上[15]。收斂性描述了算法求得的結(jié)果向真實(shí)帕累托前沿面（Pareto Front，PF）的逼近程度。算法的收斂性越強(qiáng)，表示其求得的解集越接近真實(shí)最優(yōu)解，結(jié)果也越精確。分布性描述了算法求得的結(jié)果在目標(biāo)空間上的分布特性，一方面應(yīng)當(dāng)盡可能分布在整個(gè)PF 上，另一方面應(yīng)當(dāng)盡量均勻的分布。算法的分布性越強(qiáng)，表示算法的全局探索能力越強(qiáng)。

為衡量算法的以上兩個(gè)性質(zhì)，在諸多評(píng)判指標(biāo)中，由于IGD（Inverted Generation Distance）和HV（Hyper Volume）指標(biāo)因其可以同時(shí)反映算法的收斂性和分布性而應(yīng)用最為廣泛[16]。因此，本文也采用IGD 和HV 作為算法性能的評(píng)判指標(biāo)。

IGD描述了算法結(jié)果到參考點(diǎn)的平均距離，其值越小，表明所求得的解集越逼近真實(shí)PF，并且具有較好的分布性。計(jì)算公式如下：

其中，P?為參考點(diǎn)，即真實(shí)PF 上的點(diǎn)的集合。P為算法求得的解的PF。d(z,P)是P到P?上的點(diǎn)z的最小歐式距離。為P?的規(guī)模。

HV描述了算法求得的點(diǎn)和參考點(diǎn)在目標(biāo)空間構(gòu)成的超體積。其值越大表明了算法的收斂性和分布性越好，計(jì)算公式如下：

其中，Λ 表示勒貝格測(cè)度，P為算法求得的解，xref為參考點(diǎn)。

為了研究該改進(jìn)算法的性質(zhì)，本文選取ZDT 系列測(cè)試函數(shù)對(duì)算法進(jìn)行驗(yàn)證[17]。實(shí)驗(yàn)參數(shù)設(shè)置、策略的表達(dá)式以及F取值[18]見(jiàn)表1。

4.2 進(jìn)化策略對(duì)算法的影響

為檢驗(yàn)本文提出的差分進(jìn)化策略對(duì)算法的優(yōu)化效果，將其與經(jīng)典蟻獅算法以及傳統(tǒng)的差分進(jìn)化策略優(yōu)化的算法進(jìn)行對(duì)比。在未采用準(zhǔn)對(duì)立策略的基礎(chǔ)上分別采用不同的變異策略對(duì)原始多目標(biāo)蟻獅算法進(jìn)行優(yōu)化。算法分別在各標(biāo)準(zhǔn)測(cè)試函數(shù)上進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 從左至右分別為原始MALO 算法、DE/rand/1策略改進(jìn)算法、DE/best/1 策略改進(jìn)算法、DE/current-tobest/1 策略改進(jìn)算法以及本文提出的DEQOMALO 算法。從上至下分別為五個(gè)測(cè)試函數(shù)。從圖中可以直觀觀察算法在各測(cè)試函數(shù)上結(jié)果的分布情況。從圖中第一列中可以看出，MALO 算法在求解ZDT 測(cè)試函數(shù)時(shí)最優(yōu)解集基本落均在真實(shí)PF 上，但是在求解ZDT1 和ZDT2時(shí)并為均勻地分布在整個(gè)PF上，即分布性表現(xiàn)較差；從圖中第二列中可以看出，采用DE/rand/1 策略時(shí)，算法求得的最優(yōu)解基本上全未能落在PF 上，表明此時(shí)算法的收斂性和分布性均很差，主要是因?yàn)樵摬呗圆捎猛耆S機(jī)的變異策略，未能使種群向精英蟻獅的位置移動(dòng)。從圖中第三列和第四列可以看出，DE/best/1策略以及DE/current-to-best/1 策略下算法求得最優(yōu)解均落在PF上，但是同樣未能分布在整個(gè)PF上，其求解所有ZDT測(cè)試函數(shù)時(shí)分布性均較差。而圖中最后一列為本文提出的改進(jìn)策略，可以看出算法的最優(yōu)解在所有測(cè)試函數(shù)的目標(biāo)空間內(nèi)都能夠均勻廣泛的分布在真實(shí)PF 上，算法的收斂性和分布性均為最優(yōu)。

表1 實(shí)驗(yàn)變異策略與參數(shù)設(shè)置

圖2 不帶準(zhǔn)對(duì)立學(xué)習(xí)策略的最優(yōu)解分布

為了進(jìn)一步定量分析算法的性能，將幾種算法在各測(cè)試函數(shù)上分別運(yùn)行30 次，記錄每個(gè)算法對(duì)應(yīng)每個(gè)測(cè)試函數(shù)的HV和IGD指標(biāo)的均值和標(biāo)準(zhǔn)差，其結(jié)果見(jiàn)表2和表3。表中的最優(yōu)值用加粗?jǐn)?shù)字表示，對(duì)于HV指標(biāo)其值越大為最優(yōu)，對(duì)于IGD 指標(biāo)其值越小為最優(yōu)，對(duì)于標(biāo)準(zhǔn)差其值越小表明算法越穩(wěn)定。觀察指標(biāo)的均值，可以看出本文提出的算法得到的HV 指標(biāo)均取得了最大值，IGD 指標(biāo)均取得最小值，表示DEQOMALO 的收斂性和分布性較其他算法均為最優(yōu)。觀察指標(biāo)的標(biāo)準(zhǔn)差，可以看出本文提出的DEQOMALO 算法的穩(wěn)定均優(yōu)于其他算法。

表2 HV指標(biāo)的均值和標(biāo)準(zhǔn)差

表3 IGD指標(biāo)的均值和標(biāo)準(zhǔn)差

4.3 準(zhǔn)對(duì)立學(xué)習(xí)策略對(duì)算法的影響

圖3 帶準(zhǔn)對(duì)立學(xué)習(xí)策略的最優(yōu)解分布

為進(jìn)一步分析準(zhǔn)對(duì)立學(xué)習(xí)策略對(duì)算法的影響，將準(zhǔn)對(duì)立策略引入各算法，再次對(duì)ZDT 系列測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖3所示。

可以發(fā)現(xiàn)，加入準(zhǔn)對(duì)立學(xué)習(xí)策略后，DE/best/1策略、DE/current-to-best/1策略以及本文提出的策略下的改進(jìn)算法的最優(yōu)解均能夠落在真實(shí)PF 上，而且均廣泛而均勻地分布在PF 上，表明準(zhǔn)對(duì)立學(xué)習(xí)策略能夠大大改進(jìn)算法的性能。從圖中前兩列可以看出，原始蟻獅算法和DE/rand/1策略算法效果雖然仍然較差，但是相對(duì)于圖2中未引入準(zhǔn)對(duì)立策略的算法有較大的提升。尤其是DE/rand/1 策略下算法的最優(yōu)解收斂性改善明顯，其最優(yōu)解均落在了PF 上。因此，加入準(zhǔn)對(duì)立學(xué)習(xí)策略在一定程度上提升了算法的性能。

表4 HV指標(biāo)的均值和標(biāo)準(zhǔn)差

表5 IGD指標(biāo)的均值和標(biāo)準(zhǔn)差

表4和表5記錄了各算法在各測(cè)試函數(shù)上分別運(yùn)行30 次后的HV 指標(biāo)和IGD 指標(biāo)的均值和標(biāo)準(zhǔn)差。從表中可以看出，一方面，本文提出的算法優(yōu)于經(jīng)典蟻獅算法以及傳統(tǒng)差分進(jìn)化策略改進(jìn)的算法；另一方面，通過(guò)和表2、表3結(jié)果的比較，在引入準(zhǔn)對(duì)立學(xué)習(xí)策略后的算法要優(yōu)于不帶準(zhǔn)對(duì)立策略的算法，在DE/rand/1、DE/best/1 和DE/current-to-best/1 策略下改進(jìn)算法上體現(xiàn)尤為明顯。

5 結(jié)論

為了提高蟻獅算法在解決多目標(biāo)問(wèn)題時(shí)的精度和全局搜索能力，提出改進(jìn)的多目標(biāo)蟻獅算法。在研究多目標(biāo)蟻獅算法的基礎(chǔ)上進(jìn)行了以下改進(jìn)：首先，引入差分進(jìn)化的思想，提出了一種既可以充分利用種群信息又可以利用精英蟻獅信息的查分進(jìn)化策略，代替原算法的個(gè)體更新機(jī)制。其次，采用準(zhǔn)對(duì)立學(xué)習(xí)策略對(duì)種群進(jìn)行優(yōu)化，一方面可以增加種群的多樣性，另一方面有利于提高算法的收斂速度。為了驗(yàn)證本文提出的算法的性能，選取了經(jīng)典標(biāo)準(zhǔn)測(cè)試函數(shù)，并以原始多目標(biāo)蟻獅算法和傳統(tǒng)進(jìn)化策略優(yōu)化的算法為參照進(jìn)行了數(shù)值仿真。仿真實(shí)驗(yàn)結(jié)果表明該改進(jìn)算法在求解各測(cè)試函數(shù)時(shí)，較其他算法均取得了良好的收斂性和分布性，并且改進(jìn)的多目標(biāo)蟻獅算法具有更高的穩(wěn)定性。因此，本文提出的基于差分進(jìn)化的準(zhǔn)對(duì)立學(xué)習(xí)多目標(biāo)蟻獅算法在求解多目標(biāo)優(yōu)化問(wèn)題時(shí)具有良好的適應(yīng)性和魯棒性。