基于改進(jìn)混合蛙跳算法的個(gè)性化旅游路線推薦

申曉寧 王森林 吳俊潮 仇友輝 張磊 李常峰 王玉芳

0 引言

隨著人們生活水平的不斷提高,越來越多的人會(huì)在閑暇之余選擇外出旅游,也因此帶動(dòng)了不少城市第三產(chǎn)業(yè)的發(fā)展.而外出旅游到一個(gè)陌生的地方,如果不提前做好旅游路線的規(guī)劃,可能會(huì)導(dǎo)致在旅行過程中出現(xiàn)費(fèi)時(shí)、費(fèi)錢等體驗(yàn)差的問題.同時(shí),不同的旅游人群對(duì)于歷史人文、自然景觀、美食購物等有不同的需求.因此,如何針對(duì)旅游者的個(gè)性需求,規(guī)劃適合的旅游路線,并為其選擇合適的出行方式以提高在旅游過程中的體驗(yàn),對(duì)于民眾生活質(zhì)量的提升具有重要意義[1].

旅游路線規(guī)劃問題是基于經(jīng)典的旅行商問題演化而來的,其主要思想是將候選城市的景點(diǎn)按照一定的規(guī)則進(jìn)行組合優(yōu)化.目前國內(nèi)外對(duì)此問題的研究頗為廣泛,針對(duì)此問題還提出了一些其他的改進(jìn)算法,如動(dòng)態(tài)規(guī)劃算法[2]、模擬退火算法[3]、蟻群算法[4]等.楊萍[5]的研究表明,路線規(guī)劃者最終考慮的目標(biāo)主要分為兩種,一是成本最低,二是收益最大;明勇等[6]以城市垃圾回收路線總路徑、車輛總費(fèi)用和懲罰成本為目標(biāo)建立了城市生活垃圾回收路徑規(guī)劃的數(shù)學(xué)模型,并對(duì)基本混合蛙跳算法進(jìn)行了改進(jìn),提出了一種能夠有效實(shí)現(xiàn)城市垃圾回收的路線規(guī)劃方法;黃于欣等[7]針對(duì)多景點(diǎn)景區(qū)路徑規(guī)劃問題提出了一種改進(jìn)的蟻群算法,有效地避免了算法陷入局部最優(yōu),使得算法快速收斂;楊曉敏[8]通過對(duì)蟻群算法的參數(shù)調(diào)整和改進(jìn),成功實(shí)現(xiàn)了黃河金三角旅游路線的規(guī)劃;陳春朝等[9]針對(duì)蛙跳算法迭代速度慢的問題提出了改進(jìn)混合蛙跳算法,提高了算法的進(jìn)化速度和精度,并將其用于優(yōu)化人工勢(shì)場的參數(shù)以提高路徑規(guī)劃能力;Shiripour等[10]根據(jù)旅行人口對(duì)鏈接時(shí)間的影響和在網(wǎng)絡(luò)上的分布方式,提出了混合整數(shù)非線性規(guī)劃模型,并提出了求解模型的遺傳算法(GA),解決了規(guī)劃出行時(shí)間靈活的人行道網(wǎng)絡(luò)問題;Reyes-Rubiano等[11]為了更好地指導(dǎo)搜索過程,通過在可變鄰域搜索框架內(nèi)集成偏向隨機(jī)化策略,提出了一種基于元啟發(fā)式的方法,用于解決同時(shí)考慮了經(jīng)濟(jì)、環(huán)境和社會(huì)維度的多站點(diǎn)車輛路徑問題;Snchez-Oro等[12]提出了一種通用的變量鄰域搜索算法,尋求使路線總數(shù)、總旅行成本和最長路線最小化的開放式車輛路徑問題解決方案.本文在以上研究的基礎(chǔ)上,建立個(gè)性化旅游路線推薦問題的優(yōu)化模型,并針對(duì)該模型的特點(diǎn),提出一種基于改進(jìn)混合蛙跳算法的個(gè)性化旅游路線推薦方法.通過調(diào)整可控精度在算法接近結(jié)束時(shí)擴(kuò)大搜索范圍,以降低遺漏更優(yōu)解的風(fēng)險(xiǎn);通過在劣解的改進(jìn)過程中增加篩選準(zhǔn)則以強(qiáng)化局部搜索能力,從而在保持精度的情況下盡可能加快收斂速度;通過引入懲罰因子大幅度降低異常解的適應(yīng)度,使其在子群的更新中被淘汰,以及時(shí)處理異常解,提高算法的運(yùn)算速度.以南京三日游為旅游路線優(yōu)化問題的實(shí)例,對(duì)所提模型和方法進(jìn)行了仿真驗(yàn)證.

