劉玲源

摘 要 多目標(biāo)優(yōu)化是最優(yōu)化領(lǐng)域的一個(gè)重要研究方向，本文簡(jiǎn)要介紹了多目標(biāo)優(yōu)化的模型和幾種多目標(biāo)優(yōu)化的進(jìn)化算法，并對(duì)算法進(jìn)行了簡(jiǎn)要比較。

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

一、背景

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

二、不同算法介紹

（一）多目標(biāo)遺傳算法。

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

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

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

（三）多目標(biāo)PSO約束算法。

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

（四）多目標(biāo)蟻群算法。

多目標(biāo)蟻群算法的思想是：根據(jù)目標(biāo)函數(shù)的數(shù)目將螞蟻分成若干子群體，為每個(gè)子群體分配一個(gè)目標(biāo)函數(shù)，在其他子群體優(yōu)化結(jié)果的基礎(chǔ)上通過Pareto過濾器來獲得均衡解。基本步驟如下：

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

2、局部信息素更新：當(dāng)每只螞蟻?zhàn)咄阛ij邊之后，對(duì)每個(gè)目標(biāo)k我們采取更新：

ijk=（1- ） ijk+ 0

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

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

ijk=（1- ） ijk+ △ ijk

4、設(shè)置Pareto解集過濾器：

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

三、結(jié)論

四種進(jìn)化算的優(yōu)缺點(diǎn)總結(jié)如下：

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

（作者單位： 四川大學(xué)商學(xué)院）

參考文獻(xiàn)：

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

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

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

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

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

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

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

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