禁忌搜索算法的研究及其在TSP的应用

徐丽1陈丽1宋遥2

摘要：禁忌搜索在一系列应用范围内取得了很大的成功，这篇论文致力于揭示其最主要的思想，解释其最基本的原理，并用它来求解组合优化难题中的典型代表旅行商问题（TSP），经过试验和分析，证明它是一种较好的全局启发式搜索算法。

关键词：禁忌搜索组合优化旅行商问题启发式搜索算法

引言

禁忌搜索(TabuSearch或TabooSearch，简称TS)最早由Glover(1986)提出，它是对局部邻域搜索的一种扩展，并且是一种全局逐步寻优算法。禁忌搜索算法通过引入一个灵活的存储结构，并且配备一个相应的禁忌准则来避免搜索的重复，并通过设置一个相应的藐视准则来赦免一些被禁忌的但是还有可能是优于当前解的状态，从而保证多样化的探索并且最终实现全局优化。相对于模拟退火和遗传算法，禁忌搜索算法是又一种搜索特点不同的meta-heuristic算法[1]。迄今为止，禁忌搜索算法在机器学习和组合优化，甚至包括生产调度、和神经网络等领域取得了非常大的成功，并且引起越来越多的学者的关注，得到了进一步的发展。

1TSP问题的描述

旅行商问题(TSP问题)是一个比较经典的数学问题，就是一个销售商从多个城市中的某一城市出发，不重复地走完其它的城市并且回到原点，在所有可行的路径中找出路径长度最短的一条。

将TSP用数学语言可以表述为：假设V1，V2，V3…Vn是给定的n个城市，从某个城市Vi(1≤i≤n)出发，走遍每个城市一次且只一次，然后返回到出发点，求出一条使得总路径最短的路径。aij表示城市Vi到城市Vj的两地路径的长度[2]。

2禁忌搜索算法

禁忌搜索算法的基本思想是：给定一个初始解（随机的），并且给定这个初始解的一个邻域，然后在此初始解的邻域中确定某些解作为算法的候选解；给定一个状态，“bestsofar”（既当前最优解）；若最佳候选解所对应的目标值优于“bestsofar”状态，则忽视它的禁忌特性，并且用这个最佳候选解替代当前解和“bestsofar”状态，并将相应的解加入到禁忌表中，同时修改禁忌表中各个解的任期；若找不到上述候选解，则在候选解里面选择非禁忌的最佳状态做为新的当前解，并且不管它与当前解的优劣，并且将相应的解加入到禁忌表中，同时修改禁忌表中各对象的任期；最后，重复上述搜索过程，直至我们得到的解满足停止准则。

禁忌搜索的算法步骤可描述如下：①给定相应算法的参数，并且随机产生初始解x，同时把禁忌表置为空。②判断算法是不是满足搜索终止的条件？若是，则结束算法并且输出结果；否则，继续执行以下步骤。③利用当前解x的邻域函数产生它的邻域解，并且从中确定一些解作为候选解。④对与所选择的候选解判断是否满足藐视准则？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x＝y，并用与y对应的禁忌对象替换出最早进入禁忌表的禁忌对象，同时用y替换“bestsofar”状态，然后转步骤⑥；否则，执行以下步骤。⑤判断候选解所对应的各个对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态作为新的当前解，同时用与之对应的禁忌对象来替换最早进入禁忌表中被禁忌对象元素。⑥转步骤②。

从上述算法步骤中我们可以看出，禁忌对象、邻域函数、禁忌表和藐视准则，构成了禁忌搜索算法的关键。其中，邻域函数沿用局部邻域搜索的思想，实现邻域搜索；禁忌表和禁忌对象，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的鼓励，它是对禁忌策略的一种解放[3]-[4]。

3禁忌搜索算法用于求解TSP

用于求解旅行商问题的禁忌搜索算法各个参数的设置如下：①解的领域映射为2-opt，也就是固定起点城市，后面的城市中每两个城市进行对换，邻域中的元素个数为C2n+1；②目标函数定义为走过所有城市之间的路径距离之和，目标函数同时也作为评价函数；③禁忌对象定义为目标函数所对应求得的目标值；④禁忌长度(tabu_length)我们可以根据具体问题来制定；⑤从邻域中选则最好的tabu_length+1个元素作为我们下一步搜索的候选集；⑥为了提高我们所寻求的解的质量，并且为了防止出现循环，我们设置了藐视准则。藐视准则定义为：当当前最优解未下降到指定的次数时，则赦免禁忌表中的次优解，并且将其作为下一次迭代的初始解；⑦终止规则为：程序运行超过给定的最大迭代次数，或者赦免次数超过给定的最大赦免次数；⑧为了增强搜索空间的多样性，寻求到更优的解，可以分别以每一个城市作为初始点进行搜索。

4讨论

和传统的算法相比，禁忌搜索算法的主要特点是：①在搜索过程中可以出现一些劣解，因此具有比较强的“爬山”能力；②新解不是在当前解的邻域中随机产生，而或是优于“bestsofar”状态的解，或是非禁忌的最佳解，因此选取优良解的概率就会远远大于其他解。

由于禁忌搜索算法具有灵活的存储结构和藐视准则，并且在搜索过程中可以接受某些劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增加我们获得更好的全局最优解的概率，所以禁忌搜索算法是一种局部搜索能力很强的全局迭代寻优算法。但是，禁忌搜索也有明显的不足，表现在：①对初始解有较强的依赖性，好的初始解可使禁忌搜索算法在解空间中很快的搜索到好的解，而较差的初始解则会降低禁忌搜索的收敛速度，进而影响我们找到最优解；②迭代搜索过程是串行的，也就是仅仅是单一状态的移动，而不是并行搜索。为了进一步改善禁忌搜索的性能，一方面我们可以对禁忌搜索算法本身的算法参数的选取进行改进和优化，另一方面则可以与其他算法相结合。

虽然，禁忌搜索算法在求解组合优化问题上已显示出强大的生命力，但还有不完善的地方。如解的质量与初始解有关，在求解大规模TSP问题(100城市以上)时，运行效率低等。如何将此种算法取其他算法结合在一起，是笔者的下一步要进行的研究工作。

参考文献：

[1]王凌.智能优化算法及其应用[M].北京：清华大学出版社，2001.

[2]任小康，代文征.基于禁忌搜索算法的旅行售货员问题[J].佳木斯大学学报(自然科学版)2005年7月第23卷(第3期):1.

[3]FREDCLOVER.TabuSearch—PartI[J].ORSAJournalonComputing.Summer1989.Vol.1.(No.3).

[4]FREDCLOVER.TabuSearch—PartII[J].ORSAJournalonComputing.Winter1990.Vol.2.(No.1).