馬憲民，劉妮

（西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054）

1 引言

最短路徑是智能車輛導(dǎo)航系統(tǒng)中的一個關(guān)鍵問題，在求解最短路徑的算法中，目前國內(nèi)外公認(rèn)的較好算法有經(jīng)典的迪杰斯特拉(Dijkstra)及弗洛伊德(Floyd)算法，但時(shí)間復(fù)雜度是此2種算法的瓶頸[1~3]。隨著人工智能研究的深入，一些新的智能優(yōu)化算法不斷被提出，包括遺傳算法、蟻群算法、粒子群算法、人工魚群算法等。遺傳算法的主要缺點(diǎn)是對于結(jié)構(gòu)復(fù)雜的組合優(yōu)化問題，搜索空間大，搜索時(shí)間比較長，往往會出現(xiàn)早熟收斂的情況；對初始種群很敏感，初始種群的選擇常常直接影響解的質(zhì)量和算法效率[4]?；鞠伻核惴ㄋ阉鲿r(shí)間長，而且容易出現(xiàn)停滯，存在著收斂速度慢、易陷入局部最優(yōu)等缺陷；而模型中各參數(shù)的取值更直接關(guān)系到算法的收斂速度和全局搜索能力[4,5]。粒子群算法雖然收斂速度較快，但精度較低、易發(fā)散，容易陷入局部最優(yōu)解[4]。而人工魚群算法（AFSA，artificialfish swarm algorithm）頑健性強(qiáng)、對初值的敏感性小、簡單（只需比較目標(biāo)函數(shù)）、易實(shí)現(xiàn)，而且具有較強(qiáng)的跳出局部極值點(diǎn)的能力，即全局收斂性好，這就能為最短路徑問題搜索到準(zhǔn)確的全局最優(yōu)解。

例如，文獻(xiàn)[6]將改進(jìn)的人工魚群算法應(yīng)用于交通路徑誘導(dǎo)系統(tǒng)數(shù)據(jù)庫優(yōu)化查詢中，算法提高了最優(yōu)路徑查詢的效率。文獻(xiàn)[7]基于有限適合啟發(fā)式算法與人工魚群算法相結(jié)合，完成了車輛最優(yōu)調(diào)度路徑的準(zhǔn)確迭代計(jì)算，縮短了計(jì)算時(shí)間，克服了傳統(tǒng)方法收斂速度慢的缺陷，高效地完成了最優(yōu)路徑的準(zhǔn)確選擇。

因此，本文選擇人工魚群算法求解靜態(tài)道路網(wǎng)絡(luò)上指定起點(diǎn)到終點(diǎn)的最短路徑，并且針對基本人工魚群算法在后期收斂速度慢和計(jì)算量大的缺陷，提出了基于視野自適應(yīng)的改進(jìn)算法。該改進(jìn)算法只對人工魚的覓食行為的視野進(jìn)行改變，使其隨著迭代次數(shù)的增加而逐漸減小，從而有效地加快了算法的收斂速度，減小了計(jì)算量。

2 基本人工魚群算法

人工魚群算法是我國學(xué)者李曉磊等人在 2002年模仿魚類行為特點(diǎn)提出的一種基于動物自治體的優(yōu)化策略[8]。該算法的基本思想是[9]：在一片水域中，魚類聚集最多的地方一般就是這片水域中食物最為豐富的地方；根據(jù)魚類的這個特點(diǎn)構(gòu)造人工魚，模仿魚群的覓食、聚群、追尾等行為，每條人工魚對應(yīng)一個優(yōu)化解，人工魚生存的虛擬水域?qū)?yīng)于優(yōu)化問題的解空間，食物濃度對應(yīng)于目標(biāo)函數(shù)值，通過人工魚群在虛擬水域中游動實(shí)現(xiàn)尋優(yōu)。人工魚群行為的算法描述如下。

