蟻群算法及應用研究

李樹嵩

摘 要：該文就蟻群算法的起源進行了研究，介紹了蟻群算法的原理和作用。同時介紹了蟻群算法的應用領域并以舉例的方式具體介紹了如何讓蟻群算法在軟件系統中發揮作用。

關鍵詞：遺傳算法 商旅問題 考試系統 算法實現 軟件編程

中圖分類號：TP18 文獻標識碼：A 文章編號：1674-098X（2017）02（c）-0138-02

1 蟻群算法的簡介

蟻群算法的思想最早來源于生物群體，人們通過觀察發現，一些生物群體例如螞蟻群體、蜜蜂群體等，它們的智商雖然很低，但是這些群體在覓食、尋找路徑或者群體工作時卻能體現出超高的能力。人們進而展開分析，通過借鑒它們的行為，轉換為具體思想，用以解決具體的數學問題，同時通過編程將算法實現，解決實際生活與工作的問題。

蟻群算法基本思想：蟻群能夠在初次到達的地點，迅速地找到最短、最優的路徑。那么它們是如何實現的呢。它們可以通過分泌一種化學物質，在路徑中留下氣味。其他螞蟻可以根據這種氣味，發現其他螞蟻所走的路徑，繼續前行，同時自身釋放出氣味（這種能釋放出氣味的化學物質我們稱之為信息素）這種信息素還擁有另一個特性，就是隨著時間而揮發。因此走得多的路徑，會因為信息素的不斷累積而氣味濃重，走得少的路徑信息素會不斷揮發而消散。因此，蟻群會找到最多螞蟻走的路徑，同時越短的路徑揮發得越少，所以大量蟻群有機會走到最短路徑當中。從某種意義上來說，蟻群算法也是遺傳算法的一種，利于尋找最短或者最優路徑，具備算法的并行機制，能夠解決生活中許多的實際問題，下文會有所介紹。

2 蟻群相關算法介紹

2.1 相關算法類型

首先，ACO算法，以個體為研究點，每個螞蟻釋放自己的信息素，其余螞蟻發現信息素并通過路徑的濃度來進行路徑選擇。通過揮發特色，讓該段路徑實現濃度的最大化，從而尋找到最優解。其次，還有AS算法，最大最小、最優最差的算法設計。再次，微粒群算法，也是最優算法的一種，借鑒于飛鳥的生活習性，利用迭代的數學方法，進行最優判斷，常用于神經網絡的建立。最后，機器人群體算法，既然生物可以，那人們大膽假設，利用人工智能做出的機器人也可以通過特性，實現復雜的、更高程度的自動化工作。所以以協調配合為目的，促進任務完成，這些都是以最優選擇或者協調通信為目的的算法，具有相通性。

2.2 蟻群算法特性

在蟻群算法中，為了實現對真實螞蟻覓食群體行為的研究，將真實螞蟻抽象為人工螞蟻，具有如下特點。

首先，能夠像真實螞蟻一樣在經過的路徑上留下信息素，而且使信息素隨著時間揮發，在選擇路徑時不會被前面人工螞蟻留存的信息所局限。其次，人工螞蟻并不能處在連續的空間，而是離散的空間，所以它們的運動也是從一個點到另一個點的轉換。人工螞蟻具有一定的智能，可以從問題的特征中得到啟發，依據規律而不是完全的根據可能概率來實現。

3 蟻群算法應用實例

蟻群算法已經廣泛應用于多個領域，由于它適合解決商旅、背包、著色、車輛調度等問題。所以在工業生產、數據通信、軍事運輸等方面都發揮了出色的作用。該文就商旅問題和測評系統開發方面的應用實例進行如下說明。

3.1 商旅問題蟻群算法實例

商旅問題是一個經典的數學問題，某人要去不同的地點，從起點出發，每個節點遍歷一遍并且只走一次，有哪些走法，哪一種走法是最優選擇成為這個問題研究的關鍵。其實這個問題入關地點數目不多，就并不復雜。但是它如同漢諾塔一樣，是伴隨著地點數目增多，路徑數量呈爆炸性增長。所以要引進蟻群算法進行路徑選擇。蟻群算法實現商旅問題的關鍵是要符合只走一次的特性，所以在所走路徑中要不斷進行路線記錄，同時設置違例行為，一旦路線重復，設置為不可走，不可選擇項目。而且螞蟻的下一次路徑選擇要根據概率算法進行計算獲得并不斷積累前面螞蟻的路徑特性。

