[發明專利]基于量子遺傳算法的確定最優路徑的方法、系統和介質

有效

• 申請號: 202110574816.5
• 申請日: 2021-05-26
• 公開（公告）號: CN113361753B
• 公開（公告）日: 2023-07-04
• 發明（設計）人: 卓蘭;李孟良;韓麗
• 申請（專利權）人: 中國電子技術標準化研究院
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06N3/126;G06N10/60
• 代理公司: 北京融智邦達知識產權代理事務所(普通合伙) 11885
• 代理人: 吳強

1.一種基于量子遺傳算法的確定最優路徑的方法，其特征在于，所述最優路徑為從當前計算節點出發經由多個特定計算節點回到所述當前計算節點的最短路徑，所述方法包括：

步驟S1、對所有路徑進行量子編碼，以生成包含多條染色體的量子種群，并對完成所述量子編碼的所有路徑進行初始化，使得所述量子種群中的各個染色體上的基因具有相同的初始概率；

其中，每一條染色體表征一條路徑，所述量子種群表征所述所有路徑，所述所有路徑為從所述當前計算節點出發經由多個所述特定計算節點回到所述當前計算節點的全部路徑；

步驟S2、根據所述初始概率計算所述所有路徑中各個路徑的適應度，選取所述適應度的最大值作為第一適應度，所述適應度表征所述染色體存活并且將所述染色體上的基因演化至下一代的能力；

步驟S3、基于所述第一適應度，利用修正的量子旋轉門對完成所述量子編碼的所有路徑進行第一優化，所述第一優化包括對所述量子種群進行演化以獲得新一代的量子種群；

步驟S4、對完成所述第一優化后的所述所有路徑執行第二優化，所述第二優化為染色體交叉優化，并計算經所述染色體交叉優化后的所述各個路徑的適應度，選取經所述染色體交叉優化后的所述各個路徑的適應度的最大值作為第二適應度，將所述第一適應度和所述第二適應度中的較大值作為新的第一適應度；以及

步驟S5、確定所述新的第一適應度是否為所述第一適應度，若是，則量子種群進入收斂狀態，輸出所述新的第一適應度對應的路徑作為所述最優路徑；

在所述步驟S3中，所述修正的量子旋轉門表示為：

其中所述修正的量子旋轉門的旋轉角度，f_max為所述第一適應度，f_x為所述各個染色體的適應度，為所述修正的量子旋轉門的初始旋轉角度，取值范圍為[0.001π，0.05π]，，α_i和β_i表示第i個基因的概率；

在所述步驟S4中，所述染色體交叉優化包括第一交叉優化和第二交叉優化，其中：

所述第一交叉優化具體為，獲取演化后的所述新一代的量子種群中各個染色體的當前位置序列作為第一位置序列，將所述第一位置序列隨機調整為與所述第一位置序列不同的第二位置序列；

所述第二交叉優化具體為，從所述第二位置序列中隨機選取一個染色體作為目標染色體，從所述目標染色體上隨機選取一個基因作為目標基因，獲取所述目標基因在目標染色體上的基因量子排位序號k，將所述目標基因在所述基因量子排位上移動k位。

2.根據權利要求1所述的一種基于量子遺傳算法的確定最優路徑的方法，其特征在于，在所述步驟S1中，所述對完成所述量子編碼的所有路徑進行初始化包括，設置所述量子種群的初始演化代數為0，將所述基因的初始概率均設置為。