基于免疫-細菌覓食算法的旅游線路選擇問題研究

賈潤亮

(山西省財政稅務?？茖W校 信息學院，山西 太原 030024)

基于免疫-細菌覓食算法的旅游線路選擇問題研究

賈潤亮

(山西省財政稅務專科學校 信息學院，山西 太原 030024)

針對旅游行業(yè)迅猛發(fā)展的態(tài)勢，對旅游路線選擇問題進行抽象、概化，將旅游路線選擇問題轉(zhuǎn)化為特定條件下數(shù)學方程最優(yōu)化問題。結(jié)合免疫算法和細菌覓食算法融合半解析解的思想，構(gòu)建一種全新的優(yōu)化算法——免疫細菌覓食算法(Generate Bacterial Foraging Algorithm，GBFA)，對旅游路線選擇問題進行求解，對幾種線路的旅游花費、游玩時間等方面進行比較。結(jié)果顯示：GBFA在計算效率上遠遠高于其他方法，路線花費更低、游玩時間更多、交通時間與等待時間更短、游客休息時間更充裕，說明該方法計算結(jié)果更加精確，計算流程更加優(yōu)化。

路徑選擇；等待時間；GBFA；旅游線路；期望花費

目前，社會旅游成為人們消遣的一種重要方式[1]。如何在現(xiàn)有的成本下游覽更多的景點，體驗更加友好的旅行觀感，進而提升旅游的性價比是國內(nèi)外學者廣泛關注的問題。但是，旅行線路規(guī)劃問題涉及到很強的非線性，現(xiàn)有解法多難以收斂[2-3]。鑒于此，國內(nèi)外學者對RA網(wǎng)絡的多協(xié)同排序算法進行了大量研究。SINGH、WU Guang等人[4-5]將旅游花費和游覽的景點進行加權，進而構(gòu)造滿足度函數(shù)，基于遺傳算法對旅游線路規(guī)劃問題進行求解，得到在滿足游覽時間限定和經(jīng)費預算的局部最優(yōu)解，但是文獻[4]和文獻[5]無法適應跨時區(qū)的旅游路線，僅限于小范圍求解。Huiping Liu等人[6]基于蟻群算法對旅游路徑選擇問題進行求解，充分考慮了景點的自身特性，譬如營業(yè)時間、門票價格問題，文獻[6]所使用的蟻群算法容易陷入局部最優(yōu)解，其全局搜索能力和收斂速度、求解精度欠佳。Nuengwong[7]、Dennerline[8]等人基于Priceline多年的旅游數(shù)據(jù)，建立起基于旅客自身消費習慣的路線規(guī)劃數(shù)學模型，并利用蜂群算法求解具有限定條件的數(shù)學方程，得到的結(jié)果更加人性化、更加容易滿足旅客的消費心理，但是文獻[7]和文獻[8]所使用數(shù)據(jù)過于繁雜，計算量過大，而且在計算時容易產(chǎn)生數(shù)值耗散。侯樂等人[9]首先根據(jù)相關目標和約束采用ILS算法求解旅游景點及初始旅游線路，然后在滿足旅游景點時間窗約束及景點總數(shù)不變的情況下采用CS算法進一步最小化旅游線路的時間花費，但是文獻[9]所使用方法計算精度較差。

本文在此基礎上選用細菌覓食算法(簡稱BFA)，同時基于免疫算法(generate and test)的相關概念，融合半解析解的相關思想[10]，針對BFA算法的3個操作環(huán)節(jié)(復制操作環(huán)節(jié)、趨向性操作環(huán)節(jié)和遷移操作環(huán)節(jié))，提出BFA的一種優(yōu)化算法GBFA(Generate Bacterial Foraging Algorithm)：將趨向性操作環(huán)節(jié)中的步長變?yōu)榉枪潭ú介L，可以隨著計算的進行而改變，建立趨向性操作步長的動態(tài)更新機制；此后，利用免疫算法(generate and test)替換BFA的復制操作環(huán)節(jié)，針對細菌群落進行篩選，將其中適應度較高的細菌復制并替換適應度較低的細菌；最后，在遷移操作環(huán)節(jié)中，適應度最高的個體被驅(qū)散的概率為0，適應度最高的個體被驅(qū)散的概率為Ped。利用該算法對旅游路線選擇問題進行求解，充分考慮跨時區(qū)旅游的時差問題，找到景點之后的等待問題、交通耗時問題以及餐飲花費問題。并同當前常用的幾種路線選擇方法進行比較，以驗證本文所提出方法的優(yōu)越性和適用性。

