干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码
文案 周航
审核修改 邓发珩
前言
公众号的老观众们应该会记得，在去年这个时候我们公众号发布了有关自适应大领域搜索算法（adaptive large neighborhood search）的相关系列教程，有关传送门如下：
1. 干货 | 自适应大邻域搜索(Adaptive Large Neighborhood Search)入门到精通超详细解析-概念篇2. 代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题3. 代码 | 自适应大邻域搜索系列之(2) - ALNS算法主逻辑结构解析
4. 代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析5. 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析
6. 代码 | 自适应大邻域搜索系列之(5) - ALNS_Iteration_Status和ALNS_Parameters的代码解析
7. 代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析
8. 代码 | 自适应大邻域搜索系列之(7) - 局部搜索LocalSearch的代码解
9. 自适应大邻域 | 用ALNS框架求解一个TSP问题 - 代码详解
当时，为了调用MinGW库，我们还特地做了一份安装教程。但教程中安装库的过程比较繁琐，尤其是对平时习惯使用VS而不是dev C++的观众来说，又要动手下载dev C++，不太方便。
对于有点编程基础的同学还好，照着葫芦总能画出一个瓢来：
emmm……而对于不熟悉编程的同学而言，一顿操作猛如虎：
为了造福人类，这次小编为大家带来了VS版本的ALNS框架，只需要下载处理好的项目文件导入VS中就可以直接运行啦！
代码运行
习惯使用dev C++的同学，可以直接参考过去的推文，安装MinGW库，再在dev C++上运行。
对使用VS的同学，直接从公众号中下载代码，用VS打开.sin文件就行啦！在公众号内输入【ALNSTSPVS】不带【】即可下载相关代码！如图：
怎样，是不是跟在床上翻一个身一样简单呢？不过你的VS版本要>=2015哦。
这次提供给大家的代码中，除了已经搭建好的ALNS的框架（来自Github，一个法国的PHD写的，原地址：https://github.com/biblik/alns-framework），还有编写的利用ALNS框架求解TSP的代码（代码经过小舟同学修改），并包含几个TSP算例：
图中箭头标注的.xml文件用于参数修改。箭头指向的是几个重要参数，用于设置搜索停止条件，分别代表迭代次数、运行时间、未能优化当前解的最大迭代次数。任意一项指标超过设置参数时，程序停止运行：
算例在main.cpp中输入，在图示位置输入算例名称：
如果要导入自己的算例，将算例放置到工程文件目录下，保证算例格式与所给算例一样，就可以运行啦！
简单实验
关于ALNS的介绍，过去已经有相关推文做了详细解读。这里我们对ALNS求解TSP的结果进行简单实验，看一看算法的实际运行效果。
测试算例采用TSPLIB提供的TSP算例，可以在公众号菜单【资源下载-算例下载】一栏进行下载。
我们先将ALNS与Tabu Search进行简单对比，关于Tabu Search的传送门：
干货|十分钟快速复习禁忌搜索(c++版)
对比结果如下：
经过简单的测试发现，ALNS代码运行的时间比禁忌搜索算法更长一些。并且两种算法得出的满意解与最优解都有一些差距，所以我们增加最大迭代次数，看一看两种算法能更精确到什么程度：
可以看到,增加迭代次数，ALNS会得到更优的满意解，而TS可能早就陷入了局部最优，已经无法继续得到更优的解了。我们选择算例rd400，进一步测试ALNS的运行情况：
从上面的结果可以看出：ALNS通过增加迭代次数，是能更好的逼近最优解的。不过所需要的时间也相应会增加。
经过比较可以看出，ALNS收敛的速度较慢，因为其搜索的邻域是非常大的，其达到满意解所需的搜索时间要更久。但正是由于其搜索的邻域巨大，在此过程中不容易过早陷入局部最优，增加搜索时间是有更大概率找到更好的解。
而TS搜索的邻域相对ALNS较小（和测试代码的邻域结构有关），不过，这里说的邻域相对较小，并不一定指TS搜索邻域一定比ALNS小，你也可以通过邻域结构的设计，搞得很大很大。
但一般而言，ALNS的邻域规模都大一些，毕竟他就是以大规模邻域著称的。在本那次代码中，由于TS只设计了一个邻域算子，因此收敛的速度非常快，但也过早陷入了局部最优。
当然，以上测试非常简单，反应出两种算法的不同特点还不够准确，因为实际运行过程建立在代码的基础上，比如对禁忌搜索而言，算子设计的个数、优劣会影响解的精确度；是否进行去重优化会影响搜索速度。对ALNS，代码中设计了local search，因此搜索速度会略慢一些，但优化程度会有所提升。
写在后面
ALNS相对比较复杂，尤其是我们提供的代码框架非常完善，综合了模拟退火、变邻域搜索的一些特点，要弄清楚并不容易。在接下来的一段时间里，小编也会和大家一起进一步研究ALNS，为大家带来一些ALNS相关的文章，希望大家多多关注~
在公众号内输入【ALNSTSPVS】不带【】即可下载相关代码！
评论