宋明杰，吳宇航

(1.華北理工大學(xué) 理學(xué)院，河北 唐山 063210；2.華北理工大學(xué) 教務(wù)處，河北 唐山 063210；3.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點實驗室，河北 唐山 063210)

0 引言

自駕游是當(dāng)今熱門的出行方式，是以旅行人自行駕駛交通工具，有組織、有計劃的按照既定方案進(jìn)行旅行[1]，其在旅游目的地的選擇、到達(dá)與停留時間以及食宿安排上都有很大的自主性，與傳統(tǒng)的參團(tuán)方式相比更有獨特魅力。如何合理的規(guī)劃旅行路線，在旅行體驗和經(jīng)濟(jì)開支上進(jìn)行合理平衡，成為廣大自駕游愛好者需要考慮的重要因素[2]，因此如何規(guī)劃旅行路線成為了一個現(xiàn)實性的研究課題。

蟻群算法[3]是近年來出現(xiàn)的一種新型的模擬進(jìn)化算法。它充分利用了蟻群搜索食物的過程與旅行商問題（TSP）[4]之間的相似性。蟻群算法在求解復(fù)雜優(yōu)化問題方面具有很大的優(yōu)越性，而引入分布均勻度后的自適應(yīng)蟻群算法在加速收斂和防止早熟停滯現(xiàn)象之間取得很好的平衡，更適合于求解大規(guī)模的TSP問題。

蘇州歷史悠久，是國家首批 24個歷史文化名城之一，以其獨特的園林景觀被譽(yù)為“中國園林之城”，素有“人間天堂”、“東方威尼斯”、“東方水城”的美譽(yù)。蘇州園林是中國私家園的代表，被聯(lián)合國教科文組織列為世界文化遺產(chǎn)，是人們最好的旅游勝地之一。本文以蘇州21個景點為例設(shè)定自駕游旅游路線。

1 數(shù)據(jù)獲取及數(shù)據(jù)預(yù)處理

本文選取蘇州為旅游目的地，將 21個蘇州當(dāng)?shù)鼐包c設(shè)為旅游結(jié)點。通過查閱相關(guān)數(shù)據(jù)可得到這21個景點的經(jīng)緯度、票價和逗留時間等相關(guān)信息，如表1所示。

表1 蘇州21個當(dāng)?shù)鼐包c相關(guān)信息表Tab.1 Information table of 21 local scenic spots in Suzhou

利用MATLAB軟件根據(jù)經(jīng)緯度與距離之間的關(guān)系，求出21個景點兩兩之間的最短距離?？紤]到蘇州作為交通發(fā)達(dá)的一線城市，蘇州內(nèi)部各景點之間的距離矩陣為對稱矩陣。（給出前十個景點之間的最短距離矩陣）

并根據(jù)Google earth繪出21個景點的相應(yīng)的分布圖，如圖1所示。

圖1 蘇州21個景點相對分布圖Fig.1 Relative distribution of 21 scenic spots in Suzhou

從圖1中可以明顯看出，景點2、3、4、5、6、7、8、9、10、11、12、13、15 比較集中，而景點1、14、16、17、18、19、20、21相對分散。這對自駕游路線的規(guī)劃有一定性的指導(dǎo)作用。

2 基于蟻群算法求解最少遍歷路程的模型

2.1 基本蟻群算法

蟻群算法是一種通過模擬自然界螞蟻尋徑的行為的進(jìn)化算法。螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素，當(dāng)它們碰到一個還沒有走過的路口時，就隨機(jī)地挑選一條路徑前行，與此同時釋放出與路線長度有關(guān)的信息素，路徑越長，釋放的激素濃度越低，當(dāng)后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率就會相對較大，這樣形成了一個正反饋。最優(yōu)路徑上的激素濃度越來越大，而其它的路徑上激素濃度卻會隨著時間的流逝而消減。螞蟻通過個體間的信息交流和相互協(xié)作找到最優(yōu)路線。

2.2 聚度和信息權(quán)重

在基本蟻群算法中，加速收斂和防止早熟、停滯現(xiàn)象是一對矛盾。為了加速收斂，Ant-Q Sysetm[5]讓信息量最大的路徑對每次路徑的選擇和信息量的更新起主要的作用。由于強(qiáng)化了最優(yōu)信息的反饋，會導(dǎo)致早熟、停滯現(xiàn)象。而MAX-MIN 蟻群系統(tǒng)[6]將各個路徑上的信息量的更新限定在固定的范圍內(nèi)，雖然在一定程度上避免了早熟、停滯現(xiàn)象，但在解的分布較分散時收斂速度較慢。本文提出的基于分布均勻度的自適應(yīng)蟻群算法根據(jù)螞蟻選路的分布均勻情況，動態(tài)地調(diào)整信息量更新策略和確定每次選擇路徑的概率，這樣，可以在加速收斂和防止早熟、停滯現(xiàn)象之間取得很好的平衡。為此，引入“聚度”的概念來衡量解的均勻程度，從而決定每次選擇路徑的概率以及信息量更新的策略。當(dāng)所有路徑上螞蟻的分布相對比較分散時，聚度就較小，此時難以強(qiáng)化最優(yōu)信息，可能導(dǎo)致搜索速度較慢。因此，要強(qiáng)化正反饋信息，應(yīng)該讓較少的幾個較優(yōu)的路徑有較大的概率被選取；在信息量更新時，應(yīng)該僅讓較少的幾個較優(yōu)的路徑上的信息量得到較大程度的增強(qiáng)。反之，在所有路徑上螞蟻的分布相對比較集中時，聚度就較大，此時易引起早熟、停滯現(xiàn)象。因此，要使解趨于多樣化，應(yīng)該使較多的路徑有可能被選取，在信息量更新時，應(yīng)該讓較多路徑上的信息量得以增強(qiáng)。通過這樣動態(tài)的自適應(yīng)調(diào)節(jié)，可以在有效地改善螞蟻搜索速度的同時避免局部優(yōu)化。為此，我們在基于分布均勻度的自適應(yīng)蟻群算法的迭代過程中，根據(jù)各條可能的路徑上的聚度來確定下一次迭代中可供螞蟻選擇的路徑的信息權(quán)重，并以此來確定它們被選中的概率。