1 問題描述

為了更好地用數(shù)學模型對所研究問題進行描述，對模型中所涉及到的符號進行說明。其中，R為旅游路線，R={r1,r2,r3，…}；T為旅游路線對應的旅游時間，min；C為旅游路線R對應的花費，元；Openi為景點i開門的時間；Closei為景點i關門的時間；Timei為游客到達景點i的時間；Waiti為游客提前到達景點i后所需要的等待時間，min；Visiti為可支配的旅游時間，min；Travel為游客可支配的旅游時間，min;budget為游客的費用預算，元。

旅游花費C主要包括交通費用c(eij)、景點的旅游費用c(i)；旅游時間T主要包括到達景點所需要的旅途時間t(eij)、游覽景點所需要的時間Visiti、提前到達目的地而需要等待的時間Waiti。具體計算方法如下：

(1)

(2)

(3)

如果兩個地點相隔比較遠，就需要考慮時差問題

(4)

式中：Ti為第i個地點的時間，Tj為第j個地點的時間，yi為第i個地點的經(jīng)度，yj為第j個地點的經(jīng)度。第i個地點到第j個地點的距離Li,j為

Li,j=arccos[sinxisinxjcos(yi-yj)+

cosxicosxj]R.

(5)

式中：R為地球的半徑，取6 371.004 km，xi為第i個地點的經(jīng)度，xj為第j個地點的經(jīng)度。

定義旅客滿意度函數(shù)(目標函數(shù))

(6)

式中：ω(R)是權重系數(shù)，代表了旅客對花費的在意程度。

根據(jù)現(xiàn)實問題，游客旅行所花費的總時間必須小于游客預算時間，游客所花費的錢財必須小于游客的預算花費，游客在每個景點的游玩時間必須小于該景點的營業(yè)時間，用數(shù)學語言表示為

T≤Travel，

(7)

C≤budget，

(8)

Visiti≤Closei-Openi.

(9)

至此，將旅客旅行路線規(guī)劃問題變成在有約束情況下數(shù)學模型最優(yōu)化問題。

2 算法簡介

為求解在有約束情況下數(shù)學模型最優(yōu)化問題，下面利用GBFA算法進行解答。

2.1 GBFA算法的基本思想

BFA中第i次的步長為

(10)

式中：Ns為BFA虛擬的細菌群落中細菌游動的最大次數(shù)；Led為細菌游動的初始步長。細菌移動的每一次步長均小于初始步長Led。并且計算開始之時(i值較小)，第i次的步長Ci很大，可以提高搜索的速度，使得計算可以更快進行；隨著計算過程的進行(i值的增大)，第i次的步長Ci會越來越小，這是為了在計算的后期保證足夠的收斂精度。

在趨向性操作步長的動態(tài)更新機制建立之后，將群落中所有細菌的適應度進行累加，并由從大到小的順序進行排列，形成細菌序列。將細菌序列前m(m為百分比)部分的細菌進行復制n次，將細菌序列中的其余細菌進行剔除，m和n的關系為

(11)

如此一來，使用細菌群落中m部分的細菌代表了原有的細菌菌落，可以提高細菌群落的整體覓食能力。此后，依照如下步驟對細菌菌落進行變異、繁殖：

1)挑選出細菌群落中適應度較高的細菌，標記為克隆群體A；

2)克隆群體A繁殖成為群體B：

(12)

式中：Round為四舍五入函數(shù)；S為細菌群落的整體個數(shù)；A(i)為計算的克隆群體A的個數(shù)；i為第i次計算；α為克隆的系數(shù)。為了方便計算，將適應度F進行標準化

(13)

其中，max為取最大值函數(shù)。

3)對群體B進行變異操作，產(chǎn)生群體C：

B(i)=B(i)+βrandomn(C).

(14)

式中：random為隨機函數(shù)；B(i)為計算的克隆群體B的個數(shù)；β為變異概率，計算方法為

