基于改進蟻群算法在糧食物流配送路徑優化的應用研究

何小虎

（渭南師范學院 數學與信息科學學院，陜西 渭南　714000）

基于改進蟻群算法在糧食物流配送路徑優化的應用研究

何小虎

（渭南師范學院 數學與信息科學學院，陜西 渭南714000）

為了有效地降低糧食的運輸成本，提出了一種改進的蟻群算法對糧食物流配送路徑進行優化。該算法通過改進螞蟻的轉移規則、初始化信息素和全局信息素以及增加各條路徑信息量調整的局部更新規則。仿真實驗結果表明，改進的蟻群算法比基本蟻群算法可以更好地解決糧食物流配送路徑優化問題，路徑長度明顯縮短，從而使有限的資源發揮更大的作用。

蟻群算法；糧食物流；路徑優化；信息素

在糧食價格的構成中，生產成本所占比重最大，其次就是糧食流通成本。但流通費用越來越成為影響農產品價格和競爭力的一個較為重要的因素。我國是糧食的生產大國，也是糧食的消費大國，因此，研究如何有效地降低糧食的運輸成本，提高運輸效益，將有十分重要的現實意義。

降低糧食的運輸成本，就是要設計合理的車輛運輸路線方案，盡量減少配送里程數和配送時間，有效地減少車輛的空駛率和增加車輛的利用率，降低運輸成本，節約運輸時間［1］。解決這類問題的方法較多，包括遺傳算法、模擬退火算法、禁忌搜索算法和蟻群算法等。其中，蟻群算法是一種新型的智能優化算法，已經成為解決配送路徑選擇問題的有效方法。因此，文中對基本蟻群算法進行改進，建立數學模型，進而對糧食物流配送車輛路徑問題進行了實驗仿真。結果表明，改進后的蟻群算法提高了全局尋優能力與收斂速度，取得了較好的效果。

1　蟻群算法

蟻群算法是意大利學者Marco Dorigo等人于1991年受自然界螞蟻覓食過程啟發而提出的一種新型智能搜索優化算法。隨后將蟻群算法成功地應用于旅行商問題求解上，并取得了非常好的實驗結果。受其影響，蟻群算法受到許多研究者者的關注，并不斷應用于實際問題求解，蟻群算法已經被廣泛地應用到各個領域解決復雜組合優化問題。蟻群算法具有魯棒性、并行性、分布性、全局尋優、易于與其他優化算法相結合等優點，能夠在較短時間內發現問題的最優解，使這種仿生優化算法展現出廣闊的應用前景。

1.1蟻群算法的原理

螞蟻在覓食的時候，經過一定的時間，就可以找到一條從巢穴到食物源二者的最短路徑，通過生物學家研究發現，螞蟻視覺系統發育不全甚至沒有，螞蟻協助完成覓食是依靠一種叫信息素的化學物質來完成。螞蟻在爬行過的路徑上會遺留下信息素。同時螞蟻會根據信息素的濃度來選擇走一條路徑，當那條路徑上的信息素濃度越濃時，螞蟻選擇該路徑的概率越大，這樣就會有更多的螞蟻選擇該條路徑。相反，在信息素濃度越少的路徑上，螞蟻選擇的概率越小，該路徑隨著時間的推移信息素逐漸揮發，而導致以后螞蟻選擇的可能性更小。最終信息素濃度最高的路徑就是螞蟻找出的最優路徑。蟻群算法就是通過這種正反饋機制來尋找優解的執行過程。

1.2蟻群算法的基本模型

蟻群算法可以表述如下：初始時刻，各條路徑上的信息素量相等，設τij（0）=C（C為常數），螞蟻k（k=1，2，3，…，m）在運動過程中根據各條路徑上的信息量決定轉移方向。螞蟻系統所使用的轉移規則被稱為隨機比例規則，在時刻 t，螞蟻k從城市i選擇城市j的轉移概率Pkij（t）為：

