干货|十分钟快速复习禁忌搜索(c++版)

说到的话一定要做到!做到!到!

昨天向大家保证今天分享 Tabu Search (TS) 代码 c++ 版本,然后,小编就去熬了个夜...

现在的小编 ↓ ↓ ↓

总之经过小编昨晚的狂肝,今天终于能将这份Tabu Search(TS) 复习加强攻略书(c++)版如约介绍给广大 骨·骼·清·奇 的算法master们!!

下面小编开始划重点了!

—禁忌搜索 · 概念篇 · 要素篇 · 代码篇—

坐稳发车!

概念篇

通过上一篇文章“干货 | 到底是什么算法,能让人们如此绝望?”的介绍,相信大家对于禁忌搜索算法都有了初步的认识...

什么?忘了?

不用担心!下面小编将帮大家简单划一下重点以供复习!拿走不谢!

所谓禁忌搜索是Local Search(LS)的扩展,是一种全局逐步寻优的全局性邻域搜索算法

传统的 LS 通过迭代,不断搜寻邻域中更优的解来替换当前解,实现优化,该方式十分容易陷入局部最优。

TS 则是模仿人类的记忆功能,在搜索过程中标记已经找到的局部最优解及求解过程,并于之后的搜索中避开它们。

禁忌算法通过禁忌策略实现记忆功能,通过破禁准则继承LS的强局部搜索能力。种种机制的配合,使得TS一方面具备高局部搜索能力,同时又能防止算法在优化中陷入局部最优

禁忌搜索的主要构成要素

(1)评价函数(Evaluation Function)

(2)邻域移动(Move Operator)

(3)禁忌表(Tabu Table)

(4)邻居选择策略(Neighbor Selection Strategy)

(5)破禁准则(Aspiration Criterion)

(6)停止规则(Stop Criterion)

下面我们将着重从如上几个要素来透彻的理解禁忌搜索,且后续将给出相应的C++源码。

要素篇

代码篇

下面是日常溜代码时间 ↓ ↓ ↓

例一 满秩矩阵式 ( type = 1 )

输入文件格式为:

File_name File_type

salesman.in 1

5

0 1 2 2 3

2 0 3 4 2

3 2 0 4 1

3 4 5 0 5

2 4 1 4 0

输出结果为:

opt_solution:

11

例二 二维坐标式 ( type = 2 )

输入文件格式为:

File_name File_type

KroA100.tsp 2

100

1 1380 939

2 2848 96

3 3510 1671

4 457 334

5 3888 666

6 984 965

7 2721 1482

8 1286 525

9 2716 1432

10 738 1325

11 1251 1832

12 2728 1698

13 3815 169

14 3683 1533

15 1247 1945

16 123 862

17 1234 1946

18 252 1240

19 611 673

20 2576 1676

21 928 1700

22 53 857

23 1807 1711

24 274 1420

25 2574 946

26 178 24

27 2678 1825

28 1795 962

29 3384 1498

30 3520 1079

31 1256 61

32 1424 1728

33 3913 192

34 3085 1528

35 2573 1969

36 463 1670

37 3875 598

38 298 1513

39 3479 821

40 2542 236

41 3955 1743

42 1323 280

43 3447 1830

44 2936 337

45 1621 1830

46 3373 1646

47 1393 1368

48 3874 1318

49 938 955

50 3022 474

51 2482 1183

52 3854 923

53 376 825

54 2519 135

55 2945 1622

56 953 268

57 2628 1479

58 2097 981

59 890 1846

60 2139 1806

61 2421 1007

62 2290 1810

63 1115 1052

64 2588 302

65 327 265

66 241 341

67 1917 687

68 2991 792

69 2573 599

70 19 674

71 3911 1673

72 872 1559

73 2863 558

74 929 1766

75 839 620

76 3893 102

77 2178 1619

78 3822 899

79 378 1048

80 1178 100

81 2599 901

82 3416 143

83 2961 1605

84 611 1384

85 3113 885

86 2597 1830

87 2586 1286

88 161 906

89 1429 134

90 742 1025

