吳 哲，徐圣倫，楊春梅，趙 帥，秦廣義，李 超

（東北林業(yè)大學(xué) 機電工程學(xué)院，哈爾濱 150040）

在這個高速發(fā)展的科技時代，制造業(yè)技術(shù)時刻在更新，汽車行業(yè)車體的主要結(jié)構(gòu)是鈑金，要更快提高鈑金車體的加工效率，加強切割工藝是一種很好的方式。鈑金件的切割工藝是工業(yè)中常見的成形工藝，利用氧燃料、等離子體和激光熱切割技術(shù)進行成形的工藝也非常普遍。加工和切割操作都涉及切割結(jié)束點的刀具重新定位到新切割開始點的操作，這種重新定位的刀具操作在每一個加工操作中要重復(fù)幾次［1-2］。在機械加工過程中，刀具在每個切削周期中的重新定位的過程稱為空行程，這種非生產(chǎn)性加工時間的最小化在高速加工的批量生產(chǎn)中起著重要的作用。

提高切割效率的最好方式是對刀具的切割路徑進行優(yōu)化。刀具路徑優(yōu)化的早期研究主要集中在鉆削、掏槽和銑面等加工的快速運動和加工的局部運動［3］。通過優(yōu)化切削參數(shù)、刀具順序和使用的刀具路徑類型，求解出工作過程中的最快加工時間，許多研究人員都對此進行了研究。Castellino等［4］對非生產(chǎn)性加工時間的最小化進行了研究，他們的研究是基于Ascheuer［5］對有約束的問題采用順序排序啟發(fā)式算法和Helsgaun［6］對無約束的問題采用LK 啟發(fā)式算法的理論；Oysuand［7］針對刀具路徑優(yōu)化問題，提出了一種基于遺傳算法的最小路徑搜索算法，該算法成功地優(yōu)化了切割特征點的數(shù)量和總工作時間；為了優(yōu)化切割或焊接行程，Koenigand［8］高效地應(yīng)用了很少使用的Lin-Kernighan算法，他們的程序集能夠在2 s內(nèi)計算出100個位置問題的優(yōu)化刀具路徑；Qudeiri等［9］利用遺傳算法優(yōu)化數(shù)控機床的操作順序，還解決了一個作為非對稱TSP問題的切割問題。

為了解決激光切割路徑優(yōu)化問題，本文提出了一種自適應(yīng)大鄰域搜索退火算法。該算法結(jié)合具有回火操作的模擬退火算法和自適應(yīng)大鄰域搜索算法中的破壞與修復(fù)操作。通過GTSP-Lib數(shù)據(jù)庫中的實例進行了測試，與已知最優(yōu)解進行對比，驗證算法的精確性；又將算法運用到實際切割操作中，得出了優(yōu)化路徑，并將結(jié)果與最新的解決方案進行了比較，來驗證算法的性能。

1 鈑金切割問題的模型建立

1.1 鈑金切割問題表述

在零件輪廓的完整切割中，激光束通過在輪廓的給定軌跡上移動，到在激光束返回到切割特征點之前在輪廓周長上或其附近打通一個特征點來開始切割［10］。由于激光器始終打開并在整個過程中進行連續(xù)切割，因此被認為是有成效的工作狀態(tài)。相反，當激光切割頭在關(guān)閉的情況下從一個切割特征點移至另一個切割特征點時，這是非生產(chǎn)性的工作狀態(tài)，也被稱作空行程。圖1描繪了一個切割路徑的示例，該路徑具有嵌套在金屬板上的9個不規(guī)則部分，粗實線表示從起始點開始的非生產(chǎn)性移動，每個輪廓上的小點表示切割特征點。如圖1所示，切割順序和切割特征點的位置會嚴重影響該行進路徑的總長度，必須通過確定合適的打孔位置以及切割順序，將這種非生產(chǎn)性的運動減至最少。

