周 生 超

(濰坊科技學(xué)院 商務(wù)技術(shù)學(xué)院，山東 壽光 262700)

蟻群算法(ACO)是一種尋找最優(yōu)路徑的概率型算法。最早由意大利學(xué)者M(jìn)arco、Dorigo等通過(guò)對(duì)螞蟻覓食行為的研究得出。螞蟻在尋找到食物后會(huì)自動(dòng)散發(fā)一種信息素，該信息素會(huì)對(duì)其他螞蟻產(chǎn)生某種影響，使其順著該條路徑來(lái)尋找食物，隨著螞蟻的不斷增多，會(huì)散發(fā)更多的信息素，由此形成正強(qiáng)化。同時(shí)，螞蟻本身也會(huì)以一定概率(較小概率)選擇其他區(qū)域搜索食物，這樣就保證了螞蟻能以最優(yōu)的行為尋找到最多的食物。與其它啟發(fā)式算法想比，蟻群算法除了正反饋機(jī)制、全局搜索外，不需要算法外部的干預(yù)，可以按照預(yù)期的計(jì)劃，自發(fā)地尋找到期望的結(jié)果[1]，并且對(duì)于初始解要求較低，參數(shù)個(gè)數(shù)相對(duì)較少，易于解決組合優(yōu)化問(wèn)題[2]。 蟻群算法主要應(yīng)用在TSP(旅行商問(wèn)題)，此外在中國(guó)郵路[3]，車(chē)間作業(yè)調(diào)度，圖像處理[4]，電網(wǎng)規(guī)劃[5]以及網(wǎng)絡(luò)拓?fù)鋄6]等方面應(yīng)用也較為廣泛。

壽光是我國(guó)著名的“蔬菜之鄉(xiāng)”，“三圣(農(nóng)圣、文圣、鹽圣)故里”，歷史悠久，文化旅游資源非常豐富，但由于自然和歷史原因，各景區(qū)在壽光地理位置較為分散，旅游集聚效應(yīng)比較弱，吸引力不強(qiáng)。本文將蟻群算法基本原理應(yīng)用到壽光文化旅游線路的優(yōu)化設(shè)計(jì)上，通過(guò)對(duì)景區(qū)資源數(shù)據(jù)的收集和分析，并運(yùn)用MATLAB軟件，計(jì)算出壽光文化旅游的最佳線路，為來(lái)壽光的游客提供借鑒和指導(dǎo)。

1 算法描述

1.1 參數(shù)設(shè)定

將m只螞蟻放置在n個(gè)地點(diǎn)，定義每條路徑上的初始信息素濃度為常數(shù)c，信息素濃度會(huì)隨著時(shí)間的推移不斷揮發(fā)，設(shè)ρ為信息素殘留系數(shù)(1-ρ為信息素?fù)]發(fā)程度)。τij記為點(diǎn)i到點(diǎn)j路徑上的信息素殘留度。ηij記為點(diǎn)i到點(diǎn)j的期望值，與距離成反比，dij記為點(diǎn)i到點(diǎn)j的距離。參數(shù)α為信息啟發(fā)因子，即信息素殘留度對(duì)螞蟻選擇路線的影響程度；β為期望啟發(fā)因子，即路徑可見(jiàn)度的相對(duì)重要性。本文最大迭代次數(shù)設(shè)為200。

1.2 選擇概率

設(shè)螞蟻K在t時(shí)刻，從點(diǎn)i轉(zhuǎn)移到點(diǎn)j的轉(zhuǎn)移概率可表達(dá)為:

(1)

式(1)allowedk-tabuk中示螞蟻可選擇地點(diǎn)的集合，該集合點(diǎn)的數(shù)目隨螞蟻路線的選擇而不斷減少。

1.3 調(diào)整與更新

假設(shè)在n時(shí)刻，螞蟻完成了一次覓食活動(dòng)(即完成一次循環(huán))，此時(shí)，原路徑上的信息素會(huì)隨著時(shí)間的推移不斷揮發(fā)，可用參數(shù)ρ來(lái)表示，而隨著每一次螞蟻的經(jīng)過(guò)，又會(huì)產(chǎn)生新的信息素，其關(guān)系可表述為：

τij(t+n)=prij(t)+Δ τij(t)

(2)

(3)

式(3)中，Q為參考常數(shù)。

1.4 算法流程圖

根據(jù)蟻群算法的基本原理，其算法流程圖如圖1所示。

圖1 蟻群算法流程圖

2 優(yōu)化應(yīng)用

2.1 數(shù)據(jù)來(lái)源與選取

2.1.1 資源選取

本文根據(jù)壽光市現(xiàn)有旅游資源的等級(jí)狀況以及景區(qū)的影響力，共選取10個(gè)具有代表性的旅游性景點(diǎn)(見(jiàn)表1)進(jìn)行旅游線路優(yōu)化設(shè)計(jì)。

表1 壽光市文化旅游資源定量評(píng)價(jià)表

