基于改進蟻群算法的PCB孔加工路徑優(yōu)化

王捷晨 路林吉

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

基于改進蟻群算法的PCB孔加工路徑優(yōu)化

王捷晨 路林吉

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

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

蟻群算法 孔加工 路徑優(yōu)化 信息素

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

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

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

1.1 問題描述

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

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

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

1.2 蟻群算法的原理

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

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

經(jīng)典蟻群算法的主要實現(xiàn)步驟如下[4]：

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

2 改進蟻群算法

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

2.1 信息素初始化改進

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

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

(1)

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

2.2 信息素局部更新規(guī)則的改進

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

(2)

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

2.3 信息素全局更新規(guī)則的改進

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

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

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

(3)

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

3 算法仿真與分析

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

a. PCB待加工過孔

b. PCB過孔加工最優(yōu)路徑

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

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

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

圖2 各算法30次實驗結(jié)果分布

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

圖3 各算法收斂性對比

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

表2 最優(yōu)占比統(tǒng)計結(jié)果 %

表3 平均迭代次數(shù)統(tǒng)計結(jié)果

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

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

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

4 結(jié)束語

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

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

[2] 邢啟明.基于最短路徑算法的PCB板插接優(yōu)化[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].計算機應(yīng)用與工程,2016，52(6):8～12.

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

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

[8] 何小虎.基于改進蟻群算法在糧食物流配送路徑優(yōu)化的應(yīng)用研究[J].電子設(shè)計工程, 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-)，碩士研究生，從事數(shù)字圖像處理、PCB自動布線、PCB打孔機路徑規(guī)劃的研究。

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

2016-11-21，

2017-03-15)