蟻群算法理論及其在優(yōu)化打孔機(jī)作業(yè)路徑的應(yīng)用

摘 要：蟻群算法是一種新出現(xiàn)的仿生進(jìn)化算法，廣泛應(yīng)用在現(xiàn)代化優(yōu)化領(lǐng)域。該文詳細(xì)介紹了該算法的原理與實(shí)現(xiàn)過程，并討論其在優(yōu)化打孔機(jī)作業(yè)路徑上的應(yīng)用。最后，評述了所得出的結(jié)論，分析算法的優(yōu)缺點(diǎn)，為此提供了可改進(jìn)的方向。

關(guān)鍵詞：蟻群算法 信息素 打孔機(jī) 最短路徑

中圖分類號：O224 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2012）12（c）-0-02

1 題目的背景與意義

蟻群算法作為通用型隨機(jī)優(yōu)化方法，以其更優(yōu)的時間復(fù)雜度與更高的搜索效率，優(yōu)勝于以往常用的啟發(fā)式算法，更為廣泛地應(yīng)用到組合優(yōu)化、人工智能、通訊等多個現(xiàn)代化領(lǐng)域。同時，蟻群算法的正反饋性、協(xié)同性與遺憾的并行性，是該算法具有發(fā)展?jié)摿Φ挠辛Ω鶕?jù)，該文嘗試使用蟻群算法解決多目標(biāo)優(yōu)化問題的研究工作。

過孔是印刷電路板的重要組成部分之一，其加工費(fèi)用占總制作費(fèi)用的30%到40%，打孔機(jī)主要用于在制造印刷線路板流程中的打孔作業(yè)。打孔機(jī)的生產(chǎn)效能主要取決于鉆孔作業(yè)時間、鉆頭行進(jìn)時間與刀具轉(zhuǎn)換時間。由于鉆孔作業(yè)時間由制作工藝水平?jīng)Q定，不在模型討論范圍內(nèi)。該文旨在研究打孔機(jī)生產(chǎn)作業(yè)時，刀具轉(zhuǎn)換的最佳方案與鉆頭行進(jìn)最優(yōu)路徑。

2 數(shù)據(jù)背景

該文數(shù)據(jù)來自2012年“深圳杯”全國大學(xué)生數(shù)學(xué)建模夏令營

D題。

3 蟻群算法的理論與應(yīng)用

3.1 方法介紹

蟻群算法，于20世紀(jì)90年代初由意大利學(xué)者Colorni、Dorigo和Maniezzo等人首先提出，稱之為蟻群系統(tǒng)，是一種啟發(fā)式仿生進(jìn)化算法。該算法應(yīng)用于求解TSP問題、分配問題與job-shop調(diào)度問題，并取得了較為滿意的效果。

后人依據(jù)此研究基礎(chǔ)，提出了一種求解分配類型問題的一般模型，并運(yùn)用此方法探討圖著色問題[1]。雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題，尤其是離散問題，具有一定的優(yōu)勢。

3.2 原理及算法實(shí)現(xiàn)

其中allowedk為可行集，表示螞蟻k下一步可以選擇的路徑集合；α為信息啟發(fā)式因子，是路徑ij上殘留信息的重要程度，表示軌跡的相對重要性；β為期望啟發(fā)式因子，表示能見度的相對重要性；ηij為啟發(fā)函數(shù)，且滿足ηij=。

由于人工螞蟻具有記憶功能，用tabuk（k=1，2，...，m）記錄螞蟻k當(dāng)前走過的位置并隨著進(jìn)化過程動態(tài)調(diào)整，稱為記憶列表。當(dāng)所有螞蟻完成了一次遍歷，它們本次遍歷的記憶列表則被寫滿，此時應(yīng)當(dāng)清空，并把當(dāng)前螞蟻所在城市寫入tabuk，然后進(jìn)入下一次遍歷。

這時，還要記錄每只螞蟻所走過的路徑Lk以及最短路徑

其中，Δτijk表示螞蟻k在本次循環(huán)中留在路徑ij上的信息量增量；Δτij表示本次循環(huán)中路徑ij上的信息量增量；在螞蟻遍歷的過程中，以往留下的信息量將不斷揮發(fā)，用ρ表示信息量揮發(fā)程度，1-ρ1表示揮發(fā)后剩余的信息量，即軌跡衰減度。

針對信息量增量的計算，意大利學(xué)者M(jìn).Dorigo提出了三種算法模型[3]，分別為蟻周模型（Ant-Cycle Model）、蟻量模型（AntQuantity Model）和蟻密模型（Ant-Density Model）。考慮到充分利用全局信息，該文采用蟻周模型（3）求解：

其中，Q表示螞蟻k完成一個完整的路徑搜索后所釋放的信息量總和；Lk表示螞蟻k在本次循環(huán)中所走路徑的長度。

還考慮到螞蟻不可重復(fù)訪問同一個位置，該文引入一個控制“螞蟻不再選取自己本次循環(huán)已經(jīng)走過的路徑作為下一步路徑”這一行為特性的數(shù)據(jù)結(jié)構(gòu)visited-cityk。