2.1.2 數(shù)據(jù)來(lái)源

本文以壽光政務(wù)網(wǎng)1和相關(guān)文件的統(tǒng)計(jì)資料為主，通過(guò)整理、統(tǒng)計(jì)得出壽光市文化旅游資源的相關(guān)數(shù)據(jù)；通過(guò)百度地圖、百度地圖開(kāi)放平臺(tái)，《壽光市交通旅游圖》等途徑整理出各旅游景區(qū)的經(jīng)緯度(表2)、距離(表3)等數(shù)據(jù)。

2.2 算法運(yùn)用

本文針對(duì)壽光市10個(gè)具有代表性的旅游景點(diǎn)，以壽光市府所在地為出發(fā)點(diǎn)，運(yùn)用蟻群算法進(jìn)行最優(yōu)線路設(shè)計(jì)，將問(wèn)題轉(zhuǎn)化為求10個(gè)點(diǎn)之間的路徑尋優(yōu)(1-10個(gè)點(diǎn)的編號(hào)見(jiàn)表2 )。首先對(duì)原始數(shù)據(jù)進(jìn)行優(yōu)化計(jì)算，利用百度地圖開(kāi)放平臺(tái)選取10個(gè)點(diǎn)的位置坐標(biāo)，并以自駕游的方式選取點(diǎn)與點(diǎn)之間的推薦路線距離，形成距離矩陣(表3)；其次根據(jù)已取得的數(shù)據(jù)，將對(duì)應(yīng)的坐標(biāo)點(diǎn)和距離矩陣，導(dǎo)入至MATLAB軟件，根據(jù)蟻群算法的原理進(jìn)行編程計(jì)算最優(yōu)路線，得到優(yōu)化路徑(圖2)。

圖2 壽光文化旅游ACA最優(yōu)化路徑

表2 壽光市文化旅游景點(diǎn)坐標(biāo)

表3 壽光市文化旅游景點(diǎn)間距離

從圖2可以看出，全局最優(yōu)解路徑大致成一矩形，從生態(tài)農(nóng)業(yè)觀光園(編號(hào)3)出發(fā)并回到生態(tài)農(nóng)業(yè)觀光園的閉合線路。即生態(tài)農(nóng)業(yè)觀光園(編號(hào)3)—蔬菜高科技示范園(編號(hào)1)—中華牡丹園(編號(hào)2)—壽光海洋極地世界(編號(hào)5)—濱河城市濕地公園(編號(hào)4)—三元朱村(編號(hào)8)—巨淀湖風(fēng)景區(qū)(編號(hào)6)—林海生態(tài)博覽園(編號(hào)7)—羊口航海博物館(編號(hào)9)—宏源酒文化博物館(編號(hào)10)—農(nóng)業(yè)生態(tài)觀光園(編號(hào)3)。同時(shí)，由圖3算法收斂軌跡可以看出結(jié)果穩(wěn)定性較好。進(jìn)一步通過(guò)表3可知此路線的距離為173.6km。其地理示意圖如下：

圖3 壽光文化旅游蟻群算法收斂軌跡

圖4 壽光市文化旅游最優(yōu)路線示意圖

結(jié)論

蟻群算法是一種路徑搜素尋優(yōu)算法，對(duì)TSP一類問(wèn)題提供了很好的解決方案。本文從定量與定性相結(jié)合的角度對(duì)壽光市文化旅游進(jìn)行路徑尋優(yōu)，避免了單一評(píng)價(jià)存在的不足[7]。但在具體的運(yùn)算過(guò)程中，參數(shù)設(shè)置的不同會(huì)對(duì)運(yùn)算結(jié)果產(chǎn)生一定的影響。為避免此類問(wèn)題，結(jié)合文中案例在MATLAB中進(jìn)行了參數(shù)微調(diào)，并進(jìn)行了多次程序運(yùn)算求得最優(yōu)路徑，發(fā)現(xiàn)結(jié)果(循環(huán)路徑)趨于一致，其變化主要體現(xiàn)在起始點(diǎn)的異同，這對(duì)游客的路徑選擇并無(wú)影響。

壽光地區(qū)歷史文化悠久，文化資源極其豐富，本文通過(guò)MATLAB軟件進(jìn)行編程運(yùn)算，得出最優(yōu)文化旅游線路，不僅有利于游客節(jié)省旅游成本，同時(shí)對(duì)于游客了解壽光歷史乃至中國(guó)優(yōu)秀傳統(tǒng)文化具有很好的幫助作用。本文在景點(diǎn)、景區(qū)的選擇上主要考慮了獨(dú)特性和知名度，具有一定的代表意義。但對(duì)具有較高知名度的蔬菜博覽會(huì)基于時(shí)效性原因，沒(méi)有進(jìn)行考慮。此外，對(duì)于其他一些景區(qū)景點(diǎn)因其資源獨(dú)特性差或種類單一問(wèn)題，也不在考慮范圍之內(nèi)。