一種改進(jìn)的小窗口蟻群算法

陳立　謝富強(qiáng)　李蘭君

摘要：針對(duì)現(xiàn)有小窗口蟻群算法對(duì)優(yōu)化問(wèn)題規(guī)模的適應(yīng)性較差、對(duì)設(shè)定可選城市范圍的參數(shù)依賴大、易于陷入局部最優(yōu)等缺點(diǎn)，提出了一種隨機(jī)小窗口蟻群算法，將問(wèn)題規(guī)模與隨機(jī)性同時(shí)引入小窗口蟻群算法，增強(qiáng)了算法的魯棒性，而且可以避免算法早熟，陷入局部最優(yōu)。通過(guò)對(duì)200個(gè)城市的仿真結(jié)果表明，該算法效果良好。

關(guān)鍵詞關(guān)鍵詞：蟻群算法；小窗口蟻群算法；路徑優(yōu)化；商旅問(wèn)題

DOIDOI：10.11907/rjdk.143829

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)

文章編號(hào)：16727800（2015）002004803

基金項(xiàng)目基金項(xiàng)目：湖南省科技廳項(xiàng)目（2013FJ3154）；航天支撐基金項(xiàng)目（2013ZGDZDX）

作者簡(jiǎn)介作者簡(jiǎn)介：陳立（1990—），男，湖北黃石人，南華大學(xué)電氣工程學(xué)院碩士研究生，研究方向?yàn)樽顑?yōu)控制、智能控制理論及應(yīng)用；謝富強(qiáng)（1971-），男，湖南衡山人，博士，南華大學(xué)電氣工程學(xué)院講師、碩士生導(dǎo)師，研究方向?yàn)樽顑?yōu)控制、智能控制理論及應(yīng)用、導(dǎo)航與制導(dǎo)；李蘭君（1965-），女，湖南衡陽(yáng)人，南華大學(xué)電氣工程學(xué)院教授、碩士生導(dǎo)師，研究方向?yàn)橹悄芸刂?、嵌入式系統(tǒng)應(yīng)用。

0引言

蟻群算法是20世紀(jì)90年代初期由意大利學(xué)者Colorni等人＼[1＼]提出的一種仿生算法，通過(guò)模擬自然界中螞蟻尋找食物時(shí)利用其留下的信息素強(qiáng)弱來(lái)尋找最優(yōu)路徑。本文就是在基本蟻群算法基礎(chǔ)上，通過(guò)改進(jìn)小窗口蟻群算法，增加隨機(jī)小窗口這一環(huán)節(jié)避免算法過(guò)早收斂，增強(qiáng)尋優(yōu)能力。

1基本蟻群算法

1.1算法原理

蟻群算法是源于螞蟻的覓食行為，螞蟻在尋找食物時(shí)會(huì)在經(jīng)過(guò)的路徑上留下信息素，當(dāng)某條路徑是從蟻穴到食物的較短路徑時(shí)，通過(guò)該條路徑的螞蟻就會(huì)較多，該條路徑上面的信息素濃度就會(huì)較高，以此吸引更多的螞蟻經(jīng)過(guò)這條路徑。通過(guò)多次往返，某條最短路徑上面的信息素濃度會(huì)非常高，蟻群就會(huì)都從這條最優(yōu)路徑上經(jīng)過(guò)，使得整個(gè)種群在尋找食物上的時(shí)間變短，提高了效率。

1.2算法實(shí)現(xiàn)

1.2.1禁忌表規(guī)則

蟻群算法中的螞蟻具有記憶功能，這與實(shí)際的螞蟻群有區(qū)別。記錄螞蟻k當(dāng)前走過(guò)的元素，將其坐標(biāo)記錄下來(lái)并放入禁忌表tabu＼[k＼]中，螞蟻在一次循環(huán)過(guò)程中不能再次經(jīng)過(guò)已存在禁忌表上的坐標(biāo)，當(dāng)一次循環(huán)結(jié)束后，禁忌表被清零，螞蟻又可以進(jìn)行自由選擇。

1.2.2狀態(tài)轉(zhuǎn)移規(guī)則

每只螞蟻在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上信息素的濃度以及啟發(fā)信息來(lái)計(jì)算狀態(tài)轉(zhuǎn)移概率。表達(dá)式如式（1）所示。

