一種關(guān)于駕游路線規(guī)劃的分布均勻度自適應(yīng)蟻群算法

宋明杰，吳宇航

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

0 引言

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

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

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

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

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

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

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

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

圖1 蘇州21個(gè)景點(diǎn)相對(duì)分布圖Fig.1 Relative distribution of 21 scenic spots in Suzhou

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

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

2.1 基本蟻群算法

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

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

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

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

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

為城市i的聚度[7]。

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

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

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

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

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

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

3.1 蟻群算法操作流程

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

Step1：參數(shù)初始化

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

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

Step2：迭代過(guò)程

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

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

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

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

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

選擇城市j；

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

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

終止螞蟻迭代的遍歷后，按照式（5）對(duì)所有城市的各條路徑整體更新其信息量。具體算法流程如圖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

全程路線長(zhǎng)度為250.9475km，油價(jià)費(fèi)用約為169.3895625元。

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

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

4 結(jié)論

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