茍輝　周玉婷　汪忠林

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

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

中圖分類號(hào)：TP32 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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）制作效率的要求，對(duì)印制電路板的制作工藝提出了新的挑戰(zhàn)[1-2]。在改善印制電路板生產(chǎn)效率中，孔群的加工尤為重要，它所需要的加工時(shí)間主要包含孔的加工時(shí)間和刀具換位、更換刀具等輔助時(shí)間。其中，刀具換位的運(yùn)動(dòng)時(shí)間占孔群加工的70%[3]。因此，為減少PCB孔群加工過(guò)程中刀具換位時(shí)間與提升PCB制作效率，本文將展開(kāi)基于模擬退火算法的孔群加工路徑優(yōu)化方案設(shè)計(jì)。

1 模擬退火算法

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

Metropolis算法又名Metropolis抽樣，它是構(gòu)成模擬退火算法的基礎(chǔ)。使用模擬退火算法時(shí)，必須確定初始溫度，Metropolis的鏈長(zhǎng)S，降溫速率v和結(jié)束溫度Tend。假設(shè)初始解是X，擾動(dòng)系統(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]接受新解，直至完成迭代。然后檢測(cè)是否滿足終止條件，若不滿足則降低溫度重新進(jìn)行求解，直至滿足結(jié)束條件，終止算法。

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

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

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

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

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

（4） 擾動(dòng)生成新解：本文利用三變換法對(duì)初始解X1進(jìn)行擾動(dòng)產(chǎn)生新的路徑排序，即是新的可行解X2。三變換法：任選序號(hào)u，v和ω（u≤vω），將u和v之間的路徑插到ω之后訪問(wèn)，若交換前的解為[Xi=（a1，a2，...，au，...，av，...，aω，...，an）]，因此交換后的新路徑為：[Xi`=（a1，...，au-1，...，av+1，...，aω，au，...，av，aω+1，...，an）]。例如， PCB 板上有8個(gè)孔。產(chǎn)生三個(gè)[1，8] 區(qū)間內(nèi)的隨機(jī)整數(shù)r1、r2和r3，確定三個(gè)位置，如 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)則：如果加工路徑總長(zhǎng)度的函數(shù)為f（X），則當(dāng)前解的路徑長(zhǎng)度為f（X），新解的路徑長(zhǎng)度為 f（X`），路徑長(zhǎng)度差為[Δ]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)位置，確定孔群位置信息時(shí)始終將原點(diǎn)位置的序號(hào)定為1。如果通過(guò)模擬退火算法優(yōu)化出來(lái)的路徑編號(hào)序列為： 8 5 7 2 4 8 3 6 1 8，則需要將其轉(zhuǎn)換為從編號(hào) 1 開(kāi)始的路徑為： 1 8 5 7 2 4 8 3 6 1。

3 基于matlab的仿真實(shí)驗(yàn)

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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