基于邊界規整的矩形PCB 排樣優化算法?

姚 遠 李山武 潘勛勇

（華中師范大學物理科學與技術學院 武漢 430079）

1 引言

隨著國內電子行業的快速發展，國內各廠商對PCB的需求量與日俱增，國內外原材料價格日益上漲，怎樣將打樣的PCB 耗材降到最低已成為當前PCB 制造商急需解決的問題［1］，因此PCB 排樣方案的好壞直接影響到PCB 耗材的多少。國內部分PCB制造產商的排樣方案大多采用人工手動布局，這不僅很難提高PCB的板材利用率，同時也極大地降低了PCB 廠商的打樣效率。雖然一些PCB 廠商的排樣采用基于計算機輔助設計的自動布局，但大都沒有考慮子板的邊界問題，較難滿足對子板排樣邊界整齊度高的要求。

目前PCB 排樣中具有代表性的兩種算法分別是啟發式算法［2］和元啟發式算法［3］。啟發式算法是根據PCB排樣的約束條件給出一組可行解，啟發式算法速度較快，但排樣效果較差，其主要有BF 算法［4］、分階段排樣算法［5］、四塊排樣算法［6］等。元啟發式算法則是根據PCB 的排樣約束條件給出一個近似最優解，其算法速度較慢，但排樣效果較好，其算法主要有遺傳算法［7］、蟻群算法［8］、模擬退火算法［9］等。上述算法雖能在一定程度解決PCB 排樣的利用率問題，但是由于排樣出來的PCB邊界參差不齊，較難適用于大規模PCB排樣［10～11］。

為了提高PCB 排樣的利用率、規整率和聚集度，本文在最低水平線算法［12］基礎上提出了基于邊界規整的矩形PCB排樣算法，算法對PCB子板邊界規整度和類聚度進行表征，并與板材利用率進行加權構造出優化目標函數并使用差分進化算法對排樣序列進行優化，最后進行了仿真分析。

2 基于邊界規整的PCB排樣算法

由于傳統最低水平線算法只根據當前待排PCB的高度和寬度來更新水平線，而沒有考慮排樣整齊度，導致排樣出來的母板上各子板PCB邊界參差不齊，特別是在進行排樣時完全采用貪婪策略來放置PCB，會導致越往后排樣效果越差［13］。為解決該問題，在最低水平線算法的基礎上引入微差高度概念，同時進行了垂直方向和水平方向上的邊界規整，在一定程度上解決了子板邊界整齊度問題。

2.1 傳統最低水平線算法

最低水平線PCB 排樣算法使用水平線來記錄已排PCB的母板布局信息［14］，然后從母板上的所有水平線中找出一條高度最低的水平線，如果該水平線能夠放置當前的PCB，則將PCB按照水平線的左頂點進行放置，否則從待排PCB序列中取出下一個PCB進行放置。

傳統最低水平線算法中一般使用三元組hli=(x,w,h)來描述算法中第i條水平線，其中x表示水平線的橫坐標，w表示水平線的寬度，h表示水平線的高度。算法對待排PCB 按照長和寬的大小進行降序排列，形成初始待排PCB序列［15］：

式中Pi為第i塊待排PCB，wPi,lPi分別為第i塊PCB 的寬度和長度。初始化水平線為?l0=(0,W,0)，其中W表示母板的寬度。當子PCB 按照排樣規則逐一放置到最低水平線上后，當前水平線的高度和寬度則根據當前PCB的高度和寬度進行更新。

2.2 基于邊界規整的矩形PCB排樣算法

為了解決母板上各子板PCB 的垂直邊界對齊問題，在傳統最低水平線算法上對水平線進行高度調整，每次獲取最低水平線后先對水平線左右的兩條水平線進行高度微差判斷，當微差高度小于設定值Hset時，對滿足微差高度條件的水平線進行合并，以保證子板的垂直方向上邊界對齊。本文引入垂直高度和水平邊界調整策略，從而使PCB子板邊界盡可能保持對齊。

本文約定：如果已知相鄰兩水平線之間的高度差為??，且?? 滿足條件0

圖1 本文改進算法的水平線高度規整過程

當最低水平線上放置子板PCB后，需要對當前水平線按照式（2）進行高度微差調整，即時對相鄰水平線且高度滿足微差高度條件的水平線進行合并。

式中，?li為當前最低水平線；wPi,?Pi為當前PCB的寬度和高度；xi,wi,?i分別為最低水平線的橫坐標，寬度和高度；Pi為當前在排PCB。

