殷玲玲 蘇劍鋒

摘要：蟻群算法是人工智能領(lǐng)域的一種模擬進化算法，在求解復(fù)雜優(yōu)化問題方面具有一定的優(yōu)勢，是一種很有發(fā)展前景的計算智能方法。本文首先了解并分析了蟻群算法的基本原理，接著闡述了它的經(jīng)典應(yīng)用，最后總結(jié)了該算法的優(yōu)點與不足。

Abstract： Ant colony algorithm is a simulated evolutionary algorithm in the field of artificial intelligence. It has certain advantages in solving complex optimization problems and is a promising computational intelligence method. This paper first analyzes the basic principle of ant colony algorithm， then expounds its classical application， and finally summarizes the advantages and disadvantages of the algorithm.

關(guān)鍵詞：人工智能;蟻群算法;應(yīng)用

Key words： artificial intelligence;ant colony algorithm;application

中圖分類號：TP301.6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2019）08-0156-04

0 ?引言

20世紀90年代中期，Italy科學(xué)家M.Dorigo根據(jù)動物的覓食過程，首先引出了蟻群算法（Ant Colony Optimization，ACO）。部分研究學(xué)者將蟻群算法引入到TSP（Traveling Saleman Problem）旅商問題、JSP（Job-shop Scheduling Problem）調(diào)度問題和QAP（Quadratic Assignment Problem）分配問題的研究之中，并取得了較好的研究成果。蟻群算法雖然提出的時間較短，但由于其分布運算和正反饋等特點，易于發(fā)現(xiàn)問題最優(yōu)解，現(xiàn)已推廣應(yīng)用到多個研究領(lǐng)域。

1 ?蟻群算法的基本原理

ACO算法是模仿生態(tài)界中螞蟻、昆蟲的覓食行為提出的，為了詳細了解該算法的基本原理，我們先對生態(tài)界中昆蟲的覓食過程進行詳細的了解。螞蟻在尋找食物行為中，螞蟻個體會散發(fā)出一種信息素（Pheromone）物質(zhì)，多個個體之間可以通過該物質(zhì)進行溝通，螞蟻個體通過探知周圍該物質(zhì)的強度來指引覓食行為的行走路徑。

如圖1所示：為螞蟻覓食路徑的尋優(yōu)過程，在圖a中，當螞蟻到達道路分岔口處時，無法確定往上最優(yōu)還是向下最優(yōu)？蟻群隨機進入兩個道路岔口，由統(tǒng)計學(xué)原理可知，螞蟻向上或向下走的幾率一樣，均為二分之一。假設(shè)所有螞蟻的行走速度一致，則b、c圖為接下來發(fā)生的螞蟻覓食行為路線。由于下方行走距離較少，則在相同的時間范圍內(nèi)有較多的覓食個體通過，進而散發(fā)出更多的Pheromone，如圖所示：虛線為螞蟻分泌信息素的強度，經(jīng)過一段時間以后，下方行走路線上聚集的信息素越來越多形成d圖，新出來覓食的螞蟻則有更大的可能性選擇下方行走路線，通過尋優(yōu)路徑的循環(huán)進行，造成局部行走路徑該信息素物質(zhì)累積。到最后，所有覓食昆蟲個體均行進在下方距離較短的覓食路線。

M.Dorigo等專家學(xué)者在螞蟻、蜜蜂等昆蟲尋找食物過程研究的基礎(chǔ)之上，提出了ACO算法。同時，將算法中的單個個體稱為“人工螞蟻”，如圖2所示，我們通過具體的實例對蟻群算法進行具體的研究。假設(shè)A點為螞蟻覓食出發(fā)點，E點為待尋覓食物目標地址，F(xiàn)C為蟻群覓食出發(fā)點A通往待尋覓食物目標點E道路上的路障，螞蟻個體不能夠翻越障礙FC到達食物源E處。設(shè)單個時間范圍內(nèi)總計有40只覓食昆蟲個體分別從出發(fā)點A到節(jié)點B和從食物源E到路徑節(jié)點D，設(shè)螞蟻個體經(jīng)過后留有蟻群信息素濃度為1，且經(jīng)過單個時間信息素發(fā)揮結(jié)束。當T=0開始階段，BC、CD、BF、FD螞蟻覓食行徑路徑上均沒有Pheromone物質(zhì)存在;在接下來的過程中，B點的螞蟻以相同的概率和速度分別往F、C出發(fā)，D點的螞蟻分別以相同的概率和速度分別往F、C點出發(fā)，由此可得：

