Open TS算法框架

做元啟發式的小伙伴都知道，一開始需要學習一些固定的算法框架，這是理論基礎。有了理論基礎以后就可以針對各種奇奇怪怪問題把這些算法框架給套上去，總能跑出一些結果，無論是好的差的。

經常有很多人來問我，這個問題用什么算法比較好啊？那個問題用什么框架比較合適？一開始我還很耐心的跟他們扯淡說：沒有最好的，只有更好的。。。其實不是的，按照我這幾年做啟發式的經驗來說，算法框架這東西其實吧，只要是一個類別的，基本都不會有太大差別（比如TS和SA、LNS和ALNS、GA和AFAS等等）。我們做算法開發的時候，更應該把重心放在一些問題特性的推導，或者搜索算子的思考上。

好了又扯遠了……今天的主題是分享一份代碼，一個開源的Tabu Search框架，以及如何利用該框架進行二次開發。先介紹下今天的主角：Open TS。這個是由Robert Harder開發的一個基于java平臺tabu search算法框架。用他的話說就是：

Use these classes to help build a  structured and efficient Java tabu search.

 

該package包含了實現一個tabu search框架需要的各種元素，可以說得上非常全面了。大家在編寫tabu search相關的算法時，只需要extend相關的class或者implements相關的interface即可。

 

這就使得我們可以將更多的時間和精力放在算子的設計以及其他問題特性的考慮上，而不是將大量的時間浪費在維護算法框架上。當然了，這個框架由于考慮了很多general的東西，同時也做了很多額外的異常處理什么的從而使得代碼更為健壯。thus，代碼的速度可能就會有一點點損失。

嗯……我這里指的損失是相對那種超級大神級別的人來說的，畢竟他們寫代碼會把各種冗余的計算去掉，把所有的可能slow down算法速度的因素都杜絕掉，恨不得直接用匯編寫的那種……咱這些普通打工人也還沒到那么牛逼的地步嘛！

總之，這個算法框架還是非常牛逼的，平時擼擼論文，做做項目直接拿來做二次開發也是一個不錯的選擇啦。

二次開發

其實上面給了很多類，但是對于一個單線程的tabu search來說，并不需要用到所有的class，只需要繼承一些基本的元素，然后針對你的問題將他們special化就行啦。下面我介紹下二次開發的要實現的一些東西吧。

1. SolutionAdapter

求解任何問題，首先還是要定義該問題的solution結構了。只需要extend Open TS的SolutionAdapter類即可，該類中只有一個成員變量為：

private double[] objectiveValue;

為該解的目標值向量，然后你就可以在你自己的solution中定義問題的其他變量了。比如存儲路徑啊，解的其他中間變量等等。

2. TabuSearchListener

該類呢為接口類，里面有幾個抽象方法需要實現的，分別為：

public void newBestSolutionFound(TabuSearchEvent event) {}

找到一個全局最優解時，要做的事情可以寫在里面。

public void newCurrentSolutionFound(TabuSearchEvent event) {}

找到一個新的當前解時要做的事情可以寫在這個函數。