Pkij（t）=[τij（t）]α·[ηk（t）]β∑sallowedk[τis（t）]α·[ηis（t）]β若j∈allowedk0，否則 （1）

其中，allowedk表示螞蟻k下一次允許移動(dòng)到的元素，α為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性；β為期望啟發(fā)式因子，表示能見(jiàn)度的相對(duì)重要性[23]，ηij（t）為啟發(fā)函數(shù)。

1.2.3信息素更新規(guī)則 蟻群算法中只有那些屬于最短路徑上的邊信息素才被得到增強(qiáng)[4]。這種規(guī)則使得算法在尋找最優(yōu)路徑時(shí)更具有目的性：對(duì)于最優(yōu)路徑的尋找始終是在當(dāng)前最短路徑的周圍進(jìn)行。在k個(gè)螞蟻遍歷完n個(gè)元素后，按照式（2）進(jìn)行全局更新。

τij（t+n）=（1-ρ）τij（t）+ρΔτij（t）（2）Δτij（t）=∑mk=1Δτkij（t）（3）

其中ρ為揮發(fā)系數(shù)，ρ[0，1]；Δτij（t）表示本次循環(huán)中路徑ij上的信息素增量；Δτkij（t）表示第k只螞蟻在本次循環(huán)中留在路徑ij上的信息量。

單個(gè)螞蟻在搜尋最優(yōu)路徑時(shí)使用信息素局部更新規(guī)則對(duì)其經(jīng)過(guò)路徑上的信息素按照式（4）進(jìn)行更新。

τij（t+h）=（1-ζ）τij（t）+ζτ0（4）τ0=1/（nlmin）（5）

其中ζ[0，1]，lmin表示所有元素集合中兩個(gè)最近元素之間的距離。

2小窗口蟻群算法

蟻群算法最早是應(yīng)用于商旅問(wèn)題（TSP）。TSP問(wèn)題的求解是典型的NP問(wèn)題，當(dāng)城市規(guī)模n大到一定程度后便會(huì)面臨“組合爆炸”問(wèn)題[5]，此時(shí)，傳統(tǒng)的搜索算法便會(huì)陷入困境。隨著人工智能算法的興起，這一問(wèn)題才被逐漸解決。蟻群算法就是其中之一。然而，蟻群算法同樣也存在不足，容易陷入局部最優(yōu)解。目前，對(duì)于蟻群算法的改進(jìn)大多數(shù)都是通過(guò)增加變異環(huán)節(jié)的方法，如文獻(xiàn)[6]中引入非均勻變異算子，對(duì)已完成搜索的蟻群進(jìn)行變異處理，以及調(diào)節(jié)信息素的方法，如文獻(xiàn)[7]中提出對(duì)揮發(fā)因子的取值進(jìn)行改進(jìn)。

以上這些改進(jìn)，對(duì)于小規(guī)模問(wèn)題的改善較為明顯，但是當(dāng)TSP問(wèn)題中城市的數(shù)量大于50時(shí)，優(yōu)化結(jié)果就難以令人滿意。文獻(xiàn)[8]提出了小窗口蟻群算法，其核心思想就是在螞蟻從一個(gè)城市向下一個(gè)城市移動(dòng)時(shí)，不需要對(duì)剩下所有城市（不在禁忌表上）進(jìn)行考慮，而只需要在出發(fā)城市鄰近的若干個(gè)城市中進(jìn)行選擇，因?yàn)樽罱K的最優(yōu)解是保證總路徑最短，因此不可能出現(xiàn)兩個(gè)城市距離很遠(yuǎn)的情況。

2.1固定小窗口蟻群算法

固定小窗口蟻群算法就是設(shè)定一個(gè)相鄰城市的范圍city[p]，每次螞蟻選擇下一個(gè)城市時(shí)，都是在city[p]與禁忌表tabu[k]的交集中選擇，然后再按照式（1）的規(guī)則進(jìn)行移動(dòng)。在仿真中，p的取值為6。

2.2動(dòng)態(tài)小窗口蟻群算法

