一、前言

很早之前就想寫這篇文章了，由于各種不可描述的原因拖延到了現(xiàn)在，今兒就把坑給填上吧~

前排提示：小伙伴們可以收藏下這篇文章哦，說不定那天你們就用上了。因?yàn)檎娴氖呛芨韶浥叮?/p>

二、Open TS算法框架

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

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

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

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

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

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

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

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

三、二次開發(fā)

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

1. SolutionAdapter

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

private?double[]?objectiveValue;

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

2. TabuSearchListener

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

public?void?newBestSolutionFound(TabuSearchEvent?event)?{}

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

public?void?newCurrentSolutionFound(TabuSearchEvent?event)?{}

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

public?void?tabuSearchStarted(TabuSearchEvent?event)?{

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

public?void?tabuSearchStopped(TabuSearchEvent?event)?{}

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

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

3. ObjectiveFunction

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

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

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

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

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

4. ComplexMove

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

public?abstract?void?operateOn(?Solution?soln?);

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

public?abstract?int[]?attributesDelete();

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

public?abstract?int[]?attributesInsert();

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

5. MoveManager

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

public?Move[]?getAllMoves(?Solution?solution?)?{?}

這個(gè)方法是需要我們自己實(shí)現(xiàn)的，而且非常重要，因?yàn)檫@里定義了我們?cè)O(shè)計(jì)的算子所生成的move集合。

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

6. ComplexTabuList

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

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

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

四、實(shí)例

好了以上就是一些簡單的介紹，當(dāng)然這樣介紹可能大家沒什么感覺，因?yàn)檫@東西在沒有對(duì)代碼有一個(gè)很好的全局掌控之前，很難體會(huì)到其中的精髓，反而很多人因?yàn)槠渲芯薮蟮拇a量感覺極為繁瑣。

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

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

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

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

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

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

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

當(dāng)然啦，你也可以修改框架中的代碼以達(dá)到更多個(gè)性化的功能，不過我是不太推薦這樣做的，因?yàn)閯e人封裝好的東西，你一整的話，出錯(cuò)了都不知道去哪里找。不過熟悉以后可以嘗試修改一下底層的代碼。我就對(duì)那個(gè)tabu list進(jìn)行了修改，因?yàn)楦杏X給的那個(gè)不是很好用吧~

五、代碼下載

我把修改過的代碼放在了GitHub上，地址為

https://github.com/dengfaheng/omatest

好了，大家可以慢慢去看代碼了。。。have a nice day！看在小編這么勤勞的份上，幫我點(diǎn)個(gè)在看唄~萬一你的老板喜歡看微信的看一看，看到你又在微信上學(xué)習(xí)代碼，ta肯定要高興得不得了呀！你就可以大膽告訴他：

??????