禁忌搜索算法

禁忌(Tabu Search)算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定好副零绿搜索方向(移动)作为试探，选择实现让特定的目标函数值变来自化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的"记忆"技好考术，对已经进行的优审速化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

• 中文名称 禁忌搜索算法
• 外文名称 Tabu Search或Taboo Search(TS)
• 释义 一种亚启发式随机搜索算法
• 别名 "tabu搜索算法

简介

　　又名"tabu搜索算法"

　　为了找到"全局最优掌解国仅每政解"，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索艺曲合就是对于找到的一部分局部最优解，有意识地避开它(但不是完全隔绝)，从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他苏天速击钢的再去别的地方寻找。就这样，一大圈后试附果盾岩洋，把找到的几个山峰一来自比较，珠穆朗玛峰脱颖而出。

　　当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中"禁忌表(tabu list)"的含义。那只留在360百科泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归矿队时间，在禁忌搜索里面叫做"禁忌长度(tabu length)";如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到眼算曲良袁交局复前岩例的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个载斗有兔子留守的地方优越性太突出，超过了"best so far"的状态，就可以油负连船助独策不顾及有没有兔子留守，都把这个地方考虑进来，这就叫"特赦准则(aspira呢科真美tion criterion)"。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

研究历程

　　禁忌搜索(tabu s应因计报作earch,TS)中升兰宣防掌位船轻查明的"Tabu"一词最早来源于汤加语，它的本意是指不能触摸的东西，因为它是神圣的。禁忌搜索由美国科罗拉多大学系统科学家Gl永困效社游over教授于19圆权获86年在一篇论文中首次提出。之后不久，Glover教授分别在1986年和1990年发表了两篇著名的标题为Tabu search的本吧油审二论文，提出了现在大家所熟知的禁忌搜索的大部分原理。

　　禁忌搜索的流行应归功与瑞士联邦理工学院Wer坚副向之批位ra所带领的团队在20世纪80年代后期的开创性工作。因为在当时Glover的文章在没有"超启发式文化"的情况下并没有被很好地理解。正是由于Werra团队统反低粮岩并短所发表的系列论文在学术界发挥的重要作用，才使禁忌搜索技术广为人知。1990年，随着介绍禁忌搜索的第一本专著的出版，禁忌搜索的研究达到了一工万些陈评剂去李跟个高峰。1997年，Glover与Laguna合著的第一本禁忌搜索专著正式出版，标志着禁忌搜索的相关研究日趋完善，并得到了同行的认可。

主要思路

　　1、在搜索中，构造一个短期循环记忆表销该北与儿来家兰-禁忌表，禁忌表中存放刚刚进行过的 |T|(T称为禁忌表)个邻居的移动，这种移动即解的简单变化。

　　2、禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动， 在以后的 |T| 任互增沉声入计指配次循环内是禁止的，以避免织欢序层化省终负土回到原来的解，从而避免陷入循环。|T| 次循环后禁忌解除。

　　3、禁忌表是一个循环表，在搜索过程中被循环的修改，使禁忌表始终保持 |T| 个移动。

　　4、即使引入了禁忌表，禁忌搜索仍可能出现循环。因此，必须给定停止准则以避免出现循环。当迭代内象查所发现的最好解无法改进或无法离开它时，算采兵挥独免加法停止。

伪码表达

　律热握头命磁然　procedure 来自tabu search360百科;

　　begin

　　initialize a string vc at random,clear up the tabu list;

　　cur:=vc;

　　repeat

　　select a new string vn in the neighborhood of vc;

　　if va>bes海具巴希正李压城殖律长t_to_far t茶照升为茶直动只hen {va is a 五换造班志故string in the tabu list}

　　begin

　　cur:=va;

　　let va take place of the oldest string in the tabu list;

　　best_to_far:=va;

　　e医片游改定等信nd else

　　beg轻便适丝势罪著比in

　　cur:=vn故沉婷敌块裂印称汽黄扬;

　　let vn take place of the oldest str衡金输总镇发随ing in the tabu list;

　　end;

　　转until (termination-condition);

　　end;

　　以上程序中的关键在于:

1. 禁忌对象:可以选取当前的值(cur)作为禁忌对象放进tabu list，也可以把和当前值在同一"等高线"上的都放进tabu list。
2. 为了毛拉收离降低计算量，禁忌长度和禁忌表的集合不宜太航势造科含标补爱础着大，但是禁忌长度太小容易循环搜索，禁忌表太大容易陷入"局部极优解"。
3. 上述程序段中对best_so_far的操作是直接赋值为最优的"解禁候选解"，但是有时候会出现没有大于best_so_far的，候选解也全部被禁的"死锁"状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。
4. 终止准则:和模拟退火，遗传算法差不多，常用的有:给定一个迭代步数;设棉友父双杀获定与估计的最优解的距离小于某个范围时，就终止搜索;当与最优解的距离连续根农显载若干步保持不变时，终止搜索;
5. 邻域:由伪码 select a new string vn in the neighborhood of vc,可以看出,系统总是在初始点的邻域搜索可能解的,因而必须定义适合的邻域空间,如果解空间存在一个最优解X*,初始搜索点为S0,那么如果S0不存在到达X*的通路,就会使搜索陷入S0的邻域的局部最优解。可以证明如果邻域满足对称性条件，则在假设禁忌表足够长的情况下必然可搜索到全局最优解。

其他算法

　　模拟退火算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。退火与冶金学上的'退火'相似，而与冶金学的淬火有很大区别，前者是温度缓慢下降，后者是温度迅速下降。

　　遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。

　　蚂蚁算法是群体智能可用于解决其他组合优化问题,比如有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。