[發明專利]一種基于實數編碼量子進化算法的不規則排樣方法

有效

• 申請號: 201610060417.6
• 申請日: 2016-01-29
• 公開（公告）號: CN105740953B
• 公開（公告）日: 2018-01-12
• 發明（設計）人: 楊衛波;王萬良;趙燕偉;張景玲
• 申請（專利權）人: 溫州大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 黃美娟,王兵

技術領域

本發明涉及玻璃切割、服裝及皮革剪裁等加工領域中的計算機輔助排樣技術領域，特別是涉及一種不規則形狀的樣片在寬度固定而長度不固定的矩形母板上的排樣方法。

背景技術

不規則多邊形排樣問題廣泛地存在于金屬沖裁、玻璃切割及服裝、皮革剪裁等加工中，在批量生產中排樣效率微小的提高，就可能為企業帶來巨大的經濟效益。目前，一些企業還是靠人工經驗進行排樣，不僅工作量大、效率低，且排樣效果遠不能滿足生產需求，帶來原材料的浪費。

不規則形狀排樣問題的求解方法最早使用傳統的數學方法或一些啟發式算法，這些方法一般僅適用于小規模排樣問題，難以滿足實際需求；目前大部分排樣問題主要采用人工智能的方法來求解，如遺傳算法、模擬退火算法或粒子群算法等，在實踐中，這些方法的局部搜索能力和全局搜索能力很難達到平衡，從而導致排樣時間長、排樣的搜索精度低及原材料的利用率低的問題。

2002年提出的量子進化算法使用量子比特對個體編碼，量子染色體可表示多個模態解的疊加，具有全局搜索能力強、不易陷入局部最優等優點，在解決利用遺傳算法求解不理想的問題時表現出了優異的性能。目前量子進化算法已廣泛應用于多重二次背包問題、柔性作業車間調度問題和多目標隨機需求車輛路徑問題等眾多領域的優化問題，表現出了優異的性能。迄今為止，國內外少有將量子進化算法應用到二維不規則排樣領域的相關研究。

發明內容

本發明要解決現有排樣方法排樣時間長、排樣的搜索精度低及原材料的利用率低的問題，而提出一種基于實數編碼量子進化算法的不規則排樣方法。

本發明解決其技術問題所采用的技術方案是：

一種基于實數編碼量子進化算法的不規則排樣方法，包括以下步驟：

步驟1、實數編碼，采用實數量子幾率幅值對排樣編號序列和旋轉角度序列進行統一編碼，對于具有n個排樣件和每個排樣件允許沿順時針方向旋轉m個角度的排樣問題，用n×(n+m)的二維量子位概率幅矩陣表示第t代第k個量子染色體為：

式中，inf為無窮大數，β_ij(0≤i≤n-1,1≤j≤i+1)用來編碼排樣件的編號,β′_iu(0≤i≤n-1,1≤u≤m)用來編碼排樣件的旋轉角度索引；

步驟2、系統初始化，利用不規則形狀樣片的幾何特征，構造啟發式算法生成初始排樣序列種群U(0)及第0代的量子種群Q(0)；

步驟3、計算U(0)中各個個體的適應度，將最優個體賦值給初始種群最優個體

步驟4、種群更新，進化迭代次數t＝t+1，采用量子旋轉門更新量子染色體種群，得到第t代的量子種群Q(t)；

步驟5、量子觀測，對種群Q(t)分別進行排樣編號序列量子觀測與旋轉角度索引序列量子觀測，生成排樣序列種群U(t)；

步驟6、利用基于臨界多邊形(NFP)的不規則樣片形心最低的放置策略將由種群U(t)確定的排樣順序將樣片排入母板，然后進行個體適應度評價，將其中的最優個體賦值給第t代種群最優個體

步驟7、判斷迭代次數t是否達到預先設定的數目，若否轉步驟3，是則輸出當前最優個體算法結束。

進一步，所述步驟2中，系統初始化參數包括最大迭代代數，量子旋轉門初始旋轉角度，變異間隔代數。

進一步，所述步驟4中，如果在連續n代迭代過程中沒有找到更優解，則對Q(t)中的各個個體進行量子變異操作。

更進一步，所述步驟6中，基于NFP的不規則樣片形心最低的放置策略如下：以樣片的形心坐標作為參考點來構造形心NFP，放置時選取形心NFP中具有最小橫坐標值的頂點作為排樣件的放置位置，再由多邊形的拓撲關系確定其他各個頂點的具體排放位置。

在進行排樣時，優化的目標是在滿足約束條件下使原材料的利用率η最高，即：

式中，s(i)為第i個樣片的面積。

本發明與已有技術相比，具有如下優點與有益效果：

1、將實數編碼量子進化算法應用到計算機排樣技術領域，實數編碼方式減少了染色體編碼長度，有效地縮短了排樣時間；

2、量子觀測過程始終保持概率運算，解碼效率高，提高了排樣的搜索精度；

3、通過構造啟發式算法生成高質量的初始種群，提高了算法的優化能力，提高了原材料的利用率。

附圖說明

圖1為本發明方法的流程圖。

圖2為不規則多邊形形心與排樣放置策略示意圖。