public void tabuSearchStarted(TabuSearchEvent event) {

算法開始時觸發的事件。

public void tabuSearchStopped(TabuSearchEvent event) {}

算法結束時觸發的事件。

基本上重新寫一下上面幾個抽象方法就可以滿足大部分的需求了。當然里面也定義了一些nonimprove相關的時間，可以作為shake使用。

3. ObjectiveFunction

該interface比較重要，繼承以后需要實現下面這個抽象方法：

public double[] evaluate(Solution solution, Move proposedMove) {}

它表示評估當前解solution經過proposedMove以后形成的鄰居解的目標值向量，就是前面SolutionAdapter中那個objectiveValue哦。這是什么意思呢，其實在算法實現中，我們一般不直接生成鄰居解，而是生成一個稱之為的東西，這是個什么東西呢，畫個圖：

 

其中我用紫色標出來的就是一個，簡單來說他記錄了生成鄰居解需要對當前解進行的一些操作，比如exchange(6, 15)。

因此每次生成鄰域時，可以先生成鄰居解對應的，然后去評估每個對應的鄰居解的cost，以比較各個鄰居解的好壞。

4. ComplexMove

為interface，該算法框架的鄰居解是通過當前解+move獲得的，因此你的問題中設計的operator算子需要實現該接口，它有一些抽象方法如下：

public abstract void operateOn( Solution soln );

該方法其實是更上一層extends來的，表示對該move對soln執行相應的操作，比如exchange(1, 2)或者relocate(1, 3)等等。

public abstract int[] attributesDelete();

執行該move時，刪除一個元素時返回的信息提供給tabu list記錄。比如{1,  3}表示exchange了1和3，那么tabu list就要記錄起來，防止后面的迭代中再進行exchange(1, 3)這樣的操作。

public abstract int[] attributesInsert();

執行該move時，插入一個元素時返回的信息提供給tabu list記錄。和刪除時類似的。

5. MoveManager

這也是一個interface，是不是很爽，只需要implements相關的接口即可完成一個算法，簡直不要太輕松！它的抽象方法只有一個：

public Move[] getAllMoves( Solution solution ) { }

這個方法是需要我們自己實現的，而且非常重要，因為這里定義了我們設計的算子所生成的move集合。

我覺得這個框架最好的地方就是這里了，他把所有的move都放在一起集中進行管理，后面進行約束變更的時候只需要修改這里的生成規則即可。比如客戶i不能插入路徑j，那么你在這里生成的時候就進行這些限制即可。

6. ComplexTabuList

這是一個類，表示tabu search中的禁忌表，里面有一個多維的tabu list可以記錄很多信息：

private int[][][][][] tabuList;      // Data structure used to store list

同時該類已經實現了setTabu和isTabu的方法。這兩個方法需要結合之前設置的attributesInsert()和attributesDelete()方法一起使用，如果做出修改那么需要修改相應的這幾部分，特別是tabu list要進行修改的話。。。

實例

好了以上就是一些簡單的介紹，當然這樣介紹可能大家沒什么感覺，因為這東西在沒有對代碼有一個很好的全局掌控之前，很難體會到其中的精髓，反而很多人因為其中巨大的代碼量感覺極為繁瑣。

畢竟用別人的東西，萬一出錯了都不知道怎么調。這里呢為了讓大家更好的熟悉這個框架，我貼上了一個使用該框架實現一個求解VRPTW問題的例子，這個代碼是來源于GitHub（好像是意大利都靈理工大學一些masters的課程大作業吧……）原鏈接為oma-vrptw。

https://github.com/oma-vrptw/oma-vrptw

這個代碼本身也有很多值得借鑒參考的地方的，比如它里面實現了一個relocate（代碼中叫SWPA MOVE，但是我覺得relocate更合適點）算子，在評估一個move的時候就用到了此前我們講過的以O(n)復雜度計算鄰居解的一些操作：

如何實現一個高效的啟發式算法？（VRPTW篇）

這個算子的效果還可以的，在Solomon的標準算例中C系列大部分能跑到最優，速度更是快得飛起。大家閱讀源碼時照著我上面貼出來的思路看即可。算例呢我也整合好了，我對源代碼做了一些修改，使得他能夠正常運行（不然待會又有很多人跑來問我代碼咋不能運行呢？），更改算例在以下位置即可更改。

 

單線程tabu search的主體呢是在SingleThreadedTabuSearch這個類中，執行一次迭代的邏輯都寫在了protected void performOneIteration()這個方法里面。

其實要寫的比較高效的話，每個算子生成的move都應該定制好自己單獨的evaluate函數，示例只寫了一個算子，如果move是由多個算子生成的話，需要判斷下move屬于哪個算子的，然后進行相應的evaluate，可以更改ObjectiveFunction的evaluate函數成如下形式：

 

當然啦，你也可以修改框架中的代碼以達到更多個性化的功能，不過我是不太推薦這樣做的，因為別人封裝好的東西，你一整的話，出錯了都不知道去哪里找。不過熟悉以后可以嘗試修改一下底層的代碼。我就對那個tabu list進行了修改，因為感覺給的那個不是很好用吧~