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

孫 鑒,劉凇佐,武曉曉

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

1 引言

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

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

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

2 基本知識(shí)

2.1 基本的模擬退火算法

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

圖1 物理退火和淬火過(guò)程圖示

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

表1 降溫函數(shù)初始化參數(shù)

表1 過(guò)程對(duì)應(yīng)關(guān)系表

模擬退火算法首先設(shè)定當(dāng)前解為初始值,通過(guò)降溫產(chǎn)生新解,通過(guò)比較新解和初始解的適應(yīng)度函數(shù),按照Metropolis準(zhǔn)則[12]對(duì)新解進(jìn)行一定概率的接受,達(dá)到終止溫度則停止迭代。

3 解決旅行商問(wèn)題的模擬退火算法

3.1 改進(jìn)的模擬退火算法

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

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

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

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

T0=T0*α

(1)

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

(2)

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

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

模擬退火算法產(chǎn)生新解的步驟中引入大規(guī)模鄰域搜索算法[13](Large Neighborhood Search,LNS)。如圖2所示,初始解空間為3-5-1-8-7-2-6-4,首先對(duì)初始解空間進(jìn)行破壞移除城市,移除的城市數(shù)是隨機(jī)的,本文設(shè)置為1～N/3(N為城市總數(shù))。在圖2中破壞選擇移除的是城市1和城市6,把選中的城市從初始解空間中拿掉,剩下的按照初始解依次排序?yàn)槠茐慕饪臻g:3-5-8-7-2-4。最后進(jìn)行修復(fù),對(duì)破壞解空間進(jìn)行處理,例如圖2選擇城市1重新插入破壞解空間中,第一次插入后的結(jié)果為Sr,插入后的路徑為1-3-5-8-7-2-4,計(jì)算Sr的適度值f(Sr)并且記錄,因插入首尾效果相同,可以插入的位置為破壞解空間中的城市數(shù)量,分別計(jì)算插入不同位置的適度值,選擇適度值效果最好的進(jìn)行輸出,之后把城市6插入新的破壞解空間中,直到所有移除的城市修復(fù)完成得到最終解空間,算法偽代碼如算法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是一種隨機(jī)性算法,基本思想就是隨機(jī)選擇兩個(gè)元素進(jìn)行優(yōu)化,在求解TSP問(wèn)題中得到了廣泛的應(yīng)用。如圖3所示,路徑為C1,C2,…,Cn,其中d(Ci,Cj)表示城市Ci和城市Cj之間的距離,圖3為2-opt思想實(shí)例。如果條件d(Ci,Cj)+d(Ci+1,Cj+1)

圖3 2-opt過(guò)程圖

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:

速凍。保證冷凍食品食物感覺(jué)處于良好狀態(tài)極為重要，為實(shí)現(xiàn)該目標(biāo)，在冷凍食品時(shí)主要可以應(yīng)用兩種方法：一種為快速凍結(jié)，另一種為深度凍結(jié)。同時(shí)嚴(yán)格控制凍結(jié)溫度，使其位于-35℃-45℃。設(shè)定一定時(shí)間限制，通常為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 交換和插入

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

例如當(dāng)前城市路徑為:

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

1)交換操作

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

2)插入操作

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

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

3.5 算法流程

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

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

2)貪婪策略初始化;

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

4)對(duì)當(dāng)前路徑根據(jù)輪盤(pán)賭策略以一定的概率選擇執(zhí)行交換,插入和LNS操作產(chǎn)生新的路徑Pnew;

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

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

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

4 數(shù)值實(shí)驗(yàn)

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

4.1 改進(jìn)的模擬退火算法降溫曲線模擬

首先針對(duì)改進(jìn)的降溫函數(shù)進(jìn)行測(cè)試,在本文函數(shù)的測(cè)試中選擇標(biāo)準(zhǔn)降溫、快速降溫[14]和本文降溫函數(shù)進(jìn)行效果對(duì)比,初始條件和降溫函數(shù)如表1,降溫曲線如圖4下所示。

圖4 降溫曲線對(duì)比圖

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

4.2 改進(jìn)的模擬退火算法性能測(cè)試

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

表2 對(duì)比時(shí)間和最終解

圖5 att48時(shí)間對(duì)比圖

圖6 kroA100時(shí)間對(duì)比圖

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

4.3 SALNS與IACOPSO對(duì)比

將SALNS獨(dú)立運(yùn)行10次與IACOPSO[15]求解質(zhì)量對(duì)比如表3所示。

表3 SALNS與IACOPSO對(duì)比結(jié)果

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

4.4 大規(guī)模數(shù)據(jù)實(shí)驗(yàn)

將SALNS獨(dú)立運(yùn)行10次與文獻(xiàn)一[16]求解大規(guī)模數(shù)據(jù)集質(zhì)量對(duì)比如表4所示。

表4 SALNS在大規(guī)模數(shù)據(jù)集對(duì)比結(jié)果

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

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

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

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

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

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

5 總結(jié)

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