其中，Jk（i）=｛1，2，……，n｝-tabuk表示螞蟻k下一步允許選擇的城市。列表tabuk記錄了螞蟻k在本次迭代中已經走過的城市，不允許該螞蟻在本次循環中再經過這些城市。當所有n座城市都加入到tabuk中時，螞蟻k便完成了一次周游，此時螞蟻k所走過的路徑便是TSP問題的一個可行解。式（1）中的ηij是一個啟發式因子，被稱為能見度因子。在 AS算法中，ηij通常取城市i與城市j之間距離的倒數。α和β分別反映了在螞蟻的運動過程中已積累的信息和啟發信息的相對重要程度。當所有螞蟻完成一次周游后，各路徑上的信息素根據（2）式更新。

其中ρ（0＜ρ＜1）表示路徑上信息素的揮發系數，1-ρ表示信息素的持久系數；Δτij表示本次迭代邊 （ij）上信息素的增量。Δτkij表示第k只螞蟻在本次迭代中留在邊（ij）上的信息素量。如果螞蟻 k沒有經過邊（ij），則Δτkij的值為0。Δτkij表示為：

其中，Q為正常數，Lk表示第k只螞蟻在本次周游中所走過路徑的長度。

2　改進蟻群算法

蟻群算法是模擬自然界中螞蟻覓食行為的隨機搜索算法［2］，具有正反饋作用，通過一群螞蟻之間的信息交流和傳遞，最終找到最優解。蟻群算法具有好的魯棒性、并行性計算能力、正反饋機制。但是也有一些缺點：

1）與其他算法相比，該算法收斂速度慢，搜索需要一段較長的時間［3］。

2）算法容易出現搜索停滯現象，即算法進行到一定程度后，所有媽蟻都集中走同一條路徑，不能進行新路徑的搜索，不能發現更好的解，算法收斂到局部最優解而非全局最優解［4］。

針對蟻群算法存在的缺點，提出了改進的蟻群算法，初始化信息素濃度時加入了方向引導，在全局信息素更新上引入了sigmiod函數作為動態因子σ，自適應地調節每次迭代最優解對路徑的信息素更新的比重。

2.1螞蟻的轉移規則不同

在ACS中螞蟻選擇下一個城市使用的公式。

其中q為區間［0，1］內的隨機數，q0為［0，1］內的一個參數。S是根據公式（1）確定的。這種以一定隨機概率的形式確定螞蟻行為的方法為隨機概率選擇規則。當螞蟻要選擇下一個移動的城市時。算法會產生一個［0，1］范圍內的隨機數q，并判斷隨機數與參數q0的關系，最后選擇確定螞蟻移動方向的方法。

2.2初始化信息素的改進

針對上面提到的問題［4］，修改媽蟻的初始化信息素強度，取

其中±deje為節點j與終點e的直線矢量距離，W為系統設定的一個正常數。

由式（2）可以看出deje，deje較小，τij（0）就較高，螞蟻傾向于選擇該條路徑作為移動方向，加強了螞蟻在選擇下一個節點時指向終點搜索的方向性，減少了不必要的劣質解，縮小了解空間的搜索范圍，提高解空間的質量，從而加快了找到全局最優解的速度。

2.3全局信息素的改進

當m只螞蟻都完成一次循環，則按照全局更新規則只更新該次迭代最優解路徑的信息素濃度，其他不更新［4］。全局更新規則由公式（3）給出。

其中L為目前的局部最優解之和的平均路徑長度，為此次迭代局部最優解，為目前為止的全局最短路徑長度，//為給定參數。

2.4新增了對各條路徑信息量調整的局部更新規則

所有的螞蟻在完成每一次的轉移后，都對所經過路徑上的信息素進行局部更新，其公式為

其中，Δτ（r，s）的取值可以為0，也可以為一定值。

2.5蟻群算法主要步驟描述如下［4］：

1）初始化參數Q、C、α，β，W，μ。

2）按照公式（2）初始化信息素，并將結果存放到τij（0），在起點S置于n個螞蟻。