為了解決子板的水平邊界對齊問題，可以在水平線無法放置子板PCB時進行水平線的寬度規整，在最低水平線更新時不進行直接提升，而是采用寬度對齊的方式來進行提升，如圖2中所示。

圖2 本文改進算法的水平線寬度規整過程

最低水平線更新時按照式（3）對當前最低水平線進行更新。

將水平線按照改進的水平寬度進行更新可以在很大程度上提高子板PCB的邊界規整率，同時也會間接的提高排樣算法的板材利用率。

3 算法目標函數及其優化

由于待排PCB 的初始序列S0和微差高度對齊閾值Hset很難根據經驗進行設置，為了進一步提高基于邊界規整的矩形PCB排樣算法的排樣效果，可以先對子板類聚度、規整率和利用率的表征，然后構造出目標函數，使用優化算法對初始序列S0和微差高度對齊閾值Hset在可行解中進行搜索，從而對目標函數進行優化，達到進一步提高排樣效果的目的。

3.1 子板類聚度、規整率和利用率的表征

為了準確表征同類PCB子板的類聚程度，本文提出使用矩形度來表征同類PCB子板的類聚度，類聚度越大表明同類子板排布越緊密，類聚度越小表明同類子板排布越松散。定義類聚度為表征對象的面積總和與表征對象的最小外接矩形的面積之比，定義式如式（4）所示。

式中，KD為表征對象的類聚度，SObj為表征對象的總面積，SMER為最小外接矩形面積。

對于多種類PCB，本文使用平均類聚度來表征排樣后的PCB 類聚程度。設母板上有n種類的PCB，每類PCB 有mi個PCB 子板，則其排樣出的各類子板的平均類聚度如式（5）所示。

式中，AKD 排樣出的子板平均類聚度；n為母板上所有子板PCB 種類數；KDi為第i種類子板類聚度；mi為第i種類子板個數；為第i種類第j個PCB 的寬度；為第i種類第j個PCB 的長度；為第i種類子板的最小外接矩形面積。

子板規整率用來表征母板上子板PCB 的邊界規整程度，規整率越高，說明各個PCB 之間的邊界越整齊。為了準確表征子板的規整率，本文提出使用橫縱坐標重復個數占比作為子板規整率，其定義式如式（6）所示。

式中，RR為子板規整率；RNx為排樣后所有子板PCB 的橫坐標重復個數；RNy為排樣后所有子板PCB 的縱坐標重復個數；規定只有重復次數大于1的坐標進行累計。

PCB 排樣的板材利用率定義為母板上所有子板面積之和與母板的面積比值，如式（7）所示。

式中，MUR為板材利用率；N為母板上子板PCB的總個數；ws為第s塊子板PCB 的寬度；ls為第s塊子板PCB的長度；W為母板的寬度；L為母板的長度。

本文算法將子板類聚度、規整率和板材利用率三者進行加權，構造出優化算法的目標函數，如式（8）所示。

式中，DF為優化算法的目標函數，α為類聚度的加權系數，β為規整率的加權系數，γ為板材利用率的加權系數。

3.2 算法目標函數的優化模型

算法在多數情況下可以提高算法的板材利用率、各子板邊界規整和類聚度，但是其排樣的方案并不是最優解，為了進一步提高排樣效果，本文使用差分進化算法［16］來對目標函數進行優化，使用差分進化算法來優化PCB的排樣模型如圖3所示。

圖3 差分進化算法的PCB排樣優化模型

在圖3 中，差分進化算法會在迭代過程中對排樣的可行解進行搜索，從而求出近似最優解。本文使用兩點互換來對序列進行編碼，如圖4所示，圖4中使用E=(i,j)向量來對序列中Pi和Pj互換操作進行編碼，在解碼時只需要取得向量E的i,j值，然后互換序列中i,j兩位置的PCB即可。

圖4 序列的兩點互換編碼

為了設置合適的高度規整閾值Hset，需將該閾值也進行編碼。Hset是一個在區間[0,min{wPi/2,lPi/2}],i=1,2…N的整數，式中wPi為第i塊PCB的寬度，lPi為第i塊PCB長度。這樣就得到了維度為3 的目標向量X=(i,j,Hset)，此向量作為最低水平線PCB 排樣算法的輸入參數。在上述PCB 排樣算法的目標函數基礎上，可以給出如下的優化模型：