1.2 數(shù)學(xué)模型

本文中涉及的切割路徑問題被表述為GTSP問題，其中預(yù)先定義了零件輪廓的所有特征點坐標作為潛在的打孔位置。為了確定最佳的打孔位置和切割順序，對路徑距離進行優(yōu)化。通過考慮GTSP的整數(shù)規(guī)劃，引入二進制變量xe∈｛0，1｝和yi∈｛0，1｝，其中e∈E和i∈V表示一條邊e和一個節(jié)點i是否包含在切割輪廓中［11］。這個GTSP問題的一個可行解可以記作m條邊的循環(huán)，所有的邊連接在一起，每個邊只有一個打孔點。因此，GTSP可以表示為整數(shù)規(guī)劃，目標函數(shù)為：

目標函數(shù)服從于：

式中：ce是邊緣輪廓e＝（i，j）的耗費距離；Vk是種群k中的節(jié)點；目標函數(shù)δ（v）＝｛e＝（i，j）∈E｜i∈S，j?S｝描述了生成路徑的成本。約束條件1（式（2））確保從每個輪廓／群集中僅選擇一個打孔點；約束2（式（3））用于強制每個輪廓的起始點和結(jié)束點位于同一位置；約束3（式（4））是消除子路徑（S）路徑約束的限制，即子集上的路徑少于n個節(jié)點。最后，約束4（式（5））和約束5（式（6））是使函數(shù)成立的二進制變量條件。

2 算法的設(shè)計與實現(xiàn)

本節(jié)從算法框架、鄰域搜索操作、終止條件判定3個方面展開研究，重點設(shè)計了結(jié)構(gòu)清晰且功能模塊相對獨立的自適應(yīng)大鄰域搜索算法框架，對搜索算法中的破壞算子和修復(fù)算子進行了改進，并通過改進的模擬退火算法對算法進行接受準則判定，實現(xiàn)高精度的全局搜索的自適應(yīng)大鄰域搜索退火算法構(gòu)建［12］。

2.1 自適應(yīng)大鄰域搜索算法框架

GTSP作為一類基礎(chǔ)的路徑優(yōu)化問題，在各種相關(guān)工程問題上都有所涉及。要想在特定問題上找到相對合適的特定算法，需要在原有的算法框架上進行構(gòu)建。自適應(yīng)大鄰域搜索算法具有搜索范圍廣和操作模塊較為獨立的特點，因此通過構(gòu)建算法框架將算法模塊化，然后對內(nèi)部模塊進行改進，設(shè)計更加適合的算法。

如圖2所示，根據(jù)算法框架確定改進的核心思想是：在定義好初始種群的情況下，通過改善鄰域搜索操作中的算子，使算法更快地產(chǎn)生新解，以數(shù)值優(yōu)化為目標接受更優(yōu)解，對新解進行多次迭代達到最優(yōu)。將算法分解成獨立的功能模塊，便于明確各模塊目的來進行程序設(shè)計。再運用優(yōu)化判定準則，在多約束條件下獲得更好的全局搜索。

2.2 改進鄰域搜索算子的ALNS算法

自適應(yīng)大鄰域搜索算法（ALNS）是從大鄰域搜索算法（LNS）發(fā)展而來的，兩者的算法框架是相同的，都是通過破壞和修復(fù)操作算子來獲取解的鄰域。ALNS在LNS的基礎(chǔ)上，允許在同一個搜索中使用多個破壞和修復(fù)操作，ALNS會為每個破壞和修復(fù)操作分配一個權(quán)重，通過該權(quán)重從而控制每個破壞和修復(fù)操作在搜索期間使用的頻率。在搜索的過程中，ALNS會對各個破壞和修復(fù)操作的權(quán)重進行動態(tài)調(diào)整，以便獲得更好的鄰域和解。ALNS通過使用多種破壞和修復(fù)操作，然后再根據(jù)這些破壞和修復(fù)操作生成的解的質(zhì)量，選擇那些表現(xiàn)好的破壞和修復(fù)操作，再次生成鄰域進行搜索。其簡要偽代碼如下：

