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

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

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

1 題目的背景與意義

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

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

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

該文數(shù)據(jù)來(lái)自2012年“深圳杯”全國(guó)大學(xué)生數(shù)學(xué)建模夏令營(yíng)

D題。

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

3.1 方法介紹

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

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

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

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

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

這時(shí)，還要記錄每只螞蟻所走過(guò)的路徑Lk以及最短路徑

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

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

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

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

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

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

4.1 問(wèn)題分析

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

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

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

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

T=Tk+Ti，j

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

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

因?yàn)榫艂€(gè)鉆頭獨(dú)立行進(jìn)的最短路徑只要分別建模求解出獨(dú)立行進(jìn)最短路徑分析即可，因此接下來(lái)首先以較具有代表性的d鉆頭進(jìn)行獨(dú)立分析。

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

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

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

意的。

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

[2]李秋霞，賀達(dá)漢，長(zhǎng)有德，等.螞蟻取食行為研究概況[J].寧夏農(nóng)學(xué)院學(xué)報(bào)，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.