何小虎

（渭南師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 渭南　714000）

基于改進(jìn)蟻群算法在糧食物流配送路徑優(yōu)化的應(yīng)用研究

何小虎

（渭南師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 渭南714000）

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

蟻群算法；糧食物流；路徑優(yōu)化；信息素

在糧食價(jià)格的構(gòu)成中，生產(chǎn)成本所占比重最大，其次就是糧食流通成本。但流通費(fèi)用越來越成為影響農(nóng)產(chǎn)品價(jià)格和競(jìng)爭(zhēng)力的一個(gè)較為重要的因素。我國是糧食的生產(chǎn)大國，也是糧食的消費(fèi)大國，因此，研究如何有效地降低糧食的運(yùn)輸成本，提高運(yùn)輸效益，將有十分重要的現(xiàn)實(shí)意義。

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

1　蟻群算法

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

1.1蟻群算法的原理

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

1.2蟻群算法的基本模型

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

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

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

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

2　改進(jìn)蟻群算法

蟻群算法是模擬自然界中螞蟻覓食行為的隨機(jī)搜索算法［2］，具有正反饋?zhàn)饔茫ㄟ^一群螞蟻之間的信息交流和傳遞，最終找到最優(yōu)解。蟻群算法具有好的魯棒性、并行性計(jì)算能力、正反饋機(jī)制。但是也有一些缺點(diǎn)：

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

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

針對(duì)蟻群算法存在的缺點(diǎn)，提出了改進(jìn)的蟻群算法，初始化信息素濃度時(shí)加入了方向引導(dǎo)，在全局信息素更新上引入了sigmiod函數(shù)作為動(dòng)態(tài)因子σ，自適應(yīng)地調(diào)節(jié)每次迭代最優(yōu)解對(duì)路徑的信息素更新的比重。

2.1螞蟻的轉(zhuǎn)移規(guī)則不同

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

其中q為區(qū)間［0，1］內(nèi)的隨機(jī)數(shù)，q0為［0，1］內(nèi)的一個(gè)參數(shù)。S是根據(jù)公式（1）確定的。這種以一定隨機(jī)概率的形式確定螞蟻行為的方法為隨機(jī)概率選擇規(guī)則。當(dāng)螞蟻要選擇下一個(gè)移動(dòng)的城市時(shí)。算法會(huì)產(chǎn)生一個(gè)［0，1］范圍內(nèi)的隨機(jī)數(shù)q，并判斷隨機(jī)數(shù)與參數(shù)q0的關(guān)系，最后選擇確定螞蟻移動(dòng)方向的方法。

2.2初始化信息素的改進(jìn)

針對(duì)上面提到的問題［4］，修改媽蟻的初始化信息素強(qiáng)度，取

其中±deje為節(jié)點(diǎn)j與終點(diǎn)e的直線矢量距離，W為系統(tǒng)設(shè)定的一個(gè)正常數(shù)。

由式（2）可以看出deje，deje較小，τij（0）就較高，螞蟻傾向于選擇該條路徑作為移動(dòng)方向，加強(qiáng)了螞蟻在選擇下一個(gè)節(jié)點(diǎn)時(shí)指向終點(diǎn)搜索的方向性，減少了不必要的劣質(zhì)解，縮小了解空間的搜索范圍，提高解空間的質(zhì)量，從而加快了找到全局最優(yōu)解的速度。

2.3全局信息素的改進(jìn)

當(dāng)m只螞蟻都完成一次循環(huán)，則按照全局更新規(guī)則只更新該次迭代最優(yōu)解路徑的信息素濃度，其他不更新［4］。全局更新規(guī)則由公式（3）給出。

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

2.4新增了對(duì)各條路徑信息量調(diào)整的局部更新規(guī)則

所有的螞蟻在完成每一次的轉(zhuǎn)移后，都對(duì)所經(jīng)過路徑上的信息素進(jìn)行局部更新，其公式為

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

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

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

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

3）啟動(dòng)蟻群，對(duì)每一只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則公式（1）選擇下一個(gè)節(jié)點(diǎn)，并更新它們的禁忌表。

4）經(jīng)過m個(gè)時(shí)刻，螞蟻k遍歷完一次路徑時(shí)，按照公式（4）局部更新規(guī)則進(jìn)行更改路徑的信息素濃度，更新該次迭代的當(dāng)前最好路徑。

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

6）若nc等于系統(tǒng)設(shè)定的最大迭代次數(shù)，則搜索遍歷結(jié)束，輸出最優(yōu)路徑和長度；否則清空禁忌表，返回3）。

3　改進(jìn)蟻群算法仿真測(cè)試

實(shí)驗(yàn)室采用圖1所示。模擬21個(gè)糧食運(yùn)輸點(diǎn)來進(jìn)行蟻群算法的分析和研究。

圖1　優(yōu)化線路圖

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

在參數(shù)設(shè)置基本相同的情況下，用改進(jìn)的蟻群算法與ACS算法進(jìn)行仿真比較，并將兩者的結(jié)果進(jìn)行對(duì)比，見表1。

通過結(jié)果對(duì)比，ACS的10次平均長度是：40.522 2公里，ACS的10次平均迭代次數(shù)是：113次，而改進(jìn)后的蟻群算法的10次平均長度是：38.548 6公里，改進(jìn)后的蟻群算法的10次平均迭代次數(shù)是：79次。可以看出改進(jìn)后的蟻群算法在平均路徑長度和迭代次數(shù)上要明顯優(yōu)于ACS。

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

4　結(jié)束語

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

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

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

［3］汪采萍.蟻群算法的應(yīng)用研究［D］.合肥：合肥工業(yè)大學(xué)，2007.

［4］吳虎發(fā).蟻群優(yōu)化算法在求解最短路徑問題中的研究與應(yīng)用［D］.合肥：安徽大學(xué)，2012.

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

［6］陳迎欣.基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問題研究［J］.計(jì)算機(jī)應(yīng)用研究，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稿件編號(hào)：201505137

陜西自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目（2014JM1026）；陜西教育廳教改項(xiàng)目（13BY91）；渭南師范學(xué)院項(xiàng)目（15YKP002）；校級(jí)特色學(xué)科建設(shè)項(xiàng)目資助（14TSXK02）；陜西自然科學(xué)研究發(fā)展計(jì)劃項(xiàng)目（2014JM2-1004）

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