蟻群算法發展以及在具體領域的應用探究

梁晶

摘 要：蟻群算法是生物算法的一種，是根據模仿蟻群在尋找最優、最短路徑方面的能力，模仿蟻群的搬運食物的工作思想，形成數學算法，從而實現問題的優化。具體應用領域眾多，本文就蟻群算法的思想，工作模型的塑造，以及存在的優勢與不足進行了詳細介紹，就未來發展方向進行了展望。

關鍵詞：蟻群算法；優勢與不足；數據模型；應用領域

一、蟻群算法思想以及工作原理：

蟻群算法是智能算法的一種，借鑒的是大量蟻群在搬運食物以及蟻群需要的物品時候，總能夠找到最短的搬運路徑，從而大大降低了搬運的時間，極大程度的提高了工作效率，找到了一些問題的優化路徑以及解決方法。通過生物學方式，人們找到了蟻群尋找最短路徑的方式。螞蟻的并不是擁有很高的智商，他們最初在進行路徑選擇的時候，是進行隨機選擇的，但在路徑的行走過程中，螞蟻釋放出一種信息熵，也就是一種特殊的氣味，而這種氣味的特點是能夠隨著時間進行揮發，從而使得氣味變淡。那么，我們就會發現，越短的路徑信息熵揮發的越少，氣味越濃，也就會吸引更多的螞蟻，根據氣味進行路徑的選擇。同時，越多的螞蟻走過較短路徑，也會使得信息熵濃度升高，從而讓蟻群獲得優解，獲取較短的搬運路徑。那么把這個思想應用在算法當中，適合路徑選擇，解集的優化等問題的解決。可以具化在多個領域當中。

蟻群算法及應用研究

二、蟻群算法的優勢與不足：

2.1蟻群算法屬于進化算法之一，蟻群算法也屬于并行算法思想范疇之內。所以具有較好的并行計算能力。

2.2收斂速度快，尋找最優時間短。這是因為這種算法具有正反饋的特點，如思想所描述的，信息熵越高，路徑就可能越短，那么越多的螞蟻會選擇相應的路徑，同時每只螞蟻作為個體，又會釋放自身的信息熵，使得信息熵的濃度更高，正向反饋。

2.3算法模型不局限于具體的應用，可以通過數學模型進行拓展使用，應用在多個領域，具有很強的魯棒性。

2.4針對目標為求解集合，也就是對應的蟻群，不是以最佳為目標，而是解集的集群較優為目標。

2.5問題與不足：在蟻群算法使用中，初始路徑選集范圍過廣，搜索范圍相對較大，耗費較大的計算和搜素時間，不容易完成任務。其次，在搜索到一定步驟后，容易出現無解狀態，尤其是各個路徑相對接近，難以區分的時候，這個時候單純使用蟻群算法難以滿足問題的優化目標。

三、蟻群算法應用舉例：

3.1貨郎問題

路線求解問題：當有n個城市，一個旅行者由其中某一個需市作為起點出發，需要不重復地經過所以結點后回到原點，求其最短路線。當城市數等于24個時，只需要1s時間就可以計算完成，但隨著城市數增加，計算難度呈幾何級數增大，當城市數增加到30個時，計算時間需要10年多，計算難度很大。在這里用蟻群算法來解決。城市個數用n表示， 規定每只螞蟻選擇的城市必須是不曾到過的，只有到達過所有的城市后才到回到出發城市。所以在這里為每只螞蟻建立一個禁忌表tabuk（k=1，2，…，m），將第k只螞蟻訪問過的城市放入禁忌表中，禁忌表不是固定不變的，隨著第k只螞蟻的運動進行動態調整。每只螞蟻選擇要訪問的下一個城門需要通過概率函數來實現，概率函數并不是隨機的，而是與兩個城市間的距離和兩個城市間的信息素大小有關的。隨著時間流逝，路徑上如果遺留的信息素太多就消弱啟發信息的作用，所以在每只螞蟻每訪問完一個城市或者訪問完所有城市后，需要更新信息素。

3.2題庫出卷策略問題：

題庫組卷策略中使用蟻群算法，一般是為了提升組卷的成功率與組卷時間。是為了智能組卷系統服務。進行的作用是要形成試卷基本約束相同的試卷（如分數、類型、題目）等，但試卷又并不完全相同，這種方式在國外的認證考試中一直在使用。為了公平，體現智能化能力，要控制難度范圍，將難度控制在中等難度范圍之內。同時要關注區分度的計算，所謂區分度，是每道試題的難度，并不能根據專家和老師進行評分而獲得，更加不能針對不同群體，一成不變。可以根據針對性測試，通過算法公式進行計算，而進行難度數值設定，這就是試題難度區分度的計算過程。而智能組卷如果單純使用蟻群算法容易出現計算失敗，同時在計算初期速度較慢，如果使用遺傳算法，在初期雖然計算較快，但是伴隨迭代次數的增多，容易出現后期計算減慢，同時遺傳算法是最優解不是針對整個群體，因此，蟻群算法與遺傳算法的整合，適合組卷策略的智能實現。

發展與展望：蟻群算法發展的時間并不很長，適合多種問題的優化，同時是針對集合的優化算法，同時又具有并行算法和進化算法的特點，還有很大的發展空間，尤其是在與其它算法的融合方面，現在很多系統都采用蟻群算法和其它算法的融合，從而實現提升算法速度，保證算法成功率的目的。蟻群算法發展空間巨大。

結束語：了解蟻群算法的工作思想，從編碼與開發角度，嘗試實現蟻群算法的應用。加深對蟻群算法的理解，從優勢出發，揚長避短，利用算法融合提升蟻群算法的工作前景。

參考文獻：

[1]陳成，邢立寧.求解柔性作業車間調度問題的遺傳—蟻群算法[J].計算機集成制造系統.2011（03）

[2]王萬良，趙澄，熊婧，徐新黎.基于改進蟻群算法的柔性作業車間調度問題的求解方法[J].系統仿真學報.2008（16）

[3]張超勇，饒運清，李培根，邵新宇.柔性作業車間調度問題的兩級遺傳算法[J].機械工程學報.2007（04）

[4]張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業車間調度問題[J].計算機集成制造系統.2007（02）

[5]張超勇，饒運清，李培根，劉向軍.求解作業車間調度問題的一種改進遺傳算法[J].計算機集成制造系統.2004（08）

[6]劉建華，楊建國，劉華平，耿鵬，高蒙.基于勢場蟻群算法的移動機器人全局路徑規劃方法[J].農業機械學報.2015（09）

[7]于海璁，陸鋒.一種基于遺傳算法的多模式多標準路徑規劃方法[J].測繪學報.2014（01）