算法1ALNS算法

上面就是ALNS偽代碼。在代碼第2行，定義了破壞和修復(fù)操作的權(quán)重集合，開始時所有操作都設(shè)置相同的權(quán)重。Ω1和Ω2分別表示破壞和修復(fù)操作的集合，根據(jù)ρ1和ρ2選擇破壞和修復(fù)操作。至于選擇哪個操作的可能性大小，由下面公式算出：

由式（7）可得，權(quán)重越大，被選中的可能性越大。除此之外，權(quán)重大小是根據(jù)破壞和修復(fù)操作在搜索過程中的表現(xiàn)進行動態(tài)調(diào)整的。

在ALNS算法的每個循環(huán)的迭代中，都要經(jīng)過一次破壞和修復(fù)操作，不同的操作對算法的優(yōu)化程度有著很大的影響，在進行破壞操作時，選取的刪除方法是統(tǒng)一最壞刪除方法。在統(tǒng)一最壞刪除過程中，先給定一個集合T使VT＝｛v1，v2，…，vl｝，刪除頂點vj使刪除成本最大化：

其中指數(shù)j-1和j+1用l+1≡1和0≡l進行評估。也就是說，刪除了導(dǎo)致路徑長度減少最多的頂點，因為它可能在計算中被放錯了位置。在統(tǒng)一最壞刪除方法中，通過刪除代價rj來拓展這一思想，這將創(chuàng)造一系列通過參數(shù)化λ的刪除方法。特別是：

1）λ＝1時對應(yīng)隨機刪除，其中頂點Nr從集合VT中均勻隨機選擇刪除。

2）λ＝0時對應(yīng)最壞刪除。

對于λ∈（1，∞）的值，獲得了隨機化程度不同的最壞刪除的隨機方法，類似于Ropke［13］提出的隨機化方法。每次刪除可以在O（m）次內(nèi)完成，因此Nr的清除需要O（Nrm）次。

在修復(fù)操作中也有很多的插入方法，本文選取的是統(tǒng)一插入方法。先給定一個帶有V的分區(qū)PV∶｛V1，…，Vm｝和坐標G＝（V；E；w），將部分GTSP循環(huán)定義為G中的一個循環(huán)，這樣分區(qū)PV中的每個集合最多只訪問1次（在一個完整的循環(huán)中，每個集合只訪問1次）。給定一個局部歷程T＝（VT；ET），T訪問的分區(qū)集合記為PT?PV。

剩下的就是指定選擇插入集合（Vi∈PV＼PT）的機制。對于每個集合Vi，i∈｛1，…，m｝和每個頂點u∈V＼Vi，計算距離為：

基礎(chǔ)的插入方法有最近插入方法、最遠插入方法和隨機插入方法3種方法：

最近插入方法會選取包含頂點v的集合Vi，該集合為距局部路徑T的頂點的最小距離。選擇集合Vi的方法為：

最遠插入方法選擇頂點與部分路徑T上的頂點最接近的集合Vi，選擇集合Vi的方法為：

隨機插入方法是從PV＼PT中隨機抽取1組集合Vi。

最近插入方法、最遠插入方法和隨機插入方法可以集合成統(tǒng)一插入方法。給定一個局部路徑T，接下來可以插入集合PV。對于每個集合Vi∈PV＼PT，將Vi和T之間的最小距離定義為：

給定參數(shù)λ∈［0，∞）和部分路徑：

1）通過設(shè)置λ＝1獲得隨機插入方法；

2）通過設(shè)置λ＝0獲得最近插入方法；

3）通過設(shè)置λ＝+∞（或足夠大）獲得最遠插入方法。

