基于改進蟻群算法的PCB孔加工路徑優化

王捷晨 路林吉

(上海交通大學電子信息與電氣工程學院)

基于改進蟻群算法的PCB孔加工路徑優化

王捷晨 路林吉

(上海交通大學電子信息與電氣工程學院)

針對于印制電路板(PCB)孔加工過程中刀具的路徑規劃問題，提出了一種改進的蟻群算法，使信息素濃度可以更好地反映路徑信息，解決了經典蟻群算法易收斂到局部最優解的問題。仿真實驗結果表明：改進算法不僅增強了對于解空間的搜索能力，而且提高了搜索到全局最優解的概率。

蟻群算法 孔加工 路徑優化 信息素

近幾年隨著越來越多的手持電子設備和工業自動化的蓬勃發展,印制電路板(PCB)得到了廣泛的應用。而PCB的加工過程中必然少不了鉆孔加工環節。鉆孔加工一般是用不同尺寸的刀具對PCB打孔。Merchant的調查顯示，刀具和工件的運動在加工過程中占用總加工時間的70%[1]。因此，對刀具的打孔路徑進行有效規劃，就能提高打孔效率，進而提高生成效率。

長期以來人們一直在研究路徑規劃問題的解決方法。大部分傳統算法都存在算法復雜度太高的問題，當孔個數較多時，問題就得不到良好的解決，這使得傳統算法難以應用在實際生產過程當中。而最近出現的一些人工智能算法，給路徑規劃問題的求解帶來了新的希望。蟻群算法作為一種獨特的模擬自然界中螞蟻集群智能的仿生算法，與傳統優化方法相比具有魯棒性強、分布性廣、無須依賴具體問題及算法時間復雜度較低等優點，使蟻群算法擁有了廣闊的應用領域。筆者在傳統的經典蟻群算法的基礎上提出了一些改進意見，以便于更好地解決PCB打孔路徑規劃問題。

1 問題描述與蟻群算法的原理

1.1 問題描述

在對PCB進行打孔加工時，加工過程可描述為：對某一類給定尺寸的孔徑，數控鉆銑床換上對應尺寸的刀具后，從第1個孔開始加工，沿著程序給定的路徑對剩下的孔依次進行加工，直到PCB上所有該尺寸的孔都被加工完畢，如此循環,直到所有孔徑的過孔都被加工完畢[2]。通過上述對問題的闡述，筆者把PCB孔加工問題總結為如下數學模型：

a. 變量說明。設有n個孔的集合V={v1,v2, …,vn}，dij表示任意兩個待鉆孔vi、vj之間的直線距離。

b. 約束條件。刀具遍歷所有該尺寸孔對象，并且每個孔對象只被遍歷一次，加工完所有孔之后再回到起點換刀具繼續加工。

1.2 蟻群算法的原理

蟻群算法是意大利學者Colorni A 等于1991年提出的一種智能搜索優化算法[3]，該算法的提出主要是受到了自然界中螞蟻覓食行為的啟發。

蟻群算法基本模型的變量可以表述如下：給定N節點有向圖，m只螞蟻，用變量dij(i、j=1,2, …，N)表示節點i和節點j之間的距離，τij(t)表示第t次迭代邊(i,j)上的信息素濃度。

經典蟻群算法的主要實現步驟如下[4]：

a. 信息素初始化。將m只螞蟻隨機分配在節點當中并且初始化信息素濃度。在初始化信息素濃度時，各邊上的信息素濃度相同，即τij(0)=c(c為常數)。

2 改進蟻群算法

經過1.2節對經典蟻群算法原理的描述可發現，蟻群算法具有良好的魯棒性，但是也存在搜索易出現停滯的問題，算法收斂于次優解，即使增加最大迭代次數也不能搜索到最優解。這個問題的產生主要是由算法對信息素濃度的更新不能準確反映路徑信息引起的[5]，如果信息素濃度能夠完全反映出路徑信息，最終算法將收斂到全局最優解。所以問題的核心就是信息素濃度的設置和更新。筆者針對此問題進行了優化，使信息素濃度能更為客觀地反映出路徑信息。

2.1 信息素初始化改進

在經典蟻群算法中，初始化信息素濃度時，各個邊上的信息素濃度相等，為定值。這樣設置會導致算法積累啟發因子影響相同，蟻群算法在開始搜索路徑時沒有目的性，產生大量的無關路徑，導致算法開始時信息素濃度更新混亂。而這些混亂的信息素濃度最終會影響以后迭代的搜索，且容易使算法陷入局部最優解[6]。為了解決這個問題，筆者提出的改進蟻群算法在初始化信息素濃度時利用路徑信息，加入方向引導，使蟻群算法剛開始進行搜索時就能夠找到比較好的路徑，路徑初始化信息素濃度公式修改為：

