2013年数学建模第一题方法总结禁忌搜索算法

禁忌搜索算法又名“tabu搜索算法”为了找到“全局最优解”，就不应该执着于某一个特定的区域。

局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。

禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。

兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。

就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。

当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。

这就是禁忌搜索中“禁忌表（tabu list）”的含义。

那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。

这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

伪码表达：procedure tabu search;begininitialize a string vc at random,clear up the tabu list;cur:=vc;repeatselect a new string vn in the neighborhood of vc;if va>best_to_far then {va is a string in the tabu list}begincur:=va;let va take place of the oldest string in the tabu list;best_to_far:=va;end elsebegincur:=vn;let vn take place of the oldest string in the tabu list;end;until (termination-condition);end;以上程序中有关键的几点：（1）禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当前值在同一“等高线”上的都放进tabu list。

禁忌算法心得体会禁忌算法是一种常用的优化算法，它通过维护一个禁忌表来避免搜索过程中陷入局部最优解。

在实际应用中，禁忌算法常常能够取得很好的效果。

在我使用禁忌算法的过程中，我总结了一些心得体会，希望能够对大家有所帮助。

禁忌表的设计禁忌表是禁忌算法的核心，它记录了搜索过程中已经搜索过的解，以及这些解的一些属性。

禁忌表的设计对禁忌算法的性能有着很大的影响。

在我的实践中，我总结了以下几点：禁忌表的大小禁忌表的大小是禁忌算法性能的一个重要参数。

如果禁忌表太小，那么搜索过程中可能会出现重复搜索已经搜索过的解的情况，从而浪费时间。

如果禁忌表太大，那么搜索过程中可能会出现搜索空间过大的情况，从而导致搜索时间过长。

因此，禁忌表的大小需要根据具体问题进行调整。

禁忌表的属性禁忌表的属性是指禁忌表记录的解的一些属性，例如解的质量、解的结构等。

禁忌表的属性需要根据具体问题进行选择。

在我的实践中，我发现，如果禁忌表的属性能够反映出问题的特点，那么禁忌算法的性能会更好。

禁忌表的更新策略禁忌表的更新策略是指禁忌表中记录的解的禁忌期限如何更新。

禁忌表的更新策略需要根据具体问题进行选择。

在我的实践中，我发现，如果禁忌表的更新策略能够反映出问题的特点，那么禁忌算法的性能会更好。

禁忌算法的参数禁忌算法有很多参数，例如禁忌表的大小、禁忌期限、邻域结构等。

这些参数对禁忌算法的性能有着很大的影响。

在我的实践中，我总结了以下几点：禁忌期限禁忌期限是指禁忌表中记录的解的禁忌期限。

禁忌期限需要根据具体问题进行选择。

在我的实践中，我发现，如果禁忌期限能够反映出问题的特点，那么禁忌算法的性能会更好。

邻域结构邻域结构是指禁忌算法中用于生成邻域解的方法。

邻域结构需要根据具体问题进行选择。

在我的实践中，我发现，如果邻域结构能够反映出问题的特点，那么禁忌算法的性能会更好。

禁忌表的大小禁忌表的大小是禁忌算法性能的一个重要参数。

禁忌表的大小需要根据具体问题进行调整。

禁忌搜索算法作者：季敏惠来源：《电脑知识与技术》2009年第27期摘要:随着网络应用不断广泛,网络数据也呈几何级增长。

基于内容的图像搜索算法成为一个很好的解决方案。

该文为图像提取方法提供了一个新的高效的框架,该算法框架相对于以前所使用的基于流形的方法具有明显的优势:本方法框架可以直接对图像数据评定相关性并返回相关性最高的图像数据,而以往的基于流形的方法必须要从特征空间到一个不清晰的语义流形空间做一个映射,并对这个映射进行学习。