固定小窗口蟻群算法是將可選擇城市的規(guī)模，也即數(shù)量固定下來(lái)，但是這樣存在一個(gè)缺點(diǎn)：不能更好地適應(yīng)問(wèn)題規(guī)模，當(dāng)城市數(shù)量為100個(gè)左右時(shí)，可選城市數(shù)量為p，當(dāng)城市數(shù)量為200個(gè)左右，可選城市數(shù)量還是為p，在這種情況下，就沒(méi)有將問(wèn)題規(guī)模的變化考慮進(jìn)來(lái)，無(wú)法得到一個(gè)適合不同規(guī)模的優(yōu)化算法。文獻(xiàn)[9]提出將可選城市的數(shù)量用一個(gè)分段函數(shù)表示，將其與問(wèn)題規(guī)模聯(lián)系起來(lái)，如式（6）所示，當(dāng)問(wèn)題規(guī)模n處于不同范圍時(shí)，可選城市的數(shù)量MAXYC也相應(yīng)地取不同數(shù)值。

MAXYC=8，n≤50；10，50

3隨機(jī)小窗口蟻群算法

3.1算法原理

動(dòng)態(tài)小窗口蟻群算法雖然使用分段函數(shù)的形式將可選城市的數(shù)量與問(wèn)題規(guī)模聯(lián)系起來(lái)，但是在一定城市規(guī)模的范圍內(nèi)，可選城市的數(shù)量仍然是個(gè)定值，這與固定小窗口蟻群算法一樣，同樣會(huì)使算法早熟，在解決問(wèn)題時(shí)陷入局部最優(yōu)。在綜合考慮固定小窗口蟻群算法和動(dòng)態(tài)小窗口蟻群算法的缺點(diǎn)與不足后，本文提出了隨機(jī)小窗口蟻群算法，通過(guò)數(shù)學(xué)處理，將問(wèn)題規(guī)模與隨機(jī)性同時(shí)引入小窗口蟻群算法，增強(qiáng)了算法的魯棒性，而且可以避免算法早熟，陷入局部最優(yōu)。

3.2算法實(shí)現(xiàn)

在確定可選城市數(shù)量時(shí)，確定一個(gè)基準(zhǔn)值r，其值與問(wèn)題規(guī)模正相關(guān)，表達(dá)式見(jiàn)式（7）；一個(gè)隨機(jī)值ε，其值為[0，1]之間的隨機(jī)數(shù)，則可以得到可選城市的數(shù)量，表達(dá)式見(jiàn)式（8）。

r=n10，（7）citynum=[1+rε]，（8）

式（7）的作用就是將問(wèn)題規(guī)模的參數(shù)引入確定小窗口范圍的數(shù)學(xué)表達(dá)式中，當(dāng)n為50時(shí)，r為5，當(dāng)n為200時(shí)，r為20，這樣隨著問(wèn)題規(guī)模n的變化，參數(shù)r也會(huì)隨之變化，并且將該變化傳遞到式（8）中。式（8）的作用則是引入一個(gè)隨機(jī)值，將r的值做適當(dāng)縮小，并且限定其變化范圍，為了避免當(dāng)問(wèn)題規(guī)模小于10時(shí)程序運(yùn)行出現(xiàn)問(wèn)題，特意在式（8）中加上1作為小窗口可選城市的最小值。

隨機(jī)小窗口蟻群算法如下：①初始化參數(shù)m、α、β、ρ、Nc_max；②將m只螞蟻放在n個(gè)城市上；③一組螞蟻開始循環(huán)；④螞蟻從citynum與tabu[k]這兩個(gè)列表中選擇可以移動(dòng)的城市，按照式（1）移動(dòng)；⑤在螞蟻遍歷所有城市之前轉(zhuǎn)至④；⑥記錄一次搜索的最短路徑，清空禁忌表tabu[k]；⑦更新信息素；⑧當(dāng)?shù)螖?shù)小于Nc_max時(shí)，轉(zhuǎn)至②；⑨輸出最終優(yōu)化結(jié)果。

通過(guò)式（8）可以看出，此時(shí)可選城市的數(shù)量不僅與問(wèn)題規(guī)模聯(lián)系起來(lái)，而且由于引入了限定范圍的隨機(jī)變量ε，使得蟻群算法在搜索最優(yōu)解時(shí)能夠及時(shí)跳出局部最優(yōu)，避免算法早熟，也沒(méi)有過(guò)分增加系統(tǒng)消耗。對(duì)200個(gè)城市的實(shí)例仿真結(jié)果表明，該算法效果良好。

4仿真結(jié)果與分析

4.1實(shí)例仿真