設(shè)從城市i共有r條路徑到達(dá)另外r個城市i1,i2,…,ir，另設(shè)上一次迭代中，經(jīng)過這r條路徑上的螞蟻數(shù)分別為 a1,a2,…,ar，如圖2所示。記：

圖2 源自城市i的各條路徑上螞蟻的分布情況Fig.2 Ant distribution on each path from city i

為城市i的聚度[7]。

在改善螞蟻搜索速度的同時避免局部優(yōu)化，根據(jù)城市i的聚度sta(i)來確定螞蟻在該城市時下一步可供選擇的路徑的條數(shù)w，這里?。?/p>

設(shè)定信息權(quán)重[8]來限制信息量和期望程度對螞蟻選擇路徑概率的影響，從而調(diào)整各個路徑被選中的概率。按照信息量的大小對以城市 i為起點的路徑進(jìn)行排序，將序號存于數(shù)組rank中，即數(shù)組元素rank[ j]的值為路徑(i,j)的序號。由（2）式計算得到的下一步可供選擇的路徑條數(shù)為w，取q=w/ r，記：

則ijξ為路徑(i,j)的信息權(quán)重。故螞蟻在城市i按選擇城市j的概率為：

利用信息量的均勻度自適應(yīng)[9][13]地進(jìn)行信息量的更新，動態(tài)地調(diào)整各路徑上的信息量的分布，其更新規(guī)律為：

Ll(t)為本次迭代中第l只螞蟻遍歷的路徑全長。ψl為第l只螞蟻所對應(yīng)的解對該路徑上的信息量更新的影響程度。ψl的計算方法如下：設(shè)經(jīng)過路徑(i,j)的螞蟻總數(shù)為 k，對它們在本次迭代中遍歷的路徑全長由小到大進(jìn)行排序，所得序號存放于數(shù)組rank1中，即rank1[ l]表示第l只螞蟻對應(yīng)的序號，則：

3 基于蟻群算法求解最少遍歷路程的模型求解

3.1 蟻群算法操作流程

在本文中，蟻群算法的具體實現(xiàn)步驟為：

Step1：參數(shù)初始化

令t=0，設(shè)置最大循環(huán)次數(shù)Ncmax，循環(huán)次數(shù) Nc=0 ；

將m只螞蟻置于n個節(jié)點上，在每個節(jié)點i放置bi(t)只螞蟻；

Step2：迭代過程

①對n個城市進(jìn)行循環(huán)

計算城市 i(1≤i≤n)的聚度，并求出選擇路徑數(shù)量w。

②對m只螞蟻進(jìn)行循環(huán)

當(dāng)下一步城市j可選擇城市數(shù)量小于w時，設(shè)定閾值0.4r，當(dāng)w＜0.4r時，取q0=0.8；當(dāng)w≥0.4r時，取q0=0.2

當(dāng)下一步城市j可選擇城市數(shù)量不小于w時，可根據(jù)：

選擇城市j；

若選擇該路徑的螞蟻數(shù)量大于螞蟻數(shù)量的1/3，終止遍歷。并根據(jù)公式：

局部更新路徑(i,j)上的信息量；

終止螞蟻迭代的遍歷后，按照式（5）對所有城市的各條路徑整體更新其信息量。具體算法流程如圖3所示。

圖3 算法流程圖Fig.3 Algorithm flow chart

3.2 模型求解結(jié)果及分析

利用MATLAB軟件進(jìn)行編程，得到模型求解的結(jié)果，如圖4所示。

圖4 模型求解結(jié)果Fig.4 Model solution results

由上圖可知最短路線為：

20→18→21→19→17→16→14→10→13→15→11→12→8→9→7→6→5→3→4→2→1

全程路線長度為250.9475km，油價費用約為169.3895625元。

查詢相關(guān)法律法規(guī)[10]可知，蘇州市區(qū)限速60 km/h，高速公路限速110 km/h，該路線各相鄰景點之間所需駕車時間均不大于一個小時，暫不計入時程安排。

游歷蘇州上述21個景點大概需要21天，門票價格合計為1107元，油價費用約為169.3895625元，食宿另算。實際上，一次性旅行上述21個景點并不實際，這里只是舉例介紹，自駕游的人們可根據(jù)自己喜好和實際假期時間合理規(guī)劃自己的行程。

4 結(jié)論

本文以蘇州為例，建立基于均勻度的自適應(yīng)蟻群算法的自駕游設(shè)計路線模型，以最短路線為標(biāo)準(zhǔn)，相對應(yīng)的時間和路程費用最小，食宿根據(jù)個人喜好以及經(jīng)濟(jì)能力自行設(shè)定。熱衷于自駕游的年輕人可以利用此模型自行設(shè)計自己與好友的小長假旅游路線，平時工作忙碌的家庭可在長假時帶著妻子與孩子駕車去放松心情，釋放壓力