旅游路線個性化推薦算法比較分析

李 霞，尹川東，袁 云

(1.廣東外語外貿(mào)大學(xué)語言工程與計算實驗室，廣東廣州 510006; 2.廣東外語外貿(mào)大學(xué)信息學(xué)院，廣東廣州 510006)

旅游路線個性化推薦算法比較分析

李 霞1，尹川東2，袁 云2

(1.廣東外語外貿(mào)大學(xué)語言工程與計算實驗室，廣東廣州 510006; 2.廣東外語外貿(mào)大學(xué)信息學(xué)院，廣東廣州 510006)

隨著自助游群體的增加，越來越多的人希望能夠在滿足用戶特定需求(如限定旅游天數(shù)、旅游費用、住宿標(biāo)準(zhǔn)等)的前提下，獲取自動生成的可供參考的包括旅游景點、價格和住宿一體化的旅游推薦路線，并能夠可視化呈現(xiàn)給用戶。蟻群算法和遺傳算法是0-1背包問題中的兩種經(jīng)典算法，通過建立應(yīng)用于個性化旅游路線推薦問題中的數(shù)學(xué)模型，將蟻群算法和遺傳算法應(yīng)用于旅游路線個性化推薦中。依據(jù)文中所提出的最優(yōu)路線推薦分值評價方法，對所選取的推薦算法進行了分析和測試。實驗結(jié)果表明，優(yōu)化后的蟻群算法和遺傳算法均優(yōu)于傳統(tǒng)蟻群算法和遺傳算法，并且從綜合性能看，基于貪心解的混合遺傳算法可有效應(yīng)用于旅游路線個性化推薦中。

旅游路線自動規(guī)劃;旅游挖掘;遺傳算法;貪心算法;最大最小蟻群算法

0 引言

個性化旅游路線推薦是指依據(jù)用戶喜好、設(shè)定相對應(yīng)的參數(shù)，如旅游總價格、旅游時間、入住酒店等條件因素所獲取的最佳旅游個性化路線推薦?，F(xiàn)有算法中，遺傳算法和蟻群算法被廣泛應(yīng)用于地圖搜索、路線規(guī)劃和0-1背包問題中［1-4］?，F(xiàn)有研究中，有針對群體的旅游路線推薦算法，如宋曉宇等［5］針對旅游中常見的現(xiàn)象—結(jié)伴出行，研究并提出了群體旅游路線推薦問題，目標(biāo)是為群體推薦一條能夠使群體整體滿意度大，個體滿意度差異小，對群體內(nèi)所有成員較公平的最優(yōu)群體旅游路線。通過分析聚合用戶偏好時通常采用的平均數(shù)策略與無痛苦策略在推薦結(jié)果方面存在的不足，針對搜索路線所具有的動態(tài)性特點，提出了一種動態(tài)聚合用戶偏好的策略，基于該策略建立路線評價模型，對路線進行滿意度評分，返回分值最高的路線，并驗證了算法在不同參數(shù)設(shè)置下的有效性。Wang Qingfeng等［6］提出將人工免疫算法和蟻群算法結(jié)合的混合算法用于旅游路線的規(guī)劃中。Shi Linan等［7］提出了針對改進蟻群算法的旅游路線規(guī)劃算法。任競斐等［8］建立了Logit模型，將游客在不同路線上進行分配，建立了綜合游客偏好、擁擠度、等待時間和行走時間等指標(biāo)的旅游效用函數(shù)，減少了旅游高峰期游客擁擠和等待的情況。模擬仿真表明，提出的方案要明顯優(yōu)于基于最短路徑的路線選擇方案。夏亞梅等［9］對基本蟻群算法進行研究和改進，建立了一個服務(wù)組合模型，可以適應(yīng)服務(wù)組合優(yōu)化過程。黃翰等［10］通過給出估算蟻群算法期望收斂時間的理論方法，研究和分析了蟻群算法的收斂速度。鄭立平等［11］通過混合使用多種雜交算子，獲得求解旅行商問題的更優(yōu)解。宋海生等［12］提出了基于貪心解的混合遺傳算法，并應(yīng)用于背包和多維0-1背包問題中。

已有研究中，并沒有針對蟻群算法、遺傳算法及其優(yōu)化算法在旅游路線推薦中的性能比較分析，文中在爬取互聯(lián)網(wǎng)中的旅游數(shù)據(jù)基礎(chǔ)上，將蟻群算法、遺傳算法、最大最小優(yōu)化蟻群算法和基于貪心解的混合蟻群算法應(yīng)用于旅游路線推薦中，并分別從所選出路線的平均評價分值、最優(yōu)評價分值、算法所耗費時間三個方面對算法進行評價比較。實驗結(jié)果表明，最大最小優(yōu)化蟻群算法和基于貪心解的混合蟻群算法可有效應(yīng)用于旅游路線自動化推薦中。

