基于遺傳算法的集成電路板下料算法

闞海明 胡曉彥

摘要：為了解決集成電路板（PCB）在生產過程中的自動排布問題，實現不同類型PCB板的一次性自動套裁排樣，在傳統自適應遺傳算法基礎上引入了梯度概念，實現了適用于PCB的自動排樣算法（AGA_Grad）。相比現有成熟的PCB板套裁排樣軟件，AGA_Grad有參數設置簡單、計算收斂速度更快及排列更優等優點，用于指導工業生產，能夠明顯提高多種類型PCB板的排樣速度。

關鍵詞：矩形排樣；電路板下料；動態規劃；遺傳算法

中圖分類號：TP18文獻標志碼：A文章編號：1008-1739（2020）07-58-3

0引言

矩形排樣已有比較成熟的算法，算法時間和排樣結果基本都能滿足生產需要。但在一些小批量、多品種的集成電路下料生產過程中，經常會面臨將多種類型、大小不一PCB放在同一個工作板上布局的問題，該問題屬于典型的套裁排樣，不僅需要考慮板材的布局，還要考慮待加工PCB的自身形狀。當前該類算法大致分為3類：①以傳統精確算法實現排樣，但耗時較長；②生成普通排樣的近似算法；③根據自身特性及生產情況，一定程度上進行簡化。文獻[1-4]提出生成最優2段排樣方式的確定型算法，一定程度上簡化了切割過程；文獻[5]中的動態規劃算法解決了考慮切割刀數的2段排樣方式，對工業生產有一定的指導作用；文獻[6-8]在傳統單一排樣算法、套裁排樣算法基礎上進行了改進。

企業PCB生產過程有小批量、多品種的典型特點，需要實現套裁排樣加工，本文將遺傳算法應用在其中實現了PCB套裁排樣，得到了理想效果。

1問題描述

1.1 PCB下料問題

在實際生產過程中，需要將不同類型的PCB盡可能多地拼放在同一張母板上，經過工藝成型將定型的PCB單元板再切割下來，從而達到一次性生產多個PCB的目的，這樣有助于在一定程度上簡化下料過程。

PCB下料過程中可將單張板材切割成若干大小尺寸不等和價值已知的矩形毛坯，約束條件有：①確定工作板尺寸；②毛坯數量不確定，毛坯位置不能重疊，毛坯之間距離可調整；③使得板材中排入的毛坯數量盡可能多，整體材料利用率最大，整體材料利用率計算公式為：材料利用率=（毛坯數量*單個毛坯面積/板材總面積）*100%。

3實驗結果分析

為了測試AGA_Grad算法的合理性，做了測試，隨機生成30組PCB板尺寸，選擇母板為2 500mm*3 000mm，如表1所示。

為了方便比較，分別采用普通遺傳算法和AGA_Grad算法對表2中PCB板進行切割排序，實際計算時發現二者所需時間相差無幾，但收斂速度AGA_Grad算法明顯優于普通遺傳算法，迭代次數對比如圖2所示。

PCB板的排列結果如圖3所示，其中切割使用面積占總面積的82%。

4結束語

本文研究了PCB板實際生產過程中的排樣問題，在自適應遺傳算法的基礎上引進了梯度概念，提出了AGA_Grad算法，并結合某研究所實際生產數據證明了該算法的有效性，獲得了滿意的效果。

參考文獻

[1] CUI Yaodong，HE Dongli，SONG Xiaoxia.Generating Optimal Two-section Cutting Patterns for Rectangular Blanks[J]. Computers & Operations Research，2006，33（6）：1505-1520.

[2] CUI Yaodong.A New Dynamic Programming Procedure for Three-staged Cutting Patterns[J].Journal of Global Optimization， 2013， 55（2）：349-357.

[3]季君，陸一平.查建中，等.生成矩形毛坯最優兩段排樣方式的確定型算法[J].計算機學報，2012，35（1）：183-191.

[4]孔令熠，陳秋蓮.二維多階段矩形剪切排樣算法[J].計算機應用與軟件，2015，32（5）：231-233.

[5]羅丹，崔耀東，李秋蓉.生成勻質塊排樣方式的遞推算法[J].計算機工程與設計，2013，34（3）：1112-1115.

[6]潘衛平，陳秋蓮，崔耀東.考慮切割刀數的最優兩段排樣算法研究[J].廣西大學學報（自然科學版），2014，39（3）：687-692.

[7]李東興.同尺寸集成電路板下料算法研究[D].南寧：廣西大學，2016.

[8] FAYARD D，ZISSIMOPOULOS V. Approximation Algorithm for Solving Unconstrained Two-dimensional Knapsack Problems[J]. European Journal of Operational Research， 1995，84（3）：618.