3.2 蟻群算法在網絡測評系統中的應用

蟻群算法在網絡測評系統中，主要是應用在試卷的生成模塊當中。在試卷生成模塊當中主要發揮了兩個方面的作用。第一個方面是實現試卷的難度數值控制；第二個方面是實現試卷的有效性。兩者不能簡單從字面看出具體含義，具體說明如下。

試卷難度控制作用說明：在線測評系統試卷采用具體算法，從題庫當中生成出來。為了防止作弊行為的發生，每套試卷的題目是不同的，但要保證試題的類型和數量是相同的，從而體現一定的公平性。但是這樣的算法存在缺陷，只是簡單的隨機算法，要保證試卷的高質量，應該對每張試卷的難度有所控制，讓整張試卷的難度數值居中，避免題目過難或者過于簡單。過難或者過于簡單的試卷是不利于考察考試者的真實水平的，也只有難度水平居中才能夠進一步保證考試的公平性。可想而知，如果只是題目數量相同，試題不同，但試題難度相差很大，這明顯是不公平的，也無法體現考核意義。使用蟻群算法實現試卷難度系數控制，要設置難度算子，對每道題目，通過測試與實驗建立難度數值，存儲難度算子表。不妨讓難度系數在0與1之間，那么0.5當然是居中的數值。但是這種理想的目標是難以達成的，通過算法計算，難度系數達到0.5左右一定范圍空間，就實現了試題難度的控制。在實現的時候不妨把行程符合難度空間的選擇方式作為最優路徑的尋找來理解。

蟻群算法試卷有效性應用說明：一般來說，試卷的有效性，是在保證難度控制的基礎上進行的。當采用蟻群算法進行了難度控制，讓每張試卷處于居中區域的時候，容易出現一個問題，就是采用的試題難度數值接近，所以在抽取試題的時候，行程的有效組合不夠。用深入淺出的方式說，就是行程的符合難度范圍的組合就只有幾種，那么形成的試卷也就是這幾種組合的重復，這就與每套試卷盡量不同、防止作弊的初衷相違背。解決方法可以是擴大題庫范圍，避免題目單一。第二種就是通過算法實現不同的組合方式，只要在符合難度范圍的區間內就可以。舉例說明不是要每套試卷都達到0.5難度算子數值。例如0.57，0.43都可以接受，只要符合預先設立的難度算子范圍值域就可以。可能會有人提出疑問，蟻群算法不是要尋找最優路徑嗎？那0.5為最優，故意拓展的范圍與算法有些違背如何實現？其實這也是蟻群算法可以解決的問題。蟻群算法可以解決最大與最小，最優與最短等問題。反向思維，可以解決最擁堵問題。如果都走0.5難度系數路徑，那么形成擁堵，這與采用算法解決擁堵是一樣的。綜上所述，試卷的有效性要在難度控制的前提下完成，對蟻群算法實現提出了更高的要求。

4 結語

蟻群算法來源于生物群體，與遺傳算法、群體算法有著相通之處，便于解決最優最短路徑求解問題。在不斷發展中，算法也不斷的進行拓展，應用的領域也越來越多，是值得研究、有實際應用意義、存在拓展空間的算法。

參考文獻

[1] 周建新，楊衛東，李擎.求解連續函數優化問題的改進蟻群算法及仿真[J].系統仿真學報，2009（6）：1685-1688.

[2] 李克東，劉國棟，任華.基于蟻群算法的機器人路徑規劃[J].微計算機信息，2009（5）：215-217.

[3] 裴振奎，李華，宋建偉，等.蟻群聚類算法研究及應用[J].計算機工程與設計，2008（19）：5009-5013.

[4] 張亞鳴，雷小宇，楊勝躍，等.多機器人路徑規劃研究方法[J].計算機應用研究，2008（9）：2566-2569.

[5] 楊志曉，郭勝國.基于改進蟻群算法的機器人路徑規劃算法[J].微計算機信息，2008（20）：252-253.

[6] 劉利強，戴運桃，王麗華.蟻群算法參數優化[J].計算機工程.2008（11）：208-210.

[7] 梁亮，郭波.基于混合蟻群算法的產品開發過程優化方法[J].系統工程理論與實踐.2009（10）：118-128.