基于大規(guī)模鄰域搜索的模擬退火算法求解TSP

孫 鑒,劉凇佐,武曉曉

(北方民族大學計算機科學與工程學院,寧夏 銀川 750021)

1 引言

旅行商問題[1](Traveling Salesman Problem,TSP)是較早提出的組合優(yōu)化問題,其目標是求得在給定城市坐標集合,每個城市遍歷且僅遍歷一遍構成的城市序列,該城市序列代表旅行商將隨機選擇一個城市作為起點,每個城市遍歷一次,回到出發(fā)城市。旅行商問題的最優(yōu)解是總路程最短的城市序列。在車輛路徑規(guī)劃[2]、物流配送問題[3]等領域有重要的現實意義?？紤]到該問題在各個領域的應用價值,研究人員從計算機、數學、運籌學等多個學科交叉入手,集中研究解決旅行商問題。該問題的解決方法大致劃分為精確算法和近似算法兩大類。

常用的精確算法主要有枚舉法、動態(tài)規(guī)劃法以及分支限界法。但是大量的實驗證明,精確算法只適用于求解城市規(guī)模較小的旅行商問題,隨著城市規(guī)模的增大,精確算法求解開銷較大,短時間內難以求得可行解,在實際生活中應用價值不高[4]。

近似算法是在近乎合理的時間內找到問題的近似解,近似算法可以分為常規(guī)的啟發(fā)式算法和元啟發(fā)式算法兩類。常規(guī)的啟發(fā)式算法根據問題的特點,按照規(guī)則經驗、規(guī)則和知識設計而成,雖然算法設計簡單,但是不具有遷移性[5]。當問題結構發(fā)生變化,就需要設計新的模型求解。元啟發(fā)式算法更具有通用性,也因其特點成為求解TSP問題的主要方法,包括人工蜂群算法[6](ABC)、粒子群算法[7](PSO)、模擬退火算法[8,9](SA)。朱繼生[10]提出一種人工蜜蜂融合量子編碼的方法,在算法運行過程中量子位代表城市的訪問序列,同時利用量子影響最佳蜜蜂的方向移動,影響整個蜜蜂種群找到最優(yōu)解。李文、伍鐵斌等人[11]分析了基本粒子群算法的優(yōu)點和缺點,利用混沌運動的隨機性,自適應調整慣性權重,平衡了粒子群算法的局部搜索能力和全局搜索能力。本文利用模擬退火算法,修改降溫函數結合大鄰域搜索和2-opt算子,求解旅行商問題收斂速度快,尋優(yōu)能力強。

2 基本知識

2.1 基本的模擬退火算法

模擬退火算法受固體退火原理的啟發(fā),金屬固體退溫為加溫、等溫、冷卻三個過程。在退火最初,固體的溫度較高,內部分子沒有穩(wěn)定順序,分子之間熱運動較為劇烈,溫度緩慢降低,分子逐漸有序穩(wěn)定,這一過程稱為退火;溫度快速下降,能量無法降到最低,這一過程稱為淬火。如圖1是固體退火和淬火的過程示意圖。

圖1 物理退火和淬火過程圖示

退火的過程與組合優(yōu)化的問題具有一定的相似性,故而將模擬退火算法應用到一系列組合優(yōu)化問題中,如表1是組合優(yōu)化問題和模擬退火算法的對應關系。

表1 降溫函數初始化參數

表1 過程對應關系表

模擬退火算法首先設定當前解為初始值,通過降溫產生新解,通過比較新解和初始解的適應度函數,按照Metropolis準則[12]對新解進行一定概率的接受,達到終止溫度則停止迭代。

3 解決旅行商問題的模擬退火算法

3.1 改進的模擬退火算法

模擬退火算法的主要組成要素分別是狀態(tài)產生函數、狀態(tài)接受函數、降溫函數、熱平衡穩(wěn)定準則、退火結束準則、初始溫度的選取。本文針對旅行商問題的特性,對算法的降溫函數進行改進,降溫函數是控制溫度下降的方式,溫度的大小是算法的搜索能力的體現,當溫度較高時,算法進行廣域搜索;當溫度較低時,算法進行局域搜索。溫度下降較快導致算法從廣域搜索直接進入局域搜索,這將使得當前狀態(tài)的解無法得到驗證,進而無法找到全局最優(yōu)解。當溫度下降過慢時,算法局域搜索能力較弱,將會漏掉很多可行解。常用的降溫方式有以下兩種:

第一種:T=T*a,其中a是退火率,a的大小決定溫度下降的速度,在算法迭代的過程中,都是按照線性遞減的規(guī)律進行變化的。

第二種:T=T-ΔT,ΔT是每次溫度下降的幅度,可以事先控制溫度下降的總次數,之后依次遞減。

基于第一種溫度的下降方式修改溫度下降函數為如下形式

T0=T0*α

(1)

