開源算法框架Open Tabu Search怎么編寫VRPTW的JAVA代碼

Open TS算法框架

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

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

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

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

 

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

 

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

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

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

二次開發(fā)

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

1. SolutionAdapter

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

private double[] objectiveValue;

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

2. TabuSearchListener

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

public void newBestSolutionFound(TabuSearchEvent event) {}

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

public void newCurrentSolutionFound(TabuSearchEvent event) {}

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

public void tabuSearchStarted(TabuSearchEvent event) {

算法開始時觸發(fā)的事件。

public void tabuSearchStopped(TabuSearchEvent event) {}

算法結(jié)束時觸發(fā)的事件。

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

3. ObjectiveFunction

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

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

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

 

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

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

4. ComplexMove

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

public abstract void operateOn( Solution soln );

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

public abstract int[] attributesDelete();

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

public abstract int[] attributesInsert();

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

5. MoveManager

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

public Move[] getAllMoves( Solution solution ) { }

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

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

6. ComplexTabuList

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

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

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

實例

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

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

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

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

如何實現(xiàn)一個高效的啟發(fā)式算法？（VRPTW篇）

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

 

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

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

 

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