1 基本蛙跳算法原理

混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)是由Eusuff和Lansey為解決組合優(yōu)化問題于2003年提出的一種全新的元啟發(fā)式群體進(jìn)化算法,具有高效的計(jì)算性能和優(yōu)良的全局搜索能力[13].SFLA的思想是:在一片濕地中生活著一群青蛙,濕地內(nèi)離散地分布著許多石頭,青蛙通過在不同的石頭上跳躍以找到食物較多的地方.每只青蛙可以定義為問題的一個(gè)解.將濕地的整個(gè)青蛙群體分為不同的子群體.在子群體中的每個(gè)個(gè)體有自己的文化,既影響其他個(gè)體,也受其他個(gè)體的影響,在子群內(nèi)個(gè)體之間通過文化的交流實(shí)現(xiàn)信息的交換,執(zhí)行局部搜索策略.每個(gè)個(gè)體隨著子群體的進(jìn)化而進(jìn)化.每個(gè)子群體也有著自己的文化,當(dāng)子群體進(jìn)化到一定階段以后,各個(gè)子群體再進(jìn)行混洗,實(shí)現(xiàn)子群體間思想的交流(全局信息交換),直到滿足所設(shè)置的終止條件后算法停止.基本混合蛙跳算法SFLA的偽代碼如算法1所示:

算法1基本蛙跳算法SFLA

輸入:子群個(gè)數(shù)M,子群內(nèi)個(gè)體數(shù)量I,種群個(gè)體總數(shù)量I×M,子群更新次數(shù)N,混合迭代次數(shù)G,當(dāng)前迭代次數(shù)g.

輸出:全局最優(yōu)解.

a) 初始化種群,計(jì)算個(gè)體目標(biāo)函數(shù)值;

b) forg=1 toGdo

c) 對(duì)所有個(gè)體按目標(biāo)函數(shù)值從小到大排序并分成M個(gè)子群;∥假設(shè)為最小化問題,目標(biāo)值越小,則個(gè)體越優(yōu);

d) 根據(jù)排序與分組結(jié)果記錄當(dāng)前全局最優(yōu)解Xg、各子群局部最優(yōu)解Xb、局部最差解Xw;

e) fori=1 toNdo

f)Xwnew=Xw+λ(Xb-Xw)∥λ為0～1的隨機(jī)數(shù);

g) ifF(Xwnew)

h)Xw=Xwnew

i) elseX′wnew=Xw+λ(Xg-Xw)∥λ為0～1的隨機(jī)數(shù);

j) end if

k) ifF(X′wnew)

l)Xw=X′wnew

m) else

n) 隨機(jī)產(chǎn)生新解代替Xw;

o) end if

p) 對(duì)組內(nèi)個(gè)體按目標(biāo)值從小到大排序,重新確定局部最優(yōu)解Xb,局部最差解Xw;

q) end for

r) 將所有個(gè)體混洗,記錄全局最優(yōu)個(gè)體Xg;

s) end for

其中,分組是將所有個(gè)體按目標(biāo)值大小進(jìn)行升序排序后,將種群分成了M個(gè)子群,每個(gè)子群中個(gè)體數(shù)量為I.按照混合蛙跳算法的分組規(guī)則將每個(gè)個(gè)體分配至各自的子群.分配規(guī)則如式(1)與表1所示.

表1 子群分配表

Race(k)=[rank(k),rank(M+k),

rank(2M+k),…,rank((I-1)M+k)],

(1)

式中,Race(k)表示編號(hào)為k的子群,rank(k)表示排序在第k位的個(gè)體,k=1,2,…,M.