T=T0*(1+cos(t*pi/gapIter)

(2)

其中T0表示初始溫度,T表示變化后的溫度,α為降溫系數,t迭代次數,gapIter表示浮動的間隔數。

3.2 大規(guī)模鄰域搜索

模擬退火算法產生新解的步驟中引入大規(guī)模鄰域搜索算法[13](Large Neighborhood Search,LNS)。如圖2所示,初始解空間為3-5-1-8-7-2-6-4,首先對初始解空間進行破壞移除城市,移除的城市數是隨機的,本文設置為1～N/3(N為城市總數)。在圖2中破壞選擇移除的是城市1和城市6,把選中的城市從初始解空間中拿掉,剩下的按照初始解依次排序為破壞解空間:3-5-8-7-2-4。最后進行修復,對破壞解空間進行處理,例如圖2選擇城市1重新插入破壞解空間中,第一次插入后的結果為Sr,插入后的路徑為1-3-5-8-7-2-4,計算Sr的適度值f(Sr)并且記錄,因插入首尾效果相同,可以插入的位置為破壞解空間中的城市數量,分別計算插入不同位置的適度值,選擇適度值效果最好的進行輸出,之后把城市6插入新的破壞解空間中,直到所有移除的城市修復完成得到最終解空間,算法偽代碼如算法1所示。

圖2 大規(guī)模鄰域搜索算法的流程圖

Algorithm1:Large Neighborhood Search

Input:Original route Snow,destroy＿num

Output:New optimal path sequence＿repair

sequence＿random=random.permutation(Snow)

Sequence＿destroy ← sequence＿random[0: destroy＿num]

sequence＿remain← remove the Sequence＿destroy in Snow

remain＿num ← len(Sd)

for j in range(0,destroy＿num):

for i in range(0,remain＿num+1):

if i==1:

sequence＿remain＿temp ← [Sequence＿destroy[j]+sequence＿remain]

else:

sequence＿remain＿one ←sequence＿remain [0:i-1]

sequence＿remain＿two ←sequence＿remain [i-1:]

sequence＿remain＿temp ← sequence＿remain＿one+[ sequence＿destroy[j]]+sequence＿remain＿two

len＿remain=fitness(sequence＿remain＿temp)

if i==1:

len＿remain＿best ←len＿remain

Sbest ←sequence＿remain＿temp

else:

if len＿remain

len＿remain＿best ←len＿remain

Sbest ←sequence＿remain＿temp

sequence＿remain ← sequence＿remain＿temp

3.3 局部搜索算子2-opt

2-opt是一種隨機性算法,基本思想就是隨機選擇兩個元素進行優(yōu)化,在求解TSP問題中得到了廣泛的應用。如圖3所示,路徑為C1,C2,…,Cn,其中d(Ci,Cj)表示城市Ci和城市Cj之間的距離,圖3為2-opt思想實例。如果條件d(Ci,Cj)+d(Ci+1,Cj+1)

圖3 2-opt過程圖

Algorithm2:2opt algorithm

Input:Original route R=(c1,…,ci,ci+1,…,cj,cj+1,…,cn)

Output:new shorter route R′=(c1,…,ci,cj,…,ci+1,cj+1,…,cn)

Best＿distance ← fitness(R)

for i in range(1,n-1):

for j in range(1,n-1):

if |j-(i+1)| >2:

速凍。保證冷凍食品食物感覺處于良好狀態(tài)極為重要，為實現該目標，在冷凍食品時主要可以應用兩種方法：一種為快速凍結，另一種為深度凍結。同時嚴格控制凍結溫度，使其位于-35℃-45℃。設定一定時間限制，通常為30秒，使中心溫度上升到-18℃。

New＿route ← 2opt(Current＿route,i,j)

New＿distance ←fitness(New＿route)

if New＿distance

Current＿route ← New＿route

Best＿distance ← New＿distance

Return Current＿route

3.4 交換和插入

本文使用交換和插入兩種操作來增加鄰域結構,作用是防止進入局部最優(yōu),并且輪盤賭算法的方式來選擇使用交換,插入和LNS。交換和插入概率設置高可以減少時間復雜度和提高局部搜索能力,交換和插入兩種操作介紹如下:

例如當前城市路徑為:

1→3→4→6→2→7→8→5

1)交換操作

隨機選擇兩個城市進行交換修改路徑,如果選擇的城市是3和7,那么變換后的城市序列為:1→7→4→6→2→3→8→5

2)插入操作

隨機選取兩個城市,選中進行插入操作的為i=3和j=7,進行判斷如果i

1→4→6→2→7→3→8→5

3.5 算法流程

綜上所述,本文算法步驟如下:

1)初始化迭代次數,交換概率P,初始化溫度等參數;

2)貪婪策略初始化;

3)計算適應度值,記錄最優(yōu)路徑Pbest和最優(yōu)距離Lbest;

4)對當前路徑根據輪盤賭策略以一定的概率選擇執(zhí)行交換,插入和LNS操作產生新的路徑Pnew;

5)比較兩次路徑的適應度值之差,f(Pnew) <=f(Pbest),則Pbest=Pnew;否則,按照Metropolis準則進行更新;

6)根據式(1)和(2)更新溫度,執(zhí)行2-opt優(yōu)化;

