淺析自適應蟻群算法
論文導讀：(2)所有通過路段的搜索路徑對應的候選解均會對該路段帶來信息素的增量。(3)采用了信息素均勻分配策略，即對已搜索路徑中的所有路段采用同樣的信息素增量，與路段的重要性無關,沒有考慮當連續(xù)空間優(yōu)化問題轉換到有向圖搜索問題時，信息素分配給可行解帶來的尺度變化對于連續(xù)解空間搜索效率的影響。不同的信息素更新方式對蟻群算法的性能影響很大，比如算法的收斂效率等。為了解決這一問題，提高蟻群算法的全局收斂能力和搜索速度，提出了一種新的自適應的信息量更新策略。
關鍵詞：蟻群算法，自適應，信息素，優(yōu)化
1 引 言
受自然界中真實螞蟻行為的啟發(fā)，1991年意大利學者MDofigo等首先提出了蟻群算法 ，并將之應用于復雜組合優(yōu)化問題的求解，取得了較好的效果。但該算法也存在一些缺點，如進化速度慢，易陷入局部最優(yōu)等。論文大全。我國于1998年末才開始有少量公開報道和研究成果，
2 蟻群算法原理
螞蟻在外出覓食的過程中,不斷地在經(jīng)過的路徑上釋放信息激素以便和其他的螞蟻進行聯(lián)系，這種信息激素的濃度隨著經(jīng)過該路徑的螞蟻數(shù)量而增大，而螞蟻在回巢或覓食時也會選擇信息激素濃度較大的路徑，這就會有更多的螞蟻選擇此路徑，這就是一種正反饋現(xiàn)象。也就是說某一路徑上經(jīng)過的螞蟻越多，則后來者選擇該路徑的概率就越大。
3.基本蟻群算法的優(yōu)缺點
3.1 基本蟻群算法的優(yōu)點：
（1）較強的魯棒性：對基本螞蟻算法模型稍加修改，便可應用于其它問題。
（2）分布式計算。該算法是一種基于種群的擬生態(tài)系統(tǒng)算法，具有本質(zhì)并行性，易于并行實現(xiàn)。
(3)易于與其它方法結合。該算法很容易與多種啟發(fā)式算法結合，以改善算法的性能。
3.2 基本蟻群算法的缺點
(1)需要較長的計算時間，容易出現(xiàn)停滯現(xiàn)象。螞蟻中各個體的運動是隨機的，雖然通過信息激素交換能夠向著最優(yōu)路徑進化，但是當群體規(guī)模較大時，很難在較短時間內(nèi)從大量雜亂無章的路徑中找到一條較好的路徑。
(2)所有通過路段的搜索路徑對應的候選解均會對該路段帶來信息素的增量。而實際上，候選解并非都是最好解，這樣計算信息素的增量會導致錯誤的引導信息，從而造成大量的無效搜索，使系統(tǒng)出現(xiàn)停滯現(xiàn)象。
(3)采用了信息素均勻分配策略，即對已搜索路徑中的所有路段采用同樣的信息素增量，與路段的重要性無關,沒有考慮當連續(xù)空間優(yōu)化問題轉換到有向圖搜索問題時，信息素分配給可行解帶來的尺度變化對于連續(xù)解空間搜索效率的影響。
4.自適應蟻群算法的概述
蟻群算法的主要依據(jù)是信息正反饋原理和某種啟發(fā)式算法的有機結合，這種算法在構造解的過程中，利用隨機選擇策略，這種選擇策略使得進化速度較慢，正反饋原理旨在強化性能較好的解,卻容易出現(xiàn)停滯現(xiàn)象。這是造成蟻群算法的不足之處的根本原因．因而我們從選擇策略方面進行修改，我們采用確定性選擇和隨機選擇相結合的選擇策略，并且在搜索過程中動態(tài)地調(diào)整作確定性選擇的概率當進化到一定代數(shù)后，進化方向已經(jīng)基本確定，這時對路徑上信息量作動態(tài)凋整。論文大全。縮小最好和最差路徑上的信息量的差距，并且適當加大隨機選擇的概率，以小于l對解空間的更完全搜索，從而可 有效地克服基本蟻群算法的不足，此算
法屬于自適應算法。該算法按照下式確定螞蟻由所在轉移到下一個城市S
其中，P0∈(0，1)，r是(0，1)中均勻分布的隨機數(shù)。當進化方向基本確定后，簡單的放大(或縮小)方法調(diào)整每一路徑上的信息量，該方法不僅能夠加快收斂速度，節(jié)省搜索時間，而且能夠克服停滯行為的過早出現(xiàn)，有利于發(fā)現(xiàn)更好的解這對于求解大規(guī)模優(yōu)化問題是有益的。論文大全。通過標準蟻群算法的對比，學者就提出了一種自適應蟻群算法。
5.自適應的信息更新策略
不同的信息素更新方式對蟻群算法的性能影響很大，比如算法的收斂效率等。如果對全部路徑上的信息素進行更新，則算法不易收斂；若只是更新目前搜索到最優(yōu)邊上的信息素，則加強了算法的正反饋作用，導致陷入局部最優(yōu)解。為了解決這一問題，提高蟻群算法的全局收斂能力和搜索速度，提出了一種新的自適應的信息量更新策略。
當問題規(guī)模較大時，由于信息量揮發(fā)系數(shù)的存在，使那些從未被搜索過的路徑上的信息量減小到接近于0，從而降低了算法在這些路徑上的搜索能力，反之，當某條路徑中信息量較大時，這些路徑中的信息量增大，搜索過的路徑再次被選擇的機會就會變得較大，這也影響了算法的全局搜索能力，此時通過固定地變化揮發(fā)系數(shù)雖然可以提高全局搜索能力，但卻使算法的收斂速度降低，因而提出一種自適應的改變
值的方法，將信息素更新公式：
其中
是一個與收斂次數(shù)m成正比的函數(shù)，收斂次數(shù)m越多的取值越大，如：
=連續(xù)收斂次數(shù)
，
這里c為常數(shù)，根據(jù)解的分布情況自適應地進行信息量的更新，從而動態(tài)地調(diào)整各路徑上的信息量強度，使螞蟻既不過分集中也不過分分散，從而避免了早熟和局部收斂，提高全局搜索能力。
6. 結 論
蟻群算法是一種新型的進化算法，它與其它進化算法同樣存在易陷入局部最優(yōu)值的缺點，通過自適應調(diào)整后的改進蟻群算法可以提高算法的全局搜索能力和收斂性能。改進后的蟻群算法具有更好的穩(wěn)定性和收斂性。對傳統(tǒng)蟻群算法容易出現(xiàn)早熟和停滯現(xiàn)象的缺陷，提出了一種動態(tài)更新信息素的蟻群算法。實驗表明，改進的蟻群算法具有比傳統(tǒng)蟻群算法更強的搜索全局最優(yōu)解的能力，并具有更好的穩(wěn)定性和收斂性。
參考文獻 :
[1] 楊德芹，一種自適應蟻群算法及其應用[J]，軟件導刊，2007·11
[2] 張紀會，自適應蟻群算法[J]，控制理論與應用 ，2000.2
[3] 周燕霞，一種自適應信息素改進蟻群算法[J]，計算機系統(tǒng)應用，2009.10
[4] 李士勇，蟻群優(yōu)化算法及其應用研究進展，計算機測量與控制，2003
