禁忌搜索算法tsp

㈠ 禁忌搜索算法与传统优化算法的区别

背景：禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。
使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用

㈡ TS算法是什么

就是禁忌搜索算法，又名“tabu搜索算法”，是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。
禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

㈢ LKH（Lin-Kernighan heuristic ）一种求TSP的邻域搜索策略

PART I 引入

题主应该指的是1973年的针对TSP的LKH算法。LKH算法类似于k-opt方法，常见的2-opt作为一种local search的思想题主应该是知道的，（2-opt的基本变换2-interchange如下图）。

那么k-opt的过程，也可以element by element，也就可以通过不计顺序的δ-path之间的uv-switch来实现，每个合适的k-opt里面的exchange都是总和为正的增益值，那么其每一个合适的exchange的一部分都可以被uv-switch达到，所以可以令每次的G*都大于0，作为stoppingcriteria，从逻辑上来说是合理的，符合作者的element by element，在启发式所谓的exploitation上也有好的表现力。END

P.S element by element这种思想在其他的算法也有体现，比如遗传算法的改进上也有比如单位点交叉防止收敛解震动。

其他算法效能上的提升考虑，请依次阅读文献[2][1]及其他相关的资料。

综上，LKH是可以认为基于k-opt成功的改进，无论是运行的速度上，还是搜索的精度上。它在解决TSP问题上，速度和精度上仍旧有较好的表现。

水平有限，随缘回答，若有错误，请指出评论，谢谢！

参考文献：

理解算法框架内容，文献[1]是较好的参考资料，理解算法细节、讨论，可以参考文献[2]，其指出了backtracking的要求（从数值实验/作者思考的philosophy上指出：应该从最多几层开始backtracking，每层y_1, y_2contenders的数量如何，如何进一步refinements，每一次δ-path 变换中y_i怎么高效选取等问题）

[1] Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.Combinatorial Optimization

[2] S. Lin, B. W. Kernighan,An effective heuristic algorithm for the traveling salesman problem

㈣ 有关禁忌搜索

禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的 meta-heuristic算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内容。

1. 引言

局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于领域结构和初解，尤其窥陷入局部极小而无法保证全局优化性。针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构，如TSP的2opt扩展到k-opt；多点并行搜索，如进化计算；变结构领域搜索（ Mladenovic et al,1997）；另外，就是采用TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。

禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到领域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等概念，我们首先用一个示例来理解禁忌搜索及其各重要概念，而后给出算法的一般流程。

2.禁忌搜索示例
组合优化是TS算法应用最多的领域。置换问题，如TSP、调度问题等，是一大批组合优化问题的典型代表，在此用它来解释简单的禁忌搜索算法的思想和操作。对于 n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数字，而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。

首先，我们对置换问题定义一种邻域搜索结构，如互换操作（SWAP），即随机交换两个点的位置，则每个状态的邻域解有Cn2=n（n一1）/2个。称从一个状态转移到其邻域中的另一个状态为一次移动（move），显然每次移动将导致适配值（反比于目标函数值）的变化。其次，我们采用一个存储结构来区分移动的属性，即是否为禁忌“对象”在以下示例中：考虑7元素的置换问题，并用每一状态的相应21个邻域解中最优的5次移动（对应最佳的5个适配值）作为候选解；为一定程度上防止迂回搜索，每个被采纳的移动在禁忌表中将滞留3步（即禁忌长度），即将移动在以下连续3步搜索中将被视为禁忌对象；需要指出的是，由于当前的禁忌对象对应状态的适配值可能很好，因此在算法中设置判断，若禁忌对象对应的适配值优于“ best so far”状态，则无视其禁忌属性而仍采纳其为当前选择，也就是通常所说的藐视准则（或称特赦准则）。

可见，简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。需要指出的是：

（1）首先，由于TS是局部领域搜索的一种扩充，因此领域结构的设计很关键，它决定了当前解的领域解的产生形式和数目，以及各个解之间的关系。

（2）其次，出于改善算法的优化时间性能的考虑，若领域结构决定了大量的领域解（尤其对大规模问题，如TSP的SWAP操作将产生Cn2个领域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。

（3）禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进而影响整个算法的搜索进程和行为。同时，以上示例中，禁忌表中禁忌对象的替换是采用FIFO方式（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。

（4）藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。

（5）对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。

（6）为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则来结束整个搜索过程。

此外，在许多场合禁忌对象的被禁次数（frequency）也被用于指导搜索，以取得更大的搜索空间。禁忌次数越高，通常可认为出现循环搜索的概率越大。

3.禁忌搜索算法流程
通过上述示例的介绍，基本上了解了禁忌搜索的机制和步骤。简单TS算法的基本思想是：给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。

条理化些，则简单禁忌搜索的算法步骤可描述如下：

（1）给定算法参数，随机产生初始解x，置禁忌表为空。

（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。

（3）利用当前解工的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。

（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。

（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。

（6）转步骤（2）。

同时，上述算法可用如下流程框图更直观地描述，如图4．1．1。

我们可以明显地看到，邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。需要指出的是，上述算法仅是一种简单的禁忌搜索框架，对各关键环节复杂和多样化的设计则可构造出各种禁忌搜索算法。同时，算法流程中的禁忌对象，可以是搜索状态，也可以是特定搜索操作，甚至是搜索目标值等。

同时，与传统的优化算法相比，TS算法的主要特点是：

（1）在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；

（2）新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。由于TS算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增强获得更好的全局最优解的概率，所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。

㈤ 向大神求两道计算机方面的题！

建议将问题发到美国麻省理工学院询问。

㈥ 禁忌搜索算法的简介

又名“tabu搜索算法”
为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。
当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

㈦ 约束条件是怎么加入禁忌搜索算法中的

组合优化是TS算法应用最多的领域。置换问题，如TSP、调度问题等，是一大批组合优化问题的典型代表，在此用它来解释简单的禁忌搜索算法的思想和操作。对于n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数字，而禁忌