T=1時刻，分別有40只螞蟻在B、D點;

T=2時刻，在B點和D點各有20只螞蟻，且有40只覓食螞蟻個體行進到了F點。

同時，各條線段上螞蟻揮發(fā)出的信息素濃度分別為：AB=DE=BC=CD=40，BF=FD=20。由此可見：BCD行進道路上的不同個體之間交流物質(zhì)濃度明顯高于BFD行進道路之上，隨著時間上的推移，有更多新出去覓食的昆蟲個體選擇覓食行進道路BCD，最后直至所有覓食的個體均通過BCD覓食道路外出覓食，由上可知，螞蟻覓食道路尋優(yōu)為一種通過不同個體之間信息交流溝通而得到了信息素正積累過程。

2 ?蟻群算法的模型

在個體外出覓食道路尋優(yōu)階段中，假設(shè)于某一時刻t，用bi（t）來表示地點i處的覓食個體的多少，用τij（t）用來形容由i點出發(fā)到目標點j之間行進道路上的分泌用于不同個體之間交流的信息素物質(zhì)濃度，假設(shè)總共存在m只螞蟻于n個目標點尋覓食物，dij（i，j？哿n）為覓食點i到j(luò)之間的距離，則存在等式：

本文在研究蟻群算法基本模型的過程中，假設(shè)在n個覓食節(jié)點有m只螞蟻覓食，且螞蟻在覓食過程中根據(jù)一定的因素確定下一個未訪問過的覓食節(jié)點。同時，當螞蟻由出發(fā)點移動到目標點或遍尋完所有路徑節(jié)點之后，及時將各個路徑上的分泌獲得的信息素濃度τij（t）從新更新。在覓食過程t時刻，覓食路徑節(jié)點集合C中，不同覓食節(jié)點之間的信息素分泌殘留濃度，如式（2）所示，在開始階段，不同覓食道路上用于不同個體之間交流的初始信息物質(zhì)量相同，即τij（0）=Const為常數(shù)，螞蟻在覓食遍尋過程中，根據(jù)信息素殘留濃度等一定規(guī)則確定蟻群未來的行進路線，研究學(xué)者將該算法模型規(guī)則稱之為“隨機比概率”規(guī)則，由此可得，外出覓食昆蟲個體從覓食出發(fā)點i到覓食目標點j的隨機行進概率可表述為：

式中：■表示覓食昆蟲個體k當時間為t時由覓食出發(fā)位置i到覓食行徑路徑中點j的行走轉(zhuǎn)移可行性;α表示為外出覓食昆蟲個體在覓食行進道路上用于不同個體之間用于交流的信息物質(zhì)的剩余量對蟻群轉(zhuǎn)移路線作用的誘發(fā)因子;β為啟發(fā)式信息對覓食昆蟲個體行進方向作用的期望誘發(fā)因素;■表示為螞蟻k在覓食過程中下一步可行進路徑節(jié)點，tabk為tab表，意義為記錄螞蟻k行進路線過程的路徑記錄表。螞蟻在接下的行進過程中，不能夠再次去往tab表中已經(jīng)存在記錄的覓食節(jié)點。螞蟻按照以上行進路線遍尋完所有節(jié)點，并最終形成一個閉合路徑。待所有螞蟻均完成所有地點的覓食遍尋過程，即本次覓食過程迭代完成。在下一時刻，從蟻穴新出去覓食螞蟻根據(jù)更新后的信息素濃度，進行下一次路徑迭代，并最終實現(xiàn)迭代路徑最優(yōu)過程。

