一種求解多目標(biāo)優(yōu)化問題的改進(jìn)蟻群算法

羅艷媚

摘要：針對帶約束的多目標(biāo)優(yōu)化問題，提出一種改進(jìn)的蟻群算法（Ant colony optimization，ACO）。在基本算法的基礎(chǔ)上，通過對初始信息素進(jìn)行混沌處理，動(dòng)態(tài)調(diào)整參數(shù)α（信息啟發(fā)式因子）和β（期望啟發(fā)式因子）值，引入最大-最小螞蟻系統(tǒng)來對算法進(jìn)行改進(jìn)，利用Pareto 的排序機(jī)制對搜索到的可行解進(jìn)行分類排序，得出可行解。對4個(gè)經(jīng)典測試函數(shù)的仿真結(jié)果表明，文中算法在均勻性、尋有能力均優(yōu)于另兩種算法。

關(guān)鍵詞：約束問題;多目標(biāo)優(yōu)化;蟻群算法;仿真

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

文章編號(hào)：1009-3044（2020）32-0226-04

在當(dāng)今科研與工程實(shí)踐中，決策者需要考慮的因素越來越多，處理的問題越來越復(fù)雜，往往需要同時(shí)處理多個(gè)相互關(guān)聯(lián)且矛盾的多目標(biāo)函數(shù)優(yōu)化問題。ACO作為一種啟發(fā)式智能優(yōu)化算法，能夠較好地解決這類問題，但在求解離散型問題中也存在易陷入局部最優(yōu)、搜索時(shí)間較長，收斂較慢等不足。對此，已有學(xué)者通過對ACO算法本身的結(jié)構(gòu)和參數(shù)進(jìn)行優(yōu)化，如：文獻(xiàn)[1]對算法初始時(shí)刻信息素濃度進(jìn)行改進(jìn)，在信息素更新規(guī)則中引入自適應(yīng)動(dòng)態(tài)因子，提高算法搜索能力;文獻(xiàn)[2]提出動(dòng)態(tài)自適應(yīng)調(diào)整信息素?fù)]發(fā)系數(shù)并驗(yàn)證其有效性;文獻(xiàn)[3]則引入隨機(jī)變量來調(diào)整對偽隨機(jī)選擇和輪盤賭的選擇，平衡開發(fā)當(dāng)前搜索路徑與探索其他新路徑之間的關(guān)系。文獻(xiàn)[4]利用初始正反饋的機(jī)制來更新負(fù)反饋信息素矩陣，避免螞蟻的重復(fù)探索。此外，蟻群算法作為一種進(jìn)化算法，與遺傳算法、粒子群算法、模擬退火算法等其他優(yōu)化算法結(jié)合，充分利用智能算法的互補(bǔ)性，進(jìn)而提高算法的性能。

上述改進(jìn)ACO算法在不同程度上提高了搜索效率和收斂速度，但在處理多目標(biāo)問題時(shí)，一般采用線性加權(quán)法或順序法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)來求解。這種方式比較簡單，但不能很好地平衡存在沖突關(guān)系的多個(gè)優(yōu)化目標(biāo)。為此，本文針對帶約束的多目標(biāo)優(yōu)化問題提出一種改進(jìn)的ACO算法，混沌初始化信息素，動(dòng)態(tài)調(diào)整α和β參數(shù)值，并引入最大-最小螞蟻系統(tǒng)來限制信息素濃度，利用Pareto排序?qū)λ阉鞯降目尚薪膺M(jìn)行評價(jià)。最后，對經(jīng)典測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所提算法在求解帶約束的多目標(biāo)問題的可行性及有效性。

1 改進(jìn)的ACO算法

1.1 基本ACO算法

ACO算法是受到自然界中螞蟻覓食行為的啟發(fā)而衍生的一種算法，最早適用于解決TSP（旅行商問題）。螞蟻覓食過程中，碰到還沒走過的路口，隨機(jī)選擇一條路走，同時(shí)，在其經(jīng)過的路徑上釋放與長度成反比的信息素。后來的螞蟻碰到已經(jīng)走過的路口時(shí)，選擇信息素濃度較高路徑。螞蟻個(gè)體之間通過信息素來傳遞信息。在單位時(shí)間內(nèi)，訪問螞蟻越多的路徑，其信息素濃度越強(qiáng)，被選擇的概率越大，未被訪問的路徑其信息素濃度會(huì)隨著時(shí)間而揮發(fā)。最終，所有的螞蟻都選擇同一條路徑為蟻巢和食物之間的最短路徑。