此外，通過選擇的中間值，可以獲得最近、最遠和隨機插入的隨機化版本，從而允許在大型鄰域搜索區(qū)間對解進行更大的探索。

2.3 改進模擬退火算法判定接受準則

自適應(yīng)大鄰域搜索算法的接受準則和停止準則有很多種，有最簡單的直接根據(jù)目標值來判斷，也有通過各種復(fù)雜的模擬退火降溫冷卻等過程來判斷。但這些方法都存在準確性差、魯棒性弱的缺點，本文選用的判斷接受準則是在基礎(chǔ)模擬退火算法的基礎(chǔ)上進行改進得到的。

模擬退火算法是通過控制參數(shù)T按降溫函數(shù)T（k+1）＝kTk降溫，使其值逐漸下降直至變?yōu)榱恪Ｔ赥值逐漸變小的過程中，算法跳出局部最優(yōu)的能力越來越弱，當T值降到充分小時，算法完全喪失跳出局部最優(yōu)的能力，使所求結(jié)果準確性下降［14］。

根據(jù)熱力學(xué)原理，在溫度為T時，出現(xiàn)能量變化ΔE的概率為X（t），表示為：

其中k是常數(shù)，且ΔE＜0（能量總是降低的）。式（13）表明：①溫度越高，出現(xiàn)降溫的概率越大；②溫度越低，出現(xiàn)降溫的概率越小。

又由于ΔE總是小于0，因此ΔE／kT＜0，exp（ΔE／（kT））取值是（0，1），那么X（t）的函數(shù)取值范圍是（0，1）。

在模擬退火算法運行前期，溫度值T較大，降溫概率X（t）高，算法很難達到局部最優(yōu)；但隨著算法運行到后期，T值變得較小，降溫概率X（t）也隨之變小，算法最終變?yōu)榫植克阉?，并陷入局部最?yōu)。要避免陷入局部最優(yōu)，需要通過Metropolis準則進行判定。

Metropolis準則常表示為：

從式（14）可以看出，若En+1＜En（即移動后可以獲得更優(yōu)解），則總是接受該移動；若En+1≥En（即移動后的解比當前解要差），則以一定的概率接受移動，這個概率會隨著溫度變化逐漸降低。通過Metropolis準則，可以在陷入局部最優(yōu)后進行較差值的接受，以此來跳出局部最優(yōu)，若跳出后能發(fā)現(xiàn)更優(yōu)解，則從局部搜索再次變?yōu)槿炙阉鳌?/p>

要提高整個算法獲得的最終解的質(zhì)量，應(yīng)該避免算法過早地陷入局部最優(yōu)。在運算初始，算法具有較高的溫度T，算法的接受率高，但隨著溫度T的降低，算法的接受率越來越差，不可避免地會變?yōu)榫植繉?yōu)問題。只有在溫度降為0后，重新提高T值，才能使算法的接受率再次提高，從而獲得全局最優(yōu)解。這種操作稱為模擬退火算法的回火操作，回火后再重復(fù)進行模擬退火算法，就有可能得到全局最優(yōu)解。

在初始定義參數(shù)時，加入?yún)?shù)回火結(jié)束溫度Tc和回火系數(shù)b，在退火操作后，重新回火至初始溫度，緩慢降溫，直到溫度降至Tc，結(jié)束回火階段。因為回火操作重復(fù)退火時的計算過程，進行多次會極大地增加計算時間，所以選擇5～10次較為合適。初次回火時的初始解為上次退火時的最終解，之后每次回火操作都以上次退火的最終解作初始解。

改進模擬退火算法的具體步驟如下：

步驟1給定退火初始溫度T0，初始解狀態(tài)x，定義記憶器best，退火終止溫度Tf，退火系數(shù)a，回火系數(shù)b，回火結(jié)束溫度Tc，馬爾可夫鏈長度Lk，k＝0；

步驟2k＝k+1，當k≥Lk時，轉(zhuǎn)步驟12；