β=e-F(n-i+1).

(15)

根據(jù)式(6)可知，適應度越高的個體，變異概率β越大。

因為交叉方法

H=B(x1)-B(x2)+B(x3)-B(x4).

(16)

式中：x1，x2，x3，x4為克隆群體A中4個不同的細菌。將群體C融合進入群體B中，形成群體D：

D=B+C.

(17)

4)在群體D中，將其中前m(m為百分比)部分的細菌進行復制n次，將其余細菌進行剔除。

在傳統(tǒng)的BFA算法中，需要設定一個遷移概率Ped，如果隨機數(shù)小于遷移概率Ped，就會對細菌進行遷移操作。這樣做的目的是希望細菌可以躍出局部最優(yōu)解的陷阱。但是，這種做法同樣具有極大的弊端，因為遷移概率Ped對于所有的細菌都有效，無論細菌的適應度如何，都可能被遷移。GBFA算法在遷移操作環(huán)節(jié)中，適應度最高的個體被驅(qū)散的概率為0，適應度最高的個體被驅(qū)散的概率為Ped，以提高搜索的速度。

根據(jù)以上思想，繪制GBFA算法流程如圖1所示。

圖1 GBFA算法流程

2.2 GBFA算法的斂散性

文獻[11]、文獻[12]對BFA算法的斂散性進行了研究[11-12]，但是文獻[11]、文獻[12]沒有考慮BFA算法模擬菌群內(nèi)部各個細菌個體之間的影響。筆者提出的GBFA雖然沒有觸及到傳統(tǒng)BFA算法的定義基礎，但是由于免疫算法的并入，需要重新證明GBFA的斂散性。

根據(jù)李濤的研究[13]：對于抗體種群A0，抗體空間幾何為I*，v(A(k))為計算所得最優(yōu)解的個數(shù)，B*為最優(yōu)解的個數(shù)，

(18)

化簡得到

P{v(A(k))≠0}+P{v(A(k+1))=

(23)

則有

k=1,2,….

(25)

(32)

綜上所述，GBFA以概率1收斂。

3 仿真實驗

對旅客進行信息錄入，列出所有可能路線，并利用GBFA進行計算，求解出最優(yōu)目標函數(shù)。

3.1 簡單顯示條件下的計算

劉先生家在廣東，來北京出差，居住在速八酒店景泰橋店(箭頭所指方向)，如圖2所示，希望看一下北京的一些古老建筑，比如明清的皇家園林等，但劉先生的時間比較短，時間預算為1 d，費用預算為500元。如果有可能的話，劉先生還想?yún)⒂^天安門廣場的升旗儀式(非必須)。

圖2 景點位置

對于較近的距離，比如天安門到故宮，天壇到劉先生居住的地方，皆采用步行的方式，并不計費。其他用滴滴打車的方式，滴滴打車的方式約每公里1元。表1、表2給出了景點之間的距離、景點門票以及餐飲價格。

表1 景點之間的距離 km

表2 景點門票以及餐飲價格 元

針對上述實例，利用本文所提出的算法進行計算，結(jié)果如下：06:00天安門廣場觀看升旗儀式，之后觀看毛主席紀念堂、人民大會堂外景、國家博物館外景，并于天安門就餐；7:50以滴滴打車的方式去頤和園，游玩至12:00，并在頤和園就餐；13:00以滴滴打車的方式去故宮，游玩至17:00；17:00以滴滴打車的方式去天壇，游玩至21:00并于天壇就餐，結(jié)束行程，共花費329元。

針對計算結(jié)果進行分析，早晨劉先生先由居住地(速八酒店景泰橋店)到達天安門廣場，因為天安門廣場升旗時間較早，所以說首站定在天安門廣場。在瀏覽天安門廣場之后，此時故宮博物院尚未開門，而出城高峰期尚未至，故而可以避開上班高峰期，乘坐滴滴打車到達頤和園；在瀏覽頤和園之后，恰好避開出城高峰期，從頤和園回到故宮，參觀故宮；由于天壇公園閉園較晚，所以最后游玩天壇公園，并于天壇公園就餐，之后劉先生由天壇公園步行回到旅館休息。

