模擬退火在印刷電路板最佳走刀問題中的應用

張洪雨，葉艷，楊小燕

（成都理工大學管理科學學院，成都610059）

模擬退火在印刷電路板最佳走刀問題中的應用

張洪雨，葉艷，楊小燕

（成都理工大學管理科學學院，成都610059）

電路板（PCB）走刀路線問題可以歸結為大型TSP問題。在構造了電路板走刀路線問題的模型后，采用加權的哈密頓圖方法，結合模擬退火策略對該問題進行分析求解。重點介紹了模擬退火解決這個問題的具體算法和過程。仿真試驗結果表明:采用模擬退火算法求解TSP問題效果更好，與有關算法相比有更好的可操作性。

印刷電路板；哈密頓圈；蒙特卡洛方法；模擬退火

關于印刷電路板走刀問題，當前，國內外廣泛采用CAD軟件來設計PCB。通過這種軟件生成的鉆孔數控文件經自動編程處理生成NC指令以供PCB專用數控鉆床進行加工。現有的自動編程軟件采用按孔位的XY坐標以某種約定的逐次編排方法確定鉆孔走刀順序，這樣生成的鉆孔走刀路線顯然并非最佳路線，對于大批量生產規模的專用生產來說其影響生產效率相當可觀，足見其整體過程優化的重要性。本文通過綜合分析，建立了最佳走刀路線模型，運用模擬退火算法，較好地解決了這一問題［1］。

1 電路板走刀問題中的數學規則模型

電路板通常是由許多不同直徑的孔，對某一確定的孔徑構成的孔系來說，PCB問題可以描述為∶從換刀點出發既不重復又不遺漏地加工完所有的孔再回到換刀點。所謂最佳走刀問題，就是如何安排孔的加工順序使空程移動距離最短。該問題很顯然可以歸結為著名的旅行商問題（TSP），其中鉆頭扮演了旅行商人的角色，而目標函數就是刀具行程最短的路線［2］。

對電路板問題，首先要建立一個數學規則模型∶設電路板鉆孔的個數為n，dij是兩個鉆孔i和j之間的距離，xij=0或1（1表示兩個鉆孔連通，0表示沒有連通）。則有目標函數min∑i≠jdijxij使得∶

這樣就很好地用數學表達式描述了電路板走刀問題的約束條件和最終的目標函數，建立了電路板走刀問題的數學模型。

2 電路板走刀問題的求解方法

本文分別用哈密頓通路和模擬退火兩種算法對印刷電路板的鉆孔問題進行優化處理，鉆孔在平面上的坐標位置見表1。

為了產生明顯的對比，本文給出一個隨機狀態下的路徑圖，如圖1所示［3］。顯然這是一個十分混亂的路徑，在實際生產中就會影響生產效率，對于大批量生產電路板的廠家來說，對成本的影響會相當顯著，很有必要找個最優的走刀路徑來解決這個問題。

2.1 哈密頓通路算法解決電路板走刀問題

哈密頓通路就是通過圖的每個結點一次，且僅一次的通路，就是哈密頓通路。上述問題實際上就是在賦權的哈密頓圖中找到一個最小權的哈密頓圈。對于上述問題的一個有效辦法是先求一個哈密頓圈C，然后修改C以得到較小權的另一個哈密頓圈。這叫做改良圈算法［5］，其一般思路如下∶

設初始圈C=v1v2…vnv1。對于1≤i＜i+1＜j≤n，構造新的哈密頓圈Cij=v1v2…vivjvj-1…vi+1vj+1vj+2…vnv1，新構造的這個哈密頓圈是由初始圈C刪去邊vivi+1和vjvj+1、添加邊vivj和vi+1vj+1得到，若d（vivj）+ d（vi+1vj+1）＜d（vivi+1）+d（vjvj+1），用Cij代替C，成為C圈的改良圈。重復這一操作直到無法改進。用matlab編程對上述描述進行實現，得到的最優路徑為4.5443，編號排序∶1 3 30 2 4 5 18 19 29 27 28 26 24 25 23 21 22 20 16 17 15 6 11 9 13 14 12 10 8 7 1。由此可得到哈密頓最優路徑圖（圖2）。

哈密頓圖在最小路徑中應用的時候，是利用局部最優，然后逐步到全局最優，對于比較大的數據量，很難求得全局最優解。選擇不同的初始哈密頓圈，通過實驗得到了不同的結果。把哈密頓算法的思路引入到模擬退火過程中，就可以得到模擬退火解決這個問題的方法。

2.2 模擬退火算法

模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優的串行結構的優化算法，編寫程序相對簡單。目前此法已開始用于解決非線性地球物理反問題等領域，并取得了較好的效果。

模擬退火原理∶模擬退火算法源于統計物理學，據統計熱力學，物理中的每個分子的狀態服從Gibbs分布，即∶

式中∶E（ri）為第i個分子的能量函數；ri為第i個分子所處的狀態；k為玻爾茲曼常數，T表示溫度；ρ（ri）為第i個分子的概率密度。為了計算方便，令k=1。理論上可證明，它是一個全局最優算法，并且以概率1接近最優值。

算法源于對實際固體退火過程的模擬，即先將固體加溫至充分高，再逐漸冷卻。加溫時，固體內部粒子變為無序狀態，內能增大；而逐漸降溫時，粒子趨于有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。因此，算法實際上是將優化問題類比為退火過程中能量的最低狀態，也就是溫度達到最低點時，概率分布中具有最大概率的狀態［6］。

2.2.1模擬退火步驟與實現

假設材料在狀態i之下能量為E（i），那么材料在溫度T時狀態從i進入狀態j遵循這樣的規律∶

ΔE=E（j）-E（i）

模擬退火過程為∶

（1）如果▽E≤0，則新狀態j被接受；