关键词:图像;CUDA;熵;流形中图分类号:TP391.41文献标识码:A 文章编号:1009-3044(2009)27-7748-03Active Tabu SearchJI Min-hui(College of Software Engineering, Southeast University, Nanjing 210096, China)Abstract:With the extensive of network applications, network-level data is growing geometrically. Content-based image search algorithm is a good solution. A novel framework is proposed for image retrieval in this paper. Our framework has an clear advantage over pervious manifold based methods: our method can directly rank and return relevant images and does not need to learn a mapping from the feature space to the unclear semantic manifold space, further avoiding the unnecessary exploration on the dimensionality of the semantic space.Key words: image; CUDA; manifold随着信息技术的日益发展,有一样东西以无可遏制的速度增长着,这就是数据。

禁忌搜索算法浅析摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。

禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，可以有效地解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。

关键词:禁忌搜索算法；组合优化；近似算法；邻域搜索1禁忌搜索算法概述禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。

在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。

使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。

禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。

为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。

TS是人工智能的一种体现，是局部领域搜索的一种扩展。

禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。

迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。

禁忌搜索算法局部搜索禁忌搜索禁忌搜索的关键参数和操作禁忌搜索的实现与应用局部搜索♦函数优化问题中在距离空间中，通常的邻域定义是以一点为中心的一个球体；♦组合优化问题中1. 邻域的概念:()2,()2()()D DN x D N x x N x D N x x y N x x ∈→∈∈∈且，称为一个邻域映射，其中表示的所有子集组成的集合。

称为的邻域，称为的一个邻居。

局部搜索1. 邻域的概念例TSP问题解的一种表示方法为D={x=(i1,i2,…,i n)| i1,i2,…,i n是1,2,…,n的排列}，定义它的邻域映射为2-OPT，即x中的两个元素进行对换，N(x)中共包含x的C n2=n(n-1)/2个邻居和x 本身。

例如：x=(1,2,3,4)，则C42=6，N(x)={(1,2,3,4), (2,1,3,4), (3,2,1,4), (4,2,3,1), (1,3,2,4), (1,4,3,2), (1,2,4,3)}局部搜索2. 局部搜索算法♦Step 1选定一个初始可行解x0，记录当前最优解x best:=x0, T=N(x best)；♦Step 2当T\{x best}=Φ时，或满足其它停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解x now；若f (x now)<f(x best)，则x best := x now，T=N(x best)；否则T:=T\S；重复Step 2。

局部搜索五个城市的对称TSP 问题初始解为x best =(ABCDE )，f (x best )=45，定义邻域映射为对换两个城市位置的2-OPT ，选定A 城市为起点。

3. 局部搜索示例局部搜索五个城市的对称TSP 问题方法1：全邻域搜索第1步N (x best )={(ABCDE )，(ACBDE )，(ADCBE )，(AECDB )，(ABDCE )，(ABEDC )，(ABCED )}， 对应目标函数为f (x )={45, 43, 45, 60, 60, 59, 44}x best :=x now =(ACBDE ) 3. 局部搜索示例A B C D E局部搜索3. 局部搜索示例五个城市的对称TSP问题方法1：全邻域搜索第2步N(x best)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43, 45, 44, 59, 59, 58, 43}x best:=x now=(ACBDE)局部搜索3. 局部搜索示例五个城市的对称TSP问题方法2：一步随机搜索第1步从N(x best)中随机选一点，如x now=(ACBDE)，对应目标函数为f(x now)=43< 45x best:=x now=(ACBDE)局部搜索3. 局部搜索示例五个城市的对称TSP问题方法2：一步随机搜索第2步从N(x best)中又随机选一点，如x now=(ADBCE)，对应目标函数为f(x now)=44> 43x best:=x now=(ACBDE)禁忌搜索1. 算法的主要思路♦算法的提出禁忌搜索（Tabu Search，TS）是局部邻域搜索算法的推广，Fred Glover在1986年提出这个概念，进而形成一套完整算法。