摘要：針對當前復雜圖形加工中存在加工軌跡之間空行程多，導致加工過程耗時很長等缺陷，提出一種簡單、易于實現的加工軌跡切換優化方法。分析了復雜圖形加工軌跡切換控制方法，給出了縮短總空行程的優化思想。基于雙向蟻群算法原理，推導了雙向最大最小蟻群算法(BidirectionalMax Min Ant Colony Syste ，BMMAS)，結合加工軌跡之間軌跡切換特點，對復雜圖形加工工藝路徑進行規劃設計，給出了算法實現流程及加工工藝路徑優化的實現要點。最后利用該方法對平面復雜圖形進行了優化加工實驗。實驗結果表明，該加工方法計算簡單，加工效率高，空行程路徑長度較其它方法短，加工平穩。研究結果對相似復雜圖形加工具有參考價值。

　　關鍵詞：復雜圖形;加工工藝路徑;優化;最大最小蟻群算法

　　隨著服裝、鞋、工藝品、包裝等輕工業的不斷發展，對應的加工圖形也越來越復雜。在很多時候，一個復雜圖形加工會耗時數個小時，這對復雜圖形加工工藝優化在激光切割加工中提出迫切需求。當前，在使用 CAD 類軟件進行復雜加工圖形時，圖形中每個獨立的加工軌跡繪制順序不固定，且圖形繪制過程中會涉及反復修改，導致復雜圖形轉換成加工圖形數據時，軌跡先后順序較為雜亂，從而造成加工時刀具軌跡間切換的總的空行程過長，會增加不必要的加工時間，降低加工效率。近些年來，不少學者加大在該領域的研究力度，取得了一些重要的研究成果。