注：rank(·)為各排名對(duì)應(yīng)的個(gè)體.

2 數(shù)學(xué)模型建立

2.1 數(shù)學(xué)模型假設(shè)

為了便于模型描述,本文做出如下假設(shè):

1)假設(shè)旅游者從自己所在地到達(dá)旅游目的城市的相關(guān)影響因素不在路線規(guī)劃考慮之內(nèi),模型選取的出發(fā)點(diǎn)為旅游者所在旅游目的城市的任意景點(diǎn)或者酒店.

2)根據(jù)文獻(xiàn)[14],假設(shè)旅游者在旅游過程中只能選擇步行、公交、地鐵、駕車4種出行方式,且若選中某個(gè)景點(diǎn),該景點(diǎn)只能被游覽一次.

3)假設(shè)以旅游期間內(nèi)的日平均費(fèi)用最少作為優(yōu)化目標(biāo).

4)根據(jù)文獻(xiàn)[15],假設(shè)所有景點(diǎn)開放時(shí)間為8:00—18:00,共計(jì)10 h,則每日耗時(shí)T應(yīng)滿足T≤10.

5)假設(shè)游玩的最大天數(shù)為dmax,每天最多游玩nd個(gè)景點(diǎn),其中d=1,2,…,dmax.

6) 在選定某一個(gè)酒店作為起點(diǎn)后,每天都以該酒店作為旅游路線的起點(diǎn)與終點(diǎn).

7) 假設(shè)用戶的個(gè)性化設(shè)置體現(xiàn)在選擇偏好的旅游類型,如自然景觀游、歷史人文游、美食購物游等.設(shè)共有n種可選旅游類型,每種旅游類型對(duì)應(yīng)的景點(diǎn)集合為O1,O2,…,On.滿足用戶的個(gè)性化需求是指:為其規(guī)劃出的旅游路線中,至少包含一個(gè)符合該用戶偏好旅游類型的景點(diǎn).

2.2 個(gè)性化旅游路線推薦問題的數(shù)學(xué)模型

個(gè)性化旅游路線推薦問題的數(shù)學(xué)模型可以描述為:在用戶的個(gè)性化設(shè)置下,找出最優(yōu)決策向量X=[r,Pb],其中r為地點(diǎn)標(biāo)號(hào)組成的向量,表示旅游路徑,Pb為交通方式標(biāo)號(hào)組成的向量,表示交通方式的選擇,以最小化如下目標(biāo):

minF=f(X),

(2)

f(X)=con(r)+con(Pb),

(3)

(4)

(5)

(6)

(7)

(8)

設(shè)用戶通過個(gè)性化設(shè)置選擇了第j種旅游類型,該類型對(duì)應(yīng)的景點(diǎn)集合為Oj,則滿足約束條件:

s.t.

T(d)≤10, 1≤d≤dmax,

(9)

r(1)∩r(2)∩…∩r(d)∩…∩r(dmax)=

{p0},

(10)

[r(1)∪r(2)∪…∪r(d)∪…∪r(dmax)]∩

Oj≠?,

(11)

式(9)—(11)為約束條件.式(9)由假設(shè)4給出.式(10)由假設(shè)6給出,每日旅游路線的起點(diǎn)都是同一個(gè)酒店,且每個(gè)景點(diǎn)最多只能被游覽一次,因此不同日期的路線交集僅包含p0.式(11)由假設(shè)7給出,表示為用戶規(guī)劃出的旅游路線中,至少包含一個(gè)景點(diǎn)對(duì)應(yīng)的旅游類型與該用戶設(shè)置的偏好旅游類型一致.

3 求解個(gè)性化旅游路線推薦問題的改進(jìn)混合蛙跳算法

本文采用改進(jìn)混合蛙跳算法對(duì)用戶旅行的路徑和交通方式的選擇進(jìn)行組合優(yōu)化.通過改進(jìn)混合蛙跳算法不斷迭代進(jìn)化以期獲得符合用戶需求的最佳旅游路線與交通方式.所提算法采用調(diào)整可控精度、新增篩選準(zhǔn)則和異常解的處理三種改進(jìn)策略.