1) 覓食行為：設(shè)人工魚的當(dāng)前狀態(tài)為aX，在其視野范圍內(nèi)隨機(jī)選擇一個狀態(tài)bX ，為

其中，函數(shù) ()Rand 產(chǎn)生0到1之間的隨機(jī)數(shù)，Visual為視野范圍。如果食物濃度(求極小值問題)則向該方向前進(jìn)一步，為

其中，Step為移動步長。反之，再重新隨機(jī)選擇狀態(tài)bX，判斷是否滿足前進(jìn)條件；試探一定次數(shù)后，如果仍不滿足前進(jìn)條件，則執(zhí)行其他行為，如隨機(jī)移動行為

2) 聚群行為：設(shè)人工魚的當(dāng)前狀態(tài)為aX，探測其鄰域的伙伴數(shù)目nf，如果表明伙伴中心有較多的食物且不太擁擠，并且Ya＞Yc，則向中心位置Xc前進(jìn)一步，為

否則，執(zhí)行其他行為（如覓食行為）。

3) 追尾行為：設(shè)人工魚當(dāng)前狀態(tài)為 Xi，探測其鄰域內(nèi)狀態(tài)最優(yōu)的鄰居 Xmax，如果，并且Xmax的鄰域內(nèi)伙伴數(shù)目nf滿足＜ 1 )，表明 Xmax附近有較多的食物且不太擁擠，則向 Xmax的方向前進(jìn)一步，為

否則執(zhí)行覓食行為。

4) 隨機(jī)行為：人工魚在視野范圍內(nèi)隨機(jī)選擇一個狀態(tài)，然后向該方向移動，其實(shí)是覓食行為的一個默認(rèn)缺省行為

5) 公告板：主要用于記錄優(yōu)化過程中最優(yōu)人工魚個體的狀態(tài)。

3 改進(jìn)人工魚群算法求解最短路徑問題的原理

3.1 基本人工魚群算法求解最短路徑問題的缺陷

從人工魚的基本行為算法描述中可以看出，視野在尋優(yōu)過程中是非常重要的。在反復(fù)的實(shí)驗(yàn)過程中發(fā)現(xiàn)，參數(shù)視野固定不變，導(dǎo)致算法后期收斂速度慢，且算法的計(jì)算量較大；當(dāng)路網(wǎng)的節(jié)點(diǎn)數(shù)目較大時(shí)，甚至陷入局部最優(yōu)，無法搜索到全局最優(yōu)解。

因?yàn)樵趨?shù)視野不變的情況下，當(dāng)人工魚逐漸逼近最優(yōu)解時(shí)，只有很少的人工魚狀態(tài)不同于最優(yōu)解的人工魚狀態(tài)，所以，人工魚在最優(yōu)解附近以原始的視野進(jìn)行覓食是盲目的。在這種情況下，當(dāng)給定的視野很大，算法的前期收斂很快，但后期收斂很慢，且Trynumber的試探次數(shù)會很大，增加算法的計(jì)算復(fù)雜性；如果給定的視野很小，則會使收斂變慢，計(jì)算量大，甚至陷入局部最優(yōu)。這將降低最短路徑搜索效率和準(zhǔn)確性。

3.2 解決的辦法

為了解決上述問題，提出視野自適應(yīng)的人工魚群算法（AVAFSA，artificial fish-swarm algorithm based on adaptive vision)。

由于人工魚的覓食行為是算法收斂的基礎(chǔ)，所以聚群行為和追尾行為的視野保持不變，只對覓食行為的視野改進(jìn)，采用自適應(yīng)的視野，在算法的初始階段，給覓食行為一個較大的視野，隨著算法的迭代進(jìn)行，逐漸減小視野。

但是，經(jīng)測試發(fā)現(xiàn)，當(dāng)算法后期的視野太小，算法搜索到全局最優(yōu)解的概率會變小。所以，在該視野自適應(yīng)的改進(jìn)人工魚群算法中，當(dāng)視野的當(dāng)前值小于初始值的一半時(shí)，停止減小，使其保持為初始值的一半（當(dāng)然也可以根據(jù)具體問題設(shè)置參數(shù)視野值的下限）。算法的表達(dá)式為

