差分準對立學習多目標蟻獅算法

王亞東，石 全，尤志鋒，宋衛星

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

1 引言

在工程領域以及軍事領域常遇到多目標優化問題（Multi-objective Optimization Problem，MOP），所求得的最優解集需要滿足多個互相沖突的目標。為解決多目標優化問題，很多學者提出了一系列優化方法，從精確算法發展到啟發式算法，再發展到元啟發式算法，近些年又提出了超啟發式算法。由此可見多目標優化問題一直是研究的熱點和難點問題。

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

但是，在原始的蟻獅算法中螞蟻個體的位置更新過分依賴精英蟻獅的信息。導致算法在求解多目標問題時容易過早收斂，不利于尋求全局最優解。而差分進化算法擁有較為成熟的進化策略，為提升算法性能目前已經出現了大量改進的變異、交叉以及選擇算子[12]。因此本文利用差分進化的思想，提出一種能夠同時充分利用當前種群和精英個體信息的變異策略。同時，還提出準對立學習策略以改善種群的特性，提高個體在整個解空間內的探索能力（exploration）和局部開發能力（exploitation）。

2 相關研究

2.1 蟻獅算法

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

（1）隨機游走機制，公式如下：

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

為了保證個體在搜索空間內隨機移動，防止其超出邊界，需要對個體的位置進行規范化處理：

（2）通過改變蟻獅周圍的隨機游動來模擬螞蟻掉入陷阱的過程，公式如下：

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

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

其中，系數I滿足，隨著迭代次數的增加而逐漸增大。t是迭代次數，T是最大迭代次數，ω是隨迭代次數而動態調整的參數。

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

選擇并儲存適應度值最優的蟻獅作為精英個體，精英是唯一影響螞蟻位置蟻獅。即螞蟻向著隨機選擇的蟻獅以及精英蟻獅進行隨機移動，其移動公式如下：

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

2.2 差分進化策略