3.2 復雜條件下的計算以及與其他方法的比較

假如有10名旅客同時去旅行，時間預算為30 d，費用預算為1萬元，每名乘客有30個想要去的景點。這30個景點的位置為系統(tǒng)隨機生成(可重復)，景點門票隨機生成，景點附近的餐飲價格隨機生成，但都位于歐洲和亞洲，不存在其他地區(qū)。程序計算結(jié)束條件有3個，滿足任何一條皆退出計算。第一，費用預算達到1萬元；第二，所有的景點皆被游覽；第三，游覽時間達到30 d。在程序計算之后，統(tǒng)計10名旅客游覽的景點總數(shù)目以及花費的總數(shù)目。利用GBFA算法(E)對此進行計算，并與ILS-CS優(yōu)化算法(A)、蟻群算法(B)、遺傳算法(C)、蜂群算法(D)相比較，使用Pentium(R) Dual-Core CPU T4400，2.20 GHz，2 G內(nèi)存，Win7X86操作系統(tǒng)，并考慮時差。

根據(jù)圖3可以看出，5種方法在計算該題目的時候，蜂群算法(D)迭代次數(shù)最多，蟻群算法(B)次之，本文所使用的GBFA算法(E)迭代次數(shù)最少。GBFA算法(E) 迭代次數(shù)分別是前4種方法的9.83%、2.73%、34%、0.833%。

圖3 5種算法的迭代次數(shù)

根據(jù)圖4可以看出，5種方法在計算該題目的時候，蜂群算法(D)計算耗時最多，蟻群算法(B)次之，本文所使用的GBFA算法(E) 計算耗時最少。雖然ILS-CS優(yōu)化算法(A)的迭代次數(shù)是遺傳算法(C)迭代次數(shù)的3.5倍，但ILS-CS優(yōu)化算法(A)的計算耗時是遺傳算法(C) 計算耗時的1.08倍，這是因為ILS-CS優(yōu)化算法(A)每一個迭代步的計算量較小。GBFA算法(E) 計算耗時分別是前4種方法的47%、44%、51%、18%。

圖4 5種算法的計算時間

表3列出的是5種計算方法的計算結(jié)果，分別就其休息時間、游玩時間、等待時間、交通時間、游覽景點數(shù)目、花費進行統(tǒng)計，四項的和總共為720 h(30 d)。從表3可以看出，本文所提出的GBFA算法(E)，無論在休息時間、游玩時間、游覽景點數(shù)目方面都是最高的，在等待時間、交通時間、花費方面都是最低的，說明本文所提出的GBFA算法(E)綜合效果最佳，具有更好的適用性，其次為蜂群算法(D)。其休息時間分別是前四種算法的126%、112%、116%、108%，游玩時間分別是前四種算法的106%、105%、104%、102%，等待時間分別是前四種算法的32.5%、50%、37%、68%，交通時間分別是前四種算法的57%、65%、68%、77%，游覽景點數(shù)目分別是前四種算法的113%、110%、113%、112%，交通時間分別是前四種算法的91%、88%、87%、89%。說明本文所提出的方法尋找的解比其他方法找到的解更加精確。

表3 5種算法的計算結(jié)果

4 結(jié) 論

在改進傳統(tǒng)的細菌覓食算法提出免疫-細菌覓食算法，將免疫-細菌覓食應用到旅游路線選擇問題模型中，并與常用的旅游路線選擇問題模型算法相比較，結(jié)論顯示：

1)免疫-細菌覓食算法充分考慮了景點的營業(yè)時間、餐飲費用以及交通時段，并由此來安排旅客的行程，使得旅客參觀景點等待的時間最短，餐飲費用最低，交通所花費的時間最少；

2)與其他四種算法相比較，所使用的GBFA算法(E)迭代次數(shù)最少，分別是前4種方法的9.83%、2.73%、34%、0.833%；

3)與其他四種算法相比較，所使用的GBFA算法(E)計算耗時最短，分別是前4種方法的47%、44%、51%、18%；

4)與其他四種算法相比較，所使用的GBFA算法(E)尋找的解更加優(yōu)化，在相同的限定條件下，本文所選取的方案可以游覽更多的景點，游玩更長的時間，花費更少的錢財。

