[發明專利]一種基于微生物遺傳算法的旅游路線規劃方法和系統

有效

• 申請號: 202010134691.X
• 申請日: 2020-03-02
• 公開（公告）號: CN111369047B
• 公開（公告）日: 2022-11-15
• 發明（設計）人: 李凌波;王海波
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/14;G06N3/12
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 邱曉鋒

本發明涉及一種基于微生物遺傳算法的旅游路線規劃方法和系統。該方法包括：構造景區數據庫；用戶定義游玩的區域和感興趣的主題；根據用戶的需求從景區數據庫中查找景區數據；定義種群規模、染色體長度、迭代次數，交叉概率，變異概率；將景區數據編碼并隨機初始化第一代種群；根據適應度函數計算種群中每個個體的適應度；篩選出適應度最好的個體；如果達到迭代次數則解碼生成最佳路徑，規劃結束，否則將當前代種群中的個體隨機兩兩配對，篩選需要交叉和變異的個體；然后以一定的概率發生交叉事件，并以一定的概率發生變異事件，循環執行計算適應度的步驟。本發明在提供合理的路線推薦的同時，降低了計算資源的消耗，提高了推薦結果的響應速度。

技術領域

本發明屬于旅游路線規劃領域，具體涉及一種基于微生物遺傳算法的旅游路線規劃方法和系統。

背景技術

目前，隨著國民經濟的發展和人民生活水平的提高，旅游已經成為人們日常生活中必不可少的活動。在旅游產業空前發達的今天，政府規劃的景區數量也日漸增多。據不完全統計，僅在北京地區有明確規劃的景區數量就多達千余個。旅游路線規劃已經成為旅游業一個重要的服務項目。當前，旅游路線規劃方法主要包括人工規劃和采用規劃算法自動規劃兩種。

人工規劃是指旅游業服務人員根據用戶需求和專業知識提供咨詢意見，這種方式獲得的信息質量高，但是消耗的成本大，費用昂貴。自動規劃是指基于景區數據，針對用戶的個性化需求建立數學模型，將路徑規劃問題轉化為最優化問題，采用規劃算法自動生成規劃路徑。當前，主流的路徑規劃算法主要包括三類：精確算法、啟發式搜索算法和元啟發式算法。精確算法的特點是一定能找到全局最優解但是遍歷的節點過多，計算量大；啟發式搜索算法，包括A*，D*，Focused D*算法等，一般應用于給定起點和終點的尋路問題，不適用于基于景區地理信息數據的路線推薦問題；元啟發式算法包括粒子群算法、模擬退火算法、遺傳算法、蟻群算法等，特點是結合了隨機算法和局部搜索算法，相比較于精確算法計算量少，同時又因為采用了隨機算法使得優化過程在一定程度上避免陷入局部最優解，但是經典的元啟發式算法同樣有計算量大、收斂速度慢的問題。既能獲得全局最優解又能夠提高計算效率是旅游路線規劃領域的研究重點。

微生物遺傳算法是傳統遺傳算法的改進。本發明主要基于微生物遺傳算法解決旅游路線規劃問題。

發明內容

本發明目的是提供一種基于微生物遺傳算法的旅游路線規劃方法，該方法基于開源景區數據，構建路線自動規劃算法模型，根據用戶的需求，提供合理的路線推薦；同時，降低了計算資源的消耗、提高了推薦結果的響應時間。

本發明采取的技術方案是：

一種基于微生物遺傳算法的旅游路線規劃方法，包括以下步驟：

構造景區數據庫；

根據用戶的需求從景區數據庫中查找景區數據；

將景區數據編碼并隨機初始化第一代種群；

根據適應度函數計算種群中每個個體的適應度；

篩選出適應度最好的個體，通過迭代的方式生成最佳路徑。

進一步地，所述通過迭代的方式生成最佳路徑，包括：

判斷是否達到迭代次數，如果達到則解碼生成最佳路徑，規劃結束，否則繼續以下步驟；

將當前代種群中的個體隨機兩兩配對；

篩選需要交叉和變異的個體；

以一定的概率發生交叉事件；

以一定的概率發生變異事件，循環執行所述根據適應度函數計算種群中每個個體的適應度的步驟。

進一步地，所述構造景區數據庫，包含以下步驟：