基于自適應(yīng)遺傳算法的張掖市自駕旅游時(shí)間優(yōu)化

文/孟小丁 許向陽(yáng) 張文高

1 引言

隨著人們生活水平的提高，利用節(jié)假日出行旅游已成為常態(tài)，如何為旅行者提供省時(shí)省力的出行選擇，最大化體驗(yàn)旅行帶來(lái)的收獲，已經(jīng)成為旅游企業(yè)關(guān)注的焦點(diǎn)和相關(guān)學(xué)科的研究熱點(diǎn)。

馮愛芬[1]以洛陽(yáng)市為例，從旅游者和組團(tuán)考察兩個(gè)角度，建立了洛陽(yáng)市最佳旅游路線的圖論模型和數(shù)學(xué)規(guī)劃模型，運(yùn)用Lingo軟件進(jìn)行求解。Hasuike T[2]提出了一種個(gè)性化旅游的框架，將問題歸納為非線性離散優(yōu)化問題，用基于動(dòng)態(tài)規(guī)劃的貪心算法求解得到最優(yōu)旅游路線。陸國(guó)鋒[3]研究了多屬性的景點(diǎn)評(píng)分機(jī)制和多約束多目標(biāo)的旅游路線推薦方法，設(shè)計(jì)了k-Greedy算法求解，實(shí)現(xiàn)了向用戶推薦多條旅行路線。侯樂[4]針對(duì)帶時(shí)間窗的定向問題和帶時(shí)間窗的TSP問題，提出了一種迭代局部搜索結(jié)合布谷鳥搜索的優(yōu)化算法。宋曉宇[5]提出一種新的短時(shí)間體驗(yàn)式路線搜索，目的在于找到一條非重復(fù)多類別且收益最大化的最優(yōu)景點(diǎn)訪問路線，并設(shè)計(jì)SUB和MUB兩種優(yōu)化搜索算法。Gavalas T等人[6]考慮了用戶的偏好，每天的旅行時(shí)間，景點(diǎn)的開放時(shí)間等信息，提出啟發(fā)式的求解方法。Long Liu[7]針對(duì)自駕游和散客群體，提出了滿足用戶喜好并節(jié)省總時(shí)間的實(shí)時(shí)旅游路線推薦系統(tǒng)。王楠[8]重點(diǎn)考慮了興趣點(diǎn)的動(dòng)態(tài)屬性，并提出了基于用戶需求的景點(diǎn)路線利益規(guī)劃算法。張燕君[9]考慮游客需求，交通時(shí)間，景點(diǎn)時(shí)間的不確定性，構(gòu)建多目標(biāo)的團(tuán)隊(duì)個(gè)性化旅游線路模型，提出了改進(jìn)多態(tài)自適應(yīng)的蟻群算法。吳清霞[10]提出了基于興趣點(diǎn)和用戶興趣偏好的個(gè)性化旅游路線推薦算法。

綜上所述，文獻(xiàn)主要對(duì)旅游線路的模型，算法求解兩個(gè)方面做了較為細(xì)致的研究。但實(shí)驗(yàn)仿真中并沒有對(duì)河西走廊地段的景點(diǎn)做具體的研究。本文以張掖市為例，采集數(shù)據(jù)，利用簡(jiǎn)單遺傳算法（Simple Genetic Algorithm，SGA）和自適應(yīng)遺傳算法（Adaptive Genetic Algorithm，AGA）分別求解最佳駕車旅行時(shí)間。自適應(yīng)遺傳算法能夠使得交叉概率和變異概率保持動(dòng)態(tài)變化，改進(jìn)了收斂性能，進(jìn)而顯著提高了搜索效率。

2 問題分析

選取張掖市14個(gè)旅游景點(diǎn)，以其中一個(gè)景點(diǎn)為出發(fā)點(diǎn)，通過(guò)自駕游的形式游覽各個(gè)景點(diǎn)，規(guī)定每個(gè)景點(diǎn)只能訪問1次，最后需返回出發(fā)點(diǎn)，如何安排散客選擇對(duì)這些景點(diǎn)的訪問次序，使得總駕駛時(shí)間最短。這類問題可歸納為TSP問題的一種應(yīng)用，是一種組合優(yōu)化問題。

圖1：交叉操作

圖2：變異操作

其中，目標(biāo)函數(shù)式（1）表示駕車行駛時(shí)間最小，約束條件式（2）和式（3）保證了僅有一條入邊和一條出邊，式（4）表示保證沒有任何子回路解的產(chǎn)生，式（5）表示對(duì)景點(diǎn)是否訪問。

3 簡(jiǎn)單遺傳算法求解

