多目標優(yōu)化進化算法比較綜述

劉玲源

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

關鍵詞 多目標優(yōu)化 粒子群 遺傳算法 蟻群算法 人工免疫系統(tǒng)

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

一、背景

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

二、不同算法介紹

（一）多目標遺傳算法。

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

（二）人工免疫系統(tǒng)。

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

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

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

（四）多目標蟻群算法。

多目標蟻群算法的思想是：根據(jù)目標函數(shù)的數(shù)目將螞蟻分成若干子群體，為每個子群體分配一個目標函數(shù)，在其他子群體優(yōu)化結果的基礎上通過Pareto過濾器來獲得均衡解?；静襟E如下：

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

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

ijk=（1- ） ijk+ 0

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

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

ijk=（1- ） ijk+ △ ijk

4、設置Pareto解集過濾器：

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

三、結論

四種進化算的優(yōu)缺點總結如下：

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

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

參考文獻：

[1]馬小姝.傳統(tǒng)多目標優(yōu)化方法和多目標遺傳算法的比較綜述[J].電氣傳動自動化 ，2010.

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

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

[4]樊紀山， 王經(jīng)卓.基于人工免疫系統(tǒng)的多目標優(yōu)化算法的研究[J].福建電腦2008.

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

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

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

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