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

有效

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

本公開提供一種基于量子遺傳算法的確定最優路徑的方法、系統和介質。對所有路徑進行量子編碼，以生成包含多條染色體的量子種群，并對完成量子編碼的所有路徑進行初始化，使得量子種群中的各個染色體上的基因具有相同的初始概率；根據初始概率計算所有路徑中各個路徑的適應度，選取第一適應度；基于第一適應度，利用修正的量子旋轉門對完成量子編碼的所有路徑進行第一優化，包括對量子種群進行演化以獲得新一代的量子種群；對完成第一優化后的所有路徑執行第二優化，第二優化為染色體交叉優化，并選取新的第一適應度；確定新的第一適應度為第一適應度，輸出新的第一適應度對應的路徑作為最優路徑。

技術領域

本公開涉及量子計算領域，尤其是涉及一種基于量子遺傳算法的確定最優路徑的方法、系統和介質。

背景技術

量子力學和現代信息計算的結合有兩個重要的分支，一個是量子計算平臺的物理實現，另一重要方向就是量子算法的探究。自1994年，大數質因子分解量子算法被提出以來，對量子算法的研究已經廣泛應用到神經網絡、智能控制、復雜優化等領域。同時，量子算法已經被發展到越來越多的經典算法中，如遺傳算法、粒子群算法等等。

量子遺傳算法是利用量子比特編碼染色體，用量子邏輯門更新染色體的一種概率優化的搜索算法。量子比特編碼使得一個染色體能夠同時表征多個狀態；量子邏輯門的使用使得當前的最優染色體能夠向更好的方向進化。因此，量子遺傳算法在優化和聚類問題的求解上在收斂性和收斂速度上有著較大的優勢。

考慮一個經典的TSP規劃問題(即旅行商規劃問題，該問題的描述為給定N座城市和每對城市之間的距離，求解經歷且僅經歷一次每一座城市，并回到起始城市的最短路徑)，該問題在路徑規劃方面，表征為從當前計算節點出發經由多個特定計算節點回到所述當前計算節點的最短路徑。在實際應用中，例如外賣員，每天早上從起始位置(家里/公司)出發，目的地為多個小區和餐廳，結束一天的工作后回到所述起始位置；又如快遞員，從快遞站出發，目的地為多個送貨/取貨地址，最后回到快遞站。

針對，以上路徑規劃問題，由枚舉法可知，所有的可能路徑共有條。該問題的約束條件只有一個，即搜索一個集合V＝{V₁，V₂，V₃，...，V_N}(V中的元素表示對n個城市的編號)中的一個排列X，使得：

取得最小值，那么對應的路徑就是最優路徑。其中d(v_i，v_i+1)表示城市v_i到v_i+1的距離。

對于以上問題，易于陳述但難于求解。目前的求解方法包括動態規劃法、列表搜索法、遺傳算法等等。該問題能應用在物流、芯片制造領域。

在當前量子遺傳算法的框架下，將TSP問題中每一條可能的路徑抽象為染色體，每個城市抽象為染色體上的基因，即量子位。

染色體上的一個量子位(基因位)可以表示為：|Φ1＝α|0+β|1，其中，α，β表示概率幅，它是復數，并且有：|α|2+|β|2＝1，第t代中的第j個染色體中的M個量子比特的概率幅可以如下定義：

其中j＝1,2,3…N，然后對染色體進行量子旋轉門演化，這是實現量子遺傳算法的關鍵。旋轉門的操作主要是使得染色體上的每個基因的概率幅值收斂到0或者1，進而找到最優解。最常見的量子旋轉門操作為：

其中，θ為旋轉角度，通常為固定值。染色體的第i個基因可以表示為：利用量子旋轉門演化后的基因為：演化過程為：其中R(θ_i)表示對第i位上的基因進行操作的量子旋轉門。