第二章 禁忌搜索算法

禁忌搜索算法又名“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。

图节点着色问题中的禁忌搜索算法09-03-25 作者：编辑：校方人员图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题。

目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。

综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。

本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性。

禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有效的应用于一些典型NP问题，如TSP。

但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。

本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。

最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。

1图节点着色问题图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集，其中(i,j)表示有连接(i,j)的一条边。

若，且V i内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…,V n)为V的一个划分。

图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,V n)为V的一个划分。

通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。

Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。

目录一、摘要 (2)二、禁忌搜索简介 (2)三、禁忌搜索的应用 (2)1、现实情况 (2)2、车辆路径问题的描述 (3)3、算法思路 (3)4、具体步骤 (3)5、程序设计简介 (3)6、算例分析 (4)四、禁忌搜索算法的评述和展望 (4)五、参考文献 (5)禁忌搜索及应用一、摘要工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。

禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。

本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。

二、禁忌搜索简介禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。

TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。

相对于模拟退火和遗传算法，TS是又一种搜索特点不同的meta-heuristic算法。

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

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

禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。

禁忌搜索涉及到邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念。

TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP,即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。

其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij ）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji , ni j=1 , 2, 3, ?, n）;2）非对称旅行商问题（dij dji, ? i, j=1 , 2, 3, ?, n）。

非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。

若对于城市V={V1, V2, V3, ?, V n}的一个访问顺序为T={t l, t2, t3, ?, t i, ?, t n}，其JT中t& V （i=1 , 2, 3, ?, n）,且记t n+1=t1，则旅行商问题的数学模型为：minL= TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。

因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。

二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。

但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法2）禁忌搜索算法3）Hopfield神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略2.1模拟退火算法方法1）编码选择：采用描述TSP解的最常用的一种策略一一路径编码。

2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）;②逆序操作（INV ）;③插入操作（INS）。

TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。

其图论描述为：给定图G=（V，A），其中V为顶点集，A 为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji，Πi，j=1，2，3，⋯，n）；2）非对称旅行商问题（dij≠dji，ϖi，j=1，2，3，⋯，n）。

非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。

若对于城市V={v1，v2，v3，⋯，v n}的一个访问顺序为T={t1，t2，t3，⋯，t i，⋯，t n}，其中t i∈V（i=1，2，3，⋯，n），且记t n+1=t1，则旅行商问题的数学模型为：minL=。

TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。

因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。

二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。

但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法2）禁忌搜索算法3）Hopfield神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略2.1模拟退火算法方法1）编码选择：采用描述TSP解的最常用的一种策略——路径编码。

2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SW AP）；②逆序操作（INV）；③插入操作（INS）。

3）SA状态接受函数的设计：min{1，exp（-△/t）}>random[0，1]准则是作为接受新状态的条件最常用的方案，其中△为新旧状态的目标值差，t为”温度”。

禁忌搜索算法原理及应用随着计算机技术的不断发展，各种算法也应运而生，其中禁忌搜索算法便是一种比较常用的优化算法。

禁忌搜索算法的一大特点就是能够避免搜索过程中出现循环现象，能够有效地提高搜索效率，因此在许多领域都有广泛的应用。

一、禁忌搜索算法的原理禁忌搜索算法是一种基于局部搜索的优化算法。

其基本思想就是在搜索过程中引入禁忌表，通过记录禁忌元素，避免进入不良搜索状态，从而获得更好的解。

禁忌表的作用是记录已经经过的解的信息，防止搜索陷入局部最优解，增加了搜索的广度和深度。

禁忌搜索算法的核心是寻找最优化解。

具体过程包括：初始化，构造邻域解，选择最优解，更新禁忌表，结束搜索。

当搜索过程中发现某个解是当前状态下的最优解时，将这个最优解加入到禁忌表中，以后在搜索过程中就不再去重复对该最优解的操作。

在禁忌搜索算法中，选择邻域解是非常重要的一环。

邻域解是指与当前解相邻的解，也就是在当前解的基础上进行一定的操作得到的解。

邻域解的选择通常根据问题的不同而定，可以是交换位置、插入、反转等。

而选择最优解的原则则是要在禁忌状态下优先选择不在禁忌表中的最优解，如果所有的最优解都处于禁忌状态，那么就选择设定的禁忌期最短的解。

二、禁忌搜索算法在实际应用中的应用禁忌搜索算法作为一种优化算法，在实际应用中有着广泛的应用。

下面我们就通过几个实际案例来了解禁忌搜索算法的应用。

1. 生产排程问题禁忌搜索算法在制造业的排程问题中有着广泛的应用。

在生产排程问题中，需要考虑的因素非常多，如时间、人员、设备、物料等。

禁忌搜索算法通过构建邻域空间，利用禁忌表避免了进入不良解的状态，从而在生产排程问题中，可以为厂家避免很多因时间不足而导致的决策错误。

2. 组合最优化问题禁忌搜索算法在组合最优化问题中有着很好的应用。

比如在公路路径设计中，需要从成千上万的路径中选择最优解。

禁忌搜索算法不仅可以找到全局最优解，还可以避免局部最优解的产生，使得结果更加准确。

