多目標優化進化算法比較綜述

劉玲源

摘 要 多目標優化是最優化領域的一個重要研究方向，本文簡要介紹了多目標優化的模型和幾種多目標優化的進化算法，并對算法進行了簡要比較。

關鍵詞 多目標優化 粒子群 遺傳算法 蟻群算法 人工免疫系統

中圖分類號：TP391 文獻標識碼：A

一、背景

多目標優化（Multiobjective OptimizaTionProblem，MOP）是最優化的一個重要分支，多目標問題中的各目標往往是有著沖突性的，其解不唯一，如何獲得最優解成為多目標優化的一個難點，目前還沒有絕對成熟與實用性好的理論。近年來，粒子群算法、遺傳算法、蟻群算法、人工免疫系統、等現代技術也被應用到多目標優化中，使多目標優化方法取得很大進步。本文將其中四種多目標優化的進化算法進行一個簡單的介紹和比較。

二、不同算法介紹

（一）多目標遺傳算法。

假定各目標的期望目標值與優先順序已給定，從優先級最高的子目標向量開始比較兩目標向量的優劣性，從目標未滿足的子目標元素部分開始每一級子目標向量的優劣性比較，最后一級子目標向量中的各目標分量要全部參與比較。給定一個不可實現的期望目標向量時，向量比較退化至原始的Pareto排序，所有目標元素都必須參與比較。算法運行過程中，適應值圖景可由不斷改變的期望目標值改變，種群可由此被引導并集中至某一特定折中區域。當前種群中（基于Pareto最優概念）優于該解的其他解的個數決定種群中每一個向量解的排序。

（二）人工免疫系統。

人工免疫算法是自然免疫系統在進化計算中的一個應用，將抗體定義為解，抗原定義為優化問題，抗原個數即為優化子目標的個數。免疫算法具有保持個體多樣性、搜索效率高、群體優化、避免過早收斂等優點。其通用的框架是：將優化問題的可行解對應抗體，優化問題的目標函數對應抗原，Pareto最優解被保存在記憶細胞集中，并采取某種機制對記憶集進行不斷更新，進而獲得分布均勻的Pareto最優解。

（三）多目標PSO約束算法。

將粒子群優化算法運用于優化問題，關鍵是如何確定群體全局最優位置pbest和每個粒子的最優位置gbest。由于多目標優化問題并無單個的最優解，所以不能直接確定gbest，pbest。PSO算法的優勢在于：第一，有著高效的搜索能力。第二，并行地同時搜索多個非劣解。第三，有著較好的通用性。PSO算法在處理多目標約束優化問題時，主要是解決自身和群體最佳位置，對于群體最佳位置的選擇，一是所得到的解要在Pareto邊界上具有一定得分散性，二是要求算法收斂速度好。對于自身最佳位置的選擇要求是通過較少的比較次數達到非劣解的更新。PSO算法在處理約束時，多采用懲罰函數法。

（四）多目標蟻群算法。

多目標蟻群算法的思想是：根據目標函數的數目將螞蟻分成若干子群體，為每個子群體分配一個目標函數，在其他子群體優化結果的基礎上通過Pareto過濾器來獲得均衡解。基本步驟如下：

1、轉移概率：對每一個目標k需要考慮一些信息素軌跡 k，在算法的每一代中，每一只螞蟻都計算一組權重p=（p1，p2，…，pk），并且同時使用啟發式信息和信息素軌跡。

2、局部信息素更新：當每只螞蟻走完aij邊之后，對每個目標k我們采取更新：

ijk=（1- ） ijk+ 0

其中， 0是初始信息素的值， 是信息素揮發速率。

3、全局信息素更新：對每個目標k，在當前代只對產生最好和第二好的解進行信息素更新，使用規則如下：

ijk=（1- ） ijk+ △ ijk

4、設置Pareto解集過濾器：

設置Pareto解集過濾器來存放算法運行時產生的Pareto解。

三、結論

四種進化算的優缺點總結如下：

多目標遺傳算法：有著良好的魯棒性和優越性，在擁擠選擇算子時，限制種群大小使用擁擠比較過程，使算法失去了收斂性。人工免疫系統：可以得到優化問題的多個Pareto最優解，算法運行缺乏穩定性。多目標PSO約束算法：能夠實現對多維復雜空間的高效搜索，研究還處于起步階段。多目標蟻群算法：Pareto前沿均勻性以及Pareto解集多樣性，早熟停滯和在控制參數難以確定。□

（作者單位： 四川大學商學院）

參考文獻：

[1]馬小姝.傳統多目標優化方法和多目標遺傳算法的比較綜述[J].電氣傳動自動化 ，2010.

[2]謝濤， 陳火旺.多目標優化與決策問題的演化算法[J].中國工程科學，2002.

[3]王魯，羅婷，趙琳，段海峰.基于遺傳算法的多目標優化技術[J].科技廣場，2009.

[4]樊紀山， 王經卓.基于人工免疫系統的多目標優化算法的研究[J].福建電腦2008.

[5]池元成，蔡國飆.基于蟻群算法的多目標優化[J].計算機工程，2009.

[6]孔翔宇.基于蟻群算法的多目標優化問題研究[J]四川理工學院學報，2010.

[7]薛洪波， 倫淑嫻.粒子群算法在多目標優化中的應用綜述[J].渤海大學學報，2009.

[8]吳慶洪.粒子群優化算法及其應用綜述[J].微計算機信息，2010.