τij(0)=Q/(dSj+djE)

(1)

其中dSj和djE分別為節點j到起點S與終點E的直線距離(終點E設置為距離起點S最近的節點)；Q為給定參數，是每只螞蟻每次遍歷時的總信息素濃度。由式(1)可知，當節點j越趨向于連線SE時，τij(0)越大，螞蟻就傾向于選擇該點作為自己的目的節點。這樣就抑制了對無關路徑的搜索，避免了信息素初始化時的無目的性。

2.2 信息素局部更新規則的改進

信息素局部更新指的是對完成遍歷全部節點的螞蟻經過路徑上進行信息素濃度的增強。然而單只螞蟻的遍歷很容易出現偏差，這使得偏差路徑上的信息素濃度增強，使得路徑上信息素濃度混亂。針對于上述問題，筆者提出一種局部信息素濃度更新方法。對于第(k+1)只螞蟻局部信息素濃度的更新，不僅僅考慮第(k+1)只螞蟻的路徑，也把前k只螞蟻的路徑考慮進來，更新規則為：

(2)

從式(2)中可以看出，筆者將前k只螞蟻的信息素濃度進行了揮發，并與第(k+1)只螞蟻的信息素濃度進行了加權求平均，重新分配，減弱了單只螞蟻的無關路徑對搜索全局最優路徑的影響。

2.3 信息素全局更新規則的改進

經典蟻群算法全局更新規則對單次迭代中最短路徑上的信息素濃度進行增強。然而，單次迭代得到的路徑有好有差，對于較差路徑上信息素濃度的增強容易讓算法收斂于次優解。另一方面，單次迭代最優解路徑往往與全局最優路徑有較大的關系，應該充分利用單次迭代的路徑信息[7]。

筆者在全局信息素更新規則中引入自適應動態因子σ(σ∈(0，1))，以自適應地調整較好解和較差解對信息素濃度更新的影響，更新規則為：

τij(t+1)=τij(t)+μσΔτij

(3)

由sigmoid函數式可知，當前迭代搜索到的最優路徑越長，動態因子σ就越接近于0，減小了較差路徑對于信息素濃度的影響；而當前迭代搜索到的路徑越短，動態因子σ就越接近于1，增強了較好路徑對于信息素濃度的影響。所以當采用sigmoid函數對單次迭代的最優路徑進行信息素濃度自適應更新后，算法不會很快收斂于局部最優解，保留了解空間的多樣性。

3 算法仿真與分析

針對筆者提出的改進蟻群算法(I-ACS)、經典蟻群算法(ACS)、最大最小蟻群算法(MMAS)和文獻[8]提出的蟻群算法，筆者先仿真一塊PCB采用不同蟻群算法進行路徑優化，再對打孔數不同的PCB板采用不同算法進行路徑優化，來對比不同蟻群算法的計算結果和性能。圖1所示為一塊待打孔的PCB，圖1a中空心圓標記的是需要用加工的過孔，總共有51個。圖1b為已證明的最短路徑，且最短路徑長度Lbest=423.9005。

a. PCB待加工過孔

b. PCB過孔加工最優路徑

筆者把各個蟻群算法的迭代次數都設置為100次，對算法的結果和性能進行對比。筆者提出的改進蟻群算法(I-ACS)的實驗參數見表1。

表1 改進蟻群算法(I-ACS)的實驗參數

在重復實驗30次的情況下，實驗仿真了各個蟻群算法，根據30次實驗最優路徑的分布繪制出了圖2。由圖2可知，經典蟻群算法和最大最小蟻群算法搜索到的路徑長度主要集中在較差路徑(440～470)之間，文獻[8]中提到的改進蟻群算法得到的最優路徑結果有所提高，但仍然集中在次優路徑，而筆者提出的I-ACS算法搜索到的路徑結果則主要集中在最優路徑附近。

圖2 各算法30次實驗結果分布