3）啟動蟻群，對每一只螞蟻根據狀態轉移規則公式（1）選擇下一個節點，并更新它們的禁忌表。

4）經過m個時刻，螞蟻k遍歷完一次路徑時，按照公式（4）局部更新規則進行更改路徑的信息素濃度，更新該次迭代的當前最好路徑。

5）當所有螞奴都進行一次完整的搜索遍歷后即一次迭代后，此時按照式（3）全局更新只更新該次迭代的最優路徑信息素濃度，更新找到的最好路徑，nc=nc+l。

6）若nc等于系統設定的最大迭代次數，則搜索遍歷結束，輸出最優路徑和長度；否則清空禁忌表，返回3）。

3　改進蟻群算法仿真測試

實驗室采用圖1所示。模擬21個糧食運輸點來進行蟻群算法的分析和研究。

圖1　優化線路圖

如圖1所示，我們要求出一條從節點0到節點21的這樣的最短路徑問題。運用蟻群算法搜索出存在唯一的最優路徑：21-20-17-18-6-19-4-3-10-13-5-2-7-8-11-14-12-16-15-9-1，路徑長度為38.201公里。

在參數設置基本相同的情況下，用改進的蟻群算法與ACS算法進行仿真比較，并將兩者的結果進行對比，見表1。

通過結果對比，ACS的10次平均長度是：40.522 2公里，ACS的10次平均迭代次數是：113次，而改進后的蟻群算法的10次平均長度是：38.548 6公里，改進后的蟻群算法的10次平均迭代次數是：79次。可以看出改進后的蟻群算法在平均路徑長度和迭代次數上要明顯優于ACS。

表1　本文算法與ACS在平均路徑長度和迭代次數上的對比

4　結束語

實驗仿真結果表明，求解糧食物流配送路徑優化問題時，使用文中改進后的蟻群算法有如下優點：1）找到最優解的概率更高；2）求解效率和性能都進一步提高．但是蟻群算法是一種先進的仿生智能優化算法，今后對參數的設置和算法的優化需要進一步的研究和完善。

［1］余昌艷.基于蟻群算法的糧食加工企業物流配送路徑優化研究［D］.武漢：武漢科技大學，2009.

［2］高尚.蟻群算法理論、應用及其與其他算法的混合［D］.南京：南京理工大學，2005.

［3］汪采萍.蟻群算法的應用研究［D］.合肥：合肥工業大學，2007.

［4］吳虎發.蟻群優化算法在求解最短路徑問題中的研究與應用［D］.合肥：安徽大學，2012.

［5］龍汀.基于蟻群算法的車輛路徑問題的研究［D］.合肥：合肥工業大學，2009.

［6］陳迎欣.基于改進蟻群算法的車輛路徑優化問題研究［J］.計算機應用研究，2012，29（6）：2031-2034．

Application research on quantum ant colony algorithm in grain logistics distribution path optimization

HE Xiao-hu
（College of mathematics and Information Science，Weinan Teachers College，Weinan 714000，China）

A modified ant colony algorithm was proposed to optimize grain logistics distribution path in order to reduce transportation cost effectively.The proposed algorithm adjusted local update rules via the following ways，such as improvement transition rule of the ant，initialization pheromone and global pheromone as well as increase the amount of information of each path.The simulation results showed that the modified algorithm provided a better solution in grain logistics distribution path optimization than the basic ant colony algorithm.It can cut down path length and therefore play a bigger role in utilization of the limited resources.

ant colony algorithm；grain logistics；path optimization；pheromones

TN-9

A

1674－6236（2016）09-0039-03

2015-05-17稿件編號：201505137

陜西自然科學基礎研究計劃項目（2014JM1026）；陜西教育廳教改項目（13BY91）；渭南師范學院項目（15YKP002）；校級特色學科建設項目資助（14TSXK02）；陜西自然科學研究發展計劃項目（2014JM2-1004）

何小虎（1980—），男，陜西渭南人，碩士，講師。研究方向：智能算法優化及其應用。