[發明專利]基于自適應遺傳算法的矩形件優化排樣方法

在審

• 申請號: 201911220002.0
• 申請日: 2019-11-28
• 公開（公告）號: CN111260062A
• 公開（公告）日: 2020-06-09
• 發明（設計）人: 董云成
• 申請（專利權）人: 杭州安脈盛智能技術有限公司
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06F30/20
• 代理公司: 杭州杭誠專利事務所有限公司 33109
• 代理人: 尉偉敏

本發明涉及矩形件二維排樣技術領域，公開了基于自適應遺傳算法的矩形件優化排樣方法，包括步驟：A)獲取各個矩形件的對尺寸進行歸一化處理；B)采用十進制的方法對矩形件進行基因編碼；C)采取啟發式規則進行參數初始化；D)根據排樣最大長度排樣重心位置ρ^*和排樣整齊度k^*構建適應度函數F；E)對種群中的每組解進行評估；F)設置算法停止條件；G)根據種群適應度值的統計分布設置交叉概率P_c和變異概率P_m，獲得交叉后的種群；H)按照變異概率P_m進行個體基因變異，產生新一代的群體。本發明采用一種全新的種群初始化方法并且構建了多因素相結合的適應度函數，算法收斂快速，矩形件優化效果好。

技術領域

本發明涉及矩形件二維排樣的技術領域，尤其是涉及基于自適應遺傳算法的矩形件優化排樣方法。

背景技術

在如今的工業生產領域，矩形件二維排樣的應用十分廣泛，比如石材、玻璃、皮革等材料的切割，如何在上面優化布局使原材料得到最大限度的利用，需要尋找出一種矩形件的排列組合而使剩余面積S最大化，但隨著矩形件數目的增多，其排列組合將呈爆炸式增長，無法在短時間內尋找出最優解，現有存在技術也大多是利用一些智能優化算法，比如遺傳算法、蟻群算法、模擬退火算法等尋找近似最優算法，但運用這些算法時優化目標函數考慮單一，參數也大多是預先固定，導致算法運行結果對參數設置依賴很大。

例如，一種在中國專利文獻上公開的“一種基于遺傳算法的排案優化方法”，其公告號CN108090650A，該發明建立各矩形待排件數學模型，確定待排件尺寸規模，將各待排件及其待排屬性視為一個基因，并進行基因編碼；由一組待排件組成一個種群，其基因組成視為一組染色體；實數編碼與交叉：確定交叉位置，選擇交叉部分，根據交叉概率確定是否交叉；對每一組個體的每一個位置進行變異判斷是否需要旋轉變異和位置變異；采用選擇算法在末代遺傳操作產生新的種群后，計算出種群的適應度，然后按適應度將種群中的個體進行排序，取適應度高的個體組成新的準群。該發明優化目標函數考慮單一，另外參數也是預先固定的，導致算法運行結果對參數設置依賴很大，優化效果對參數的設置依賴性高。

發明內容

本發明是為了解決現有算法求解矩形件優化排樣時對參數設置依賴大的問題，提供基于自適應遺傳算法的矩形件優化排樣方法。本發明采用自適應遺傳算法對矩形件排樣問題進行優化，采取啟發式規則進行參數初始化，并且綜合考慮了排樣最大長度排樣重心位置ρ^*和排樣整齊度k^*這三個方面，根據這三個方面構建適應度函數F，還根據種群適應度值的統計分布自適應地設置交叉概率P_c和變異概率P_m，優化效果好。

為了實現上述目的，本發明采用以下技術方案：

基于自適應遺傳算法的矩形件優化排樣方法，包括步驟：

A)采集待排樣矩形件，獲取各個矩形件的尺寸和質量，對尺寸進行歸一化處理；

B)采用十進制的方法對矩形件進行基因編碼，每一個矩形件表示一個基因，各個基因構成一條染色體，每條染色體代表一組解，每條染色體上的基因數為矩形件的總個數，種群規模為N；

C)采取啟發式規則進行參數初始化；

D)獲取排樣最大長度排樣重心位置ρ^*和排樣整齊度k^*，根據排樣最大長度排樣重心位置ρ^*和排樣整齊度k^*構建適應度函數F；

E)對種群中的每組解進行評估，計算每組解的適應度函數值，根據適應度函數值對染色體進行排序；

F)設置算法停止條件，若滿足停止條件，則結束算法，獲得矩形件最佳排樣方案；若不能滿足停止條件，則進入步驟G)；