蘇前義

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

蟻群算法沒有強力的數(shù)學基礎作為支撐，在實際運用中依然存在一些不足之處，希望有越來越多的人加入研究的行列，有越來越多的學者關注蟻群算法，推動蟻群算法的發(fā)展，更好地為人類的學習、工作、生活做貢獻。

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

中圖分類號： TP301.6 文獻標識碼： A 文章編號： 1673-1069（2016）32-158-2

1 蟻群算法的提出

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

2 蟻群算法的應用

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

2.1 旅行商問題

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

2.2 二次分配問題

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

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

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

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

電路是錯綜復雜的，需要有一個點來支撐所有的電路，確保電路有序。

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

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

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

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

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

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

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

v[] 是粒子的速度， persent[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand （） 是介于（0， 1）之間的隨機數(shù). c1， c2 是學習因子. 通常 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ù)值對應到相對應的蟻群算法中去，新的參數(shù)值會要求蟻群算法做出新的調(diào)整，在把這時的蟻群算法的參數(shù)值設定為初始值；

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

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

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

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

①描述簡單，來自生活，理解起來也相對來說比較容易；

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

③算法實施起來很容易，并且求解速度快；

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

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

⑥和其他算法相比，算法具有很強的收斂性；

⑦沒有什么特殊的約束條件，個體間是獨立的，不會影響到其他的粒子，具有很強的魯棒性。

4 結束語

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

參 考 文 獻

[1] 石華瑀.改進的蟻群算法在實際VRP中的應用研究[D].山東大學，2012.

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