3.3 自適應(yīng)視野人工魚群算法最短路徑實(shí)現(xiàn)原理

人工魚群算法是求解 TSP問題的一個有效方法，而TSP問題與指定起點(diǎn)到目標(biāo)點(diǎn)的靜態(tài)最短路徑問題的相同點(diǎn)是：兩者都屬于組合優(yōu)化問題。區(qū)別在于：TSP的每一種路徑都要遍歷所有的城市，而指定 2點(diǎn)間的最短路徑問題不需要遍歷每個節(jié)點(diǎn)。所以，本文在人工魚群算法求解最短路徑問題中，借鑒了文獻(xiàn)[10]中人工魚群算法求解TSP的編碼方式，但算法模型有2點(diǎn)不同。

1) 目標(biāo)函數(shù)：從起點(diǎn)到目標(biāo)點(diǎn)所經(jīng)過的路徑段的道路權(quán)重(經(jīng)濟(jì)、時(shí)間、距離的加權(quán)組合)求和。若某條人工魚所代表的路徑（以6個網(wǎng)絡(luò)節(jié)點(diǎn)為例）為：N4、N1、N2、N3、N6、N5，要求的路徑為起始節(jié)點(diǎn)1到終點(diǎn)節(jié)點(diǎn)6的最短路徑，則該人工魚的目標(biāo)函數(shù)

2) 新路徑的產(chǎn)生

（a）交換節(jié)點(diǎn)與節(jié)點(diǎn)在路徑序列中的位置，將得到新的路徑；

（b）從起點(diǎn)到目標(biāo)點(diǎn)所經(jīng)過的節(jié)點(diǎn)數(shù)目不同，也將產(chǎn)生新的路徑。

3.4 改進(jìn)人工魚群算法求解最短路徑問題的步驟

算法的實(shí)現(xiàn)步驟如下。

1) 輸入原始數(shù)據(jù)，獲取路網(wǎng)節(jié)點(diǎn)數(shù) P o i ntNum、各節(jié)點(diǎn)的具體坐標(biāo)位置 P o i ntP osition[]、節(jié)點(diǎn)的權(quán)值矩陣 e dge[]、獲取人工魚群的群體規(guī)模FishNum、最大迭代次數(shù) I terate_times、人工魚的視野初始值Visual、最多試探次數(shù)Trynumber、人工魚的最大移動步長Step、擁擠度因子δ等參數(shù)。

2) 當(dāng)前迭代次數(shù) P assed _ t imes= 0 ，生成FishNum個人工魚個體，形成初始魚群，每一個人工魚代表從起點(diǎn)到目標(biāo)點(diǎn)的一種路徑，即從起點(diǎn)至終點(diǎn)的隨機(jī)序列。

3) 各人工魚分別模擬執(zhí)行覓食行為、追尾行為和聚群行為；選擇最優(yōu)行為執(zhí)行，缺省行為方式為覓食行為。

4) 各人工魚每行動一次后，檢驗(yàn)自身狀態(tài)與公告牌狀態(tài)，若自身狀態(tài)優(yōu)于公告牌狀態(tài)，則以自身狀態(tài)取代公告牌狀態(tài)。

5) 終止條件判斷。判斷 p assed _ times是否已達(dá)到預(yù)置的最大迭代次數(shù) I terate_times，若是，則輸出計(jì)算結(jié)果（公告牌的值）；否則， P assed _ times=Passed _ t imes+ 1，轉(zhuǎn)步驟3)。

4 算法的仿真

4.1 道路網(wǎng)拓?fù)浣Y(jié)構(gòu)

