蟻群算法的運(yùn)用及其優(yōu)化分析

蘇前義

摘 要：生物科學(xué)領(lǐng)域在快速的發(fā)展，人類善于從自然界中去學(xué)習(xí)，研究自然界，為自身的學(xué)習(xí)、工作、生活創(chuàng)造便利的條件。蟻群算法正是受到螞蟻尋食所創(chuàng)造的一種啟發(fā)性的算法。大量的研究證明，蟻群算法具有魯棒性、并行性、正反饋性，是一種自組織的算法，但是它運(yùn)行所需要的時(shí)間長(zhǎng)，有時(shí)甚至?xí)霈F(xiàn)停滯的現(xiàn)象，但和遺傳算法、模擬退火算法等其他算法相比依然具有不可忽視的優(yōu)勢(shì)。

蟻群算法沒有強(qiáng)力的數(shù)學(xué)基礎(chǔ)作為支撐，在實(shí)際運(yùn)用中依然存在一些不足之處，希望有越來(lái)越多的人加入研究的行列，有越來(lái)越多的學(xué)者關(guān)注蟻群算法，推動(dòng)蟻群算法的發(fā)展，更好地為人類的學(xué)習(xí)、工作、生活做貢獻(xiàn)。

關(guān)鍵詞：蟻群算法；蟻群算法的應(yīng)用；粒子群算法；優(yōu)化分析

中圖分類號(hào)： TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1673-1069（2016）32-158-2

1 蟻群算法的提出

科學(xué)家們?cè)谘芯咳壕有岳ハx的時(shí)候發(fā)現(xiàn)，雖然它們單個(gè)只是簡(jiǎn)單的個(gè)體，但是它們一起合作卻能一起完成復(fù)雜的工作。昆蟲的這種群體生物智能特征，吸引了一些學(xué)者的目光。意大利學(xué)者M(jìn).Dorigo等人在研究螞蟻的覓食過程中發(fā)現(xiàn)，螞蟻似乎有一種本能，總能找到食物，總能找到巢穴與食物之間的最短路徑。螞蟻?zhàn)鳛橐环N群居性昆蟲，它們本身的視線很差，卻能找到大量的食物。經(jīng)過長(zhǎng)期的觀察與研究，于1991年M.Dorigo等人首次提出蟻群算法。

2 蟻群算法的應(yīng)用

如今蟻群算法已經(jīng)深入到我們生活的方方面面，在交通、智能、通信技術(shù)方面有著廣泛的運(yùn)用，在求解優(yōu)化組合、網(wǎng)絡(luò)路由問題、連續(xù)性空間優(yōu)化問題、聚類分析、圖像識(shí)別、電網(wǎng)故障分析等領(lǐng)域的應(yīng)用已經(jīng)取得了良好的效果。具體包括以下幾種：

2.1 旅行商問題

蟻群算法最早是應(yīng)用旅行商問題的解決，該問題的核心就是要求經(jīng)過所有的城市，每個(gè)城市經(jīng)過一次，還要返回到原來(lái)的出發(fā)點(diǎn)，這條線路要求是最短的。眾多的實(shí)驗(yàn)研究結(jié)果表明，蟻群算法遠(yuǎn)遠(yuǎn)高于遺傳算法、模擬退火法等其他優(yōu)化算法。

2.2 二次分配問題

最開始的二次分配問題指的是，把m個(gè)工廠分配在m個(gè)城市，要求分配的時(shí)候所用的花費(fèi)是最少的。這是蟻群算法在旅行商問題后的又一大應(yīng)用。

2.3 車間任務(wù)調(diào)度問題

車間任務(wù)調(diào)度問題指的是一定數(shù)量的機(jī)器在一定的時(shí)間里完成一定的任務(wù)量，要求所有的機(jī)器同時(shí)運(yùn)行，有序的操作，但所要的時(shí)間是最短的。

2.4 大規(guī)模集成電路問題

電路是錯(cuò)綜復(fù)雜的，需要有一個(gè)點(diǎn)來(lái)支撐所有的電路，確保電路有序。

2.5 連續(xù)對(duì)象優(yōu)化問題

螞蟻一旦選擇了一條目標(biāo)，會(huì)一直向著目標(biāo)前進(jìn)，選擇的路線是固定的，空間不是完整的，是分散的，局部的，若空間是線性的或非線性的連續(xù)空間，則相對(duì)較弱。使用蟻群算法解決連續(xù)對(duì)象優(yōu)化問題，還要求信息素的濃度函數(shù)等循環(huán)過程。

3 蟻群算法的優(yōu)化分析

蟻群算法是一種智能化算法，被廣泛運(yùn)用到各個(gè)方面，而且性能優(yōu)良。但也看到蟻群算法要花費(fèi)大量的時(shí)間，有時(shí)甚至?xí)霈F(xiàn)停滯的現(xiàn)象。在蟻群算法中起著關(guān)鍵作用的就是參數(shù)的選擇，下面將基于粒子群參數(shù)優(yōu)化，提出一種新的改進(jìn)蟻群算法的算法。