同時，螞蟻在行徑過程中，移動行進規(guī)則遵循式：

式中，q表示為0到1區(qū)間范圍內(nèi)的一個隨機變量，q0為事先確定在[0，1]范圍內(nèi)的一個常數(shù)，當q的取值大于q0時，J即為由蟻群算法轉(zhuǎn)移概率■確定的下個覓食地點。在螞蟻轉(zhuǎn)移過程中，為了防止多余的信息分泌素過多引起啟發(fā)信息淹沒，因此當螞蟻完成n個覓食地點的遍歷以后，本文擬將所有的信息素物質(zhì)進行整體更新，螞蟻行走路徑行為展示出了生物記憶特征，當有新的信息記憶碎片進入到大腦之后，大腦中原有記憶的信息將伴著時間的前進慢慢的消失。由此，當所有螞蟻完成一次遍歷循環(huán)以后，n個食物源節(jié)點之間所有路徑中的信息素變化按如下方式更新：

根據(jù)以上研究成果，蟻群算法提出學(xué)者M.Dorigo結(jié)合蟻群行進過程中信息素濃度的變化規(guī)律，總結(jié)研究，分別獲得了蟻群數(shù)量（Ant-Quantity）、蟻群周期（Ant-Cycle）和蟻群密度（Ant-Density）三種蟻群算法模型，其中，蟻群算法模型，從全局遍歷出發(fā)，保證了信息素濃度隨著螞蟻行進時間的推移不斷的累加更新，和其他兩種模型相比正反饋效果明顯較強，其具體求解過程如下所示：

3 ?蟻群算法的應(yīng)用

3.1 蟻群算法求解VRP問題

本文以ACO算法在經(jīng)典商旅問題求解的過程為例，詳細闡述ACO問題求解過程的實現(xiàn)流程：

①定義系統(tǒng)在開始時刻t=0時，算法循環(huán)次數(shù)N=0，并規(guī)定最大循環(huán)次數(shù)Nmax，假設(shè)n個商旅待去城市中放置m個螞蟻（代表商旅），賦予初始階段節(jié)點i與節(jié)點j路徑上蟻群信息素初始量τij（0）=Const，且Δτij（0）=0;②設(shè)置循環(huán)次數(shù)N=N+1;③假設(shè)螞蟻路徑記錄表索引開始值1;④設(shè)置螞蟻個數(shù)定義符合K=K+1;⑤螞蟻行進過程中根據(jù)公式（2）選擇下一個城市j的行進路線;⑥更新螞蟻路徑記錄索引表tab，即把螞蟻行徑過的城市序號記錄到索引表tab中;⑦若螞蟻行經(jīng)過所有城市則跳到步驟⑧，否則執(zhí)行步驟④;⑧根據(jù)式（4）、（5）重設(shè)螞蟻行經(jīng)道路上的信息素情況;⑨若循環(huán)次數(shù)N？叟Nmax則循環(huán)過程截止，輸出螞蟻最短行走路徑，否則清空tab表，重復(fù)步驟②。

算法在TSP經(jīng)典商旅問題中的計算求解流程如圖3。

3.2 蟻群算法在配送車輛優(yōu)化過程中的應(yīng)用

3.2.1 掃描算法原理

掃描（Sweep）算法定義為：在車輛調(diào)度過程中即以指定的待配送目標位置為原點，進行順或逆時針方向掃描。在掃描進行過程中，每掃描到一個目標客戶，就根據(jù)配送車輛最大容量確定該客戶快件是否分配給該配送車輛;倘若超過該配送車輛容量限制，則換下一輛配送車輛服務(wù)該目標客戶，如此依次反復(fù)掃描，直至所有客戶待配送快件，均安排到配送車輛之上。

3.2.2 求解一般車輛調(diào)度模型

當采用ACO算法求解調(diào)度車輛（VRP）配送的過程中，本文首先采用Sweep掃描算法對所有目標點的快件逐一掃描并分配車輛。緊接著，利用ACO算法中的Ant-Cycle求解算法對目標客戶地點的服務(wù)順序智能排序。