步驟3對個體x進行個體鄰域搜索算法，生成新的初始解x′；

步驟4計算能量的增量ΔE＝f（x′）-f（x），其中f（x）為評價函數(shù)；

步驟5若ΔE＜0，則接受x′為新的初始解，即if（ΔE′＜0），x＝x′轉(zhuǎn)步驟7；

步驟6若ΔE≥0，通過Metropolis準則進行判定，接受達到概率的新解x′；

步驟7Tk+1＝a·Tk，對退火溫度進行重新定義；

步驟8if（Tk≤Tf），退火終止；

步驟9進行回火操作，回溫到初始溫度；

步驟10Tk′＝b·Tk，對回火溫度進行重新定義；

步驟11if（Tk′≤Tc），回火終止，轉(zhuǎn)步驟2；

步驟12輸出最終解best＝x，算法結(jié)束。

在回火過程中，最高溫度隨著每次回火而逐漸下降，直至達到回火終止溫度，算法停止。在回火過程中，算法接受最優(yōu)解的能力將得到提高，這對于獲取最優(yōu)解是有益的。

事實上，回火操作早期有著較高的回火溫度，算法對較差值的接受能力也很高，能很好地擾亂當前解，迫使算法程序繼續(xù)移動，從而獲得很好的解。而當算法進行到后期時，回火溫度開始變低，算法的結(jié)果越來越趨近于最優(yōu)解，最終將回火溫度控制在有效域區(qū)間，再通過退火操作對較優(yōu)解進行保留，經(jīng)過比較后求得最優(yōu)解，以此來平衡局部搜索與全局搜索，使算法的性能得到增強。

在時間復(fù)雜度上，普通的模擬退火是O（n2），面對小規(guī)模的問題時，效率和準確性極高。但隨著數(shù)據(jù)規(guī)模的增加，計算量增大的同時卻不能帶來較好的準確性。而本文的改進算法只需要增加回火次數(shù)M和插入刪除操作次數(shù)N，最終時間復(fù)雜度為O（MNn2），與普通的模擬退火屬于相同的量級，但在準確性上得到了極大的提高。

3 實驗與分析

3.1 激光切割路徑優(yōu)化

為了驗證上文中提出的自適應(yīng)大鄰域搜索退火算法的可行性，在WindowsWin10，CPU 3.4 GHz，8 GRAM，Matlab2016a的開發(fā)環(huán)境下進行激光切割路徑優(yōu)化。在進行切割路徑優(yōu)化前，先通過GTSP-Lib數(shù)據(jù)庫［15］中的幾個二維笛卡爾算例進行測試，并對改進算法求得解與數(shù)據(jù)庫最優(yōu)解進行對比，結(jié)果見表1。

表1 GTSP-Lib數(shù)據(jù)庫算例測試結(jié)果

該算法求解了25個來自GTSP-Lib數(shù)據(jù)庫的算例，結(jié)果如表1所示，達到最優(yōu)解的解用黑體表示。通過對比發(fā)現(xiàn)，在解決小對象規(guī)模問題時，該算法具有較好的求解質(zhì)量，與已知解相比，平均誤差僅為0.31%。隨著對象規(guī)模的增加，最優(yōu)解獲得概率和求解效果都有所下降。對達到最優(yōu)解的算例14st70進行分析，得到的具體優(yōu)化路徑如圖3所示。圖4是經(jīng)過分析后的優(yōu)化過程曲線，細線表示優(yōu)化運算中的路徑當前值，粗線是通過運算可以得到的較優(yōu)解。算法每次迭代后都會記憶退火操作后的較優(yōu)解，通過改變每次迭代的破壞和修復(fù)方法和更優(yōu)解接受規(guī)則，實現(xiàn)了搜索范圍的逐步收縮，由大鄰域逐漸縮小至最優(yōu)解，并且每次退火運算后，結(jié)果都能夠得到很大程度的提升。

