李樹嵩

摘 要：該文就蟻群算法的起源進(jìn)行了研究，介紹了蟻群算法的原理和作用。同時(shí)介紹了蟻群算法的應(yīng)用領(lǐng)域并以舉例的方式具體介紹了如何讓蟻群算法在軟件系統(tǒng)中發(fā)揮作用。

關(guān)鍵詞：遺傳算法 商旅問題 考試系統(tǒng) 算法實(shí)現(xiàn) 軟件編程

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2017）02（c）-0138-02

1 蟻群算法的簡(jiǎn)介

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

蟻群算法基本思想：蟻群能夠在初次到達(dá)的地點(diǎn)，迅速地找到最短、最優(yōu)的路徑。那么它們是如何實(shí)現(xiàn)的呢。它們可以通過分泌一種化學(xué)物質(zhì)，在路徑中留下氣味。其他螞蟻可以根據(jù)這種氣味，發(fā)現(xiàn)其他螞蟻所走的路徑，繼續(xù)前行，同時(shí)自身釋放出氣味（這種能釋放出氣味的化學(xué)物質(zhì)我們稱之為信息素）這種信息素還擁有另一個(gè)特性，就是隨著時(shí)間而揮發(fā)。因此走得多的路徑，會(huì)因?yàn)樾畔⑺氐牟粩嗬鄯e而氣味濃重，走得少的路徑信息素會(huì)不斷揮發(fā)而消散。因此，蟻群會(huì)找到最多螞蟻?zhàn)叩穆窂?，同時(shí)越短的路徑揮發(fā)得越少，所以大量蟻群有機(jī)會(huì)走到最短路徑當(dāng)中。從某種意義上來說，蟻群算法也是遺傳算法的一種，利于尋找最短或者最優(yōu)路徑，具備算法的并行機(jī)制，能夠解決生活中許多的實(shí)際問題，下文會(huì)有所介紹。

2 蟻群相關(guān)算法介紹

2.1 相關(guān)算法類型

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

2.2 蟻群算法特性

在蟻群算法中，為了實(shí)現(xiàn)對(duì)真實(shí)螞蟻覓食群體行為的研究，將真實(shí)螞蟻抽象為人工螞蟻，具有如下特點(diǎn)。

首先，能夠像真實(shí)螞蟻一樣在經(jīng)過的路徑上留下信息素，而且使信息素隨著時(shí)間揮發(fā)，在選擇路徑時(shí)不會(huì)被前面人工螞蟻留存的信息所局限。其次，人工螞蟻并不能處在連續(xù)的空間，而是離散的空間，所以它們的運(yùn)動(dòng)也是從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的轉(zhuǎn)換。人工螞蟻具有一定的智能，可以從問題的特征中得到啟發(fā)，依據(jù)規(guī)律而不是完全的根據(jù)可能概率來實(shí)現(xiàn)。

3 蟻群算法應(yīng)用實(shí)例

蟻群算法已經(jīng)廣泛應(yīng)用于多個(gè)領(lǐng)域，由于它適合解決商旅、背包、著色、車輛調(diào)度等問題。所以在工業(yè)生產(chǎn)、數(shù)據(jù)通信、軍事運(yùn)輸?shù)确矫娑及l(fā)揮了出色的作用。該文就商旅問題和測(cè)評(píng)系統(tǒng)開發(fā)方面的應(yīng)用實(shí)例進(jìn)行如下說明。

3.1 商旅問題蟻群算法實(shí)例

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

3.2 蟻群算法在網(wǎng)絡(luò)測(cè)評(píng)系統(tǒng)中的應(yīng)用

蟻群算法在網(wǎng)絡(luò)測(cè)評(píng)系統(tǒng)中，主要是應(yīng)用在試卷的生成模塊當(dāng)中。在試卷生成模塊當(dāng)中主要發(fā)揮了兩個(gè)方面的作用。第一個(gè)方面是實(shí)現(xiàn)試卷的難度數(shù)值控制；第二個(gè)方面是實(shí)現(xiàn)試卷的有效性。兩者不能簡(jiǎn)單從字面看出具體含義，具體說明如下。

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

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

4 結(jié)語

蟻群算法來源于生物群體，與遺傳算法、群體算法有著相通之處，便于解決最優(yōu)最短路徑求解問題。在不斷發(fā)展中，算法也不斷的進(jìn)行拓展，應(yīng)用的領(lǐng)域也越來越多，是值得研究、有實(shí)際應(yīng)用意義、存在拓展空間的算法。

參考文獻(xiàn)

[1] 周建新，楊衛(wèi)東，李擎.求解連續(xù)函數(shù)優(yōu)化問題的改進(jìn)蟻群算法及仿真[J].系統(tǒng)仿真學(xué)報(bào)，2009（6）：1685-1688.

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

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

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

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

[6] 劉利強(qiáng)，戴運(yùn)桃，王麗華.蟻群算法參數(shù)優(yōu)化[J].計(jì)算機(jī)工程.2008（11）：208-210.

[7] 梁亮，郭波.基于混合蟻群算法的產(chǎn)品開發(fā)過程優(yōu)化方法[J].系統(tǒng)工程理論與實(shí)踐.2009（10）：118-128.