干货 | 自适应大邻域搜索(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】不带【】即可下载相关代码!
评论
炸裂!最新CVPR2024、ICLR2024、AAAI2024、ICML、ACL2024论文+Code大合集!
我花了3个月的时间整理了包括CVPR 2023/2024、ECCV 2023、ICML 2023、ICLR 2024/2023、NeurIPS 2023、ACL 2024、EMNLP 2023、AAAI 2024/2023、WWW 2023/2024等顶会在内的超过20000篇人工智能优质论文,今天
GiantPandaCV
0
微软大模型Phi3安装和介绍,普通电脑不联网也能提问!
你好,我是郭震1 前沿 最近,微软发布Phi-3模型,最小尺寸的phi-3-mini(3.8B参数量)在更大、更干净的数据集(包含3.3T个tokens)上进行训练,在各大公开的学术基准和内部测试中,实现了与Mixtral 8x7B和GPT-3.5等大尺寸模型的性能。模型小,phi-3-mini的尺
Python与算法社区
0
10万亿市场的数据资产化背景下,工业大数据如何发挥最大价值?
作者:王飞鹏物联网智库 原创随着今年年初数据资产“入表”正式实行,喊了多年的“发挥数据价值”的口号终于可以说是落到了实处。所谓数据资产入表,是指将数据确认为企业资产负债表中“资产”一项,即数据资产入资产负债表,在财务报表中体现其真实价值与业务贡献。国家发改委价格监测中心副主任王建冬表示,我国数据资产
物联网智库
0
目标检测正负样本区分策略和平衡策略总结
点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达作者丨深度眸@知乎(已授权)来源丨https://www.zhihu.com/people/huanghaian编辑丨极市平台未经允许不得二次转载极市导读 本文抛弃网络具体结构,仅仅从正负样本区分和正负样本平衡策略进行分
小白学视觉
0
性能提升,星辰AI大模型TeleChat-12B评测
0x0. 前言2月份的时候评测过TeleChat-7B大模型,见星辰AI大模型TeleChat-7B评测。最近中电信 AI 科技有限公司针对TeleChat-7B进行了性能升级,并开源了一个更大的模型TeleChat-12B,受邀对这个大模型进行新的评测。本文主要关注TeleChat-7B在做一些文
GiantPandaCV
0
一文总结:AI大模型之LangChain基础用法
你好,我是郭震现在或未来最火的无疑是AI大模型开发,现在去boss直聘,随便一搜大模型开发,岗位薪资是下面这样的。工资高,还有前景,这不就是风口吗。AI大模型开发中最重要的一个框架就是LangChain,今天我们先来看看它的简介和基础用法。LangChain 框架简介LangChain 是一个用于简
Python与算法社区
0
如何确定神经网络的层数和隐藏层神经元数量?
点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达公众号:尤而小屋作者:呦呦鹿鸣编辑:Peter大家好,我是Peter~关于神经网络中隐藏层的层数和神经元个数充满了疑惑。刚好看到一篇文章很好地答疑了,分享给大家~https://zhuanlan.zhihu.com/p/10041
小白学视觉
0
教程来了!3分钟教你搭建:AI大模型前端界面
你好,我是郭震今天这篇教程,总结大模型前端界面搭建,让你免费使用AI大模型,更加方便和舒服。1 界面升级这是自带的终端窗口,使用不友好:这是升级后的网站界面,自带各种大模型适配,还集成很多助手,支持消息持久存储。2 更多功能内置200多个助手:多种主题设置:3 极简部署
Python与算法社区
3