基于邊界規(guī)整的矩形PCB 排樣優(yōu)化算法?

姚 遠(yuǎn) 李山武 潘勛勇

（華中師范大學(xué)物理科學(xué)與技術(shù)學(xué)院 武漢 430079）

1 引言

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

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

為了提高PCB 排樣的利用率、規(guī)整率和聚集度，本文在最低水平線算法［12］基礎(chǔ)上提出了基于邊界規(guī)整的矩形PCB排樣算法，算法對(duì)PCB子板邊界規(guī)整度和類(lèi)聚度進(jìn)行表征，并與板材利用率進(jìn)行加權(quán)構(gòu)造出優(yōu)化目標(biāo)函數(shù)并使用差分進(jìn)化算法對(duì)排樣序列進(jìn)行優(yōu)化，最后進(jìn)行了仿真分析。

2 基于邊界規(guī)整的PCB排樣算法

由于傳統(tǒng)最低水平線算法只根據(jù)當(dāng)前待排PCB的高度和寬度來(lái)更新水平線，而沒(méi)有考慮排樣整齊度，導(dǎo)致排樣出來(lái)的母板上各子板PCB邊界參差不齊，特別是在進(jìn)行排樣時(shí)完全采用貪婪策略來(lái)放置PCB，會(huì)導(dǎo)致越往后排樣效果越差［13］。為解決該問(wèn)題，在最低水平線算法的基礎(chǔ)上引入微差高度概念，同時(shí)進(jìn)行了垂直方向和水平方向上的邊界規(guī)整，在一定程度上解決了子板邊界整齊度問(wèn)題。

2.1 傳統(tǒng)最低水平線算法

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

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

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

2.2 基于邊界規(guī)整的矩形PCB排樣算法

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

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

圖1 本文改進(jìn)算法的水平線高度規(guī)整過(guò)程

當(dāng)最低水平線上放置子板PCB后，需要對(duì)當(dāng)前水平線按照式（2）進(jìn)行高度微差調(diào)整，即時(shí)對(duì)相鄰水平線且高度滿(mǎn)足微差高度條件的水平線進(jìn)行合并。

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

為了解決子板的水平邊界對(duì)齊問(wèn)題，可以在水平線無(wú)法放置子板PCB時(shí)進(jìn)行水平線的寬度規(guī)整，在最低水平線更新時(shí)不進(jìn)行直接提升，而是采用寬度對(duì)齊的方式來(lái)進(jìn)行提升，如圖2中所示。

圖2 本文改進(jìn)算法的水平線寬度規(guī)整過(guò)程

最低水平線更新時(shí)按照式（3）對(duì)當(dāng)前最低水平線進(jìn)行更新。

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

3 算法目標(biāo)函數(shù)及其優(yōu)化

由于待排PCB 的初始序列S0和微差高度對(duì)齊閾值Hset很難根據(jù)經(jīng)驗(yàn)進(jìn)行設(shè)置，為了進(jìn)一步提高基于邊界規(guī)整的矩形PCB排樣算法的排樣效果，可以先對(duì)子板類(lèi)聚度、規(guī)整率和利用率的表征，然后構(gòu)造出目標(biāo)函數(shù)，使用優(yōu)化算法對(duì)初始序列S0和微差高度對(duì)齊閾值Hset在可行解中進(jìn)行搜索，從而對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，達(dá)到進(jìn)一步提高排樣效果的目的。

3.1 子板類(lèi)聚度、規(guī)整率和利用率的表征

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

式中，KD為表征對(duì)象的類(lèi)聚度，SObj為表征對(duì)象的總面積，SMER為最小外接矩形面積。

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

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

子板規(guī)整率用來(lái)表征母板上子板PCB 的邊界規(guī)整程度，規(guī)整率越高，說(shuō)明各個(gè)PCB 之間的邊界越整齊。為了準(zhǔn)確表征子板的規(guī)整率，本文提出使用橫縱坐標(biāo)重復(fù)個(gè)數(shù)占比作為子板規(guī)整率，其定義式如式（6）所示。