　　CuneytOysu 等[1]提出一種遺傳算法和模擬退火算法結合的混合算法應用于刀具路徑優化問題;楊建軍等[2 提出了建立考慮時間距離和熱效應的多目標優化數學模型，利用改進的遺傳算法對激光切割路徑進行優化;劉山和等[3 提出了一種基于遺傳蟻群混合算法的激光切割路徑優化方法;Jin Lan 等[4提出了一種采用有限差分法、人工神經網絡和遺傳算法相結合的加工軌跡規劃方法。

　　候普良等[5 提出了通過最鄰近插入算法對蟻群系統算法路徑優化結果進行了再優化的改進算法，提高了運行效率;李世紅等[6 采用傳統蟻群算法，將激光切割路徑優化問題轉化為 GTSP 模型進行優化處理;王娜等[7 對傳統蟻群算法進行改進，提出了雙向蟻群算法，對正向和反向搜索蟻群的引導信息進行不同的設計，減少了空行程和切割時間。以上這些方法主要分為兩種類型：

　　一是忽略復雜圖形切割工藝中某些工藝約束，從而獲得較優的加工工藝路徑。該方法計算量小，但由于是局部最優，對整體加工效率提升有限;二是算法過程較為復雜，算法運行時間長。該方法能有效提升加工效率，但會使運算效率降低，且加工數據計算量大大增加。結合以上研究方法分析，本文提出了一種優化效果好、易于實現的復雜圖形加工路徑優化方法。該方法在滿足復雜圖形加工質量的前提下，有效減小加工過程中空行程路徑長度，對實際生產中降低總的加工時間、提高加工效率具有重要意義。

　　1路徑優化數學模型

　　1.1 路徑優化問題

　　設備在加工復雜零件時，在設置好板材排樣后，控制系統取出復雜圖形上各個軌跡圖形的待切割點的坐標位置，根據每個圖形在板材中先后順序，選擇順序靠前的軌跡圖形進行加工，完成后，再切換到下一個軌跡 。從而存在兩個問題：一是加工順序可能是多種組合，每種可能加工順序對應的加工軌跡間空行程長度不同;二是針對同一個加工順序，如 ，在加工軌跡 上，加工起點位置為①時和加工起點為②時，所對應的加工軌跡間空行程長度也不同。本文采用的優化思想為：

　　( 1)基于加工圖形數據，先找出每個代加工軌跡圖形特征點，建立復雜圖形特征點集。( 2)再以特征點集為基礎，找出通過全部特征點集的最優加工路徑，保證空行程路徑長度更短。

　　1.2 單個軌跡特征

　　點提取規則單個軌跡圖形特征點的提取對算法的求解有著重要的影響。對一個零件輪廓提取的特征點過少，會導致空行程過長，優化效果差;提取的特征點過多，則又會導致算法運算時間過長，不利于實際生產應用。

　　本文特征點的提取規則為：①對于多邊形，其特征點取多邊形的相鄰兩邊的交點;②對于圓形和橢圓形，其特征點取四象限點以及象限平分線上的點，對圓弧則取兩個端點和弧線的中心點;③由圓、圓弧、線段 種基本元素組成的封閉圖形，其特征點取其各元素之間的連接點;④對于圖形輪廓由樣條曲線組成，其特征點取樣條曲線上的擬合點。

　　1.3 數學模型

　　激光路徑優化問題的目的是為了尋找激光頭輔助運動軌跡[8 中切割圖形輪廓軌跡之間的空行程運動行程最短，通過上述待切割特征點的提取方法，找出加工零件每個輪廓的待切割特征點集，因此該激光切割路徑優化問題可轉化為研究每個點集經過一次的第一類 GTSP 問題[9 。在激光切割加工中，由于機床原點是刀具運動的起始點和終點，為了更方便的將其統籌進整個數學模型，將其看作是只有一個外輪廓，并且外輪廓只有一個特征點的加工零件。

　　2 BMMAS 算法

　　推導本 文 提 出 運 用 雙 向 最 大 最 小 蟻 群 算 法Bidirectional max min ant colony algorithm ，BMMAS)對激光切割路徑進行優化。BMMAS 算法使用雙種群螞蟻分別從選定的路徑起點和終點之間相向搜索，同時采用精英蟻群策略 10 11 ，僅更新最優路徑上的信息素，并引入最大最小蟻群算法(Max Min Ant System，MMAS)[12 的信息素閾值區間 τmin, τmax ，保證算法收斂速度的基礎上使算法不容易陷入局部最優。

　　2.1 確定候選特征

　　點集合設候選特征點集合為 allowed，若螞蟻在 時刻位于輪廓 ij 的特征點 ijk，記螞蟻允許移動的候選特征點集合為 allowed 。建立 Pre_allowed 為臨時的預備集合，起點到終點的候選特征點集合確定準則，終點到起點則與之相反。

　　2.2信息素更新

　　根據上述特征點選擇方法，每只螞蟻在完成所有輪廓的移動后即找到一條可行路徑，計算出可行路徑的長度，找出每次迭代所有螞蟻中長度最小的路徑記為 Pathlb。第一次迭代完成后，同時將該次迭代的 Pathlb 作為初始全局最優路徑 Pathgb，往后每次迭代都將當次迭代的 pathlb 路徑長度和 Pathgb 的路徑長度進行對比，不斷將 Pathgb 替換成長度最小的路徑。在每完成一次迭代后，需要對零件輪廓不同特征點之間路段的信息素進行更新。

　　相比無優化時按排樣中輪廓順序生成加工路徑，經過各種優化算法優化后的加工路徑長度都有不同程度的減小;橫向掃描法、縱 向掃 描 法 雖然 運 行 時間 比 雙 向蟻 群 算 法 和BMMAS 算法都短，但與無優化時對比，空行程路徑長度減小都在 25%以內，優化效果不太明顯;雙向蟻群算法和BMMAS算法能在較短運行時間內得出較優解，其中 BMMAS 算法又比雙向蟻群運行時間更短，得出的加工路徑長度也更優。以上實驗結果證明了BMMAS算法對于復雜圖形加工工藝路徑優化的可行性與優越性。

　　3結論

　　改進了復雜圖形加工問題的數學模型，對其目標函數進行簡化，并在雙向蟻群算法的基礎上提出了 BMMAS 算法，算法采用雙種群蟻群從正反兩方向進行路徑搜索，使用精英蟻群策略加快算法的收斂速度，同時應用最大最小蟻群算法的信息素閾值限定螞蟻信息素的濃度范圍，從而增加算法跳出局部最優的概率。實驗結果表明，與雙向蟻群算法以及工業加工中常用的橫向掃描法、縱向掃描法等運行結果相比， BMMAS 算法優化效果顯著，具有一定的工程應用價值。

　　參考文獻

　　[1] Cuneyt Oysu, Zafer Bingul. Application of heuristic andhybrid GASA algorithms to tool path optimizationproblem for minimizing airtime during machining[J]. Engineering Applications of Artificial Intelligence 2009,22(3):389 396.

　　[2] 楊建軍 劉保業 鞠錄巖 激光切割路徑優化的雙重編碼改進遺傳算法[J].解放軍理工大學學報 自然科學版),2012,13 6):684 687.Yang Jianjun, Liu Baoye, Ju Luyan.Improved GeneticAlgorithm Based on Dual Coding for Path Optimization ofLaser Cutting [J]. Journal of PLA University of Scienceand Technology (Natural Science Edition), 2012,13 6):684 687. (in Chinese)

　　[3] 劉山和 錢曉明 樓佩煌 武星 基于遺傳蟻群混合算法的激 光 切 割 機 路 徑 優 化 [J]. 機 械 制 造 與 自 動化,2016,45 6):92 95.Liu Shanhe, Qian Xiaoming, Lou Peihuang, Wu Xing.PathOptimization of Laser Cutting Machine Based on GeneticAnt Colony Hybrid Algorithm [J]. Machine Building &Automation, 2016, 45 6):92 95. (in Chinese)

　　[4] Jin Lan Bin Lin Tian Huang,et al. Path planning forsupport heads in mirror milling machining system [J].International Journal of Advanced ManufacturingTechnology, 2017, 91(1 4):617 628.

　　作者：潘盛湖 ，張小軍