干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码
程序猿声
共 2214字，需浏览 5分钟
· 2020-02-24
文案 周航
审核修改 邓发珩
前言
公众号的老观众们应该会记得，在去年这个时候我们公众号发布了有关自适应大领域搜索算法（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】不带【】即可下载相关代码！
评论
互联网晚报 | 大麦网已退款凤凰传奇演唱会“柱子票”；钟薛高再成被执行人；iPhone 16或取消实体音量键和电源键
大麦网回应凤凰传奇演唱会买到“柱子票”：已退票退款据报道，凤凰传奇2024巡回演唱会常州站演出结束的第二天，有网友称自己在大麦网买到“柱子票”，因为观看效果不佳，要求退款被拒。23日，记者从涉事网友处了解到，大麦方面给出了退款建议，但被其拒绝，“我希望平台退款加赔偿，并重视屡次出现的‘柱子票’问题。
产品刘
0
AI论文写作工具和生成器（一）
随着人工智能和大模型的迅猛发展，AI对研究人员和学生提供了极大的写作便利。本文将介绍市面上常用的AI论文写作工具，帮助你提高论文写作效率并遵循学术道德。请仅将AI论文生成器视为辅助参考手段，切勿直接挪用全文。XPaper AlXPaper AI是由点击式创作工具晓语台推出的一款论文写作生成平台，只需
IQ前端
0
Langchain使用 | 模型、提示和解析器、存储
零、LangChain介绍为各种不同基础模型提供统一接口- 帮助管理提示的框架- 一套中心化接口，用于处理长期记忆（参见Memory）、外部数据（参见Indexes）、其他 LLM（参见Chains）以及 LLM 无法处理的任务的其他代理（例如，计算或搜索）。总的来说，有六大核心模块：Models：
Python之王
0
【第127期】推荐常用的国内外AI大模型
概述 多个国内外的AI大模型及其特点。以下是一些被提及的AI大模型和平台：全球大模型：ChatGPT：由OpenAI开发，支持多种语言，包括中文。Claude：由Anthropic开发，擅长深层次语言模式和复杂推理。Gemini：由Google Research开发，擅长自然语言理解和生成。Mis
前端微服务
0
你真的理解 devDependencies 和 dependencies 的区别吗？
点击上方 前端Q，关注公众号回复加群，加入前端Q技术交流群作者：井柏然原文：https://juejin.cn/post/7135795969370619918你是否真的理解 devDependencies 和 dependencies 的区别？如果不能确切的回答、理解还停留在模糊的阶段，
前端Q
0
为啥大模型还没完全取代你？
点击下方“JavaEdge”，选择“设为星标”第一时间关注技术干货！免责声明~任何文章不要过度深思！万事万物都经不起审视，因为世上没有同样的成长环境，也没有同样的认知水平，更「没有适用于所有人的解决方案」；不要急着评判文章列出的观点，只需代入其中，适度审视一番自己即可，能「跳脱出来从外人的角度看看现
JavaEdge
0
会写代码的总理！全球第一“开源”名门望族
转自：OSC开源社区4 月 15 日，新加坡总理公署发表声明宣布，总理李显龙将于 5 月 15 日辞职，并正式交棒给副总理兼财政部长黄循财。对于李氏家族下一代是否会继续活跃在新加坡政坛，目前外界说法不一。但在开源圈里，李氏家族绝对有一席之地。李显龙有 4 名子女，其本人、次子，以及幼子都有非常专业的
开源前哨
0
面试官：MySQL 上亿大表，如何深度优化？
来源：cnblogs.com/YangJiaXin/p/10828244.html背景分析测试实施索引优化后delete大表优化为小批量删除总结前段时间刚入职一家公司，就遇上这事！背景XX实例（一主一从）xxx告警中每天凌晨在报SLA报警，该报警的意思是存在一定的主从延迟（若在此时发生主从切换，需要
好好学java
0