开源算法框架Open Tabu Search怎么编写VRPTW的JAVA代码

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进行了修改，因为感觉给的那个不是很好用吧~