7)判斷是否達到結束條件,如果沒有達到執(zhí)行4)～6),達到結束條件輸出結果。

4 數值實驗

為了檢測大規(guī)模鄰域搜索的模擬退火算法(simulated annealing algorithm with large neighborhood search,SALNS)的性能,使用TSPLIB中標準數據集作為實驗數據進行測試。實驗環(huán)境為:Python3.8,Inter(R)i7-9750H 2.60GHz,內存為16GB的PC進行實驗分析。過程中交換概率設為0.4,插入概率設為0.5,LNS概率設為0.1。表中已知最優(yōu)解,最優(yōu)解和平均解分別用Hbest,Best和Avg表示。

4.1 改進的模擬退火算法降溫曲線模擬

首先針對改進的降溫函數進行測試,在本文函數的測試中選擇標準降溫、快速降溫[14]和本文降溫函數進行效果對比,初始條件和降溫函數如表1,降溫曲線如圖4下所示。

圖4 降溫曲線對比圖

由圖4中可知,快速降溫可以在較少的迭代次數達到低溫狀態(tài),過早的達到了低溫狀態(tài)使得后續(xù)多次迭代做無效功。標準降溫在多次迭代依舊無法達到低溫狀態(tài),達到低溫狀態(tài)需要的迭代次數過多。然而本文降溫曲線圖很好的結合二者的優(yōu)點,同時規(guī)避了缺點,降溫的速度剛好,在整個退火過程中出現回火升溫的過程,算法就可以在該點跳出局部最優(yōu),從而更有機會找到全局最優(yōu)解。多次降溫增加算法的記憶功能,能夠保持最優(yōu)解。

4.2 改進的模擬退火算法性能測試

在本節(jié)選取經典的粒子群算法(PSO)、遺傳算法(GA) 、模擬退火算法(SA)和SALNS在數據集Att48和KroA100運行相同時間做了一個對比,對比時間和最終解如表2所示。四種算法使用貪婪策略初始解提高算法的效率,四種算法對比圖如圖5和圖6。

表2 對比時間和最終解

圖5 att48時間對比圖

圖6 kroA100時間對比圖

圖5,6中,橫坐標為時間,縱坐標為距離的總和,由圖5可知,在Att48數據集中,SALNS在第7s找到已知最優(yōu)解,遺傳算法早早的收斂陷入局部最優(yōu),而粒子群算法和模擬退火算法和已知最優(yōu)解相差過大。由圖6可知,在KroA100數據集中,SALNS在第23s找到已知最優(yōu)解,遺傳算法在11s陷入了局部最優(yōu),粒子群算法和模擬退火算法迭代時間過長結果較差。結果可知,SALNS在收斂速度和尋優(yōu)能力方面均優(yōu)于所對比的三種經典啟發(fā)式算法。

4.3 SALNS與IACOPSO對比

將SALNS獨立運行10次與IACOPSO[15]求解質量對比如表3所示。

表3 SALNS與IACOPSO對比結果

從表3可知共測試5個數據集,IACOPSO算法只獲取了Burma14和Oliver30這兩個數據集最優(yōu)解,而SALNS獲取了全部數據集的已知最優(yōu)解;從均值來看IACOPSO算法只在Burma14數據集中達到已知最優(yōu)解,而SALNS除Ch130數據集外均值都達到已知最優(yōu)解,Ch130數據集的均值比IACOPSO算法最優(yōu)解效果好。

4.4 大規(guī)模數據實驗

將SALNS獨立運行10次與文獻一[16]求解大規(guī)模數據集質量對比如表4所示。

表4 SALNS在大規(guī)模數據集對比結果

從表4可知共測試8個大規(guī)模數據集進行實驗,文獻一最優(yōu)解都接近已知最優(yōu)解,而且Tsp225數據集優(yōu)于已知最優(yōu)解,而SALNS得到了6個實驗數據的已知最優(yōu)解,在數據集Tsp225中最優(yōu)解優(yōu)于文獻一和已知最優(yōu)解,并且Tsp225的均值優(yōu)于已知最優(yōu)解。

選取Eil51、Ch130、KroA200和Tsp225數據集最優(yōu)解路徑如圖7～圖10所示。

圖7 Eil51最優(yōu)路徑圖

圖8 Ch130最優(yōu)路徑圖

圖9 KroA200最優(yōu)路徑圖

圖10 Tsp225最優(yōu)路徑圖

5 總結

本文針對旅行商問題的特性,在模擬退火算法的基礎上,修改降溫函數,降溫函數是控制溫度下降的方式,溫度的大小關乎算法的搜索能力,改進后的降溫函數可以很好的跳出局部最優(yōu)解。同時采用在產生新解的過程中采用隨機選擇產生方式,使用交換和插入來增加鄰域結構,作用是防止進入局部最優(yōu),并且輪盤賭算法的方式來選擇使用交換,插入和LNS,之后通過2-opt優(yōu)化解空間。通過實驗仿真證明,SALNS修改的降溫函數效果得到了很大的提高,求解質量相較于三種經典的啟發(fā)式算法較好,同時和當前較新改進的算法比較,收斂速度快,求解質量高。