3.1 個(gè)體的編碼方式

本模型的解由路徑r與交通方式Pb組成,算法采用十進(jìn)制整數(shù)編碼的方式對(duì)個(gè)體進(jìn)行編碼.對(duì)于n個(gè)候選景點(diǎn){s1,s2,s3,…,sn},為便于表示,依次標(biāo)記為S={1,2,3,…,n}，對(duì)于4種交通方式{公交,地鐵,駕車,步行},依次標(biāo)記為W={1,2,3,4},則旅游天數(shù)為dmax,第d天游玩景點(diǎn)數(shù)量為nd的個(gè)體X的編碼方式如圖1所示.

圖1 個(gè)體X編碼方式示意圖Fig.1 Schematic diagram of individual X coding mode

3.2 調(diào)整可控精度

基本蛙跳算法中,種群規(guī)模與分組數(shù)量這兩個(gè)參數(shù)在進(jìn)化過程中均保持不變.如果增大種群規(guī)模和分組數(shù)量,能夠使得算法的搜索范圍擴(kuò)大、尋優(yōu)能力增強(qiáng),但同時(shí)也加大了運(yùn)算的軟硬件資源消耗,運(yùn)算時(shí)間較長.因此,本文為了權(quán)衡求解精度與資源消耗及運(yùn)算時(shí)間之間的互斥關(guān)系,為混合蛙跳算法設(shè)定了一個(gè)迭代次數(shù)的中間閾值T=fth×G,其中G為算法的總迭代次數(shù),fth為控制結(jié)果精度的調(diào)節(jié)因子.當(dāng)?shù)螖?shù)達(dá)到T時(shí),在原種群中加入規(guī)模與原種群規(guī)模相同的新的種群,使搜索范圍擴(kuò)大,該方案的示意圖如圖2所示.

圖2 調(diào)整可控精度示意圖Fig.2 Schematic diagram of adjusting controllable accuracy

由圖2可知,在對(duì)初始種群A進(jìn)行了T次的進(jìn)化迭代之后得到了種群A(T),此時(shí)在種群A(T)中加入與其規(guī)模相同的種群B得到了新的種群(A(T)+B).對(duì)于新的種群進(jìn)行(G-T)次的進(jìn)化后算法達(dá)到了終止條件,此時(shí)種群(A(T)+B)(G-T)中的最優(yōu)個(gè)體即為混合蛙跳算法搜索到的全局最優(yōu)個(gè)體.

顯然,調(diào)節(jié)因子fth取值越小,種群規(guī)模擴(kuò)大得就越早,搜索范圍也就越大,從而使得發(fā)現(xiàn)最優(yōu)解的概率增大.但是過早地進(jìn)行種群擴(kuò)大與直接增大初始種群規(guī)模是近似等效的,這樣做固然可以提高結(jié)果精度,但是也會(huì)大幅度地降低收斂速度,加大軟硬件資源的損耗.

在算法運(yùn)行到后期時(shí),種群缺乏多樣性,且可能已陷入局部最優(yōu)解,原本的搜索范圍不足以搜索到潛在的更優(yōu)解,于是可以選擇在此時(shí)擴(kuò)大搜索范圍,以降低遺漏更優(yōu)解的風(fēng)險(xiǎn).在本文的仿真實(shí)驗(yàn)中,取調(diào)節(jié)因子f=0.9,即迭代次數(shù)中間閾值T=0.9G.

3.3 新增篩選準(zhǔn)則

圖3 基本蛙跳算法兩次個(gè)體更新示意圖Fig.3 Schematic diagram of two individual updates for basic frog leaping algorithm

