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

有效

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

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

構造景區數據庫；

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

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

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

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

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

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

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

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

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

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

所述以一定的概率發生交叉事件，包括以下步驟：

隨機生成一個交叉點；

將適應度計算值較小的個體的交叉點后的基因序列移植到適應度計算值較大的個體的交叉點后；

判斷適應度計算值較大的個體交叉點前重復的基因，和被替換掉的基因序列中多余的基因，將多余基因的順序打亂依次替換重復基因。

2.根據權利要求1所述的方法，其特征在于，所述構造景區數據庫，包含以下步驟：

從互聯網上爬取景區的信息，重點爬取景區的名稱、所在城市、經緯度、大地坐標、特色；

人工整理互聯網爬取的原始數據，并按照景區特色給每個景區打標簽，共有六類標簽，包括歷史、自然、人文、科學、藝術、軍事；

將人工整理過的數據存入關系型數據庫。

3.根據權利要求1所述的方法，其特征在于：所述用戶的需求包括用戶定義的游玩的區域和感興趣的主題。

4.根據權利要求1所述的方法，其特征在于：在所述將景區數據編碼并隨機初始化第一代種群之前，定義種群規模、染色體長度、迭代次數，交叉概率、變異概率。

5.根據權利要求1所述的方法，其特征在于，所述根據適應度函數計算種群中每個個體的適應度，包含以下步驟：

根據每個個體的ID查找對應景區的大地坐標；

根據適應度公式計算個體適應度，適應度公式為：

其中Cn是染色體的長度，x和y表示景區的大地坐標，i表示景區。

6.一種基于微生物遺傳算法的旅游路線規劃系統，其特征在于，包括：

景區數據庫構造模塊，用于構造景區數據庫；

用戶需求設置模塊，用于供用戶定義游玩的區域和感興趣的主題；

微生物遺傳算法模塊，用于將景區數據編碼并隨機初始化第一代種群，根據適應度函數計算種群中每個個體的適應度，并篩選出適應度最好的個體，通過迭代的方式生成最佳路徑；

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

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

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

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

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

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

所述以一定的概率發生交叉事件，包括以下步驟：

隨機生成一個交叉點；

將適應度計算值較小的個體的交叉點后的基因序列移植到適應度計算值較大的個體的交叉點后；

判斷適應度計算值較大的個體交叉點前重復的基因，和被替換掉的基因序列中多余的基因，將多余基因的順序打亂依次替換重復基因。

7.一種電子裝置，其特征在于，包括存儲器和處理器，所述存儲器存儲計算機程序，所述計算機程序被配置為由所述處理器執行，所述計算機程序包括用于執行權利要求1～5中任一權利要求所述方法的指令。

8.一種計算機可讀存儲介質，其特征在于，所述計算機可讀存儲介質存儲計算機程序，所述計算機程序被計算機執行時，實現權利要求1～5中任一權利要求所述的方法。