1 遺傳算法

1.1 解決旅游路線規(guī)劃上的數(shù)學(xué)模型

為了和基本遺傳算法進行比較，文中參考了文獻［7］中所提出的混合遺傳算法的思想，并將所提出的混合遺傳算法應(yīng)用于旅游路線推薦問題中，所涉及到的數(shù)學(xué)模型主要包括染色體編碼、適應(yīng)度函數(shù)以及選擇算子，詳細模型描述如下:

(1)染色體編碼。

將用戶的游覽路線用二進制編碼表示，例如10維度下的染色體(0，1，0，1，0，0，0，0，0，1)表示景點2，4，10被選入當(dāng)前路線中。

(2)適應(yīng)度函數(shù)。

遺傳算法中較為關(guān)鍵的是適應(yīng)度函數(shù)，它被用于評價和選擇染色體，并將影響到該個體在選擇算子中的遺傳概率，是遺傳算法是否能夠達到最優(yōu)代的關(guān)鍵因素。適應(yīng)度函數(shù)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)熱度，文中選擇的適度函數(shù)如下:

其中，fit(f(x)，g(x))為旅游景點 x的適應(yīng)度; f(x)為該景點費用的目標(biāo)優(yōu)化函數(shù)，由景點門票價格等信息組合而成;g(x)為該景點熱度的目標(biāo)優(yōu)化函數(shù)，表示景點游玩人數(shù)總和;Amin為花費的最小值，Amax為花費的最大值;γ為花費的縮放系數(shù)，μ為熱度的縮放系數(shù)，γ，μ的作用是防止花費或者熱度數(shù)值波動過大;ρ為懲罰系數(shù)，為了平衡花費和熱度對適度的影響。

(3)選擇算子。

1.2 基于貪心策略的混合遺傳算法

在解決旅游路線規(guī)劃問題上，傳統(tǒng)遺傳算法的編碼不能全面將優(yōu)化問題的約束表示出來。同時，遺傳算法容易過早收斂，可能無法搜索到全局最優(yōu)路徑。遺傳算法的過早收斂、效率低等問題主要是因為初始種群采取了隨機方式，這導(dǎo)致遺傳算法需要大數(shù)量的進化代數(shù)，且進化代數(shù)跟種群的大小呈正比。當(dāng)種群達到一定規(guī)模時，遺傳算法的效率會降低，并且可能收斂于局部最優(yōu)，無法達到最優(yōu)熱度。同時應(yīng)用于旅游大數(shù)據(jù)時，進化代數(shù)的增加將極大增加算法的時間效率。

為了能夠和傳統(tǒng)遺傳算法在旅游路線推薦效率上進行比較分析，文中選取了文獻［4］所提出的基于貪心解的混合遺傳算法(MGGA)，并將其應(yīng)用于旅游路線推薦中。算法的第一階段，先對旅游景點進行評分，根據(jù)分值將旅游景點按降序排列，依次將景點放入路線內(nèi)，直至超出最大游玩時間為止。算法的第二階段，先用貪心算法生成問題的貪心解，然后在遺傳算法的進化過程中，讓每一代最差適應(yīng)度的個體無條件地變?yōu)榇素澬慕狻Ｋ惴ㄔ敿毭枋鋈缦?

(1)算法第一階段。

Input:原始個體染色體編碼chromosome，景點熱度數(shù)組hotness，景點游玩時間數(shù)組visitDays;

Output:經(jīng)過優(yōu)化的染色體編碼chromosome。

Step1:根據(jù)個體染色體編碼，找出未加入路線的景點;

Step2:將這些景點按照熱度(即景點旅游人數(shù)的總和)，從大到小依次放入時間小于當(dāng)前路線游玩天數(shù)景點至不能再放入任何景點。

(2)算法第二階段。

Input:景點熱度數(shù)組hotness，游玩時間數(shù)組visit-Days，路線游玩時間upDays，交叉率Pc，變異率Pm，種群規(guī)模scale，遺傳代數(shù)maxGen;

Output:最優(yōu)熱度的染色體chromosome。

Step1:使用貪心算法隨機求得scale個貪心解作為初始種群，其中scale為種群規(guī)模。