圖3中黑色圓點(diǎn)表示子群體的局部最差解Xw,黑色三角表示第一次更新產(chǎn)生的新解Xwnew,灰色三角代表第二次更新產(chǎn)生的新解X′wnew,白色三角表示尚未搜索到的候選新解.根據(jù)混合蛙跳算法的篩選規(guī)則,若Xwnew和X′wnew都比Xw差,則會(huì)直接舍去Xw,用搜索空間內(nèi)的一個(gè)隨機(jī)解替代.這也就意味著,兩次更新不僅決定了產(chǎn)生的新解的取舍,也決定了當(dāng)前解Xw的取舍.在Xwnew和X′wnew都比Xw差的情況下,當(dāng)舍去Xw后,當(dāng)前狀態(tài)下的搜索區(qū)域會(huì)被產(chǎn)生的隨機(jī)解的搜索區(qū)域替換.與經(jīng)歷過多次搜索更新操作的Xw相比,隨機(jī)解具有更大的不確定性,以隨機(jī)解為更新對(duì)象的搜索區(qū)域在很大概率上會(huì)劣于Xw,因此,原混合蛙跳算法僅通過判斷適應(yīng)度大小來決定當(dāng)前解Xw的取舍,可能會(huì)造成具有較大搜索潛力的Xw的丟失.

針對(duì)上述問題,本文在基本蛙跳算法的篩選規(guī)則中新增了一條:如果在第二次更新后的新解X′wnew仍劣于Xw,則計(jì)算X′wnew與Xw之間的歐拉距離(即跳躍步長的幅值)來衡量變化程度,若變化程度大于閾值ε,則說明當(dāng)前Xw的搜索范圍較大,仍采用X′wnew替代Xw;反之舍去,隨機(jī)產(chǎn)生新解代替當(dāng)前Xw.特別地,在本模型中取

(12)

其中,D1max=Xb-Xw,D2max=Xg-Xw,它們分別表示第一次和第二次更新中,跳躍步長的最大可能值;‖·‖2表示向量的2范數(shù).所提新增篩選規(guī)則的特點(diǎn)是:通過在個(gè)體的更新過程中判斷實(shí)際步長的幅值大小,既可以降低丟失具有較大搜索潛力的Xw的風(fēng)險(xiǎn),又能夠防止算法陷入局部最優(yōu).改進(jìn)混合蛙跳算法篩選準(zhǔn)則的偽代碼如算法2所示.

算法2改進(jìn)混合蛙跳算法的篩選準(zhǔn)則

輸入:當(dāng)前子群局部最差解Xw,第二次更新后得到新解的X′w.

輸出:更新后的解Xw.

a) ifF(X′wnew)≥F(Xw) then

b) if ‖X′wnew-Xw‖2<εthen

c) 在搜索空間里產(chǎn)生隨機(jī)解Xwnew代替Xw；

d) else

e)Xw=Xwnew

f) end if

g) end if

3.4 異常解的處理

在生成解的過程中,經(jīng)常會(huì)出現(xiàn)重復(fù)、交叉等異常解的情況,若是采用強(qiáng)制性的循環(huán)來避免異常解的產(chǎn)生會(huì)大大增加算法運(yùn)算時(shí)長甚至陷入死循環(huán).為了解決這一系列問題,本文在生成每一個(gè)隨機(jī)個(gè)體之后,立即判斷其是否為異常解,若為異常解,則用一個(gè)數(shù)值足夠大的懲罰因子ΔC代替其目標(biāo)值，即

f(Xh)=ΔC.

(13)

顯然,通過引入懲罰因子后異常解的目標(biāo)值被賦予了一個(gè)較大的懲罰值,使其在后續(xù)的子群更新中被淘汰,簡化了模型,提高了運(yùn)算速度.

3.5 改進(jìn)算法的實(shí)現(xiàn)

基于上述3種改進(jìn)策略,用于求解個(gè)性化旅游路線推薦問題的改進(jìn)混合蛙跳算法ISFLA(Improved Shuffled Frog Leaping Algorithm)的偽代碼如算法3所示.

算法3改進(jìn)蛙跳算法偽代碼ISFLA

輸入:子群個(gè)數(shù)M,子群內(nèi)個(gè)體數(shù)量I,種群個(gè)體總數(shù)量I×M,子群更新次數(shù)N,混合迭代次數(shù)G,當(dāng)前迭代次數(shù)g.

輸出:全局最優(yōu)解.

a) 初始化種群,計(jì)算個(gè)體目標(biāo)函數(shù)值;

b) forg=1 toGdo

c) ifg==Tthen

d) 根據(jù)3.2節(jié)擴(kuò)大種群規(guī)模;