91 1625 1651

92 1187 706

93 1787 1009

94 22 987

95 3640 43

96 3756 882

97 776 392

98 1724 1642

99 198 1810

100 3950 1558

输出结果为:

best_known_solution: 21282

注意:

使用本程序的时候只需要建立一个上述文件名的文档,放在与源程序同目录下面,并运行程序,输入文件名以及数据类型。

例如:

运行程序之后会遇到以下提升:

input file_name and data type

只需要输入

KroA100.tsp 2

即可得到一个启发解以及相应路径

更多的数据可以从TSPLIB下载。

上述代码仅供分享交流学习用,如有需要请复制下面链接自取 ↓ ↓ ↓

http://paste.ubuntu.com/25449352/

或者戳文章底部 阅读原文 获取代码!

相信现在大家对禁忌搜索的相关内容更加了解了!

如果大家对 禁忌算法文中所叙内容 还有疑问或想要交流心得建议,欢迎移步留言区!

最后再来一发安利——如果你是初学算法,或者是喜欢交流算法的master,再或者仅仅是想要了解算法是什么...欢迎关注我们的公众号和我们一起交流!学习!进步!

—end—

编辑:谢良桢(1922193128@qq.com)

贺兴(hexing15@gmail.com)

代码:贺兴(hexing15@gmail.com)

指导老师:秦时明岳(professor.qin@qq.com)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

UG数控编程“新手必看”

1.坐标详解 1. 绝对坐标系:是模型空中的概念性位置和方向,将绝对坐标系为X=0,Y=0,Z=0.不可见不能移动。 2. 视图三重轴:是在建模最左下角有个正方...

247100
来自专栏北京马哥教育

干货 | 10 行 Python 代码创建可视化地图

当我开始建造Vincent时, 我的一个目的就是使得地图的建造尽可能合理化. 有一些很棒的python地图库-参见Basemap 和 Kartograph能让地...

47570
来自专栏PPV课数据科学社区

手把手教你学习R语言

随着分析数据的方式在近两年发生了翻天覆地的变化,随着互联网在人们的生活中广泛的普及,人手一部智能机的时代,人们的衣食住行都接上的互联网,这使得数据的获取量得以指...

1.2K80
来自专栏杨建荣的学习笔记

通过java画文本格式的统计图

一直想做一个东西,能够直接在Linux下显示文本格式的图形,比如点阵图,连线图,直方图等等。直接使用第三方的工具会有一些平台和类库的限制,所以小米加步枪自己周末...

40750
来自专栏FreeBuf

如何搭建你自己的“深度学习”机器?

深度学习是一门用来解决复杂问题的技术,例如自然语言处理和图像处理。目前,我们已经可以很快的处理超大计算量的问题——这多亏了GPU,GPU最初就是用于快速生成高分...

21050
来自专栏人工智能头条

利用Amazon ML与Amazon Redshift建立二进制分类模型

18150
来自专栏玉树芝兰

如何用云端 GPU 为你的 Python 深度学习加速?

下午,我用 Python 深度学习框架 Keras 训练了一个包含3层神经网络的回归模型,预测波士顿地区房价。

16510
来自专栏机器人网

线性执行元件的工作方式及分类

线性执行元件是一种以直线为基础进行能量转换的一种元件。线性执行元件可以根据应用者的要求而改变控制对象的状态,这种独特性能吸引着越来越多的人发现和应用它。线性执行...

29450
来自专栏FreeBuf

谈谈鱼叉式网络钓鱼黑箱粉碎机

美国加州大学伯克利分校和劳伦斯伯克利国家实验室(LBNL)的几位安全研究人员开发了鱼叉式网络钓鱼黑箱粉碎机,通过分析鱼叉式网络钓鱼攻击的根本特点设计了一组新的信...

42570
来自专栏机器学习算法工程师

免费使用谷歌GPU资源训练自己的深度模型

作者:刘威威 编辑:黄俊嘉 注:本文编译自medium,原英文链接:https://medium.com/@nick...

60380

扫码关注云+社区

领取腾讯云代金券