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

在審

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

1.一種多條件約束下的智能路徑規劃算法，其特征在于：使用免疫遺傳算法結合2-opt算法，免疫遺傳算法可以有效抑制退化現象，提高全局搜索速度，2-opt可以避免陷入局部最優陷阱；

算法實施步驟如下：

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

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

S3、排除相似抗體；

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

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

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

2.根據權利要求1所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S6中變異操作采用2-opt算法，迭代次數超過預先的設定，則輸出最優解，否則返回S2。

3.根據權利要求1所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S1中采用自然數編碼，定義免疫系統由N個抗體組成，即群體規模為N，M表示抗體的基因數。

4.根據權利要求3所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S2中定義P_ij是第i個等位基因在j基因座上出現的頻率；

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

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

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

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

5.根據權利要求4所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S3中AX_v,wω，則淘汰一條抗體，ω為濃度閾值；v為相同等位基因段的數量；

6.根據權利要求5所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S4中計算抗原與抗體的親和度axv，排除親合力小于上一代親和度最小值的抗體；

QUOTE 。

7.根據權利要求6所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S5中在傳統適應度選擇比例的基礎上增加基于濃度的調節概率因子，抗體v的濃度計算公式為：

QUOTE ；

個體的選擇概率 QUOTE 由適應度概率 QUOTE 和濃度抑制概率 QUOTE 兩部分組成：

QUOTE 。

8.根據權利要求7所述的一種多條件約束下的智能路徑規劃算法，其特征在于，所述S6中交叉操作采用順序交叉，在雙親1中隨機選擇一個匹配區域，產生原始后代，將雙親2中與匹配區域不同的部分按照原來的順序插入到原始后代，組成子代1，按照同樣的方法組成子代2。