針對(duì)上述的問題，遺傳算法求解的主要步驟可以描述為：

第1步：編碼操作。對(duì)于14個(gè)景點(diǎn)的訪問，給每個(gè)景點(diǎn)編號(hào)（1～14），則（14—8—13—9—6—2—4—7—12—5—11—10—3—1）是一條合法的染色體。

圖3：SGA和AGA運(yùn)行結(jié)果比較

表1：張掖市14個(gè)景點(diǎn)的經(jīng)緯度信息

表2：張掖市各景點(diǎn)之間的駕車時(shí)間 （單位：min）

表3：求解參數(shù)及運(yùn)行結(jié)果

第2步：初始化種群。設(shè)初始化種群的數(shù)目為100，產(chǎn)生100×14的隨機(jī)初始種群作為起始解；

第3步：適應(yīng)度函數(shù)設(shè)計(jì)。記ti，i+1相鄰景點(diǎn)i和i+1之間的駕車行駛時(shí)間，考慮起點(diǎn)終點(diǎn)相同的情況下，個(gè)體的適應(yīng)度函數(shù)為：

優(yōu)化的目標(biāo)為選擇駕車行駛時(shí)間的倒數(shù)，即駕車行駛時(shí)間越短，f取值越大，適應(yīng)值最大的染色體越優(yōu)。

第4步：遺傳算子的設(shè)計(jì)

（1）選擇操作。去除舊群體中適應(yīng)值低的個(gè)體，將適應(yīng)度值大的個(gè)體加入到下一代種群中。

（2）交叉操作。首先產(chǎn)生[1，14]區(qū)間內(nèi)的兩個(gè)隨機(jī)數(shù)r1和r2，確定交配區(qū)域，對(duì)r1和r2兩位置中間的數(shù)據(jù)進(jìn)行交叉。若交叉后有重復(fù)的景點(diǎn)編號(hào)，采用部分映射的方法消除沖突。如圖1所示。

（3）變異操作。變異策略采用對(duì)換變異方法，即產(chǎn)生兩個(gè)[1，14]區(qū)間內(nèi)隨機(jī)整數(shù)，確定兩個(gè)位置，互換其值。如圖2所示。

4 自適應(yīng)遺傳算法求解

在上述SGA的描述中，算法作如下改動(dòng)：

第1步：編碼操作同上；

第2步：產(chǎn)生初始化種群同上。

第3步：定義適應(yīng)度函數(shù)同上，計(jì)算各個(gè)個(gè)體的適應(yīng)度值。

第5步：交叉操作。對(duì)種群中隨機(jī)搭配成對(duì)的每一對(duì)個(gè)體，按照文獻(xiàn)[11]的公式計(jì)算自適應(yīng)交叉概率Pc。以Pc為交叉概率進(jìn)行交叉操作。

第6步：變異操作。對(duì)種群中的所有個(gè)體，按照文獻(xiàn)[11]的公式計(jì)算自適應(yīng)交叉概率Pm。以Pm為變異概率進(jìn)行變異操作。

在式子（7）和（8）中，一般取Pcl=0.9；Pc2=0.6；Pml=0.1；Pm2=0.001。

第7步：計(jì)算新個(gè)體的適應(yīng)度，產(chǎn)生新種群；

第8步：判斷是否達(dá)到給定的迭代次數(shù)，若達(dá)到，則結(jié)束；否則轉(zhuǎn)到第4步。

5 實(shí)例驗(yàn)證

通過(guò)GPSspg查詢網(wǎng)得到百度地圖顯示的張掖市14個(gè)景點(diǎn)的經(jīng)緯度信息，如表1所示。編寫matlab程序計(jì)算得到各景點(diǎn)之間的駕車行駛時(shí)間，如表2所示。

結(jié)合上述數(shù)據(jù)，各自重復(fù)實(shí)驗(yàn)11次，利用SGA計(jì)算得到平均最小駕車行駛時(shí)15.0099h，利用AGA計(jì)算得到平均最小駕車行駛時(shí)間為14.6485h，算法的控制參數(shù)及運(yùn)行結(jié)果見表3所示。進(jìn)化過(guò)程如圖3所示。

6 總結(jié)

本文分別探討了簡(jiǎn)單遺傳算法和自適應(yīng)遺傳算法，應(yīng)用于求解張掖市14個(gè)景點(diǎn)之間旅游路線的最短駕車行駛時(shí)間。結(jié)果表明，自適應(yīng)遺傳算法在改進(jìn)了交叉算子和變異算子之后，程序的運(yùn)行效果更佳，提高了遺傳算法的尋優(yōu)能力。