[發明專利]一種基于改進蛙跳算法的個性化旅游路線推薦方法

有效

• 申請號: 202010319466.3
• 申請日: 2020-04-21
• 公開（公告）號: CN111523059B
• 公開（公告）日: 2023-08-22
• 發明（設計）人: 申曉寧;吳俊潮;王森林;仇友輝;張磊;李常峰
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/958;G06F16/29;G06N3/006;G06Q50/14
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 冒艷

1.一種基于改進蛙跳算法的個性化旅游路線推薦方法，其特征在于：包括如下步驟：

(1)讀取模型所需數據和個性化參數，確定優化目標和約束條件；

(2)數據預處理與算法參數初始化；

(3)隨機生成初始種群，并計算其適應度；

(4)判斷是否進行種群的擴大；

(5)對所有個體按適應度進行降序排序并分組；

(6)對種群進行更新；

(7)種群混合，記錄最優解；

(8)判斷算法是否到達終止條件；

步驟(1)模型所需的數據包括當地所有候選景點與旅館的位置、候選景點和旅館的數量、游玩過程中在時間和金錢上的平均消費、在出行中消耗的時間與交通費用、旅館的住宿費用；個性化參數包括旅游天數、每日游玩景點數、旅游偏好、優先級別、旅游開始時期；優化目標包括每日游玩時間最少、游玩期間內平均金錢消費最小；約束條件為選定某一個旅館作為多日游或一日游固定的起點，每個景點最多游玩一次并于當天回到起點；

所述景點與旅館的位置通過在已知經緯度，在平面直角坐標系中以坐標的形式來表示，

其中S為候選景點集，候選景點數量為ns；H為候選旅館集，候選旅館數量為nh；在各大景點游玩消耗的的時間、金錢，候選旅館的費用以向量的形式表示，

Pm＝[pm₁,pm₂,pm₃，……,pm_ns]

Pt＝[pt₁,pt₂,pt₃,……，pt_ns]

Ph＝[ph₁,ph₂,ph₃,……,ph_nh]

其中Pm為候選景點的平均游玩費用，Pt為候選景點的游玩時間，Ph為候選旅館的單價；

根據約束條件，在選定某一旅館作為起點的情況下，旅館與景點間出行交通費用與耗費時間的交互數據以矩陣mcost和tcost的形式表示，且

size(mcost)＝size(tcost)＝(1+ns)×(1+ns)×4

即mcost和tcost的維度都是(1+ns)×(1+ns)×4，mcost(i，j，k)則表示第i個地點前往第j個地點采用第k種交通方式的交通費用；tcost(i，j，k)則表示第i個地點前往第j個地點采用第k種交通方式的出行時間；其中i，j∈{1，2，3......，ns+1}，k∈{1，2，3，4}，規定：選定的旅館在其中編號為1，第2到ns+1的順序與S中候選景點編號順序一致；k＝1,2,3,4時分別對應公交、地鐵、駕車、步行，顯然mcost(i，j，4)＝0；

個性化參數包括旅游天數t_days、每日游玩景點數t_pnum、旅游偏好t_type、優先級別t_sup、旅游開始時期t_date；

其中，所述步驟(4)判斷是否進行種群的擴大的方法：判斷當前迭代次數g是否等于選定閾值T，若等于選定閾值，則增大種群規模，在原種群的基礎上，新增一組等同于原種群數量的隨機解；種群規模擴大后的種群數量變為M′＝2M，種群內個體數量變為I′＝2I，初始種群個體數量變為(M×I)′＝2M×2I，初始種群更新次數變為N′＝2N；

在種群的擴大判斷基礎上增加了種群規模擴大閾值T＝f_th×G，其中f_th為結果精確度的調節因子，在迭代次數未達到T時，算法結果還未收斂于最優值，此時使用普通搜索；當迭代次數超過T時，算法即將收斂，此時擴大搜索范圍，減少最優解的遺漏，旨在提高結果精確度，T的選擇由調節因子f_th確定；G為全局混合迭代次數；

其中，所述步驟(6)對種群進行更新的方法：根據分組結果，提取各個種群中的最差解X_w_k與最優解X_b_k(k＝1,2,3……M)，對各個種群內部進行N次的局部搜索，對于每一次局部搜索得到的新解X_new_k，計算其適應度并判斷其是否為異常解，若為異常解則通過加入懲罰因子的方式大幅度降低其適應度，最后使用改進的篩選規則決定新解的取舍；

所述異常解的產生包括在進行種群更新時產生的新解出現景點重復，多日游的路線規劃中出現路線交叉，路線不滿足旅游偏好；在生成每一個隨機個體之后，立即判斷其是否為異常解，若為異常解，則用一個數值足夠大的懲罰因子ΔC代替目標值，

f(X_h)＝ΔC

在懲罰因子ΔC足夠大的情況下，異常個體的適應度降低，使其在種群的更新中被淘汰；

所述的改進的篩選規則：

步驟(6)中的改進篩選規則是在基本混合蛙跳的基礎上新增了一項判斷條件，在以全局最優解和局部最差解之間的差距作為最大步長進行跳躍之后，若

||X_new_k-X_w_k||ε

則產生一個新的隨機解代替原有的X_w_k，否則保留原有的X_w_k；其中ε為根據模型和需求自行選定的閾值；

種群更新的實現步驟如下：

(a)種群更新計數器i＝1；

(b)種群編號k＝1；

(c)計算最大跳躍步長step_max＝X_b_k-X_w_k；

(d)產生一個0～1的隨機數λ；

(e)對最差解進行更新X_new_k＝X_w_k+λstep_max，并對X_new_k進行取整操作；

(f)計算新解適應度F(X_new_k)；

(g)若F(X_new_k)＞F(X_w_k)，則令X_w_k＝X_new_k，轉(m)；否則轉(h)；

(h)計算新的最大跳躍步長

(i)產生一個0～1的隨機數λ′；

(j)對最差解進行第二次更新并對X_new_k

進行取整操作；

(k)若F(X_new_k)＞F(X_w_k)，則令X_w_k＝X_new_k，轉(m)；否則轉(l)；

(l)若或則保留X_w_k，否則產生一個新解代替原有的X_w_k；Route表示路線，Pb表示交通方式的編號；

(m)k＝k+1，若k≤M轉(c)否則轉(n)；

(n)i＝i+1若i≤N轉(b),否則算法終止。