在利用Sweep掃描算法對所有快件進行掃描并分配配送車輛的過程中，可能會獲取多種快件車輛分組情況，為了獲取最優(yōu)車輛配送調(diào)度方案，本文依據(jù)所有目標客戶點在極坐標中的角度位置分別和貨物配送中心進行Sweep掃描分析，近而獲取n（n為目標客戶數(shù)量）個相異的掃描分組情況，并可根據(jù)掃描結(jié)果獲得n種車輛配送方案，結(jié)合Ant-Cycle蟻群算法模型在以上獲得的結(jié)果中確定得出最優(yōu)的調(diào)度配送方案。具體求解過程如下：

Step1：將待配送快件分派到車輛上具體實施方法為：首先選用未使用的車輛k，在未分配的待派送快件中依據(jù)目標點位置，從角度最小開始為車輛k指定目標派送點，直到達到汽車容量上限為止，如果有剩余未分配快件，則重復(fù)上面快件配送車輛分配方法;

Step2：對已經(jīng)分配好任務(wù)的車進行如下操作確定配送地點訪問順序，設(shè)配送車輛k分配的目標集合為Vk，且|Vk|=n，設(shè)定有m只螞蟻，按照Ant-Cycle確定最優(yōu)配送路徑;

Step3：按照各配送目標點極坐標中角度的大小和車場位置，利用Sweep掃描確地定n條初始掃描線，重復(fù)n次Step1和Step2得到n種調(diào)度方案，比較得到最優(yōu)配送路徑解。

4 ?蟻群算法的優(yōu)點與不足

蟻群算法作為模仿螞蟻覓食行為的一種仿生學(xué)路徑尋優(yōu)計算方法，為研究VRP、TSP等復(fù)雜的路徑尋優(yōu)問題提供了一種新的解決思路，具有一定的先進性和智能性。但該算法起步于上世紀90年代，發(fā)展歷史不長，在具體應(yīng)用過程中仍存在有部分缺陷，下面對蟻群算法的優(yōu)缺點依次進行闡述：

優(yōu)點：作為仿生物覓食演化而來的蟻群算法，利用螞蟻覓食過程中信息素濃度變化的原理，擁有較強的最短路徑計算求解能力。同時蟻群算法中的分布計算特點避免了問題求解過程中過早收斂、利用貪婪式搜索能力在開始運算的早期即盡可能提供最短路徑，節(jié)省了尋優(yōu)路徑求解時間。同時，蟻群算法具有較強的魯棒性和并行計算能力，即僅通過螞蟻之間分泌的信息素濃度變化即可實現(xiàn)不同個體之間的交流與信息溝通，適用范圍較廣。

缺點：在利用蟻群算法求解具體問題過程中，雖然不同螞蟻之間可以通過信息素溝通，但是在種群過大的情況下，因為單個螞蟻的不確定性特點，該算法難以在小段時間范圍中求解出最優(yōu)的行走路徑，造成搜索時間過長;同時，在具體應(yīng)用求解中容易陷入部分區(qū)域搜索停滯情況，即在運算過程中，當達到相應(yīng)規(guī)模以后，存在部分個體發(fā)現(xiàn)求解結(jié)果一樣的情況，進而造成搜索停滯，不利于求出行進最短的路徑。

參考文獻：

[1]李寧馨.采用不同算法求解車輛路徑問題的對比分析[J].重慶工商大學(xué)學(xué)報（自然科學(xué)版），2014，31（5）：70-76.

[2]梁承姬，崔佳誠，丁一.基于混合蟻群算法的車輛路徑問題研究[J].重慶交通大學(xué)學(xué)報（自然科學(xué)版），2016（3）.

[3]朱喜基.基于蟻群算法的旅行商問題的研究[J].無線互聯(lián)科技，2012（11）：120-121.

[4]趙吉東.蟻群算法的改進策略研究[J].中國科技信息，2012（12）：149-150.