e) end if

f) 對(duì)所有個(gè)體按目標(biāo)函數(shù)值大小排序并分組，根據(jù)排序與分組結(jié)果記錄當(dāng)前全局最優(yōu)解Xg、各組局部最優(yōu)解Xb、局部最差解Xw;

g) fori=1 toNdo

h)Xwnew=Xw+λ(Xb-Xw)∥λ為0～1的隨機(jī)數(shù);

i) ifF(Xwnew)

j)Xw=Xwnew

k) else

X′wnew=Xw+λ(Xg-Xw) ∥λ為0～1的隨機(jī)數(shù)；

l) end if

m) ifF(X′wnew)

n)Xw=X′wnew

o) else

執(zhí)行算法2；

p) end if

q) 對(duì)每組個(gè)體按目標(biāo)函數(shù)值大小排序,重新確定局部最優(yōu)解Xb,局部最差解Xw;

r) end for

s) 將所有個(gè)體混洗,記錄全局最優(yōu)個(gè)體Xg；

t) end for

4 仿真實(shí)驗(yàn)

4.1 數(shù)據(jù)集的建立

本文實(shí)驗(yàn)以南京游為例建立數(shù)據(jù)集.搜集南京周邊的19個(gè)熱門景點(diǎn)數(shù)據(jù),假設(shè)旅游時(shí)長為3 d,每天游玩3個(gè)景點(diǎn).通過百度地圖搜集目標(biāo)地點(diǎn)的數(shù)據(jù),每組數(shù)據(jù)包括坐標(biāo)、名稱、景區(qū)的開放時(shí)間、景區(qū)的門票價(jià)格、不同出行方式所需的時(shí)間和費(fèi)用以及對(duì)應(yīng)的食宿價(jià)格.表2—4分別列出了各景點(diǎn)經(jīng)緯度、門票費(fèi)用及游玩時(shí)間.由于版面限制,費(fèi)用和消耗時(shí)間的數(shù)據(jù)不在此列出.以歷史人文、自然景觀、美食購物作為3種個(gè)性化旅游類別.對(duì)各景點(diǎn)的分類如下:歷史人文={南京長江大橋,頤和路,雞鳴寺,中山陵,明孝陵,夫子廟,總統(tǒng)府,侵華日軍南京大屠殺遇難同胞紀(jì)念館,中華門,大報(bào)恩寺,雨花臺(tái)風(fēng)景區(qū),牛首山,南京博物院}；自然景觀={南京長江大橋,棲霞山,玄武湖,中山陵,南京眼步行橋,中華門,雨花臺(tái)風(fēng)景區(qū),牛首山}；美食購物={新街口,夫子廟,湖南路}.

表2 各景點(diǎn)經(jīng)緯度

4.2 實(shí)驗(yàn)結(jié)果與分析

在CPU為Intel(R) Core(TM) i7-7700HQ 2.8 GHz、內(nèi)存8 GB、WINDOWS 10系統(tǒng)上使用Matlab 2016a進(jìn)行仿真實(shí)驗(yàn).

實(shí)驗(yàn)中的參數(shù)取值如下:全局混合迭代次數(shù)、初始子群數(shù)量、子群內(nèi)個(gè)體數(shù)量、種群總規(guī)模、子群更新次數(shù)、結(jié)果精確度的調(diào)節(jié)因子.為驗(yàn)證所提策略的有效性,分別使用基本蛙跳算法SFLA(算法1)、改進(jìn)蛙跳算法Ⅰ(SFLA+調(diào)整可控精度+異常解的處理)、改進(jìn)蛙跳算法Ⅱ(SFLA+新增篩選準(zhǔn)則+異常解的處理)以及所提改進(jìn)蛙跳算法ISFLA(SFLA+調(diào)整可控精度+新增篩選準(zhǔn)則+異常解的處理,即算法3)求解個(gè)性化旅游路線推薦問題的數(shù)學(xué)模型,4種算法分別獨(dú)立地運(yùn)行30次,求取它們?cè)?0次運(yùn)行中求得的最少費(fèi)用的最佳值、均值和方差,比較結(jié)果如表5所示.