其次對各個算法的收斂性進行仿真分析。在30次重復實驗當中，選擇了搜索到最優路徑的那次實驗進行了收斂性分析。各個蟻群算法均迭代了100次，筆者根據各個蟻群算法100次迭代的收斂結果，繪制了圖3。從圖3中可以看出，各個算法在到達最大迭代次數之前都收斂了，由于筆者提出的算法會利用路徑信息初始化信息素濃度，所以一開始就能找到較短的路徑，而且筆者提出的I-ACS算法在局部和全局信息素濃度更新時進行了改進，能持續搜索解空間，在迭代次數較高時才收斂，增加了找到最優解的概率。

圖3 各算法收斂性對比

最后，針對不同個數的節點對各個算法進行了重復30次的仿真實驗。在仿真實驗中，分別仿真了30、50、70、90個節點的PCB來進行各個蟻群算法的性能對比，對比結果見表2、3。

表2 最優占比統計結果 %

表3 平均迭代次數統計結果

表2中的最優占比，指的是在30次重復實驗中，各個算法的結果當中與最優結果距離不超過10的實驗次數所占的百分比，占比越高，說明算法的結果越好，越容易找到最優解。

表3中的平均迭代次數指的是平均經過多少次的迭代后算法收斂于局部最優解，反映的是算法對解空間的搜索能力，平均迭代次數越大，說明算法越不容易收斂于局部最優解，對解空間的搜索能力越強，有更大概率搜索到全局最優解。

從表2、3中可以看出，筆者提出的改進蟻群算法對解空間的搜索能力較強，而且也有較大概率搜索到最優解，相對于其他算法具有一定的優勢。

4 結束語

主要解決了PCB打孔加工過程中刀具走刀的路徑規劃問題。首先對走刀的路徑規劃問題進行了數學描述，接著對經典蟻群算法提出了一些改進意見，來避免經典蟻群算法過早收斂于局部最優解。改進的核心是使信息素濃度盡可能客觀地反映出路徑信息?；谶@一原則，筆者提出了3個方面的改進，一是在初始化信息素濃度時引入方向信息，減少了無關路徑對搜索最優路徑的影響；二是在信息素濃度局部更新的過程中利用先前螞蟻的信息素濃度進行加權平均，使算法不因為個別螞蟻的偏差路徑誤入歧途；三是在信息素濃度全局更新過程中，利用sigmoid函數自適應地調整每次迭代路徑上的信息素濃度更新，增強較短路徑影響力，抑制較差路徑影響力。最后的算法仿真結果表明筆者提出的改進蟻群算法對解空間的搜索能力更強大，有更大的概率找到最優解。

[1] 周琨,邵華.基于Hopfield算法的孔群加工路徑規劃[J].模具技術,2003, 21(1): 48～50．

[2] 邢啟明.基于最短路徑算法的PCB板插接優化[J].江蘇科技信息,2014，(16):31～34.

[3] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[C]. Proceedings of the First European Conference on Artificial Life. Paris: Elsevier Publishing,1991:134～142.

[4] Gambardella L M, Dorigo M. Solving Symmetric and Asymmetric TSPs by Colonies[C]. Proceedings of the IEEE Conference on Evolutionary Computation. Piscataway,NJ:IEEE，1996: 622～627.

[5] 袁亞博,劉羿,吳斌.改進蟻群算法求解最短路徑問題[J].計算機應用與工程,2016，52(6):8～12.

[6] 鄭衛國,田其沖,張磊.基于信息素強度的改進蟻群算法[J].計算機仿真,2010，27(7):191～193.

[7] 張學敏,張航.基于改進蟻群算法的最短路徑問題研究[J].自動化技術與應用,2009，28(6):4～7.

[8] 何小虎.基于改進蟻群算法在糧食物流配送路徑優化的應用研究[J].電子設計工程, 2016，24(9):39～41.

PCBDrillingPathOptimizationBasedonImprovedAntColonyAlgorithm

WANG Jie-chen, LU Lin-ji

(School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University)

As for the tool’s path planning in the PCB drilling process, an improved ant colony algorithm was proposed to make pheromone concentration reflect the path information better and to solve the problem that the classic ant colony algorithm is easy to fall into local optimal solution. The simulation results show that the improved algorithm not only strengthens the ability to search solution space, but also increases the probability of finding the global optimal solution.

ant colony algorithm, drilling manufacturing, path optimization, pheromone

TP14

A

1000-3932(2017)05-0434-05

王捷晨(1991-)，碩士研究生，從事數字圖像處理、PCB自動布線、PCB打孔機路徑規劃的研究。

聯系人路林吉(1965-)，副教授，從事工業自動化軟硬件設計、數字圖像處理、機器人技術及應用的研究，lulinji2002@163.com。

2016-11-21，

2017-03-15)