Step2:將Step1中的初始種群進行二進制編碼(其中第i位為1表示第i個景點被選擇，若為0，則表示第i個景點未被選擇)。

Step3:按照1.1節(jié)所定義的適應(yīng)度函數(shù)計算群體中每個個體的適應(yīng)度。

Step4:將以上個體作為第0代，記錄此代最高適應(yīng)度的個體。

Step5:當(dāng)此代的適應(yīng)值不滿足最高要求并且當(dāng)前代數(shù)小于初始化設(shè)定的最大代數(shù)時，執(zhí)行Step5.1-5.6并循環(huán)，否則，執(zhí)行Step6。

Step5.1:執(zhí)行選擇算子;

Step5.2:以Pc執(zhí)行交叉算子;

Step5.3:以Pm執(zhí)行變異算子;

Step5.4:計算此代的適應(yīng)值，方法同Step3;

Step5.5:找出適應(yīng)度最差的個體，將其通過貪心算法優(yōu)化;

Step5.6:用此代最高適應(yīng)度的個體適應(yīng)值與上次所記錄的最高適應(yīng)度的適應(yīng)值進行比較，若比上一次好，則將此個體記錄為當(dāng)前最高適應(yīng)度個體。

Step6:打印最佳解的選擇個數(shù)、所選景點的總分值數(shù)和總花費。

2 蟻群算法

2.1 蟻群算法解決旅游路線規(guī)劃的數(shù)學(xué)模型

旅游路線規(guī)劃并不是TSP問題，而是類似于0-1背包問題。旅游的天數(shù)類似于0-1背包問題中背包的容量，景點的熱度則類似于0-1背包問題中每個物品的價值，所不同的是，在旅游路線規(guī)劃中景點的熱度由游玩人數(shù)、門票價格、評論數(shù)等得分共同構(gòu)成。景點被選擇的概率Pki(t)為:

信息素的更新為:

其中，ρ為信息素揮發(fā)因子，1-ρ表示信息的殘留系數(shù)，ρ的取值范圍一般為［0，1］;Δτi(t)為所有螞蟻在景點i上的信息素總和，即Δτi(t)=τki(t)，(t)為第k只螞蟻在第t代循環(huán)中留在景點i的信息量，采用Ant-Cycle模型進行更新，其公式如下:

其中，Q為一個常量，表示螞蟻完成一次完整的路徑搜索后所釋放的信息素總量，它在一定程度上影響算法的收斂速度;Lk表示第k個螞蟻在t代循環(huán)中所走路徑的總長度，即熱度的總和。

2.2 最大最小優(yōu)化蟻群算法

蟻群算法在旅游路線推薦中，由于缺乏參考選擇路徑使得景點搜索時間長，同時算法容易出現(xiàn)某景點因為一直不被采納而變的權(quán)重極低，使得后續(xù)路線無法選擇該景點，從而停滯的現(xiàn)象。最大最小優(yōu)化蟻群算法［13-14］對原始蟻群算法做了以下改進:

(1)每次循環(huán)完之后，選出最佳螞蟻，最佳螞蟻可以留信息素，其他螞蟻都不留。

(2)為了防止所有信息素都被蒸發(fā)掉，最后只剩下最佳螞蟻的路徑，MMAS采用很小的蒸發(fā)率，從而保證所有路徑不會迅速變?yōu)?。

(3)強制所有路徑的信息素有最大值和最小值限制，高于低于這個范圍都會被自動設(shè)置為最大值或者最小值，因此信息素的范圍在［τmin，τmax］之間，從而保證最少信息素的路徑也有機會被選擇。

(4)為了使螞蟻在算法的初始階段能夠更多地搜索新的解空間，最大-最小蟻群系統(tǒng)將τmax設(shè)置為每條邊上的信息素初始值s。

(5)使用輪盤賭注方法計算景點被選擇的概率，使得更多的路線可以被挖掘。

3 實驗

3.1 實驗數(shù)據(jù)

實驗中涉及到景點數(shù)據(jù)和酒店數(shù)據(jù)。其中，景點數(shù)據(jù)包括景點拼音、景點名、游玩人數(shù)、門票價格、推薦游玩時間和大地坐標(biāo);酒店數(shù)據(jù)包括酒店名稱、酒店地址、酒店電話、酒店評論得分和酒店價格。圖1分別展示了文中的景點數(shù)據(jù)和酒店數(shù)據(jù)的jason格式。

3.2 實驗評估模型

