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

張洪雨，葉艷，楊小燕

（成都理工大學(xué)管理科學(xué)學(xué)院，成都610059）

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

張洪雨，葉艷，楊小燕

（成都理工大學(xué)管理科學(xué)學(xué)院，成都610059）

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

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

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

1 電路板走刀問題中的數(shù)學(xué)規(guī)則模型

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

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

這樣就很好地用數(shù)學(xué)表達(dá)式描述了電路板走刀問題的約束條件和最終的目標(biāo)函數(shù)，建立了電路板走刀問題的數(shù)學(xué)模型。

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

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

為了產(chǎn)生明顯的對(duì)比，本文給出一個(gè)隨機(jī)狀態(tài)下的路徑圖，如圖1所示［3］。顯然這是一個(gè)十分混亂的路徑，在實(shí)際生產(chǎn)中就會(huì)影響生產(chǎn)效率，對(duì)于大批量生產(chǎn)電路板的廠家來說，對(duì)成本的影響會(huì)相當(dāng)顯著，很有必要找個(gè)最優(yōu)的走刀路徑來解決這個(gè)問題。

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

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

設(shè)初始圈C=v1v2…vnv1。對(duì)于1≤i＜i+1＜j≤n，構(gòu)造新的哈密頓圈Cij=v1v2…vivjvj-1…vi+1vj+1vj+2…vnv1，新構(gòu)造的這個(gè)哈密頓圈是由初始圈C刪去邊vivi+1和vjvj+1、添加邊vivj和vi+1vj+1得到，若d（vivj）+ d（vi+1vj+1）＜d（vivi+1）+d（vjvj+1），用Cij代替C，成為C圈的改良圈。重復(fù)這一操作直到無法改進(jìn)。用matlab編程對(duì)上述描述進(jìn)行實(shí)現(xiàn)，得到的最優(yōu)路徑為4.5443，編號(hào)排序∶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。由此可得到哈密頓最優(yōu)路徑圖（圖2）。

哈密頓圖在最小路徑中應(yīng)用的時(shí)候，是利用局部最優(yōu)，然后逐步到全局最優(yōu)，對(duì)于比較大的數(shù)據(jù)量，很難求得全局最優(yōu)解。選擇不同的初始哈密頓圈，通過實(shí)驗(yàn)得到了不同的結(jié)果。把哈密頓算法的思路引入到模擬退火過程中，就可以得到模擬退火解決這個(gè)問題的方法。

2.2 模擬退火算法

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

模擬退火原理∶模擬退火算法源于統(tǒng)計(jì)物理學(xué)，據(jù)統(tǒng)計(jì)熱力學(xué)，物理中的每個(gè)分子的狀態(tài)服從Gibbs分布，即∶

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

算法源于對(duì)實(shí)際固體退火過程的模擬，即先將固體加溫至充分高，再逐漸冷卻。加溫時(shí)，固體內(nèi)部粒子變?yōu)闊o序狀態(tài)，內(nèi)能增大；而逐漸降溫時(shí)，粒子趨于有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。因此，算法實(shí)際上是將優(yōu)化問題類比為退火過程中能量的最低狀態(tài)，也就是溫度達(dá)到最低點(diǎn)時(shí)，概率分布中具有最大概率的狀態(tài)［6］。

2.2.1模擬退火步驟與實(shí)現(xiàn)

假設(shè)材料在狀態(tài)i之下能量為E（i），那么材料在溫度T時(shí)狀態(tài)從i進(jìn)入狀態(tài)j遵循這樣的規(guī)律∶

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

模擬退火過程為∶

（1）如果▽E≤0，則新狀態(tài)j被接受；

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

2.2.2模擬退火算法過程描述

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

（2）目標(biāo)函數(shù)∶

（3）新解產(chǎn)生∶

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

Δf=（dvu-1vw

+dvuvw+1）-（dvu-1vu

+dvwvw+1）

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

（5）降溫∶利用降溫系數(shù)k進(jìn)行降溫，每次取T=kT作為新的溫度，k＜1，這里k越接近1降溫越緩慢，效果越好，但是耗時(shí)會(huì)較長(zhǎng)。

（6）結(jié)束條件∶選定一個(gè)終止的溫度e，這里e＞0，e越接近0所得的結(jié)果最優(yōu)。T＜e時(shí)結(jié)束過程，輸出此時(shí)的狀態(tài)［5］。

對(duì)于電路板最佳走刀問題，解空間分別對(duì)應(yīng)表1中的編號(hào)，通過兩點(diǎn)間的距離公式求得兩個(gè)孔之間的距離d，按照上述模擬退火過程通過matlab工具編程實(shí)現(xiàn)，得到最優(yōu)路徑長(zhǎng)度為4.1151，編號(hào)排列為∶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。最優(yōu)路徑如圖3所示。

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

3 算法分析

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

4 結(jié)束語

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

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

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

［3］苗連英'王萃琦.圖論及其算法［M］.徐州:中國(guó)礦業(yè)大學(xué)出版社'2012.

［4］司守奎'孫璽菁.數(shù)學(xué)建模算法與應(yīng)用［M］.北京:國(guó)防工業(yè)出版社'2011.

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

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

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

［8］郎茂祥.裝卸混合車輛路徑問題的模擬退火算法研究［J］.系統(tǒng)工程學(xué)報(bào)'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-），男，河北滄州人，碩士生，主要從事數(shù)學(xué)地質(zhì)方面的研究，（E-mail）zhanghongyu_198827@126.com