表3 各景點(diǎn)門票費(fèi)用

通過觀察表5中各算法的運(yùn)行結(jié)果可知,在引入了改進(jìn)策略后,算法的性能得到了一定程度的提高.與基本蛙跳算法SFLA相比,改進(jìn)蛙跳算法Ⅰ求得的最少費(fèi)用均值有所減少,方差也有所降低.這是由于改進(jìn)蛙跳算法Ⅰ引入了控制結(jié)果精度的調(diào)節(jié)因子,當(dāng)?shù)螖?shù)達(dá)到設(shè)定的中間閾值時(shí),在原種群中加入規(guī)模與原種群規(guī)模相同的新種群,從而使得搜索范圍擴(kuò)大,群體的多樣性增強(qiáng),有利于增強(qiáng)算法的全局搜索能力.改進(jìn)蛙跳算法Ⅱ求得的最少費(fèi)用均值也優(yōu)于SFLA.原因是在基本混合蛙跳算法的篩選規(guī)則中,如果兩個(gè)新解都比舊解差,則會(huì)直接舍去舊解,這就導(dǎo)致在舍去了舊解后,當(dāng)前狀態(tài)下的候選新解也會(huì)被舍去掉很大一部分甚至是全部.而在本文所提篩選規(guī)則中,個(gè)體在更新時(shí),跳動(dòng)的實(shí)際步長為最大步長乘以一個(gè)[0,1]內(nèi)的隨機(jī)數(shù),通過判斷實(shí)際步長的幅值大小可以很好地降低丟失具有較大潛力舊解的風(fēng)險(xiǎn),能夠防止陷入局部最優(yōu).從表5的結(jié)果可以看出,本文所提算法ISFLA在同時(shí)引入調(diào)整可控精度、新增篩選準(zhǔn)則及異常解的處理策略后,結(jié)合了3個(gè)改進(jìn)措施的優(yōu)點(diǎn),使得求得的最少費(fèi)用的最佳值、均值和方差都得到改善,搜索結(jié)果也較SFLA和僅引入部分改進(jìn)策略的改進(jìn)算法Ⅰ和Ⅱ更加精確,且結(jié)果分布的離散程度更小,說明所提算法ISFLA搜索的穩(wěn)定性更強(qiáng).

表4 各景點(diǎn)游玩時(shí)間

表5 算法改進(jìn)前后結(jié)果對(duì)比

利用顯著度水平為0.05的秩和檢驗(yàn)法將上述改進(jìn)蛙跳算法Ⅰ、改進(jìn)蛙跳算法Ⅱ、ISFLA與基本蛙跳算法SFLA在30次運(yùn)行中的結(jié)果進(jìn)行了統(tǒng)計(jì)測(cè)試,結(jié)果如表6所示.其中“+”表示相應(yīng)算法的搜索結(jié)果顯著優(yōu)于基本蛙跳算法,“=”表示兩者無顯著差異,“-”表示顯著劣于基本蛙跳算法.

表6 秩和檢驗(yàn)結(jié)果

通過觀察表6的統(tǒng)計(jì)測(cè)試結(jié)果可知,在引入新增篩選準(zhǔn)則后,改進(jìn)蛙跳算法Ⅱ與基本蛙跳算法得到的結(jié)果無顯著差異,而加入調(diào)整可控精度策略的改進(jìn)蛙跳算法Ⅰ以及所提改進(jìn)蛙跳算法ISFLA的求解結(jié)果均顯著優(yōu)于基本蛙跳算法,進(jìn)一步說明本文所提改進(jìn)策略是可行而有效的.

圖4給出了4種對(duì)比算法的收斂曲線.由圖4可見,當(dāng)總的迭代次數(shù)相同時(shí),對(duì)于僅引入調(diào)整可控精度策略的改進(jìn)算法Ⅰ,雖然它搜索到的結(jié)果優(yōu)于基本蛙跳算法SFLA,但是其收斂速度相較于SFLA并沒有明顯的提升;對(duì)于僅引入新增篩選準(zhǔn)則的改進(jìn)蛙跳算法Ⅱ,雖然它對(duì)最優(yōu)解精度的改進(jìn)并不明顯,但是它能夠以較快的速度收斂;對(duì)于同時(shí)引入調(diào)整可控精度策略和新增篩選準(zhǔn)則的所提算法ISFLA,它將改進(jìn)策略的優(yōu)點(diǎn)有機(jī)地結(jié)合,既具有較快的收斂速度,也能夠跳出局部極值,獲得了更高的求解精度,算法的全局搜索性能得到了大幅度地提升.

