蟻群算法理論及其在優化打孔機作業路徑的應用

摘 要：蟻群算法是一種新出現的仿生進化算法，廣泛應用在現代化優化領域。該文詳細介紹了該算法的原理與實現過程，并討論其在優化打孔機作業路徑上的應用。最后，評述了所得出的結論，分析算法的優缺點，為此提供了可改進的方向。

關鍵詞：蟻群算法 信息素 打孔機 最短路徑

中圖分類號：O224 文獻標識碼：A 文章編號：1674-098X（2012）12（c）-0-02

1 題目的背景與意義

蟻群算法作為通用型隨機優化方法，以其更優的時間復雜度與更高的搜索效率，優勝于以往常用的啟發式算法，更為廣泛地應用到組合優化、人工智能、通訊等多個現代化領域。同時，蟻群算法的正反饋性、協同性與遺憾的并行性，是該算法具有發展潛力的有力根據，該文嘗試使用蟻群算法解決多目標優化問題的研究工作。

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

2 數據背景

該文數據來自2012年“深圳杯”全國大學生數學建模夏令營

D題。

3 蟻群算法的理論與應用

3.1 方法介紹

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

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

3.2 原理及算法實現

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

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

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

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

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

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

還考慮到螞蟻不可重復訪問同一個位置，該文引入一個控制“螞蟻不再選取自己本次循環已經走過的路徑作為下一步路徑”這一行為特性的數據結構visited-cityk。

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

4 算法在求解打孔機作業最短路徑的應用

4.1 問題分析

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

首先，該文運用貪心算法，確定出最優刀具轉換次序，則不同孔型加工作業過程中刀具轉換最優順序模型為：

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

最優作業線路下行進時間的關系表達式為：

T=Tk+Ti，j

其中，Tk代表最優作業線路下刀具行進總時間；Ti，j代表最優作業線路下刀具從轉換到所耗費的時間。

4.2 數據與結語

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

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

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

可以觀察出，依據蟻群算法結果的路徑設計，過孔平均距離在初始階段急劇減少，并迅速進入平穩階段，同時過孔最短距離波動逐漸減小。可以得出，該方法對此問題的解決程度是較令人滿

意的。

5 結語

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

參考文獻

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

[2]李秋霞，賀達漢，長有德，等.螞蟻取食行為研究概況[J].寧夏農學院學報，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.