一、前言
很早之前就想寫這篇文章了，由于各種不可描述的原因拖延到了現在，今兒就把坑給填上吧~
前排提示：小夥伴們可以收藏下這篇文章哦，說不定那天你們就用上了。因為真的是很幹貨哦！
二、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進行了修改，因為感覺給的那個不是很好用吧~
五、代碼下載下傳
我把修改過的代碼放在了GitHub上，位址為
https://github.com/dengfaheng/omatest
好了，大家可以慢慢去看代碼了。。。have a nice day！看在小編這麼勤勞的份上，幫我點個在看呗~萬一你的老闆喜歡看微信的看一看，看到你又在微信上學習代碼，ta肯定要高興得不得了呀！你就可以大膽告訴他：