某道路網(wǎng)的無向賦權(quán)拓?fù)淙鐖D1所示，路網(wǎng)中共有9個節(jié)點(diǎn)。用 wi,j(t)表示每一路段的非負(fù)權(quán)值，靜態(tài)環(huán)境下，常數(shù)，表示從節(jié)點(diǎn) vi出發(fā)到達(dá)節(jié)點(diǎn) vj所需要的行駛代價(jià)（時(shí)間或費(fèi)用），若路段(vi, vj)不連通，則其權(quán)重，同一個節(jié)點(diǎn)的權(quán)重為

圖1 9節(jié)點(diǎn)無向賦權(quán)路網(wǎng)拓?fù)?/p>

則路網(wǎng)中的權(quán)重可用矩陣表示為

4.2 仿真結(jié)果與數(shù)據(jù)分析

9節(jié)點(diǎn)路網(wǎng)拓?fù)鋱D如圖1所示，假設(shè)起點(diǎn)為節(jié)點(diǎn)1，終點(diǎn)為節(jié)點(diǎn)9，權(quán)重矩陣如式（8）所示，則利用人工魚群算法計(jì)算這2點(diǎn)間的靜態(tài)最短路徑。

現(xiàn)在將對上述改進(jìn)型的自適應(yīng)視野人工魚群算法求解最短路徑方法進(jìn)行仿真，并與基本人工魚群算法及蟻群算法優(yōu)化結(jié)果進(jìn)行對比。仿真環(huán)境為：Pentium（R）Dual-Core，2.19 GHz，2.00 G內(nèi)存的計(jì)算機(jī)。仿真工具為： Matlab R2010a。參數(shù)路阻∞=100，人工魚群算法參數(shù)：人工魚數(shù)目FishNum= 1 0，最大迭代次數(shù) I terate_ t imes= 2 00，最大試探次數(shù) T rynumber= 1 00，初始化視野 V isual=5（根據(jù)節(jié)點(diǎn)數(shù)給定），擁擠度因子deta = 0 .8。蟻群算法參數(shù)：最大迭代次數(shù) N cMax= 2 00，蟻群規(guī)模m=10，留在每個節(jié)點(diǎn)上的信息量受重視程度α=0.1，啟發(fā)式信息受重視程度β=2，信息的保留率ρ=0.1。

因?yàn)橄伻核惴?、基本人工魚群算法和自適應(yīng)視野的改進(jìn)人工魚群算法最終都以 100%的成功率搜索到了全局最優(yōu)解，所以圖2給出改進(jìn)算法求得的最短路徑。所求的最優(yōu)解為 8，得出的路徑為1→2→3→6→9→8→4→7→5；其中 1→2→3→6→9為所求的從起點(diǎn)1至目標(biāo)點(diǎn)9的最短路徑。

圖3為9節(jié)點(diǎn)路網(wǎng)中基本蟻群算法、基本人工魚群算法及自適應(yīng)視野的改進(jìn)人工魚群算法的尋優(yōu)過程對比。3種算法分別在第2次、5次、3次迭代后搜索到全局最優(yōu)解?？梢钥闯龈倪M(jìn)魚群算法比基本魚群算法的收斂速度快。蟻群算法雖然以最快速度搜索到最優(yōu)解，但搜索過程中出現(xiàn)“之”字形路徑，不穩(wěn)定。

圖2 視野自適應(yīng)人工魚群算法（AVAFSA）搜索的最短路徑

圖3 ACO、基本AFSA與改進(jìn)的AVAFSA收斂曲線

下面重點(diǎn)對3種算法的計(jì)算量和收斂速率進(jìn)行比較，仿真環(huán)境和初始條件不變，對比實(shí)驗(yàn)結(jié)果如表1所示。

