干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码

简介: 干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码

前言


大家好呀,你们帅气的小编又回来啦!

微信图片_20220423101252.png

公众号的老观众们应该会记得,在去年这个时候我们公众号发布了有关自适应大领域搜索算法(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++,不太方便。


对于有点编程基础的同学还好,照着葫芦总能画出一个瓢来:


微信图片_20220423101254.jpg


emmm……而对于不熟悉编程的同学而言,一顿操作猛如虎:


微信图片_20220423101256.jpg


为了造福人类,这次小编为大家带来了VS版本的ALNS框架,只需要下载处理好的项目文件导入VS中就可以直接运行啦!

代码运行


习惯使用dev C++的同学,可以直接参考过去的推文,安装MinGW库,再在dev C++上运行。
对使用VS的同学,直接从公众号中下载代码,用VS打开.sin文件就行啦在公众号内输入【ALNSTSPVS】不带【】即可下载相关代码!如图:


微信图片_20220423101259.png微信图片_20220423101301.png


怎样,是不是跟在床上翻一个身一样简单呢?不过你的VS版本要>=2015哦。
微信图片_20220423101303.gif

这次提供给大家的代码中,除了已经搭建好的ALNS的框架(来自Github,一个法国的PHD写的,原地址:https://github.com/biblik/alns-framework),还有编写的利用ALNS框架求解TSP的代码(代码经过小舟同学修改),并包含几个TSP算例:
微信图片_20220423101305.jpg

图中箭头标注的.xml文件用于参数修改。箭头指向的是几个重要参数,用于设置搜索停止条件,分别代表迭代次数、运行时间、未能优化当前解的最大迭代次数。任意一项指标超过设置参数时,程序停止运行:
微信图片_20220423101308.jpg

算例在main.cpp中输入,在图示位置输入算例名称:
微信图片_20220423101311.jpg

如果要导入自己的算例,将算例放置到工程文件目录下,保证算例格式与所给算例一样,就可以运行啦!

简单实验


关于ALNS的介绍,过去已经有相关推文做了详细解读。这里我们对ALNS求解TSP的结果进行简单实验,看一看算法的实际运行效果。


测试算例采用TSPLIB提供的TSP算例,可以在公众号菜单【资源下载-算例下载】一栏进行下载。
我们先将ALNSTabu Search进行简单对比,关于Tabu Search的传送门:
干货|十分钟快速复习禁忌搜索(c++版)
对比结果如下:
微信图片_20220423101313.jpg

经过简单的测试发现,ALNS代码运行的时间比禁忌搜索算法更长一些。并且两种算法得出的满意解与最优解都有一些差距,所以我们增加最大迭代次数,看一看两种算法能更精确到什么程度:
微信图片_20220423101316.jpg

可以看到,增加迭代次数,ALNS会得到更优的满意解,而TS可能早就陷入了局部最优,已经无法继续得到更优的解了。们选择算例rd400,进一步测试ALNS的运行情况:
微信图片_20220423101319.jpg

从上面的结果可以看出:ALNS通过增加迭代次数,是能更好的逼近最优解的。不过所需要的时间也相应会增加。


经过比较可以看出,ALNS收敛的速度较慢,因为其搜索的邻域是非常大的,其达到满意解所需的搜索时间要更久。但正是由于其搜索的邻域巨大,在此过程中不容易过早陷入局部最优,增加搜索时间是有更大概率找到更好的解。
而TS搜索的邻域相对ALNS较小(和测试代码的邻域结构有关),不过,这里说的邻域相对较小,并不一定指TS搜索邻域一定比ALNS小,你也可以通过邻域结构的设计,搞得很大很大。
但一般而言,ALNS的邻域规模都大一些,毕竟他就是以大规模邻域著称的。在本那次代码中,由于TS只设计了一个邻域算子,因此收敛的速度非常快,但也过早陷入了局部最优。


当然,以上测试非常简单,反应出两种算法的不同特点还不够准确,因为实际运行过程建立在代码的基础上,比如对禁忌搜索而言,算子设计的个数、优劣会影响解的精确度;是否进行去重优化会影响搜索速度。对ALNS,代码中设计了local search,因此搜索速度会略慢一些,但优化程度会有所提升。
微信图片_20220423101322.gif

写在后面


ALNS相对比较复杂,尤其是我们提供的代码框架非常完善,综合了模拟退火、变邻域搜索的一些特点,要弄清楚并不容易。在接下来的一段时间里,小编也会和大家一起进一步研究ALNS,为大家带来一些ALNS相关的文章,希望大家多多关注~

相关文章
|
算法 Java API
手把手教你用CPLEX求解一个数学模型(Java版)
手把手教你用CPLEX求解一个数学模型(Java版)
2443 0
手把手教你用CPLEX求解一个数学模型(Java版)
|
资源调度 JavaScript 编译器
Vite中如何更好的使用TS
【8月更文挑战第4天】Vite中如何更好的使用TS
698 4
Vite中如何更好的使用TS
|
7月前
|
存储 固态存储
磁盘和内存的区别
存储特性: • 磁盘:非易失性存储,数据在断电后不会丢失,适合长期存储数据。 • 内存:易失性存储,数据在断电后会丢失,适合临时存储当前运行的程序和数据。 容量: • 磁盘:容量通常较大,从几百GB到数TB不等,适合存储大量的文件和数据。 • 内存:容量相对较小,一般在几GB到几十GB之间,用于提供快速的临时存储空间。 速度: • 磁盘:读写速度较慢,HDD一般在几十MB/s,SSD可以达到几百MB/s甚至数GB/s。 • 内存:读写速度非常快,通常在几十纳秒到几百纳秒之间,能够快速响应CPU的指令。
363 2
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
机器学习/深度学习 人工智能 自然语言处理
《智能语音助手的未来:从理解到预测的跃进》
随着人工智能技术的飞速发展,智能语音助手已经从简单的命令响应进化到能够理解和预测用户需求的高度。本文将深入探讨智能语音助手如何通过自然语言处理、机器学习和大数据分析等技术,实现从基础交互到高级认知功能的转变,并预测未来可能的发展方向。 【7月更文挑战第29天】
341 4
|
人工智能 自然语言处理
还在因AI检测头疼?尝试一下 AI Humanize
AI Humanize是一款将AI文本转化为人性化、难以检测的高质量内容的工具。它提供基础和高级模型,支持多语言,如英语、中文等,并能在多种AI检测器中通过。训练于大量人类语料库,AI Humanize的"Humanize AI LLM"模型确保生成自然、流畅的文本,增强可读性和原创性,同时保持用户友好界面。适用于各领域的用户提升内容质量。[AI Humanize](https://aihumanize.io/)**
还在因AI检测头疼?尝试一下 AI Humanize
【图片公式识别】图片公式转Word与LaTeX文档:智能识别与转换
【图片公式识别】图片公式转Word与LaTeX文档:智能识别与转换
518 4
|
关系型数据库 MySQL 数据库
数据库降本秘籍:阿里云RDS经济版(RDS倚天版)最高可省48%
RDS倚天版结合软硬件协同技术的优化,持续释放技术红利。 云数据库 RDS MySQL、RDS PostgreSQL 倚天ARM版通用规格最高降价40%