蟻群算法發(fā)展以及在具體領(lǐng)域的應(yīng)用探究

梁晶

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

關(guān)鍵詞：蟻群算法；優(yōu)勢與不足；數(shù)據(jù)模型；應(yīng)用領(lǐng)域

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

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

蟻群算法及應(yīng)用研究

二、蟻群算法的優(yōu)勢與不足：

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

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

2.3算法模型不局限于具體的應(yīng)用，可以通過數(shù)學(xué)模型進行拓展使用，應(yīng)用在多個領(lǐng)域，具有很強的魯棒性。

2.4針對目標(biāo)為求解集合，也就是對應(yīng)的蟻群，不是以最佳為目標(biāo)，而是解集的集群較優(yōu)為目標(biāo)。

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

三、蟻群算法應(yīng)用舉例：

3.1貨郎問題

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

3.2題庫出卷策略問題：

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

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

結(jié)束語：了解蟻群算法的工作思想，從編碼與開發(fā)角度，嘗試實現(xiàn)蟻群算法的應(yīng)用。加深對蟻群算法的理解，從優(yōu)勢出發(fā)，揚長避短，利用算法融合提升蟻群算法的工作前景。

參考文獻：

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

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

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

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

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

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

[7]于海璁，陸鋒.一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J].測繪學(xué)報.2014（01）