[1] TANG L, KAN Z, ZHANG X, et al. Travel time estimation at intersections based on low-frequency spatial-temporal GPS trajectory big data[J]. Cartography & Geographic Information Science, 2016.

[2] 尹陽. 基于節(jié)約里程算法的瀝青配送線路優(yōu)化研究——以廈門新立基瀝青配送體系為例[J]. 長春工程學院學報(自然科學版), 2016(1).

[3] 肖海紅, 蔣瑞波, 王蘭洲,等. 基于GIS矢量數(shù)據(jù)結(jié)構(gòu)的公交數(shù)據(jù)模型的實現(xiàn)[J]. 長春工程學院學報(自然科學版), 2015(3).

[4] SINGH, Harpreet, SKRYPCHUK, Lee. Route Planning Device and Associated Method:, WO/2016/026865[P]. 2016.

[5] 曹體濤,羅刊. 混沌微粒群優(yōu)化算法及其在非線性函數(shù)參數(shù)估計中的應用[J]. 黑龍江工程學院學報,2014(5):54-56.

[6] WU Guang, JIANG Hui-xian, CHEN Fen. Research on Allocation of the Emergency Evacuation in and Around the Major Shopping Malls[J]. Journal of Fujian Normal University(Natural Science Edition), 2016.

[7] LIU Huiping, JIN Cheqing, ZHOU Aoying. Popular Route Planning with Travel Cost Estimation[M]// Database Systems for Advanced Applications. Springer International Publishing, 2016.

[8] TUAYCHAROEN N, SAKCHAROEN A, CHA-AIM W. Bangkok Bus Route Planning API[J]. Procedia Computer Science, 2016, 86:441-444.

[9] 黃恩洲. 基于粒子群—小波神經(jīng)網(wǎng)絡的短時交通量預測[J]. 黑龍江工程學院學報,2014(2):42-45.

[10] DENNERLINE R R. Database System To Organize Selectable Items For Users Related to Route Planning[J]. 2016.

[11] 侯樂, 楊輝華, 樊永顯,等. 基于ILS-CS優(yōu)化算法的個性化旅游線路研究[J]. 計算機科學與探索, 2016, 10(1):142-150.

[12] 王俊奇, 李闖, 董曄. Bishop 法的半解析解及其廣義數(shù)學模型[J]. 水利與建筑工程學報, 2015(6):123-128.

[13] TANG W J, LI M S, HE S, et al. Optimal Power Flow With Dynamic Loads Using Bacterial Foraging Algorithm[C]// Power System Technology, 2006. PowerCon 2006. International Conference on. IEEE, 2006:1-5.

[14] DAS S，BISWAS A，DASGUPTA S，et al． Bacterial Foraging Optimization Algorithm: the Oretical Foundations，Analysis，and Applications [C]∥Foundations of Computational Intelligence Volume 3． Berlin / Heidelberg: Springer，2009: 23-55.

[責任編輯：郝麗英]

Research on the tourism route selection based on generate bacterial foraging algorithm

JIA Yunliang

(Shanxi Institute of Taxation, Taiyuan 030024，China)

For the rapid development of the tourism industry in the current situation, this paper explores the issue of which is widely concerned—the problem of tourism route selection. Aiming at the problem of tourism route selection, it makes it abstracted and generalized, transforming the problem of tourism route selection into the optimization problem of mathematical equation under certain conditions. Combined with the concept of immune algorithm and bacterial foraging algorithm, and compromising the idea of semi-analytical solution, this paper constructs a new optimization algorithm—Generate Bacterial Foraging Algorithm (GBFA) to solve the problem of tourism route selection, from the aspects of travel cost, play time and so on. The result shows: GBFA is much higher than other methods in computational efficiency, the cost of solution route is lower, the play time is increased, traffic time and waiting time are shorter, and the disposable rest time of visitors is more abundant, of which reflects this algorithm is more accurate, and the calculation process is more optimized.

path choice; waiting time; GBFA; expected cost

10.19352/j.cnki.issn1671-4679.2016.06.007

2016-06-02

賈潤亮(1973-),男，講師，研究方向：人工智能；計算機應用.

O246

A

1671-4679(2016)06-0029-06