實驗選取廣州市的451個景點和該景點周圍的酒店數(shù)據(jù)，其中景點數(shù)據(jù)從百度旅游網(wǎng)站中爬取，酒店數(shù)據(jù)則從馬蜂窩網(wǎng)站上爬取，所爬取的數(shù)據(jù)庫截圖如圖2所示。

3.3 評價模型

為了選取最優(yōu)路線，文中建立了一個應(yīng)用于評價是否為最優(yōu)旅游路線的評估模型。建模思想是:所選出的旅游路線優(yōu)先考慮熱門景點且景點門票價格和酒店費用總和較低，為此定義了一個旅游路線的最優(yōu)分值函數(shù)，該函數(shù)被用于評價不同算法在挖掘得到的旅游路線的評分值，分值高表示該路線優(yōu)。

其中，Score(x)為算法計算所得到旅游路線的最優(yōu)分值;f(x)為該路線門票費用和酒店費用之和; g(x)為該路線游玩人數(shù)之和;Amin為花費總和的最小值;Amax為花費總和的最大值;γ為花費的縮放系數(shù);μ為熱度的縮放系數(shù);ρ為花費的懲罰系數(shù)。

γ，μ的作用是將Score限制在一個范圍中，防止過大的波動;ρ的作用是為了平衡花費和熱度對適度的影響。在該模型中，游玩人數(shù)占主導(dǎo)優(yōu)勢，當(dāng)兩條路線游玩人數(shù)相當(dāng)時，價格便成為了決定因素，價格較低的路線熱度更大。

3.4 實驗結(jié)果

所有實驗均在系統(tǒng)為MacOSX 10.10 Yosemite、處理器為2.2 GHz Intel Core i7、內(nèi)存為16 GB 1 600 MHz DDR3、硬盤為256 GB SSD的平臺上進行。文中分別對蟻群算法(AS)和最大最小蟻群算法(MMAS)、遺傳算法(GA)和提出的混合遺傳算法(MGGA)在推薦路線的平均分值、最優(yōu)分值、平均耗時三個參數(shù)上進行了對比，其中平均分值代表了算法的局部搜索能力和穩(wěn)定性，最優(yōu)分值代表了算法的全局搜索能力和準(zhǔn)確性。

在AS和MMAS評測中，信息素更新公式中令α= 1，β=2，實驗通過改變迭代次數(shù)和螞蟻數(shù)量來測試算法的性能。每改變一次迭代次數(shù)或螞蟻數(shù)量都將AS 和MMAS運行10次，去除重復(fù)路徑之后，記錄分值排名前20條路線的平均分值、最優(yōu)分值和平均耗時，實驗結(jié)果如表1所示。

實驗結(jié)果表明，MMAS算法耗時明顯小于傳統(tǒng)蟻群算法，并且隨著迭代次數(shù)和螞蟻數(shù)量的增加，MMAS發(fā)現(xiàn)的解逐漸優(yōu)于AS。

在GA和MGGA評測中，設(shè)置Pc=Pm=0.9，通過改變進化代數(shù)和種群規(guī)模來測試算法的性能。每改變一次進化代數(shù)或種群規(guī)模都將GA和MGGA運行10次，去除重復(fù)路徑之后，記錄分值排名前20條路線的平均分值、最優(yōu)分值和平均耗時，實驗結(jié)果如表2所示。

從表2可知，GA和MGGA的平均分值都與種群規(guī)模大小呈正比，總體上來看，隨著進化代數(shù)的增加，GA和MGGA的平均分值逐漸增加，最終趨于穩(wěn)定。在該實驗中，對于MGGA，當(dāng)進化代數(shù)達到100且種群規(guī)模達到500時，平均分值和最優(yōu)分值達到最高，分別為104.77和114.62。

同時實驗結(jié)果還表明，文中所提出的MGGA與GA相比，在耗時差別不大的前提下，所推薦出的旅游路線的平均分值和最優(yōu)分值明顯優(yōu)于GA。另外，還分別計算了AS、MMAS、GA、文中算法在不同情況下所得到的推薦路線的平均分值、最優(yōu)分值和消耗時間的平均值，實驗結(jié)果表明在推薦路線的最優(yōu)分值差異不大的情況下，MGGA所花時間小于MMAS，同時文中算法在時間與GA差異不大的前提下，所得到的旅游路線的最優(yōu)分值大于GA。

4 結(jié)束語

