切割路徑優(yōu)化問題的自適應(yīng)大鄰域搜索退火算法

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

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

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

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

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

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

1.1 鈑金切割問題表述

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

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

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

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

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

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

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

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

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

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

2.2 改進(jìn)鄰域搜索算子的ALNS算法

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

算法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)進(jìn)行動態(tài)調(diào)整的。

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

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

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

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

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

在修復(fù)操作中也有很多的插入方法，本文選取的是統(tǒng)一插入方法。先給定一個帶有V的分區(qū)PV∶｛V1，…，Vm｝和坐標(biāo)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）的機(jī)制。對于每個集合Vi，i∈｛1，…，m｝和每個頂點(diǎn)u∈V＼Vi，計算距離為：

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

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

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

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

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

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

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

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

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

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

2.3 改進(jìn)模擬退火算法判定接受準(zhǔn)則

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

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

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

Metropolis準(zhǔn)則常表示為：

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

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

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

改進(jìn)模擬退火算法的具體步驟如下：

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

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

步驟3對個體x進(jìn)行個體鄰域搜索算法，生成新的初始解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準(zhǔn)則進(jìn)行判定，接受達(dá)到概率的新解x′；

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

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

步驟9進(jìn)行回火操作，回溫到初始溫度；

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

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

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

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

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

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

3 實驗與分析

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

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

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

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

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

3.2 針對實際樣板切割實驗

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

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

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

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

4 結(jié)束語

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