基于模擬退火算法的PCB孔群加工路徑優(yōu)化

茍輝　周玉婷　汪忠林

摘要：為改善印制電路板孔群的加工質(zhì)量與效率，該文采用模擬退火算法對孔群的加工路徑進(jìn)行了優(yōu)化。文中通過PCB孔群實例詳細(xì)描述了模擬退火算法的實現(xiàn)過程，結(jié)果表明，利用模擬退火算法可有效提升PCB孔群加工效率以及質(zhì)量，降低孔群加工中的空行程比例。

關(guān)鍵詞：模擬退火算法；路徑優(yōu)化；PCB孔群

中圖分類號：TP32 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）27-0247-02

Optimization of PCB Path Processing Based on Simulated Annealing Algorithm

GOU Hui， ZHOU Yu-ting， WANG Zhong-lin

（Computing Technique Research Institute， Aviation Industry Corporation of China， Xi'an 710068， China）

Abstract： In order to improve the processing quality and efficiency of the hole group of the printed circuit board， the simulated annealing algorithm was used to optimize the processing path of the hole group. In this paper， the implementation of simulated annealing algorithm is described in detail through examples， and the results show that the use of simulated annealing algorithm can effectively improve the processing efficiency and quality of PCB clusters， and reduce the empty stroke ratio in cluster machining.

Key words： simulated annealing algorithm； path Optimization； PCB cluster

21世紀(jì)伊始，伴隨著電子電路技術(shù)的飛速發(fā)展、提升電子類儀器集成度以及印制電路板（PCB）制作效率的要求，對印制電路板的制作工藝提出了新的挑戰(zhàn)[1-2]。在改善印制電路板生產(chǎn)效率中，孔群的加工尤為重要，它所需要的加工時間主要包含孔的加工時間和刀具換位、更換刀具等輔助時間。其中，刀具換位的運(yùn)動時間占孔群加工的70%[3]。因此，為減少PCB孔群加工過程中刀具換位時間與提升PCB制作效率，本文將展開基于模擬退火算法的孔群加工路徑優(yōu)化方案設(shè)計。

1 模擬退火算法

模擬退火算法是一種十分常用的優(yōu)化算法，它的設(shè)計思想主要是參考固體物質(zhì)的退火過程。假如固體的溫度過高，將會因其內(nèi)能較大而使物質(zhì)內(nèi)部粒子處于快速無序運(yùn)動狀態(tài)；隨著溫度降低，內(nèi)能將不斷減小，繼而使粒子運(yùn)動逐漸趨于有序狀態(tài)。然后，當(dāng)物質(zhì)處于常溫時，內(nèi)能最小，粒子的運(yùn)動狀態(tài)也最為穩(wěn)定。模擬退火算法的設(shè)計流程如圖1所示。

Metropolis算法又名Metropolis抽樣，它是構(gòu)成模擬退火算法的基礎(chǔ)。使用模擬退火算法時，必須確定初始溫度，Metropolis的鏈長S，降溫速率v和結(jié)束溫度Tend。假設(shè)初始解是X，擾動系統(tǒng)，產(chǎn)生新的解X`；相應(yīng)的，解的函數(shù)由f（X）變?yōu)閒（X`）。如果f（X`）小于等于f（X），則系統(tǒng)接受新解；否則以概率[exp-f（X`）-f（X）T]接受新解，直至完成迭代。然后檢測是否滿足終止條件，若不滿足則降低溫度重新進(jìn)行求解，直至滿足結(jié)束條件，終止算法。

2 路徑優(yōu)化算法設(shè)計

結(jié)合上文中有關(guān)模擬退火算法的設(shè)計流程可將PCB孔群加工路徑優(yōu)化步驟分為以下幾個部分：

（1） 編號：首先，采用自然數(shù)序列對印制電路板需待加工孔的坐標(biāo)位置進(jìn)行編號，假設(shè)有8個小孔，因此它們的編號為{1，2，3，4，5，6，7，8 }。

（2） 設(shè)置算法控制參數(shù)：影響模擬退火算法實現(xiàn)過程的主要參數(shù)有：降溫速率v、初始溫度 Tstart、結(jié)束溫度 Tend 以及 Metropolis 鏈長S。

（3） 初始解：本文通過產(chǎn)生隨機(jī)序列的方式產(chǎn)生模擬退火算法需要的初始解X1，假若是對包含8個孔的印制電路板進(jìn)行加工路徑優(yōu)化，所產(chǎn)生的初始解就是對這些孔的排序，每個數(shù)字就是對應(yīng)孔的編號，即2|4|1|5|8|3|6|7就是一個合法解。