文中選取經(jīng)典旅游規(guī)劃算法，在所爬取的旅游數(shù)據(jù)上，分別從所選取的旅游路線的平均分值、最優(yōu)分值和耗費時間進行分析對比。實驗結(jié)果表明，優(yōu)化后的最大最小蟻群算法和基于貪心解的混合遺傳算法的綜合效率優(yōu)于傳統(tǒng)蟻群算法和遺傳算法，可應(yīng)用于系統(tǒng)實踐中。

［1］ Cormen T H，Leiserson C E，Rivest R L，et al.Introduction to algorithms［M］.2nd ed.［s.l.］:MIT Press and McGraw-Hill，2001.

［2］ Dréo J，Siarry P P，Pétrowski A，et al.Metaheuristics for hard optimization［M］.［s.l.］:［s.n.］，2006:123-150.

［3］ Dubitzky W，Wolkenhauer O，Cho Kwang-Hyun，et al.Encyclopedia of systems biology［M］.［s.l.］:［s.n.］，2013.

［4］ 張文修，梁 怡.遺傳算法的數(shù)學(xué)基礎(chǔ)［M］.西安:西安交通大學(xué)出版社，2001.

［5］ 宋曉宇，閆玉奇，孫煥良，等.基于簽到數(shù)據(jù)的群體旅游路線推薦［J］.計算機科學(xué)與探索，2015，9(1):51-62.

［6］ Wang Qingfeng，Wang Yuhui.Route planning based on combination of artificial immune algorithm and ant colony algorithm ［M］//Foundations of intelligent systems.Berlin:Springer-Verlag，2011:121-130.

［7］ Shi Linan，Li Li，Zhao Wenjing，et al.A delay-constrained multicast routing algorithm based on the ant colony algorithm ［C］//Proceedings of the international conference on information engineering and applications.［s.l.］:［s.n.］，2012:875-882.

［8］ 任競斐，鄭偉民.景區(qū)旅游高峰期游客旅游路線動態(tài)實時調(diào)度仿真研究［J］.統(tǒng)計與決策，2013(8):42-45.

［9］ 夏亞梅，程 渤，陳俊亮，等.基于改進蟻群算法的服務(wù)組合優(yōu)化［J］.計算機學(xué)報，2012，35(2):270-281.

［10］黃 翰，郝志峰，吳春國，等.蟻群算法的收斂速度分析［J］.計算機學(xué)報，2007，30(8):1344-1353.

［11］鄭立平，郝忠孝.基于混合雜交的遺傳算法求解旅行商問題［J］.計算機工程，2005，31(20):168-169.

［12］宋海生，宋海洲，傅仁毅，等.求解多限制0-1背包問題的混合遺傳算法［J］.計算機工程，2009，35(13):4-7.

［13］Dorigo M，Gambardella L M.Guest editorial special section on ant colony optimization［J］.IEEE Transactions on Evolutionary Computation，2002，6(4):317-319.

［14］ Dorigo M，Gambardella L M.Ant colonies for the traveling salesman problem［J］.Bio-Systems，1997，43(2):73-81.

Comparison and Analysis of Personalized Recommending Algorithm of Travelling Route

LI Xia1，YIN Chuan-dong2，YUAN Yun2
(1.Laboratory of Language Engineering and Computing，Guangdong University of Foreign Studies，Guangzhou 510006，China; 2.Informatics School，Guangdong University of Foreign Studies，Guangzhou 510006，China)

With the increasing of self-driving tours population，more and more people want to get the automatically generated route based on their specific needs，like special traveling days，traveling fees，special hotel expense quarterage.Ant colony algorithm and genetic algorithm are two classical algorithms used in 0-1 Knapsack Problem.It builds a mathematic model in this paper which can be applied to automatically generated route.An evaluation method for assessing the best compatible recommending traveling route is also given，which is used to analyze and test the selected algorithms.The results from the experiment show that optimized ant colony algorithm and the hybrid genetic algorithm outperform the basic ant colony algorithm and genetic algorithm.And also found that the hybrid genetic algorithm can be used in the traveling route recommending system from synthetic property.

traveling route planning;traveling mining;genetic algorithm;greedy algorithm;maximum and minimum ant colony algorithm

TP301.6

A< class="emphasis_bold">文章編號:1

1673-629X(2016)09-0073-05

10.3969/j.issn.1673-629X.2016.09.017

2015-08-11

2015-12-16< class="emphasis_bold">網(wǎng)絡(luò)出版時間:

時間:2016-08-23

廣東省普通高?？萍紕?chuàng)新項目(2013KJCX0071)

李 霞(1976-)，女，副教授，研究方向為文本挖掘。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1343.024.html