[發明專利]一種多條件約束下的智能路徑規劃算法

在審

• 申請號: 202011209848.7
• 申請日: 2020-11-03
• 公開（公告）號: CN112257952A
• 公開（公告）日: 2021-01-22
• 發明（設計）人: 田鵬飛;孫偉;吳丹;儲鑫淼
• 申請（專利權）人: 億景智聯（北京）科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 南京鼎傲知識產權代理事務所(普通合伙) 32327
• 代理人: 劉藹民

本發明公開了一種多條件約束下的智能路徑規劃算法，使用免疫遺傳算法結合2?opt算法，免疫遺傳算法可以有效抑制退化現象，提高全局搜索速度，2?opt可以避免陷入局部最優陷阱，算法實施步驟如下，S1、首先進行抗體編碼，將排班路徑規劃問題轉化為免疫系統能夠處理的抗原形式，抗體則對應問題的解，S1中采用自然數編碼，定義免疫系統由N個抗體組成，即群體規模為N，M表示抗體的基因數，本發明結構科學合理，使用安全方便：本發明結合免疫遺傳算法與2?opt算法，能夠更有效的得到最優路徑規劃，有效抑制退化現象，提高全局搜索速度，避免陷入局部最優的缺點。

技術領域

本發明涉及智能控制技術領域，具體為一種多條件約束下的智能路徑規劃算法。

背景技術

業務人員拜訪客戶的路徑規劃，受多種條件約束，針對業務人員，需要支持工作有效時間約束、出發點和返回點約束、每日拜訪的總數量約束、交通方式的約束，針對客戶需要支持客戶點停留時間約束、客戶拜訪頻次約束、客戶辦公時間約束等，在如此眾多的約束條件下，如何才能達到路程最短的情況下，有效的完成最多的客戶有效拜訪，這是路徑規劃算法的難點。

發明內容

本發明提供一種多條件約束下的智能路徑規劃算法，可以有效解決上述背景技術中提出每個業務人員在復雜的條件下尋找到最有效的拜訪路徑，有效提高業務人員工作效率的問題。

為實現上述目的，本發明提供如下技術方案：一種多條件約束下的智能路徑規劃算法，使用免疫遺傳算法結合2-opt算法，免疫遺傳算法可以有效抑制退化現象，提高全局搜索速度，2-opt可以避免陷入局部最優陷阱；

算法實施步驟如下：

S1、首先進行抗體編碼，將排班路徑規劃問題轉化為免疫系統能夠處理的抗原形式，抗體則對應問題的解；

S2、計算抗體與抗體間的親和力，在進化過程中免疫系統是一個不確定系統，其多樣性由平均信息熵來表示；

S3、排除相似抗體；

S4、計算抗原與抗體的親和度；

S5、選擇優良抗體加入記憶庫；

S6、交叉、變異、隨機產生新抗體。

根據上述技術方案，所述S6中變異操作采用2-opt算法，迭代次數超過預先的設定，則輸出最優解，否則返回S2。

根據上述技術方案，所述S1中采用自然數編碼，定義免疫系統由N個抗體組成，即群體規模為N，M表示抗體的基因數。

根據上述技術方案，所述S2中定義P_ij是第i個等位基因在j基 因座上出現的頻率；

P_ij＝等位基因i在等位基因j上出現的總個數/N；

則處于j位置的基因信息熵為：

整個群體的基因信息熵為：

那么根據熵的定義，得到抗體v和w的親和力：

根據上述技術方案，所述S3中AX_v,wω，則淘汰一條抗體，ω 為濃度閾值；v為相同等位基因段的數量；

根據上述技術方案，所述S4中計算抗原與抗體的親和度axv， 排除親合力小于上一代親和度最小值的抗體；

AX_v＝1/C(v)。

根據上述技術方案，所述S5中在傳統適應度選擇比例的基礎上 增加基于濃度的調節概率因子，抗體v的濃度計算公式為：