王捷晨 路林吉

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

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

王捷晨 路林吉

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

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

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

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

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

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

1.1 問題描述

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

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

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

1.2 蟻群算法的原理

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

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

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

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

2 改進(jìn)蟻群算法

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

2.1 信息素初始化改進(jìn)

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

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

(1)

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

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

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

(2)

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

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

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

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

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

(3)

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

3 算法仿真與分析

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

a. PCB待加工過孔

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

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

表1 改進(jìn)蟻群算法(I-ACS)的實(shí)驗(yàn)參數(shù)

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

圖2 各算法30次實(shí)驗(yàn)結(jié)果分布

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

圖3 各算法收斂性對(duì)比

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

2016-11-21，

2017-03-15)