蟻群算法的運用及其優化分析

蘇前義

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

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

關鍵詞：蟻群算法；蟻群算法的應用；粒子群算法；優化分析

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

1 蟻群算法的提出

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

2 蟻群算法的應用

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

2.1 旅行商問題

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

2.2 二次分配問題

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

2.3 車間任務調度問題

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

2.4 大規模集成電路問題

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

2.5 連續對象優化問題

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

3 蟻群算法的優化分析

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

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

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

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

v[] 是粒子的速度， persent[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand （） 是介于（0， 1）之間的隨機數. 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

利用粒子群優化蟻群算法的基本步驟：

步驟一：設立初始值，一定數量的粒子；

步驟二：將每個粒子所對應的參數值對應到相對應的蟻群算法中去，新的參數值會要求蟻群算法做出新的調整，在把這時的蟻群算法的參數值設定為初始值；

步驟三：根據蟻群算法的計算方式判斷是優值還是差值；

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

步驟五：若是得到的結果已經是最優解了，或者已經沒有最優解了，則算法結束，反之，繼續步驟二的操作。

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

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

②相互間是獨立的，打破了要求優化問題需要是連續性的問題；

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

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

⑤大部分的參數是不需要去調整的，只有小部分的參數是需要去調整的；

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

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

4 結束語

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

參 考 文 獻

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

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