粒子群優(yōu)化算法通常也被稱作粒子群算法、微粒群算法。這是一種模仿鳥類捕食的算法。鳥類在尋找食物的時(shí)候，目的是隨機(jī)地，也是多樣的，但區(qū)域里只有一塊食物，并且它們也不知道食物在哪里。應(yīng)如何找到食物，肯定是在食物附近的鳥類最先找到的，所以說(shuō)在食物附近的鳥類是最有利的。這引起了一些學(xué)者的注意，由Kennedy等博士提出，認(rèn)為這是一種群體智能。在粒子群算法中把區(qū)域里的每只鳥都看作是一個(gè)粒子。每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。在初始化中，一群隨機(jī)無(wú)序的粒子，要通過迭代才能找到最優(yōu)解。要想找到最優(yōu)解，每個(gè)粒子在迭代時(shí)通過更新兩個(gè)極值來(lái)更新自己的信息素。第一個(gè)得到的解就是粒子本身所要尋找的最優(yōu)解，另一個(gè)極值就是相對(duì)于整個(gè)種群來(lái)說(shuō)最優(yōu)解。第一個(gè)就是另外也可以不用整個(gè)種群而只是用其中一部分最優(yōu)粒子的鄰居，那么在所有鄰居中的極值就是局部極值。要想找到這兩個(gè)最優(yōu)值時(shí)，粒子要及時(shí)更新自己的速度和新的位置，根據(jù)如下的公式：

v[] = v[] + c1 * rand（） * （pbest[] - present[]） + c2 * rand（） * （gbest[] - present[]） （a）

present[] = persent[] + v[] （b）

v[] 是粒子的速度， persent[] 是當(dāng)前粒子的位置. pbest[] and gbest[] 如前定義 rand （） 是介于（0， 1）之間的隨機(jī)數(shù). c1， c2 是學(xué)習(xí)因子. 通常 c1 = c2 = 2.

程序的偽代碼可以用如下的表示：

For each particle

____Initialize particle

END

Do

____For each particle

________Calculate fitness value

________If the fitness value is better than the best fitness value （pBest） in history

____________set current value as the new pBest

____End

____Choose the particle with the best fitness value of all the particles as the gBest

____For each particle

________Calculate particle velocity according equation （a）

________Update particle position according equation （b）

____End

While maximum iterations or minimum error criteria is not attained

利用粒子群優(yōu)化蟻群算法的基本步驟：

步驟一：設(shè)立初始值，一定數(shù)量的粒子；

步驟二：將每個(gè)粒子所對(duì)應(yīng)的參數(shù)值對(duì)應(yīng)到相對(duì)應(yīng)的蟻群算法中去，新的參數(shù)值會(huì)要求蟻群算法做出新的調(diào)整，在把這時(shí)的蟻群算法的參數(shù)值設(shè)定為初始值；

步驟三：根據(jù)蟻群算法的計(jì)算方式判斷是優(yōu)值還是差值；

步驟四：根據(jù)公式v[] = v[] + c1 * rand（） * （pbest[] - present[]） + c2 * rand（） * （gbest[] - present[]） （a）present[] = persent[] + v[] （b）改變粒子的速度和位置；

步驟五：若是得到的結(jié)果已經(jīng)是最優(yōu)解了，或者已經(jīng)沒有最優(yōu)解了，則算法結(jié)束，反之，繼續(xù)步驟二的操作。

信息素的更新決定了蟻群算法的求解質(zhì)量。改進(jìn)后的信息素只是用與每個(gè)粒子的一次移動(dòng)，并且相互間是獨(dú)立的，沒有關(guān)聯(lián)的，一旦結(jié)束后，所有的數(shù)據(jù)會(huì)消失掉，不會(huì)有所保留。粒子群優(yōu)化算法作為一種啟發(fā)式算法，具有下面的眾多優(yōu)點(diǎn)：

①描述簡(jiǎn)單，來(lái)自生活，理解起來(lái)也相對(duì)來(lái)說(shuō)比較容易；

②相互間是獨(dú)立的，打破了要求優(yōu)化問題需要是連續(xù)性的問題；

③算法實(shí)施起來(lái)很容易，并且求解速度快；

④和其他的算法相比，不需要龐大的個(gè)體，小眾的個(gè)體即可實(shí)現(xiàn)算法；

⑤大部分的參數(shù)是不需要去調(diào)整的，只有小部分的參數(shù)是需要去調(diào)整的；

⑥和其他算法相比，算法具有很強(qiáng)的收斂性；

⑦沒有什么特殊的約束條件，個(gè)體間是獨(dú)立的，不會(huì)影響到其他的粒子，具有很強(qiáng)的魯棒性。

4 結(jié)束語(yǔ)

蟻群算法最先是用來(lái)解決旅行商問題，如今蟻群算法在各個(gè)方面被運(yùn)用，得到了一定的效果。但是和遺傳算法、模擬退火算法、微粒子算法相比，雖然得到的解更加優(yōu)化，但是蟻群算法沒有系統(tǒng)的分析方法，同時(shí)它的數(shù)學(xué)基礎(chǔ)也不是很強(qiáng)大。在實(shí)際的操作過程中，參數(shù)的選取比較復(fù)雜。雖然在一些領(lǐng)域運(yùn)用，但運(yùn)用技術(shù)不成熟，還是習(xí)慣采用傳統(tǒng)的方式。

參 考 文 獻(xiàn)

[1] 石華瑀.改進(jìn)的蟻群算法在實(shí)際VRP中的應(yīng)用研究[D].山東大學(xué)，2012.

[2] 孟凡聰.優(yōu)化的蟻群算法在快速公交系統(tǒng)中的應(yīng)用研究[D].湖南大學(xué)，2011.