（4）重復步驟（1）～（3），直到滿足條件為止［4］。

2.2.2模擬退火算法過程描述

（1）解空間S可表示為｛1，2，3…n，n+1｝的所有的固定起點和終點排列的集合，為了方面編程，把出發地定為編號1，最后回到出發地的編號定為n+1，即∶S=｛（v1，v2，v3…vn，vn+1）|v1，（v2，v3，…，vn）的循環排列，vn+1｝，其中vi=i。這樣始發地和終點分別確定，中間地點的編號用蒙特卡洛方法獲得。

（2）目標函數∶

（3）新解產生∶

由蒙特卡洛方法得到初始解，設為∶｛v1，…，vu-1，vu，vu+1，…，vw-1，vw，vw+1，…，vn+1｝任意選擇序號u，w，交換順序使之成為逆序∶｛v1，…，vu-1，vw，vw-1，…，vu+1，vu，vw+1，…，vn+1｝可以得到兩個路徑的距離差∶

Δf=（dvu-1vw

+dvuvw+1）-（dvu-1vu

+dvwvw+1）

但是，范文芳（2007）提出，語法隱喻的產生必然涉及與一致式不同的選擇，但并非不同的選擇就導致隱喻的產生。比如，[11a]是一致式，雖然[11b]和[11c]都選擇了不同的過程，卻只有[11c]是隱喻式。這也符合張德祿和趙靜（2008）提出的形似性原則④。可見，在形式變體的問題上，我們對不同的體現形式要作進一步的區分，并且參考形似性原則來判定一致式和隱喻式。形似性原則能為范文芳（2017）的判斷和類似問題提供直接、有效的依據。

（5）降溫∶利用降溫系數k進行降溫，每次取T=kT作為新的溫度，k＜1，這里k越接近1降溫越緩慢，效果越好，但是耗時會較長。

（6）結束條件∶選定一個終止的溫度e，這里e＞0，e越接近0所得的結果最優。T＜e時結束過程，輸出此時的狀態［5］。

對于電路板最佳走刀問題，解空間分別對應表1中的編號，通過兩點間的距離公式求得兩個孔之間的距離d，按照上述模擬退火過程通過matlab工具編程實現，得到最優路徑長度為4.1151，編號排列為∶1 3 30 2 4 5 8 10 13 12 14 19 18 29 27 23 21 25 28 26 24 22 20 16 17 15 6 11 9 7 31。最優路徑如圖3所示。

因此，利用模擬退火算法求解電路板走刀問題是可行有效的［6］。

3 算法分析

一般情況下，模擬退火算法采取的是隨機地選取坐標的方法，本文為了提高算法的執行效率，將原本隨機選取初始值的方式改為盡可能找出一個有用的初始值。實際中，可以結合哈密頓圖方法，先利用哈密頓圖方法求得一個相對好的結果，以此作為模擬退火算法中的初始路徑，這樣，既能保證得到一個最優結果，在時間上，求解過程也可以更快完成［7］。

4 結束語

本文將PCB數控鉆孔最佳走刀問題歸結為TSP問題，引入模擬退火算法對其求解。與其它算法相比較，模擬退火算法是一種描述簡單、使用靈活、較少受到初始條件約束的擬物型隨機近似算法。通過模擬退火算法，有效地解決了電路板走刀加工中刀具路徑冗長、空行程導致加工效率低的問題。在實際應用中，為了更好的應用模擬退火算法，可以預先搜尋最佳的冷卻溫度和升溫達到的最高溫度范圍，從而在保證良好結果的基礎上，獲得更好的時間效益［8］。

［1］莫愿斌'陳德釗'胡上序.動態規劃粒子群算法解PCB數控鉆孔最佳走刀路線問題［J］.機床與液壓' 2006(8）:18-21.

［2］王銀年'葛洪偉.求解TSP問題的改進模擬退火遺傳算法［J］.計算機工程與應用'2010'46(5）:44-47'85.

［3］苗連英'王萃琦.圖論及其算法［M］.徐州:中國礦業大學出版社'2012.

［4］司守奎'孫璽菁.數學建模算法與應用［M］.北京:國防工業出版社'2011.

［5］朱顥東'鐘勇.一種改進的模擬退火算法［J］.計算機技術與發展'2009'19(6）:32-35.

［6］張盛意'蔡之華'占志剛.基于改進模擬退火的遺傳算法求解0-1背包問題［J］.微電子學與計算機' 2011'28(2）:61-64.

［7］蔣龍聰'劉江平.模擬退火算法及其改進［J］.工程地球物理學報'2007'4(2）:135-140.

［8］郎茂祥.裝卸混合車輛路徑問題的模擬退火算法研究［J］.系統工程學報'2005'20(5）:485-491.

Application of Simulated Annealing in the Best Feeding Problems of Printed Circuit Board

ZHANG Hongyu，YE Yan，YANG Xiaoyan
（College of Management Science，Chengdu University of Technology，Chengdu 610059，China）

The feeding line problem of printed circuitboard（PCB）can be regarded as a large-scale TSP problem.After the circuit board feeding route problem model is constructed，the weighted Hamiltonian graph method and the simulated annealing strategy are used to analyze and resolve the problem.The concrete algorithms and process of simulated annealing in solving the problem aremainly introduced.The simulation results show that the simulated annealing algorithm performs better in solving TSP problem，and it has bettermaneuverability compared with other algorithms.

Printed circuit board；Hamiltonian cycle；Monte Carlomethod；simulated annealing

TN41

A

1673-1549（2014）01-0045-04

10.11863/j.suse.2014.01.12

2013-09-25

張洪雨（1988-），男，河北滄州人，碩士生，主要從事數學地質方面的研究，（E-mail）zhanghongyu_198827@126.com