差分進化算法（Differential Evolution，DE）是在遺傳算法等基礎上提出的，通過模擬基因遺傳學中的變異、交叉和選擇來不斷更新個體，逐步找到最優的個體種群。與遺傳算法不同的是，差分進化算法的變異個體是由父代差分個體生成，并與其他父代個體交叉生成新個體，直接與其父代個體進行選擇。目前常用的差分進化變異策略如下[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策略：

其中，Fi是控制參數為定值；xri為種群中隨機選取的個體，xi為發生變異的個體，xbest為適應度最優的個體，且滿足xi≠xbest≠xri。

以上變異策略能夠利用父代種群的信息產生新的個體，其中策略（3）、（4）、（5）還利用了種群中最優個體的信息優化個體的變異方向。但是，通過實驗發現（見本文實驗部分），單純將這些變異策略引入蟻獅算法并沒有很好的改善蟻獅算法的性能。因此需要借用差分進化思想，提出與蟻獅算法相適應的變異策略。

2.3 準對立學習策略

傳統元啟發式算法通常對一組隨機的初始解進行尋優，而隨機產生的初始解可能距離最優解很遠，因此算法需要很長時間去向最優解收斂。反向學習策略是機器學習中的一種優化策略，它要求在每次優化時同時對當前解和其對應的對立解進行檢驗并擇優作為新的解。在黑盒優化中，反向學習策略得到的很好的應用，其優化結果通常更加接近優化問題的最優解。

對于一個可行域為[a,b]的實數x，定義其對立數ox如下：

但是，反向學習僅考慮某個解的對立數，而為了增加種群的多樣性，保證全局尋優能力，本文采用（Quasi-Opposition Based Learning，QOBL）策略對初始種群進行優化[14]。定義x的準對立數qox如下：

則對于D維螞蟻個體，其準對立個體中第i維變量的值為。

在得到準對立種群后，將其與原種群個體混合，并擇優作為新的種群。

3 改進多目標蟻獅算法

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

其次，原蟻獅算法中螞蟻位置更新公式僅使用了外部存檔中蟻獅的信息，拋棄了螞蟻種群的信息。這可能導致算法過早收斂，不利于全局探索。而傳統差分進化的變異策略則強調了螞蟻種群的信息，沒有充分發揮蟻獅信息的作用，不利于算法的收斂。因此要考慮如何全面利用種群和蟻獅的位置信息。因此，本文提出了一種新的螞蟻位置更新公式：

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

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

在每次迭代結束產生新的螞蟻種群后，求其準對立個體，并將兩個種群混合后根據支配關系擇優作為新的種群進入下次迭代。偽代碼如下：

算法準對立差分多目標蟻獅算法

2. 設置種群規模，外部存檔規模，產生初始種群

3. While (t

4. fori=1∶n

5. 計算螞蟻種群個體適應度函數

6. 根據個體支配關系，更新外部存檔（蟻獅種群）

7. 計算存檔中蟻獅個體的擁擠度，選出精英蟻獅和隨機蟻獅

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

9. end for

10. fori=1∶n

11. forj=1∶d

12. 根據公式（7）和（8）計算個體向量的準對立向量

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. 將準對立種群與原種群混合，根據支配關系和擁擠度擇優產生新的種群

22. end while

4 仿真實驗及結果分析

4.1 實驗設置

對于多目標優化算法，其算法的性能主要體現在收斂性（conversation）以及分布性（distribution）上[15]。收斂性描述了算法求得的結果向真實帕累托前沿面（Pareto Front，PF）的逼近程度。算法的收斂性越強，表示其求得的解集越接近真實最優解，結果也越精確。分布性描述了算法求得的結果在目標空間上的分布特性，一方面應當盡可能分布在整個PF 上，另一方面應當盡量均勻的分布。算法的分布性越強，表示算法的全局探索能力越強。

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

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

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

HV描述了算法求得的點和參考點在目標空間構成的超體積。其值越大表明了算法的收斂性和分布性越好，計算公式如下：

其中，Λ 表示勒貝格測度，P為算法求得的解，xref為參考點。

為了研究該改進算法的性質，本文選取ZDT 系列測試函數對算法進行驗證[17]。實驗參數設置、策略的表達式以及F取值[18]見表1。

4.2 進化策略對算法的影響

為檢驗本文提出的差分進化策略對算法的優化效果，將其與經典蟻獅算法以及傳統的差分進化策略優化的算法進行對比。在未采用準對立策略的基礎上分別采用不同的變異策略對原始多目標蟻獅算法進行優化。算法分別在各標準測試函數上進行測試，實驗結果如圖2所示。

圖2 從左至右分別為原始MALO 算法、DE/rand/1策略改進算法、DE/best/1 策略改進算法、DE/current-tobest/1 策略改進算法以及本文提出的DEQOMALO 算法。從上至下分別為五個測試函數。從圖中可以直觀觀察算法在各測試函數上結果的分布情況。從圖中第一列中可以看出，MALO 算法在求解ZDT 測試函數時最優解集基本落均在真實PF 上，但是在求解ZDT1 和ZDT2時并為均勻地分布在整個PF上，即分布性表現較差；從圖中第二列中可以看出，采用DE/rand/1 策略時，算法求得的最優解基本上全未能落在PF 上，表明此時算法的收斂性和分布性均很差，主要是因為該策略采用完全隨機的變異策略，未能使種群向精英蟻獅的位置移動。從圖中第三列和第四列可以看出，DE/best/1策略以及DE/current-to-best/1 策略下算法求得最優解均落在PF上，但是同樣未能分布在整個PF上，其求解所有ZDT測試函數時分布性均較差。而圖中最后一列為本文提出的改進策略，可以看出算法的最優解在所有測試函數的目標空間內都能夠均勻廣泛的分布在真實PF 上，算法的收斂性和分布性均為最優。

表1 實驗變異策略與參數設置

圖2 不帶準對立學習策略的最優解分布

為了進一步定量分析算法的性能，將幾種算法在各測試函數上分別運行30 次，記錄每個算法對應每個測試函數的HV和IGD指標的均值和標準差，其結果見表2和表3。表中的最優值用加粗數字表示，對于HV指標其值越大為最優，對于IGD 指標其值越小為最優，對于標準差其值越小表明算法越穩定。觀察指標的均值，可以看出本文提出的算法得到的HV 指標均取得了最大值，IGD 指標均取得最小值，表示DEQOMALO 的收斂性和分布性較其他算法均為最優。觀察指標的標準差，可以看出本文提出的DEQOMALO 算法的穩定均優于其他算法。

表2 HV指標的均值和標準差

表3 IGD指標的均值和標準差

4.3 準對立學習策略對算法的影響

圖3 帶準對立學習策略的最優解分布

為進一步分析準對立學習策略對算法的影響，將準對立策略引入各算法，再次對ZDT 系列測試函數進行實驗。實驗結果如圖3所示。

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

表4 HV指標的均值和標準差

表5 IGD指標的均值和標準差

表4和表5記錄了各算法在各測試函數上分別運行30 次后的HV 指標和IGD 指標的均值和標準差。從表中可以看出，一方面，本文提出的算法優于經典蟻獅算法以及傳統差分進化策略改進的算法；另一方面，通過和表2、表3結果的比較，在引入準對立學習策略后的算法要優于不帶準對立策略的算法，在DE/rand/1、DE/best/1 和DE/current-to-best/1 策略下改進算法上體現尤為明顯。

5 結論

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