表1對3種算法各取5次仿真實(shí)驗(yàn)數(shù)據(jù)，其中，BEST_GEN表示算法首次搜索到最優(yōu)解的迭代次數(shù)，BEST表示最優(yōu)解（即最短路徑總長度），TIME表示算法迭代200次花費(fèi)的時(shí)間。分析表1的實(shí)驗(yàn)數(shù)據(jù)，可以明顯地看出，基本蟻群算法在求解簡單路網(wǎng)的最短路徑時(shí)，速度還是很快的。改進(jìn)人工魚群算法比基本人工魚群算法的運(yùn)算量小，收斂性好。也驗(yàn)證了自適應(yīng)視野改進(jìn)算法的可行性和高效性。

表1 9節(jié)點(diǎn)ACO、AFSA及AVAFSA算法的對比實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法的高效、穩(wěn)定性，假設(shè)路網(wǎng)更復(fù)雜些，抽象為 16節(jié)點(diǎn)的賦權(quán)無向圖，其道路權(quán)重的鄰接矩陣為

圖4為改進(jìn)的自適應(yīng)視野人工魚群算法得出的16節(jié)點(diǎn)靜態(tài)最優(yōu)路徑為7→4→3→2→12→14→1→5→9→10→11→15→16→6→13→8，其中，1→5→9→10→11→15→16為所求的從起點(diǎn)1到終點(diǎn)16的最短路徑。最優(yōu)值為19。

圖4 視野自適應(yīng)人工魚群算法（AVAFSA）搜索的最短路徑

圖5 為16節(jié)點(diǎn)路網(wǎng)中，基本蟻群算法、基本人工魚群算法及自適應(yīng)視野的改進(jìn)人工魚群算法的尋優(yōu)過程對比?？梢钥闯鱿伻核惴ㄓ捎跊]有方向性引導(dǎo)，在路網(wǎng)變復(fù)雜時(shí)，搜索過程中的“之”字形路徑現(xiàn)象更嚴(yán)重；又因?yàn)槠涓怕市院驼答佔(zhàn)饔茫顾惴ㄏ萑肓司植孔顑?yōu)，最終不能得到全局最優(yōu)解?；救斯~群算法在迭代93次后得到全局最優(yōu)解，而改進(jìn)人工魚群算法在迭代35次后就得到全局最優(yōu)解。顯然，改進(jìn)的自適應(yīng)視野的人工魚群算法比基本魚群算法的后期收斂速度快，而且，路網(wǎng)越復(fù)雜（節(jié)點(diǎn)越多），該改進(jìn)算法的優(yōu)勢越明顯。

圖5 ACO、基本AFSA及AVAFSA收斂曲線

下面對ACO、AFSA和AVAFSA的計(jì)算量和收斂速率進(jìn)行比較，仿真環(huán)境和初始條件與上面的 9節(jié)點(diǎn)完全相同，對比實(shí)驗(yàn)結(jié)果如表2所示。

表2 16節(jié)點(diǎn)ACO、AFSA及AVAFSA算法的對比實(shí)驗(yàn)結(jié)果

從表2可以明顯地看出，基本蟻群算法在路網(wǎng)復(fù)雜時(shí)，搜索不到全局最優(yōu)解，只能得出較優(yōu)解，而且算法時(shí)間復(fù)雜度明顯增加。而本文視野自適應(yīng)的改進(jìn)人工魚群算法比基本人工魚群算法收斂速度快、運(yùn)算量小，而且準(zhǔn)確性高。與表 1對比，得出路網(wǎng)越復(fù)雜，該改進(jìn)算法的優(yōu)越性越突出，說明該改進(jìn)算法是一種高效、穩(wěn)定的最短路徑求解方法。

5 結(jié)束語

