[發明專利]一種基于鯨魚優化算法與人工魚群算法的旅游路徑規劃方法

在審

• 申請號: 202110786210.8
• 申請日: 2021-07-12
• 公開（公告）號: CN113420938A
• 公開（公告）日: 2021-09-21
• 發明（設計）人: 馮文龍;熊搏;黃夢醒;馮思玲
• 申請（專利權）人: 海南大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/14;G06N3/00
• 代理公司: 北京哌智科創知識產權代理事務所(普通合伙) 11745
• 代理人: 趙維亮

一種基于鯨魚優化算法與人工魚群算法的旅游路徑規劃方法，首先，將鯨魚算法中的鯨魚群體看成預計在某時段內在相同景區游覽不同景點的游客群體，對算法初始化設置并生成初始游客數，然后利用適應度函數獲得初始游客當前所在位置上的適應度值(即目標函數值)，從而確定初始游客的最優位置與全局最優位置并記錄下來放入最優解池中。并且可以從路程的遠近角度出發為游客提供一個比較舒適的旅行路線，能夠在實際的旅游路徑規劃中幫助旅行者們尋得一條較好的旅游路徑。

技術領域

本發明屬于旅游路徑規劃算法技術領域，具體地說，涉及一種基于鯨魚優化算法與人工魚群算法的旅游路徑規劃方法。

背景技術

隨著旅游經濟的發展和人們生活方式的變化，人們越來越熱衷于自駕游，因此游客對旅游服務信息的需求迅速增加。但如何安排個性化的旅程是一項非常棘手的事情，游客往往無法尋得一條最方便、快捷且適合自己的出行路線。旅游路徑規劃的出現便很好地緩解了這一問題。隨著旅游路徑規劃的興起，TSP問題(旅行商問題)成為了旅游路徑規劃中的一方面，在旅游路徑規劃中，TSP問題的有效解決將對旅游路徑規劃中如何更好地利用旅行者的旅行時間及費用等問題有很大的幫助。

TSP問題(Traveling Salesman Problem)是數學領域中的著名問題之一，該問題就是假設一個人需要經過n個城市，他需要在這n個城市中選擇所要走的路徑，路徑的限制條件是每個城市只能走一次，最終需要回到起點城市，并且需要所求得的路徑的路程為所有路徑之中的最小值。該問題的核心就是如何尋得一條經過這n個不同的城市且不重復經過每一個城市的最優路徑。

針對如何解決TSP問題，科學家們研究了許多的群智能算法進行解決，其中包括有蟻群算法、人工魚群算法、粒子群算法、遺傳算法等。隨著群智能算法被不斷地挖掘，2016年，澳大利亞學者Mirjalili和Lewis根據座頭鯨的獨特的泡泡網覓食行為提出了一種新型群智能優化算法，即鯨魚優化算法(Whale Optimization Algorithm,WOA)，該算法分為三個階段，分別為包圍捕食、螺旋更新、搜尋獵物階段。

鯨魚算法是一種元啟發式優化算法，該算法與其他群智能算法相比具有結構簡單、參數少、搜索能力強且易于實現等特點。但由于該算法的研究及應用仍處于起步階段，因此該算法還存在著求解精度較低、易陷入局部最優且收斂速度較慢等缺點。因此傳統的鯨魚算法并不能很好地應用到旅游路徑規劃中。

有鑒于此特提出本發明。

發明內容

為解決上述技術問題，本發明采用技術方案的基本構思是：

基于鯨魚優化算法與人工魚群算法的旅游路徑規劃方法的大致思路如下：首先，將鯨魚算法中的鯨魚群體看成預計在某時段內在相同景區游覽不同景點的游客群體，對算法初始化設置并生成初始游客數，然后利用適應度函數獲得初始游客當前所在位置上的適應度值(即目標函數值)，從而確定初始游客的最優位置與全局最優位置并記錄下來放入最優解池中。然后隨著算法的不斷迭代，游客根據多種個體位置更新公式進行位置更新，將計算出的每次新位置的適應度值與之前位置的適應度值進行比較，從中選取更小適應度值(更優)的游客的最優位置與全局最優位置。通過多次的迭代，最終可獲得一條從起始位置出發，歷經各個景點且不重復，最終又回到起始景點，并且每條路徑的適應度值最小(即最優)的最優旅行路徑。

本發明與現有技術相比具有以下有益效果：

本發明中將游客尋找游覽不同景點的最優路徑的行為類比于鯨魚種群覓食行為，從而可以實現將該優化算法轉變為一種旅游路徑規劃的方法。算法過程中的游客可看成鯨魚，本發明與傳統的鯨魚算法之間的主要區別在于，本發明中改進的鯨魚算法是結合了人工魚群算法的擁擠度的特點，由于人工魚群算法具有擁擠度概念，可以很好地避免由于某一個區域內魚群數量過多而導致魚群陷入局部最優的問題。因此將該擁擠度的概念引入到鯨魚算法中也可以有效解決鯨魚算法的易陷入局部最優的問題。