干貨 | 自適應(yīng)大鄰域搜索(ALNS)和禁忌搜索(TS)實(shí)驗(yàn)對(duì)比附代碼
文案?周航
審核修改 鄧發(fā)珩
前言
公眾號(hào)的老觀眾們應(yīng)該會(huì)記得，在去年這個(gè)時(shí)候我們公眾號(hào)發(fā)布了有關(guān)自適應(yīng)大領(lǐng)域搜索算法（adaptive large neighborhood search）的相關(guān)系列教程，有關(guān)傳送門如下：
1.?干貨 | 自適應(yīng)大鄰域搜索(Adaptive Large Neighborhood Search)入門到精通超詳細(xì)解析-概念篇2.?代碼 | 自適應(yīng)大鄰域搜索系列之(1) - 使用ALNS代碼框架求解TSP問(wèn)題3.?代碼 | 自適應(yīng)大鄰域搜索系列之(2) - ALNS算法主邏輯結(jié)構(gòu)解析
4.?代碼 | 自適應(yīng)大鄰域搜索系列之(3) - Destroy和Repair方法代碼實(shí)現(xiàn)解析5.?代碼 | 自適應(yīng)大鄰域搜索系列之(4) - Solution定義和管理的代碼實(shí)現(xiàn)解析
6. 代碼 | 自適應(yīng)大鄰域搜索系列之(5) - ALNS_Iteration_Status和ALNS_Parameters的代碼解析
7.?代碼 | 自適應(yīng)大鄰域搜索系列之(6) - 判斷接受準(zhǔn)則SimulatedAnnealing的代碼解析
8. 代碼 | 自適應(yīng)大鄰域搜索系列之(7) - 局部搜索LocalSearch的代碼解
9.?自適應(yīng)大鄰域 | 用ALNS框架求解一個(gè)TSP問(wèn)題 - 代碼詳解
當(dāng)時(shí)，為了調(diào)用MinGW庫(kù)，我們還特地做了一份安裝教程。但教程中安裝庫(kù)的過(guò)程比較繁瑣，尤其是對(duì)平時(shí)習(xí)慣使用VS而不是dev C++的觀眾來(lái)說(shuō)，又要?jiǎng)邮窒螺ddev C++，不太方便。
對(duì)于有點(diǎn)編程基礎(chǔ)的同學(xué)還好，照著葫蘆總能畫出一個(gè)瓢來(lái)：
emmm……而對(duì)于不熟悉編程的同學(xué)而言，一頓操作猛如虎：
為了造福人類，這次小編為大家?guī)?lái)了VS版本的ALNS框架，只需要下載處理好的項(xiàng)目文件導(dǎo)入VS中就可以直接運(yùn)行啦！
代碼運(yùn)行
習(xí)慣使用dev C++的同學(xué)，可以直接參考過(guò)去的推文，安裝MinGW庫(kù)，再在dev C++上運(yùn)行。
對(duì)使用VS的同學(xué)，直接從公眾號(hào)中下載代碼，用VS打開.sin文件就行啦！在公眾號(hào)內(nèi)輸入【ALNSTSPVS】不帶【】即可下載相關(guān)代碼！如圖：
怎樣，是不是跟在床上翻一個(gè)身一樣簡(jiǎn)單呢？不過(guò)你的VS版本要>=2015哦。
這次提供給大家的代碼中，除了已經(jīng)搭建好的ALNS的框架（來(lái)自Github，一個(gè)法國(guó)的PHD寫的，原地址：https://github.com/biblik/alns-framework），還有編寫的利用ALNS框架求解TSP的代碼（代碼經(jīng)過(guò)小舟同學(xué)修改），并包含幾個(gè)TSP算例：
圖中箭頭標(biāo)注的.xml文件用于參數(shù)修改。箭頭指向的是幾個(gè)重要參數(shù)，用于設(shè)置搜索停止條件，分別代表迭代次數(shù)、運(yùn)行時(shí)間、未能優(yōu)化當(dāng)前解的最大迭代次數(shù)。任意一項(xiàng)指標(biāo)超過(guò)設(shè)置參數(shù)時(shí)，程序停止運(yùn)行：
算例在main.cpp中輸入，在圖示位置輸入算例名稱：
如果要導(dǎo)入自己的算例，將算例放置到工程文件目錄下，保證算例格式與所給算例一樣，就可以運(yùn)行啦！
簡(jiǎn)單實(shí)驗(yàn)
關(guān)于ALNS的介紹，過(guò)去已經(jīng)有相關(guān)推文做了詳細(xì)解讀。這里我們對(duì)ALNS求解TSP的結(jié)果進(jìn)行簡(jiǎn)單實(shí)驗(yàn)，看一看算法的實(shí)際運(yùn)行效果。
測(cè)試算例采用TSPLIB提供的TSP算例，可以在公眾號(hào)菜單【資源下載-算例下載】一欄進(jìn)行下載。
我們先將ALNS與Tabu Search進(jìn)行簡(jiǎn)單對(duì)比，關(guān)于Tabu Search的傳送門：
干貨|十分鐘快速?gòu)?fù)習(xí)禁忌搜索(c++版)
對(duì)比結(jié)果如下：
經(jīng)過(guò)簡(jiǎn)單的測(cè)試發(fā)現(xiàn)，ALNS代碼運(yùn)行的時(shí)間比禁忌搜索算法更長(zhǎng)一些。并且兩種算法得出的滿意解與最優(yōu)解都有一些差距，所以我們?cè)黾幼畲蟮螖?shù)，看一看兩種算法能更精確到什么程度：
可以看到,增加迭代次數(shù)，ALNS會(huì)得到更優(yōu)的滿意解，而TS可能早就陷入了局部最優(yōu)，已經(jīng)無(wú)法繼續(xù)得到更優(yōu)的解了。我們選擇算例rd400，進(jìn)一步測(cè)試ALNS的運(yùn)行情況：
從上面的結(jié)果可以看出：ALNS通過(guò)增加迭代次數(shù)，是能更好的逼近最優(yōu)解的。不過(guò)所需要的時(shí)間也相應(yīng)會(huì)增加。
經(jīng)過(guò)比較可以看出，ALNS收斂的速度較慢，因?yàn)槠渌阉鞯泥徲蚴欠浅４蟮?/strong>，其達(dá)到滿意解所需的搜索時(shí)間要更久。但正是由于其搜索的鄰域巨大，在此過(guò)程中不容易過(guò)早陷入局部最優(yōu)，增加搜索時(shí)間是有更大概率找到更好的解。
而TS搜索的鄰域相對(duì)ALNS較小（和測(cè)試代碼的鄰域結(jié)構(gòu)有關(guān)），不過(guò)，這里說(shuō)的鄰域相對(duì)較小，并不一定指TS搜索鄰域一定比ALNS小，你也可以通過(guò)鄰域結(jié)構(gòu)的設(shè)計(jì)，搞得很大很大。
但一般而言，ALNS的鄰域規(guī)模都大一些，畢竟他就是以大規(guī)模鄰域著稱的。在本那次代碼中，由于TS只設(shè)計(jì)了一個(gè)鄰域算子，因此收斂的速度非常快，但也過(guò)早陷入了局部最優(yōu)。
當(dāng)然，以上測(cè)試非常簡(jiǎn)單，反應(yīng)出兩種算法的不同特點(diǎn)還不夠準(zhǔn)確，因?yàn)閷?shí)際運(yùn)行過(guò)程建立在代碼的基礎(chǔ)上，比如對(duì)禁忌搜索而言，算子設(shè)計(jì)的個(gè)數(shù)、優(yōu)劣會(huì)影響解的精確度；是否進(jìn)行去重優(yōu)化會(huì)影響搜索速度。對(duì)ALNS，代碼中設(shè)計(jì)了local search，因此搜索速度會(huì)略慢一些，但優(yōu)化程度會(huì)有所提升。
寫在后面
ALNS相對(duì)比較復(fù)雜，尤其是我們提供的代碼框架非常完善，綜合了模擬退火、變鄰域搜索的一些特點(diǎn)，要弄清楚并不容易。在接下來(lái)的一段時(shí)間里，小編也會(huì)和大家一起進(jìn)一步研究ALNS，為大家?guī)?lái)一些ALNS相關(guān)的文章，希望大家多多關(guān)注~
在公眾號(hào)內(nèi)輸入【ALNSTSPVS】不帶【】即可下載相關(guān)代碼！
評(píng)論
圖片
表情