圖4 算法收斂曲線對(duì)比Fig.4 Comparison of convergence curves

由圖4還可以看出,當(dāng)引入改進(jìn)策略后,所提改進(jìn)算法ISFLA的收斂速度較SFLA有小幅度降低,其主要原因是在ISFLA的求解過程中,為了避免陷入局部最優(yōu),在進(jìn)化到一定程度時(shí)擴(kuò)大了種群的搜索范圍.然而,與SFLA相比,ISFLA能夠收斂到精度更優(yōu)的解,顯著提高了算法的求解效率.

進(jìn)一步,將模型與相應(yīng)的個(gè)性化旅游設(shè)置相結(jié)合,以花費(fèi)最少為目標(biāo)進(jìn)行優(yōu)化時(shí)得出自然景觀、歷史人文、美食購物的路線規(guī)劃如圖5—10所示.

從圖5—10可以看出,當(dāng)旅游者選擇游覽3 d且每天游覽3個(gè)景點(diǎn),以費(fèi)用最低為優(yōu)化目標(biāo)時(shí),自然景觀、歷史人文、美食購物3種個(gè)性化旅游方式下各需總花費(fèi)1 031.2、1 012.1和1 057.2元,ISFLA推薦出的路線能夠較好地滿足用戶的個(gè)性需求.

圖5 選擇自然景觀游且以費(fèi)用最少為優(yōu)化目標(biāo)的推薦路線Fig.5 Recommended routes for natural landscape tour with least spending

圖6 選擇自然景觀游且以費(fèi)用最少為優(yōu)化目標(biāo)的軌跡地圖Fig.6 Trajectory map for natural landscape tour with least spending

圖7 選擇歷史人文游且以費(fèi)用最少為優(yōu)化目標(biāo)的推薦路線Fig.7 Recommended routes for historical & cultural tour with least spending

圖8 選擇歷史人文游且以費(fèi)用最少為優(yōu)化目標(biāo)的軌跡地圖Fig.8 Trajectory map for historical & cultural tour with least spending

圖9 選擇美食購物游且以費(fèi)用最少為優(yōu)化目標(biāo)的推薦路線Fig.9 Recommended routes for food & shopping tour with least spending

圖10 選擇美食購物游且以費(fèi)用最少為優(yōu)化目標(biāo)的軌跡地圖Fig.10 Trajectory map for food & shopping tour with least spending

5 總結(jié)

本文針對(duì)旅游路線個(gè)性化推薦問題,設(shè)計(jì)了一種改進(jìn)的混合蛙跳算法.通過調(diào)整可控精度,新增篩選準(zhǔn)則和即時(shí)處理異常解來增加群體多樣性、降低遺漏最優(yōu)解風(fēng)險(xiǎn),強(qiáng)化了局部搜索能力,提高了算法的求解精度.以南京游作為實(shí)例,采用改進(jìn)混合蛙跳算法進(jìn)行求解,并根據(jù)用戶的個(gè)性選擇推薦出了具體的出行方案,在一定程度上為旅游者的出行提供了參考.以多次運(yùn)行中的最佳值、均值和方差作為測(cè)度,驗(yàn)證了不同改進(jìn)策略的有效性.實(shí)驗(yàn)結(jié)果表明,在求解精度方面,所提改進(jìn)算法相較于基本的蛙跳算法有了顯著的提升.然而,本文算法也存在著不足，例如本文采用的是單目標(biāo)優(yōu)化,而現(xiàn)實(shí)生活中旅游者可能有多個(gè)旅游需求需要同時(shí)優(yōu)化,如何高效求解個(gè)性化旅游路線推薦的多目標(biāo)優(yōu)化問題,將是下一步的研究方向.