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

有效

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

本發明公開了一種基于改進蛙跳算法的個性化旅游路線推薦方法，包括如下步驟：(1)讀取模型所需數據和個性化參數，確定優化目標和約束條件；(2)數據預處理與算法參數初始化；(3)隨機生成初始種群，并計算其適應度；(4)判斷是否進行種群的擴大；(5)對所有個體按適應度進行降序排序并分組；(6)對族群進行更新；(7)族群混合，記錄最優解；(8)判斷算法是否到達終止條件。該方法具有搜索能力強、所得結果精確的特點。

技術領域

本發明涉及一種基于改進蛙跳算法的個性化旅游路線推薦方法。

背景技術

路徑規劃問題是日常生活中較為常見且復雜的問題，在很多領域都具有廣泛的應用。在高新科技領域的應用有：無人機的避障突防飛行、巡航導彈躲避雷達搜索、機器人的自主無碰行動、防反彈襲擊等。在日常生活領域的應用有：GPS導航、基于GIS系統的道路規劃、城市道路網規劃導航等。只要是能夠轉化成為點線網絡的規劃問題基本上都可以采用路徑規劃的方法解決。而路徑規劃問題實際上是屬于組合優化問題的一種。

為了更好的解決組合優化問題，Eusuff和Lansey在2003年提出了一種仿生學的智能優化算法——混合蛙跳算法(SFLA)。蛙跳算法的思想是對青蛙群體覓食行為的模擬，對于數量眾多且分布廣泛的覓食點，青蛙通過分組尋找不同的覓食點。每一組的青蛙通過交換各個覓食點的信息，進行組內的局部搜索。當各組的局部搜索進行到一定程度時，所有青蛙重新混合到一起，進行信息的交換，接著再次重新分組，重復以上行為直至最優覓食路線的出現。

當下的路線規劃方法中存在的不足之處有：硬件資源消耗大，運行時間差，易于陷入局部最優，求解精度低。

發明內容

發明目的：本發明目的是提供一種基于改進蛙跳算法的個性化旅游路線推薦方法。

技術方案：本發明提供一種基于改進蛙跳算法的個性化旅游路線推薦方法，包括如下步驟：

(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]