ACO算法在求解優(yōu)化問題時(shí)，把食物的位置抽象成為解的空間點(diǎn)，代表問題的潛在解。設(shè)有[n]個(gè)節(jié)點(diǎn)有向圖，[m]只螞蟻，用[dij（i，j = 1，2，...，n ）]表示節(jié)點(diǎn)[i]和[j]之間的距離，初始信息素均一樣，即[τij0=c]（[c]為常數(shù)）。螞蟻個(gè)體在搜索時(shí)，從當(dāng)前節(jié)點(diǎn)i選擇概率值較大的節(jié)點(diǎn)j作為下一個(gè)轉(zhuǎn)移點(diǎn)，概率值[Pkij（t）]跟信息濃度及啟發(fā)信息有關(guān)，其計(jì)算公式為：

1.2? Logistic混沌映射

混沌是指發(fā)生在確定性系統(tǒng)中的不可重復(fù)、不可預(yù)測的隨機(jī)不規(guī)則擾動(dòng)現(xiàn)象，具有不確定性，是非線性動(dòng)力系統(tǒng)的固有特性。其數(shù)學(xué)表達(dá)式為：

式中：[xn]為混沌變量，n為迭代次數(shù)，[μ]為控制系統(tǒng)混沌行為的參數(shù)，一般取值范圍為 [0，4]，當(dāng)[μ=4]時(shí)，系統(tǒng)處于完全混沌狀態(tài)，產(chǎn)生的值在[0， 1]內(nèi)。

采用上使產(chǎn)生初始信息素，充分地利用混沌的遍歷性，克服了基本ACO由于初始時(shí)刻各路徑上信息素相等而盲目進(jìn)行搜索。

1.3參數(shù)的動(dòng)態(tài)調(diào)整

基本ACO中，α和β值是固定，在本文中，動(dòng)態(tài)調(diào)整α和β值，即其值隨迭代次數(shù)的變化而變化。算法在搜索初期，以路徑長度為依據(jù)來引導(dǎo)算法的搜索，此時(shí)產(chǎn)生[α∈（0，0.5）]、[β∈（0.5，0.9）]之間的隨機(jī)數(shù);在搜索后期，產(chǎn)生α為（0.5，0.9）、β為（0，0.5）之間的隨機(jī)數(shù)，將算法調(diào)整為依靠信息度濃度進(jìn)行搜索，有利于增強(qiáng)算法的搜索能力。參數(shù)α、β和迭代關(guān)系如下：

1.4 最大-最小螞蟻系統(tǒng)

為了避免算法因信息素積累過高而陷入局部最優(yōu)，在算法中融合最大-最小螞蟻系統(tǒng)的思想。

① 將各路徑上的信息素濃度限值在[[τmin，τmax]]范圍之內(nèi)，當(dāng)[τ>τmax]，則[τ=τmax]大于最大值的取[τmax]，當(dāng)[τ<τmin]，則[τ=τmin]。

②在每次迭代后，只更新最優(yōu)解對應(yīng)的路徑上的信息素濃度;

③本文算法將初始時(shí)刻的信息素濃度設(shè)置為[τ0]，上限值[τmax]為[1.5τ0]，下限值[τmin]為[0.3τ0]，即：

1.5 改進(jìn)算法的具體實(shí)現(xiàn)步驟

2 算法驗(yàn)證及結(jié)果分析

2.1 評價(jià)指標(biāo)與測試函數(shù)

2.1.1 評價(jià)指標(biāo)

為了驗(yàn)證算法的性能，本文采用以下三個(gè)指標(biāo)來評價(jià)算法的性能。

1）間距評估S

衡量算法結(jié)果分布度的指標(biāo)，S越小，均勻性越好。

2）可行解的個(gè)數(shù)N

在約束條件內(nèi)搜索到可行解的個(gè)數(shù)，N越大說明算法的尋優(yōu)能力越強(qiáng)。

3）最大散布范圍D

兩個(gè)極值解間的距離，D越大，表明算法的解散布范圍越廣。