仿真環(huán)境是MATLAB R2011b 64位，計(jì)算機(jī)系統(tǒng)為Windows7 64位，硬件配置為Intel（R） Core（TM） i3 M350雙核主頻2.27GHz，內(nèi)存3GB。編寫MATLAB程序進(jìn)行實(shí)例仿真，蟻群的循環(huán)次數(shù)Nc_max=10，蟻群數(shù)量m=300，α=1，β=5，ρ=0.5。每個(gè)程序運(yùn)行20次，對(duì)每次測(cè)得的數(shù)據(jù)進(jìn)行記錄，最后計(jì)算其平均值。

一個(gè)有200個(gè)城市的區(qū)域，城市位置隨機(jī)分布，區(qū)域的橫坐標(biāo)范圍是0～50，縱坐標(biāo)范圍是0～30，其坐標(biāo)位置如圖1所示。

4.2結(jié)果分析

由表1可知，固定小窗口蟻群算法和動(dòng)態(tài)小窗口蟻群算法在最優(yōu)路徑的平均長(zhǎng)度上比基本蟻群算法分別縮短了1.57%和1.79%，而隨機(jī)小窗口蟻群算法在最優(yōu)路徑的平均長(zhǎng)度上比基本蟻群算法縮短了4.25%，可以看出隨機(jī)小窗口蟻群算法在尋找最優(yōu)解上有較好的表現(xiàn)。同時(shí)，通過(guò)觀察達(dá)到收斂所需要的循環(huán)次數(shù)，隨機(jī)小窗口蟻群算法的數(shù)據(jù)比上面3種算法的要增加一倍，這也反映了隨機(jī)小窗口蟻群算法可以避免算法早熟，能夠跳出局部最優(yōu)。

5結(jié)語(yǔ)

本文基于基本蟻群算法，通過(guò)改進(jìn)動(dòng)態(tài)小窗口蟻群算法的不足，提出了隨機(jī)小窗口蟻群算法，該算法既可以適應(yīng)問(wèn)題規(guī)模的變化，又可以避免算法早熟，陷入局部最優(yōu)解。但同時(shí)也存在收斂速度不夠快的缺陷，這有待進(jìn)一步研究改進(jìn)。

參考文獻(xiàn)參考文獻(xiàn)：

＼[1＼]COLORNI A，DORIGO M，MANIEZZO V，et al.Distributed optimization by ant colonies＼[C＼].Paris：Proc of European Conf on Artificial Life，1991：134142.

＼[2＼]DORIGO M，CARO G D，GAMBARDELLA L M.Ant algorithms for discrete optimization＼[J＼]. Artificial Life，1999，5（2）：137172.

＼[3＼]JAMES M，MARCUS R.Antipheromone as a tool for better exploration of search space＼[C＼]. Brussels：Proc of 3rd Int Workshop on Ant Algorithms，2002：100110.

＼[4＼]倪慶劍，邢漢承，張志政，等.蟻群算法及其應(yīng)用研究進(jìn)展＼[J＼].計(jì)算機(jī)應(yīng)用與軟件，2008，25（8）：1215.

＼[5＼]冀俊忠，黃振，劉椿年，等.基于多粒度的旅行商問(wèn)題描述及其蟻群優(yōu)化算法＼[J＼].計(jì)算機(jī)研究與發(fā)展，2010，47（3）：434444.

＼[6＼]龔躍，吳航，趙飛.基于非均勻變異算子的改進(jìn)蟻群優(yōu)化算法＼[J＼].計(jì)算機(jī)工程，2013，39（10）：196199.

＼[7＼]葉仕通，萬(wàn)智萍.一種基于改進(jìn)全局信息素更新效率的蟻群算法及仿真＼[J＼].計(jì)算機(jī)應(yīng)用與軟件，2014，31（1）：176179.

＼[8＼]蕭蘊(yùn)詩(shī)，李炳宇.小窗口蟻群算法＼[J＼].計(jì)算機(jī)工程，2003，29（20）：143145.

＼[9＼]趙娟平，高憲文，劉金剛，等.移動(dòng)機(jī)器人路徑規(guī)劃的參數(shù)模糊自適應(yīng)窗口蟻群優(yōu)化算法＼[J＼].控制與決策，2011，26（7）：10961100.

責(zé)任編輯（責(zé)任編輯：孫娟）