（4） 擾動生成新解：本文利用三變換法對初始解X1進(jìn)行擾動產(chǎn)生新的路徑排序，即是新的可行解X2。三變換法：任選序號u，v和ω（u≤vω），將u和v之間的路徑插到ω之后訪問，若交換前的解為[Xi=（a1，a2，...，au，...，av，...，aω，...，an）]，因此交換后的新路徑為：[Xi`=（a1，...，au-1，...，av+1，...，aω，au，...，av，aω+1，...，an）]。例如， PCB 板上有8個孔。產(chǎn)生三個[1，8] 區(qū)間內(nèi)的隨機(jī)整數(shù)r1、r2和r3，確定三個位置，如 r1 = 2，r2 = 5，r3=7，則根據(jù)三變換法序列6 |3| 7 1 |4| 8 |2| 5變換后，得到的新解為6 8 |2| |3| 7 1 |4| 5。

（5） Metropolis準(zhǔn)則：如果加工路徑總長度的函數(shù)為f（X），則當(dāng)前解的路徑長度為f（X），新解的路徑長度為 f（X`），路徑長度差為[Δ]f（X`）-f（X） ，則 Metropolis 準(zhǔn)則為：

[P=1， Δf<0exp-ΔfT， Δf0]

如果[Δf]< 0，則以概率1接受新的路徑解；否則以概率 exp（ -[Δf/T]） 接受新的路徑解。

（6） 降溫：利用降溫速率v進(jìn)行降溫，即T`= vT，若T`

（7） 加工路徑優(yōu)化：把鉆孔機(jī)鉆頭初始化位置當(dāng)作原點(diǎn)位置，確定孔群位置信息時始終將原點(diǎn)位置的序號定為1。如果通過模擬退火算法優(yōu)化出來的路徑編號序列為： 8 5 7 2 4 8 3 6 1 8，則需要將其轉(zhuǎn)換為從編號 1 開始的路徑為： 1 8 5 7 2 4 8 3 6 1。

3 基于matlab的仿真實驗

實驗平臺為64位Win8操作系統(tǒng)，matlab r2014a版本和繪制電路原理圖軟件Altium Designer13。本次實驗通過利用模擬退火算法對一個實例進(jìn)行路徑優(yōu)化設(shè)計以驗證算法的有效性與可行性。利用AD設(shè)計一塊49.28mm*49.40mm大小的印制電路板，如圖2所示。以左下角作為坐標(biāo)原點(diǎn)，測量各小孔相對于原點(diǎn)的位置信息，并將其作為孔的坐標(biāo)。然后將坐標(biāo)輸入至模擬退火算法中對孔群的加工路徑進(jìn)行優(yōu)化。

結(jié)合模擬退火算法的設(shè)計思想以及文獻(xiàn)資料，本文設(shè)計的基于模擬退火算法的matlab程序中各參數(shù)如下：加工孔群數(shù)目為38再加上坐標(biāo)原點(diǎn)，因此退火算法中的城市數(shù)目為39；初始溫度Tstart為97℃，降溫速率為0.99℃/代，結(jié)束溫度Tend為3℃，鏈長S為10000mm。

將孔群中小孔的坐標(biāo)矩陣代入模擬退火算法進(jìn)行優(yōu)化，可得優(yōu)化前的一個隨機(jī)加工路徑如圖3所示，該加工路徑長度為965.2156mm。

4 結(jié)論

通過本次仿真實驗結(jié)果可以得出：模擬退火算法可有效對PCB孔群的加工路徑進(jìn)行優(yōu)化，總距離由優(yōu)化前的965.2156mm變?yōu)?35.8965mm，縮短為原來的24.40%。并且通過多次實驗發(fā)現(xiàn)退火算法參數(shù)對優(yōu)化過程有較大的影響，接下來將著重研究具體參數(shù)對優(yōu)化結(jié)果的影響，以獲得最佳參數(shù)的范圍。根據(jù)實驗結(jié)果可以看出，模擬退火算法能夠有效優(yōu)化加工路徑，為提升PCB孔群加工效率提供了可行的設(shè)計方案。

參考文獻(xiàn)：

[1] 顏國霖.基于TSP的孔群加工路徑優(yōu)化算法[J].延邊大學(xué)學(xué)報：自然科學(xué)版，2014，40（4）：370-374.

[2] 肖人彬，陶振武.孔群加工路徑規(guī)劃問題的進(jìn)化求解[J].計算機(jī)集成制造系統(tǒng)，2005（5）：725-732.

[3] 楊婷，賈朝川.基于模擬退火算法的PCB鉆孔機(jī)空行路徑優(yōu)化[J].蚌埠學(xué)院學(xué)報，2016，5（5）：6-9.

[通聯(lián)編輯：代影]