蟻群算法流程圖如圖1所示；

4 算法在求解打孔機(jī)作業(yè)最短路徑的應(yīng)用

4.1 問題分析

打孔機(jī)主要用于在制造印刷線路板流程中的打孔作業(yè)，過孔是印刷線路板的重要組成部分之一。同時，因為過孔的加工費(fèi)用在制版成本中占據(jù)較大比例，通常達(dá)到總費(fèi)用的30%到40%?？紤]到單鉆頭打孔機(jī)在打孔作業(yè)過程中，生產(chǎn)效能受到三方面因素的影響，即：單個過孔鉆孔時間、鉆頭在不同過孔之間的行進(jìn)時間與加工不同孔型時刀具的轉(zhuǎn)換時間。針對此問題，該文接下來討論如何通過選擇合適的算法建立合理的模型，以達(dá)到求解與分析單鉆頭打孔機(jī)作業(yè)的生產(chǎn)效能問題。

首先，該文運(yùn)用貪心算法，確定出最優(yōu)刀具轉(zhuǎn)換次序，則不同孔型加工作業(yè)過程中刀具轉(zhuǎn)換最優(yōu)順序模型為：

d→c→b→a→h→g→f→e→c

最優(yōu)作業(yè)線路下行進(jìn)時間的關(guān)系表達(dá)式為：

T=Tk+Ti，j

其中，Tk代表最優(yōu)作業(yè)線路下刀具行進(jìn)總時間；Ti，j代表最優(yōu)作業(yè)線路下刀具從轉(zhuǎn)換到所耗費(fèi)的時間。

4.2 數(shù)據(jù)與結(jié)語

因為九個鉆頭獨(dú)立行進(jìn)的最短路徑只要分別建模求解出獨(dú)立行進(jìn)最短路徑分析即可，因此接下來首先以較具有代表性的d鉆頭進(jìn)行獨(dú)立分析。

利用matlab軟件，運(yùn)用蟻群算法進(jìn)行運(yùn)算，得出了d鉆頭最優(yōu)打孔路線如圖2所示。容易觀察出，打孔路線的設(shè)計較為合理，不存在鉆頭重復(fù)跨越的區(qū)域，過孔之間的連接符合實(shí)際生產(chǎn)要求。因此運(yùn)用蟻群算法求解出d鉆頭優(yōu)化路徑模型，為提高生產(chǎn)效能提供了可行的方案。

為檢驗計算結(jié)果的準(zhǔn)確性，該文以d鉆頭為例，利用matlab程序繪制出過孔平均距離與最短距離曲線，如圖3所示。

可以觀察出，依據(jù)蟻群算法結(jié)果的路徑設(shè)計，過孔平均距離在初始階段急劇減少，并迅速進(jìn)入平穩(wěn)階段，同時過孔最短距離波動逐漸減小?？梢缘贸?，該方法對此問題的解決程度是較令人滿

意的。

5 結(jié)語

蟻群算法經(jīng)由改進(jìn)后應(yīng)用于組合優(yōu)化、函數(shù)優(yōu)化、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘等許多領(lǐng)域，并顯示出其求解復(fù)雜優(yōu)化問題的優(yōu)勢，但是，因為蟻群算法的出現(xiàn)時間較短，期研究成熟度仍具有一定不足，仍存在以下留待改進(jìn)的問題：（1）由于多只螞蟻分頭尋找路徑，再按照概率轉(zhuǎn)移相遇，造成計算復(fù)雜，搜索時間長，對于計算機(jī)資源有一定要求，需要一定的時間成本；（2）由于螞蟻通過信息素和特定概率公式由一個結(jié)點(diǎn)轉(zhuǎn)移到另一個結(jié)點(diǎn)，所對參數(shù)的設(shè)置需要很嚴(yán)謹(jǐn)。若參數(shù)過小，則結(jié)果收斂慢；若參數(shù)過大，容易陷入局部最優(yōu)解。（3）算法研發(fā)時間較短，缺少系統(tǒng)的分析方法與有力的數(shù)學(xué)理論基礎(chǔ)；該文通過對存在于自然界的群體運(yùn)動—蟻群效應(yīng)，進(jìn)行了深入的了解，并介紹了蟻群算法的基本原理與實(shí)現(xiàn)過程，最后，針對實(shí)際應(yīng)用問題將該算法實(shí)現(xiàn)，分析結(jié)果得出打孔機(jī)作業(yè)的最優(yōu)路徑，為該工業(yè)的優(yōu)化生產(chǎn)效能提供了參考與建議。

參考文獻(xiàn)

[1]張紀(jì)會，徐心和.一種新的進(jìn)化算法：蟻群算法[J].系統(tǒng)工程理論與實(shí)踐，1999，19（3）：84-87.

[2]李秋霞，賀達(dá)漢，長有德，等.螞蟻取食行為研究概況[J].寧夏農(nóng)學(xué)院學(xué)報，2000（2）.

[3]M Dorigo，V Maniezzo，A Clolorni.The ant system：Optimization by a colony of cooperationg agents[J].IEEE Transactions on Systems，Man，and Cybernetics Part B，1996，26（1）：29-41.