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

闞海明 胡曉彥

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

關(guān)鍵詞：矩形排樣；電路板下料；動態(tài)規(guī)劃；遺傳算法

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

0引言

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

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

1問題描述

1.1 PCB下料問題

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

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

3實驗結(jié)果分析

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

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

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

4結(jié)束語

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

參考文獻

[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]季君，陸一平.查建中，等.生成矩形毛坯最優(yōu)兩段排樣方式的確定型算法[J].計算機學報，2012，35（1）：183-191.

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

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

[6]潘衛(wèi)平，陳秋蓮，崔耀東.考慮切割刀數(shù)的最優(yōu)兩段排樣算法研究[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.