表1中數(shù)據(jù)來自于GTSP-Lib數(shù)據(jù)庫，其中計算偏差率＝［（改進算法-最佳解決方案）／最佳解決方案］×100%。通過數(shù)據(jù)可以發(fā)現(xiàn)，改進算法在求解小規(guī)模問題時，精確度極高，幾乎沒有誤差，平均最優(yōu)解獲得率達到90%。但當問題規(guī)模大于45個種簇時，算法性能開始下降，平均最優(yōu)解獲得率變成70%。這種性能減弱在處理大問題時特別明顯，這是因為問題大小的增加放大了可能的解決方案的數(shù)量，從而延長了運行時間，降低了算法解決性能。在有限實驗次數(shù)中的最優(yōu)解數(shù)值并不能完全反映算法性能，因此通過偏差率來評價算法的普遍求解效果，如表1所示。自適應(yīng)大鄰域搜索退火算法的平均偏差率為0.31%，整體計算結(jié)果與最優(yōu)解的相差較小，即表明算法每次求解能夠大概率獲得一個較好的解，適用于次數(shù)較少的運算過程?？偟膩砜矗赃m應(yīng)大鄰域搜索退火算法不僅獲得了大部分算例的最優(yōu)解，求解精度令人滿意，而且整體偏差率較小，魯棒性好。

3.2 針對實際樣板切割實驗

本文采用高速數(shù)控激光加工機床進行實驗，參數(shù)設(shè)置為：切割速度為1 000，加速度為8 000，減速度為8 000，操作系統(tǒng)界面如圖5。

切割樣式通過CAD制圖導(dǎo)入操作系統(tǒng)，在CAD上先繪制排版好的零件版圖，如圖6所示。圖中的實例是由全封閉圖元組成的圖形，圖中共有18個封閉圖元，每個圖元都有獨立的標號，是作為圖元讀取時設(shè)定的記號，用來區(qū)分各個圖元。封閉圖元切割的起始點與結(jié)束點相同，保證有效切割，減少工作性切割損耗［16］。

本研究針對圖6全封閉圖元組成的實例，分別用本文提出的自適應(yīng)大鄰域搜索算法和Stephen L.Smith［17］提出的GLNS算法進行優(yōu)化。進行10次實驗，分別記錄下得出規(guī)劃路徑的時長和路徑總長度，詳細數(shù)據(jù)見表2。由表2可得出，優(yōu)化后的最佳路徑長度為6 657 mm，得到的最優(yōu)解用黑體表示。通過對比可以發(fā)現(xiàn)，本文提出的自適應(yīng)大領(lǐng)域搜索退火算法在準確性上與最新提出的GLNS算法大致相同，但計算時間有所減少，提高了計算效率，表明了該算法在解決復(fù)雜輪廓切割路徑規(guī)劃問題上較為穩(wěn)定，也驗證了算法在解決這類GTSP問題時是可行的。

表2 排樣規(guī)劃路徑參數(shù)對比

4 結(jié)束語

為了解決激光切割過程中的路徑優(yōu)化問題，提出了一種自適應(yīng)大鄰域搜索退火算法，該算法是一種啟發(fā)式算法，它以自適應(yīng)大鄰域搜索退火算法（ALNS）為基礎(chǔ)，通過統(tǒng)一最壞刪除方法和統(tǒng)一插入方法進行破壞和修復(fù)操作的改進，再以改進模擬退火算法作為接受準則。所提出的算法已通過GTSP-Lib的各種實例進行了測試，其結(jié)果與現(xiàn)有的最著名解決方案相比較，平均誤差僅為0.31%。當使用該算法解決切割路徑實例時，在保證準確率的情況下，運算效率得到了很大的提高。因此，該算法將成為解決激光切割過程以及其他機械制造操作中的路徑優(yōu)化問題的一種優(yōu)勢算法。