式中，RR為子板規(guī)整率；RNx為排樣后所有子板PCB 的橫坐標(biāo)重復(fù)個(gè)數(shù)；RNy為排樣后所有子板PCB 的縱坐標(biāo)重復(fù)個(gè)數(shù)；規(guī)定只有重復(fù)次數(shù)大于1的坐標(biāo)進(jìn)行累計(jì)。

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

式中，MUR為板材利用率；N為母板上子板PCB的總個(gè)數(shù)；ws為第s塊子板PCB 的寬度；ls為第s塊子板PCB的長(zhǎng)度；W為母板的寬度；L為母板的長(zhǎng)度。

本文算法將子板類(lèi)聚度、規(guī)整率和板材利用率三者進(jìn)行加權(quán)，構(gòu)造出優(yōu)化算法的目標(biāo)函數(shù)，如式（8）所示。

式中，DF為優(yōu)化算法的目標(biāo)函數(shù)，α為類(lèi)聚度的加權(quán)系數(shù)，β為規(guī)整率的加權(quán)系數(shù)，γ為板材利用率的加權(quán)系數(shù)。

3.2 算法目標(biāo)函數(shù)的優(yōu)化模型

算法在多數(shù)情況下可以提高算法的板材利用率、各子板邊界規(guī)整和類(lèi)聚度，但是其排樣的方案并不是最優(yōu)解，為了進(jìn)一步提高排樣效果，本文使用差分進(jìn)化算法［16］來(lái)對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，使用差分進(jìn)化算法來(lái)優(yōu)化PCB的排樣模型如圖3所示。

圖3 差分進(jìn)化算法的PCB排樣優(yōu)化模型

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

圖4 序列的兩點(diǎn)互換編碼

為了設(shè)置合適的高度規(guī)整閾值Hset，需將該閾值也進(jìn)行編碼。Hset是一個(gè)在區(qū)間[0,min{wPi/2,lPi/2}],i=1,2…N的整數(shù)，式中wPi為第i塊PCB的寬度，lPi為第i塊PCB長(zhǎng)度。這樣就得到了維度為3 的目標(biāo)向量X=(i,j,Hset)，此向量作為最低水平線PCB 排樣算法的輸入?yún)?shù)。在上述PCB 排樣算法的目標(biāo)函數(shù)基礎(chǔ)上，可以給出如下的優(yōu)化模型：

式中，DF為目標(biāo)函數(shù)。W為母板的寬度。L為母板的長(zhǎng)度。α為板材利用率的加權(quán)系數(shù)。β為子板平均類(lèi)聚度的加權(quán)系數(shù)。γ為子板規(guī)整率的加權(quán)系數(shù)。N為母板上子板PCB 的總個(gè)數(shù)。n為母板上子板PCB 的種類(lèi)總數(shù)。mi為母板上第i類(lèi)子板PCB 的總個(gè)數(shù)。為母板上第i類(lèi)PCB 的最小外接矩形面積。RNx為排樣后所有子板PCB的橫坐標(biāo)重復(fù)個(gè)數(shù)。RNy為排樣后所有子板PCB的縱坐標(biāo)重復(fù)個(gè)數(shù)。wmin為待排PCB 所有子板中的最小寬度。lmin為待排PCB 所有子板中的最小長(zhǎng)度。

3.3 具體計(jì)算步驟

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

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

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

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

步驟5：對(duì)當(dāng)前水平線按照式（2）進(jìn)行垂直高度規(guī)整；

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

步驟7：計(jì)算種群個(gè)體的PCB 排樣的目標(biāo)函數(shù)DFi,i=1,2,…,NP；

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

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

4 算法仿真分析

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

表1 三組PCB測(cè)試算例

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

表2 三組算例的PCB排樣結(jié)果對(duì)比

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

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

5 結(jié)語(yǔ)

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