干货|十分钟快速复习禁忌搜索(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）