[發明專利]基于量子進化算法的復雜場景排產方法及系統

有效

• 申請號: 201710601329.7
• 申請日: 2017-07-21
• 公開（公告）號: CN107330808B
• 公開（公告）日: 2021-01-15
• 發明（設計）人: 邵鵬;張嗣昌;盧毅;劉宇
• 申請（專利權）人: 山東萬騰電子科技有限公司
• 主分類號: G06F17/11
• 分類號: G06F17/11;G06Q50/04;G06N3/12;G06N3/00
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 黃海麗

1.基于量子進化算法的復雜場景排產方法，其特征是，包括如下步驟：

步驟(1)：量子種群初始化：包括初始化量子種群進化代數、初始化量子比特編碼和初始化量子染色體數量；

步驟(2)：量子排產與適應度評估：設立量子目標函數，考慮大型機械設備的生產制造環境的約束條件下，對量子目標函數進行求解；量子種群生成目標函數的二進制控制變量，根據生成的二進制控制變量，對應到工單任務的順序，進行排產，按照排產順序計算整個大型機械設備工單的完成時間，即為量子的適應度值；

步驟(3)：比較適應度值，通過最小適應度值確定最優解；保存最優解；判斷是否到達結束條件，若達到結束條件則輸出最優解；若未達到結束條件則跳轉至步驟(4)；

步驟(4)：量子更新：利用量子旋轉門對量子種群進行更新；返回步驟(2)重新計算量子的適應度值，繼續尋優；

所述步驟(1)中量子種群初始化，包括如下步驟：

步驟(1-1)：初始化進化代數t＝0；

步驟(1-2)：初始化量子比特編碼：通過確定大型機械設備工單任務所選擇的機器以及上線加工的順序，以獲得更優量子目標函數；

在初始化過程中需要定義兩個變量：

第一個變量表示工單i的第j個工序是否在第k個機器上加工，記為變量a_ijk，如果選擇機器k則變量a_ijk取值為1，如果未選擇機器k則變量a_ijk取值為0；

第二個變量表示工單i的第j個工序的加工順序為l，記為變量b_ijl，當工單i的第j個工序在第l個加工順序處開始上線加工時，變量b_ijl記為1，否則變量b_ijl為0；

令A＝[a₁₁₁，a₁₁₂，…，a_ijk，…]，用于存放工單i的第j個工序是否在第k個機器上加工的狀態；

令B＝[b₁₁₁，b₁₁₂，…，b_ijl，…]，用于存放工單i的第j個工序是否在第l個加工順序處開始上線加工的狀態；

對A和B進行順序拼接，得到多個大型機械設備工單的量子比特編碼，記為X；

X＝A+B＝[a₁₁₁，a₁₁₂，…，a_ijk，…，b₁₁₁，b₁₁₂，…，b_ijl，…](1)

其中，公式(1)中的“+”表示順序拼接，a_ijk、b_ijl分別取0或者取1，X為二進制序列；

通過所述編碼方式將工單任務、加工設備及加工工序信息包含于二進制序列X中；

具體的，一個量子比特位表示為：量子比特的狀態表示為：|ψ＝α|0+β|1，

其中|0和|1表示量子比特的兩種基本狀態；α和β為復數，表示量子位狀態的概率幅，α²為量子比特處于狀態0的概率、β²為量子比特處于狀態1的概率，α和β的幅值和角度隨機取值，但滿足|α|²+|β|²＝1；

令q表示染色體個體，則m個量子比特位表示的量子染色體為

其中，α_i²+β_i²＝1，i＝1，2，…，m；m表示單個染色體量子比特位長度，m的計算公式如下：

m＝工單任務總數×設備數+工單任務總數² (3)

則公式(1)用量子比特位表示為：

步驟(1-3)：初始化種群：染色體種群與進化代數t關聯，設第t代的量子染色體種群為：

則公式(2)轉化為：

式中，j代表染色體個數，j＝1，2，…n，n為染色體種群規模大小即染色體總數量；

則公式(4)與進化代數t關聯后轉化為：