乾貨 | 自適應大鄰域搜索(ALNS)和禁忌搜索(TS)實驗對比附程式碼

  • 2020 年 2 月 26 日
  • 筆記

前言

大家好呀,你們帥氣的小編又回來啦!

公眾號的老觀眾們應該會記得,在去年這個時候我們公眾號發布了有關自適應大領域搜索演算法(adaptive large neighborhood search)的相關係列教程,有關傳送門如下:

1. 乾貨 | 自適應大鄰域搜索(Adaptive Large Neighborhood Search)入門到精通超詳細解析-概念篇

2. 程式碼 | 自適應大鄰域搜索系列之(1) – 使用ALNS程式碼框架求解TSP問題

3. 程式碼 | 自適應大鄰域搜索系列之(2) – ALNS演算法主邏輯結構解析

4. 程式碼 | 自適應大鄰域搜索系列之(3) – Destroy和Repair方法程式碼實現解析

5. 程式碼 | 自適應大鄰域搜索系列之(4) – Solution定義和管理的程式碼實現解析

6. 程式碼 | 自適應大鄰域搜索系列之(5) – ALNS_Iteration_Status和ALNS_Parameters的程式碼解析

7. 程式碼 | 自適應大鄰域搜索系列之(6) – 判斷接受準則SimulatedAnnealing的程式碼解析

8. 程式碼 | 自適應大鄰域搜索系列之(7) – 局部搜索LocalSearch的程式碼解

9. 自適應大鄰域 | 用ALNS框架求解一個TSP問題 – 程式碼詳解

當時,為了調用MinGW庫,我們還特地做了一份安裝教程。但教程中安裝庫的過程比較繁瑣,尤其是對平時習慣使用VS而不是dev C++的觀眾來說,又要動手下載dev C++,不太方便。

對於有點編程基礎的同學還好,照著葫蘆總能畫出一個瓢來:

emmm……而對於不熟悉編程的同學而言,一頓操作猛如虎:

為了造福人類,這次小編為大家帶來了VS版本的ALNS框架,只需要下載處理好的項目文件導入VS中就可以直接運行啦!

程式碼運行

習慣使用dev C++的同學,可以直接參考過去的推文,安裝MinGW庫,再在dev C++上運行。

對使用VS的同學,直接從公眾號中下載程式碼,用VS打開.sin文件就行啦!在公眾號內輸入【ALNSTSPVS】不帶【】即可下載相關程式碼!如圖:

怎樣,是不是跟在床上翻一個身一樣簡單呢?不過你的VS版本要>=2015哦。

這次提供給大家的程式碼中,除了已經搭建好的ALNS的框架(來自Github,一個法國的PHD寫的,原地址:https://github.com/biblik/alns-framework),還有編寫的利用ALNS框架求解TSP的程式碼(程式碼經過小舟同學修改),並包含幾個TSP算例:

圖中箭頭標註的.xml文件用於參數修改。箭頭指向的是幾個重要參數,用於設置搜索停止條件,分別代表迭代次數、運行時間、未能優化當前解的最大迭代次數。任意一項指標超過設置參數時,程式停止運行:

算例在main.cpp中輸入,在圖示位置輸入算例名稱:

如果要導入自己的算例,將算例放置到工程文件目錄下,保證算例格式與所給算例一樣,就可以運行啦!

簡單實驗

關於ALNS的介紹,過去已經有相關推文做了詳細解讀。這裡我們對ALNS求解TSP的結果進行簡單實驗,看一看演算法的實際運行效果。

測試算例採用TSPLIB提供的TSP算例,可以在公眾號菜單【資源下載-算例下載】一欄進行下載。

我們先將ALNSTabu Search進行簡單對比,關於Tabu Search的傳送門:

乾貨|十分鐘快速複習禁忌搜索(c++版)

對比結果如下:

經過簡單的測試發現,ALNS程式碼運行的時間比禁忌搜索演算法更長一些。並且兩種演算法得出的滿意解與最優解都有一些差距,所以我們增加最大迭代次數,看一看兩種演算法能更精確到什麼程度:

可以看到,增加迭代次數,ALNS會得到更優的滿意解,而TS可能早就陷入了局部最優,已經無法繼續得到更優的解了。我們選擇算例rd400,進一步測試ALNS的運行情況:

從上面的結果可以看出:ALNS通過增加迭代次數,是能更好的逼近最優解的。不過所需要的時間也相應會增加。

經過比較可以看出,ALNS收斂的速度較慢,因為其搜索的鄰域是非常大的,其達到滿意解所需的搜索時間要更久。但正是由於其搜索的鄰域巨大,在此過程中不容易過早陷入局部最優,增加搜索時間是有更大概率找到更好的解。

而TS搜索的鄰域相對ALNS較小(和測試程式碼的鄰域結構有關),不過,這裡說的鄰域相對較小,並不一定指TS搜索鄰域一定比ALNS小,你也可以通過鄰域結構的設計,搞得很大很大。

但一般而言,ALNS的鄰域規模都大一些,畢竟他就是以大規模鄰域著稱的。在本那次程式碼中,由於TS只設計了一個鄰域運算元,因此收斂的速度非常快,但也過早陷入了局部最優。

當然,以上測試非常簡單,反應出兩種演算法的不同特點還不夠準確,因為實際運行過程建立在程式碼的基礎上,比如對禁忌搜索而言,運算元設計的個數、優劣會影響解的精確度;是否進行去重優化會影響搜索速度。對ALNS,程式碼中設計了local search,因此搜索速度會略慢一些,但優化程度會有所提升。

寫在後面

ALNS相對比較複雜,尤其是我們提供的程式碼框架非常完善,綜合了模擬退火、變鄰域搜索的一些特點,要弄清楚並不容易。在接下來的一段時間裡,小編也會和大家一起進一步研究ALNS,為大家帶來一些ALNS相關的文章,希望大家多多關注~

在公眾號內輸入【ALNSTSPVS】不帶【】即可下載相關程式碼!

贊 賞

–The End—

文案 && 編輯:周航

審稿&&修正:鄧發珩(華中科技大學管理學院)

指導老師:秦時明岳(華中科技大學管理學院)


如對文中內容有疑問,歡迎交流。PS:部分資料來自網路。