无时限单向配送车辆优化调度问题的禁忌搜索算法无时限单向配送车辆优化调度问题，是指在制定配送路线时不考虑客户对货物送到（或取走）时间要求的纯送货（或纯取货）车辆调度问题。

无时限单向配送车辆优化调度问题可以描述为：从某配送中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足一下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。

一、禁忌搜索算法的原理禁忌搜索算法是解决组合优化问题的一种优化方法。

该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。

在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。

为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。

另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。

二、算法要素的设计1.禁忌对象的确定禁忌对象是指禁忌表中被禁的那些变化元素。

由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。

一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。

根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。

举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。

禁忌搜索算法评述摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。

禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。

本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。

关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法1 引言工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。

优化算法主要分为启发式算法和智能随机算法。

启发式算法依赖对问题性质的认识,属于局部优化算法。

智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。

禁忌搜索算法(tabu search, ts)最早是由lover在1986年提出,它的实质是对局部邻域搜索的一种拓展。

ts算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。

同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。

ts算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化[1]。

迄今为止,ts算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景[2~9,11~15]。

目前关于ts的研究主要分为对ts算法过程和关键步骤的改进,用ts 改进已有优化算法和应用ts相关算法求解工程优化问题三个方面。

禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。

2 禁忌搜索算法的基本流程ts算法一般流程描述[1]:(1)设定算法参数,产生初始解x,置空禁忌表。

TSP的⼏种求解⽅法及其优缺点TSP的⼏种求解⽅法及其优缺点⼀、什么是TSP问题旅⾏商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定⼀条经过各城市当且仅当⼀次的最短路线。

其图论描述为：给定图G=（V，A），其中V为顶点集，A 为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定⼀条长度最短的Hamilton回路，即遍历所有顶点当且仅当⼀次的最短距离。

旅⾏商问题可分为如下两类：1）对称旅⾏商问题（dij=dji，Πi，j=1，2，3，?，n）；2）⾮对称旅⾏商问题（dij≠dji，?i，j=1，2，3，?，n）。

⾮对称旅⾏商问题较难求解，我们⼀般是探讨对称旅⾏商问题的求解。

若对于城市V={v1，v2，v3，?，v n}的⼀个访问顺序为T={t1，t2，t3，?，t i，?，t n}，其中t i∈V（i=1，2，3，?，n），且记t n+1=t1，则旅⾏商问题的数学模型为：minL=。

TSP是⼀个典型的组合优化问题，并且是⼀个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接⽐较标准。

因此，快速、有效地解决TSP有着重要的理论价值和极⾼的实际应⽤价值。

⼆、主要求解⽅法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插⼊、最远插⼊、最近添加、贪婪插⼊等。

但是，由于构造型算法优化质量较差，迄今为⽌已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退⽕算法2）禁忌搜索算法3）Hopfield神经⽹络优化算法4）蚁群算法5）遗传算法6）混合优化策略2.1 模拟退⽕算法⽅法1）编码选择：采⽤描述TSP解的最常⽤的⼀种策略——路径编码。

2）SA状态产⽣函数的设计：对于基于路径编码的SA状态产⽣函数操作，可将其设计为：①互换操作（SWAP）；②逆序操作（INV）；③插⼊操作（INS）。

基于禁忌搜索算法求解TSP问题（JA V A）时间2013-04-17 22:38:51 CSDN博客原文/wangqiuyun/article/details/8816463一、TSP问题TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题。

该问题可以被证明具有NPC计算复杂性。

TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。

所有的TSP问题都可以用一个图（Graph）来描述：V={c 1 , c 2, …, c i, …, c n }，i = 1,2, …, n ，是所有城市的集合. c i表示第i个城市，n为城市的数目；E={(r, s): r,s∈ V}是所有城市之间连接的集合；C = {c rs : r,s∈ V} 是所有城市之间连接的成本度量（一般为城市之间的距离）；如果c rs = c sr, 那么该TSP问题为对称的，否则为非对称的。

一个TSP问题可以表达为：求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。

二、禁忌搜索算法禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。

其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。

禁忌搜索算法2009210042 李同玲运筹学与控制论搜索是人工智能的一个基本问题，一个问题的求解过程就是搜索。

人工智能在各应用领域中，被广泛的使用。

现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索方法。

禁忌搜索算法(Tabu Search或Taboo Search,简称TS)的思想最早由Glover (美国工程院院士，科罗拉多大学教授)在1977年提出，它是对局部邻域搜索的一种扩展，是一种全局邻域搜索算法，是人工智能的一种体现，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。

TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。

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

1.1引言1.1.1局部邻域搜索局部邻域搜索是基于贪婪思想持续地在当前的邻域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于邻域结构和初始解，尤其容易陷入局部极小而无法保证全局优化性。

局部搜索的算法可以描述为：1、 选定一个初始可行解：0x ；记录当前最优解0best x x =，()best T N x =；2、 当\best T x =∅时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T 中选一集合S ，得到S 中的最好解now x ；若()()now best f x f x <，则best now x x =，()best T N x =；否则，\T T S =；重复2，继续搜索这种邻域搜索方法容易实现理解，容易实现，而且具有很好的通用性，但是搜索结果完全依赖于初始解和邻域的结构，而且只能搜索到局部最优解。

为了实现全局搜索，禁忌搜索采用允许接受劣解来逃离局部最优解。