前期背景申明

本文讲解的背景是NP-hard问题中的TSP问题，如有不了解的小伙伴，这里附上度娘的链接TSP，这里便不再多补充。
禁忌搜索，英文为tabu search，故可简称为TS，它属于启发式算法中基于适合于求解大规模问题的较好解。如果对启发式算法等名词不懂的小伙伴，可以翻看笔者的智能算法，或自行百度。这里最后再补充TS的背景。

禁忌搜索(tabu search，TS)中的“Tabu”一词最早来源于汤加语，它的本意是指不能触摸的东西。
禁忌搜索由美国科罗拉多大学系统科学家Glover教援于1956年在一篇论文中首次提出。之后不久，Glover教投分别在198年和190年发表了两篇著名的标题为lahu serci的论文，提出了现在
大家所熟知的禁忌搜索的大部分原理。
禁忌搜索的流行应归功与瑞士联邦理工学院verra教授所带领的团队在20世纪89年代后期的开创性工作。因为在当时Glover的文章在没有超启发式文化”的情况下并没有被报好地理解。正是出
于Werra团队所发表的系列论文在学术界发挥的重要作用，才使禁忌搜索技术广为人知。1990年，
随着介绍禁忌搜索的第一本专著的出版，禁忌搜索的研究达到了一个高峰。1997年，Glover与Lag
una合著的第一本禁忌搜索专著正式出版，标志着禁忌搜索的相关研究日趋完善，并得到了同行的
认可。
禁忌(Tabu Searsh)算法是一种亚启发式(neta hearistic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择能够实现让特定的目标函数值变化最多
的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优
化过程进行记录和选择，指导下一步的搜索方向，这就是禁忌表的建立。
TS是人工智能的一种体现。是局部领域搜索的一种扩展。是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域(neighbork
pod)、禁忌表(tabu list)、禁忌长度(tabu length)、候选解( candidate )、特赦准则(candida
te)等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化生产调度、机器学习、电
路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并
大有发展的趋势。

禁忌搜索

免子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别前地方寻找。当兔子们再寻找时，一般地会有意识地逆开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁思拨索中
“禁忌表(tabulist)”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找
最高峰的大军，因为这个时候已经有了许多新的消息。这个归队时间，在禁忌搜索里面叫做“禁忌长度(tabu l
ength)”;
如果在搜索的过程中，留守泰山的党子还没有白队，但是找到的地方全是华北平原等比较低的地方，免子们就不得不再次考电选中泰山，泰山华竟也有一个不错的高度，也就是说。当一个有爽子留守的地方优越性太灾
出，超过了“best so far”“的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特
敖准则(aspiration criterion)”这三个概念就是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键
在这里。


在大概理解完算法的原理之后，大家看我做的手写笔记和TS算法的流程图，旁边会对具体的步骤进行分析注释

数值实验

背景和算法讲解完之后，我们就进行数值实验
数据：所选的实验数据是31个城市的坐标，他们两两之间的的距离为平面上的欧氏距离。
评价函数：对于旅行社问题来说，评价函数自然是按顺序走完所有城市所花费的距离总和，且是距离越小越好。
禁忌表：刚开始的初始化为null，且评价值为∞。
禁忌长度为31。
紧急步长：设置为禁忌表的大小（种群大小）
领域搜索策略：策略有两种分为最好解优先、第一个改进解优先。肉眼可知二者差异在于时间和结果效率的差别，一个时间所需较短，一个性能结果更佳，更有利于迭代和进化寻优。
种群大小与迭代次数：40和200。
初始化：初始化种群的40个31的1*31向量，并用数组保存，笔者用C完成的，由于没用随机向量生成函数，故自己动手 写了一个，这里附上链接C向量随机生成函数。
接了下来我们只需要按照流程图上的步骤进行编程即可
更新规则：领域搜索，简单地替换向量中的两个随机位置，生成x倍的候选解，再根据评价值进行替换。我们这里本可以采用GA那种成熟的替换，但为了探寻TS算法的优良性，不采用多算法结合。如若可以的话，可以做一个对比实验，但算法的涉及可能存在差异性，对比的标准不一致，且文章和学习的目的在于涉猎，故不再进行深入研究，不再提。
特赦规则：之前的介绍和流程图就有提到，当个体比紧急表中的所有个体都要好时特赦。
迭代停止时机：①运行指定的代数 ②某个解比例在禁忌表中的比例超过阈值 ③在某些代数的更新中optimu不变 等等。

源码和学习资料：这里

写在最后

写本篇blog的初心其实在几个月前就有形成，因为各种原因一直搁浅，学到这里笔者可以自信说启发式算法已大致涉猎学习过，现在终于完成内心甚是欣慰。启发式的算法笔者学习的时间说长也不长，说短也不短了，也参加过一些科研项目，其中TS算法一直有耳闻，心驰神往，之前想要跟随的导师也跟TS算法的发明者颇有渊源，所有更加加深了学习的动力，但是硕士研究生阶段也许不再研究此方向，与本科所研究有差池，这次写作算是对本科学习的告结，以后再根据自己想要研究的知识的机会也许会愈来愈少，以此纪念这个本科生升研究生的暑假。