針對基本人工魚群算法因參數(shù)視野固定不變而導(dǎo)致算法后期收斂速度慢、運(yùn)算量大、陷入局部最優(yōu)的缺陷，本文根據(jù)車輛導(dǎo)航系統(tǒng)中的靜態(tài)最短路徑問題的特點(diǎn)，對人工魚群算法進(jìn)行了改進(jìn)。該改進(jìn)算法只對人工魚的覓食行為的視野進(jìn)行調(diào)整，使其隨著迭代次數(shù)的變化而自適應(yīng)地變化，并設(shè)置了視野值的下限，以防視野過小，算法又陷入局部最小。實(shí)驗(yàn)結(jié)果表明，改進(jìn)型人工魚群算法的收斂速度、計(jì)算量、尋優(yōu)精度和準(zhǔn)確性均優(yōu)于基本蟻群算法及基本人工魚群算法，而且道路越復(fù)雜，節(jié)點(diǎn)越多，這種優(yōu)勢越顯著。

[1] 孫中華. GIS路徑尋優(yōu)中的蟻群算法研究[D]. 南京: 南京理工大學(xué),2009.SUN Z H. Research on Ant Colony Algorithm in GIS Path Optimization[D]. Nanjing: Nanjing University of Science and Technology, 2009.

[2] 譚國真, 高文. 時(shí)間依賴網(wǎng)絡(luò)最小時(shí)間路徑算法[J]. 計(jì)算機(jī)學(xué)報(bào),2002, 25(2):165-172.TAN G Z, GAO W. The minimum time path algorithm of the time-dependent network[J]. Chinese Journal of Computers, 2002,25(2):165-172.

[3] 王海梅. 基于 GIS的最優(yōu)路徑算法研究與實(shí)現(xiàn)[D]. 南京: 南京理工大學(xué), 2008.WANG H M. Research and Implementation of the Optimal Path Algorithm Based on the GIS[D]. Nanjing: Nanjing University of Science and Technology, 2008.and Technology, 2008.

[4] 甘榮偉. 蟻群優(yōu)化算法及其應(yīng)用研究[D]. 廣州: 中山大學(xué), 2009.GAN R W. Research on Ant Colony Optimization and Its Application[D]. Guangzhou: Sun Yat-sen University, 2009.

[5] 張學(xué)敏, 張航. 基于改進(jìn)蟻群算法的最短路徑問題研究[J]. 自動化技術(shù)與應(yīng)用, 2009, 28(6):4-7.ZHANG X M, ZHANG H. Research on the shortest path problem based on an improved ant colony algorithm[J]. Automation Technology and Application, 2009, 28(6):4-7.

[6] 潘海珠, 杜曉昕, 王波. 基于人工魚群的交通誘導(dǎo)系統(tǒng)最優(yōu)查詢研究[J]. 齊齊哈爾大學(xué)學(xué)報(bào), 2012,28(5):6-9.PAN H Z, DU X X, WANG B. Research on the optimal query research of traffic guidance system based on artificial fish-swarm algorithm[J].Journal of Qiqihar University, 2012, 28(5):6-9.

[7] 鄭根讓. 基于混合人工魚群算法車輛擁堵調(diào)度方案[J]. 計(jì)算機(jī)仿真, 2012, 29(6):328-331.ZHEN G R. Vehicle congestion scheduling scheme based on a mixed artificial fish-swarm algorithm[J]. Computer Simulation, 2012, 29(6):328-331.

[8] 李曉磊, 邵之江, 錢積新. 一種基于動物自治體的尋優(yōu)模式：魚群算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2002, 22(11):32-38.LI X L, SHAO Z J, QIAN J X. An optimization mode based on Autonomous: fish-swarm algorithm[J]. Systems Engineering Theory and Practice, 2002, 22(11):32-38.

[9] 李曉磊. 一種新型的智能優(yōu)化方法—人工魚群算法[D]. 杭州: 浙江大學(xué), 2003.LI X L. A New Type of Intelligent Optimization Method: Artificial Fish-swarm Algorithm[D]. Hangzhou: Zhejiang University, 2003.

[10] 江銘炎, 袁東風(fēng). 人工魚群算法及其應(yīng)用[M]. 北京: 科學(xué)出版社,2012.JIANG M Y, YUAN D F. Artificial Fish-swarm Algorithm and Its Application[M]. Beijing: Science Press, 2012.