式中，DF為目標函數。W為母板的寬度。L為母板的長度。α為板材利用率的加權系數。β為子板平均類聚度的加權系數。γ為子板規整率的加權系數。N為母板上子板PCB 的總個數。n為母板上子板PCB 的種類總數。mi為母板上第i類子板PCB 的總個數。為母板上第i類PCB 的最小外接矩形面積。RNx為排樣后所有子板PCB的橫坐標重復個數。RNy為排樣后所有子板PCB的縱坐標重復個數。wmin為待排PCB 所有子板中的最小寬度。lmin為待排PCB 所有子板中的最小長度。

3.3 具體計算步驟

步驟1：初始化加權系數α,β,γ并設置種群大小NP，縮放因子F，交叉概率CR和迭代次數G，進行種群初始化，給出NP個初始排樣序列S0；

步驟2：按照該序列取出待排PCB，記當前取出的PCB 為Pi，設其較長的一邊為wPi，較短的一邊為lPi；從水平線中尋找最低水平線且記為?li；

步驟3：計算出余下待排PCB 序列中PCB 的最小長度和寬度，分別記為l0和w0；

步驟4：如果當前最低水平線寬度大于wPi，則直接放置在該水平線上，如果水平線寬度小于wPi且大于lPi，則將wPi與lPi互換（相當于旋轉90°）后放置；如果水平線寬度小于lPi時，則從待排PCB 序列中按順序取出下一個Pi+1，同時更新Pi=Pi+1，重新回到步驟2；如果水平線寬度小于l0和w0，則按照式（3）進行更新；

步驟5：對當前水平線按照式（2）進行垂直高度規整；

步驟6：如果母板上的水平線條數為1 且無法再放置PCB，則繼續下一步，否則回到步驟2；

步驟7：計算種群個體的PCB 排樣的目標函數DFi,i=1,2,…,NP；

步驟8：根據適應度函數值DFi進行選擇操作，然后進行變異操作和交叉操作，并對參數邊界進行處理，生成新的排樣序列Si；

步驟9：如果迭代次數小于或等于G，則轉到步驟2，否則算法結束，并從該代種群中選擇出目標函數最大的編碼Xbest，然后解碼生成Sbest，最后使用該序列對PCB排樣得到最終排樣結果。

4 算法仿真分析

為了驗證本文提出的基于邊界規整的矩形PCB 排樣算法優化的有效性，在i3-4005U CPU @1.7GHz，4G RAM 的平臺上分別對最低水平線算法、剩余矩形算法［17］和本文算法進行仿真。仿真測試算例如表1 所示。約定：MUR 表示板材利用率；AKD 表示平均類聚度；RR 表示規整率；DF 表示目標函數，用于綜合評價排樣效果。表1 的三組測試測試算例包含大子板和小子板的排樣情況，同時母板大小也是根據PCB廠商的常規尺寸來選定的。

表1 三組PCB測試算例

仿真時差分進化算法的參數設置如下：種群規模設置為NP=50，F=0.8，CR=0.9，G=500。為了在盡可能高的板材利用率下提高子板規整率和類聚度，設置α=0.6,β=0.1,γ=0.3。三組算例的仿真測試排樣效果如圖5 所示，圖中的方框為同類PCB的最小外接矩形，方框的左上角的數值為同類子板的類聚度，仿真結果相關數據如表2所示。

表2 三組算例的PCB排樣結果對比

圖5 使用最低水平線算法、剩余矩形算法和本文算法對三組算例的仿真結果

從圖5 中可以看出，本文算法相對于最低水平線算法和剩余矩形算法在板材利用率、子板規整率和類聚度的綜合排樣效果上更優，母板上各子板PCB 邊界更加整齊，分布更為集中。從表2 中的相關數據上看，第一組算例中本文算法雖然類聚度和規整率稍低，但是其利用率較高；第二組算例中本文算法各指標均高于其他兩種算法；第三組算例中本文算法的利用率、平均類聚度、規整率和目標函數值優于其他兩種算法。本文算法由于使用差分進化算法且進化代數較多，所以在耗時上略長。

5 結語

針對有邊界規整要求的矩形PCB排樣問題，利用水平寬度和垂直高度規整的思想，本文提出了基于邊界規整的PCB 排樣優化算法。為了克服差分進化算法在搜索迭代過程中容易出現的優化曲線震蕩和收斂速度過慢缺陷，通過對排樣序列使用兩點互換編碼，提高差分進化算法的優化速度和魯棒性。對高度微差閾值進行整數編碼，降低了設置超參數的難度，在差分進化算法中使用精英保留策略保證算法的收斂性。仿真結果表明，本文算法在綜合排樣效果上優于最低水平線算法和剩余矩形算法，對本文算法的實時性進行優化將是未來需要進一步研究的方向。