禁忌搜索算法浅析

　　禁忌搜索算法浅析摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法 （Tabu Search 或Taboo Search，简称TS 算法）是一种全局性邻域搜索算法，可以有效地 解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。 关键词: 禁忌搜索算法；组合优化；近似算法；邻域搜索 禁忌搜索算法概述禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover 教授在1986 年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两 种方式：一种是传统的方法，另一种方是一些式搜索算法。使用传统的方法，我们 必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算 法的正确性，我们可以找到的答案是最优的；而对于式算法，针对不同的问题，我 们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到 下一个可能解的函数等，所以式算法的广泛性比较高，但相对在准确度上就不一定能够 达到最优，但是在实际问题中式算法那有着更广泛的应用。 禁忌搜索是一种亚式随机搜索算法，它从一个初始可行解出发，选择一系列的特 定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入 局部最优解，TS 搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录 和选择，指导下一步的搜索方向。 TS 是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基 础上，通过设置禁忌表来禁忌一些已经历的操作，并利用准则来励一些优良状态，其 中涉及邻域 （neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、 准则（candidate）等影响禁忌搜索算法性能的关键因素。迄今为止，TS 算法在组合优 化、生产调度、机器学习、电设计和神经网络等领域取得了很大的成功，近年来又在函数 全局优化方面得到较多的研究，并大有发展的趋势。 禁忌搜索算法的基本思想禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭 代搜索中尽量避开这些对象（而不是绝对循环），从而对不同的有效搜索途径的探 索，TS 的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。局部邻域搜 索是基于思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解， 但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法全局优化型。 禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即 从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优 解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁 忌表中点的禁忌，而达到一些没有搜索的点，从而实现更大区域的搜索。TS 算法作为一种 全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征。它通过局部邻域搜索机制和相应 的禁忌准则来避免迂回搜索，并通过破禁水平来一些被禁忌的优良状态，进而多样 化的有效探索，以最终实现全局优化。 考虑最优化问题 ，对于X 中每一个解x，定义一个邻域N(x)，禁 忌搜索算法首先确定一个初始可行解x，初始可行解x 可以从一个式算法获得或者在可 行解集合X 中任意选择，确定完初始可行解后，定义可行解x 的邻域移动集s(x)，然后从 邻域移动中挑选一个能改进当前解x 的移动 ，s(x)，再从新解x’开始，重复搜 索。如果邻域移动中只接受比当前解x 好的解，搜索就可能陷入循环的。为避免陷入循 环和局部最优，构造一个短期循环记忆表——禁忌表(TabuList)，禁忌表中存放刚刚进行过 称为禁忌表长度)个邻域移动，这些移动称作为禁忌移动(TabuMove)。对于当前 的移动，在以后的T 次循环内是的，以避免回到原先的解， 次以后该移动。禁 忌表是一个循环表，搜索过程中被循环的修改，使禁忌表始终保存着 个移动。即使引入 了一个禁忌表，禁忌搜索算法仍有可能出现循环。因此必须给定停止准则以避免算法出现循 环。当迭代内所发现的最好解无法改进或无法离开它时，则算法停止。 禁忌搜索算法构成要素简单的禁忌搜索是在局部邻域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操 作，并利用准则来励一些优良状态，其中邻域结构、候选解、禁忌长度、禁忌对象、 准则、终止准则等是影响禁忌搜索算法性能的关键。禁忌搜索算法是一种由多种策略组 成的混合式算法。每个策略均是一个式过程，它们对整个禁忌搜索起着关键的作用。 3.1 初始解的确定 禁忌搜索对初始解的依赖较大，不同的初始解，在搜索过程中耗费时间和资源往往不 同，同一邻域结构，不同的初始点会得到不同的计算结果，好的初始解往往会提高最终的优 化效果。一个直观的结论就是：如果初始点选择的足够好，总可以计算出全局最优解。 初始解的构造可以随机产生，但效果往往不够理想，常用方法是基于问题的特征信息， 借助一下式方法产生的，这样可以初始解的性能。 3.2邻域移动 邻域移动亦称邻域操作，邻域变换等；邻域移动是从一个解产生另一个解的途径。它 是产生好的解和算法搜索速度的最重要因素之一。邻域移动定义的方法很多，对于不同 的问题应采用不同的定义方法。通过移动，目标函数值将产生变化，移动前后的目标函数值 之差，称之为移动值。如果移动值负的，则称此移动为改进移动;否则称作非改进移动。 最好的移动不一定是改进移动，也可能改进移动，这一点就搜索陷入局部最优时， 禁忌搜索算法能自动把它跳出局部最优。邻域移动的涉及策略既要变化的有效性，还要 变化的平滑性，即产生的邻域解和当前解有不同，又不能差异太大。不同会使搜索过程 向前进行，不能差异太大搜索是有序而非随机的搜索。 3.3禁忌表 禁忌表是用来存放禁忌对象的一个容器，放入禁忌表中的禁忌对象在解禁之前不能被 再次搜索。禁忌表模拟了人的记忆机制，主要目的是搜索过程中出现循环和避免陷入局 部最优，进而探索更多搜索空间；禁忌表可以使用数组、队列、栈、链表等顺序结构实现。 它通常记录前若干次的移动，这些移动在近期内返回。在迭代固定次数后，禁忌 表这些移动，重新参加运算，因此它是一个循环表，每迭代一次，将最近的一次移动放 在禁忌表的末端，而它的最早的一个移动就从禁忌表中出来。为了节省记忆时间，禁忌 表并不记录所有的移动，只记录那些有特殊性质的移动，如记载能引起目标函数发生变化的 移动。 禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影响着搜索速度和解的质 量。如果选择的好，可有助于识别出曾搜索过的区域。实验表明，如果禁忌表长度过小，那 么搜索过程就可能进入死循环，整个搜索将围绕着相同的几个解徘徊;相反，如果禁忌表长 度过大，那它将在相当大的程度上了搜索区域，好的解就有可能被跳过，同时，不会改 进解的效果反而增加算法运算时间。因此一个好的禁忌表长度应该是尽可能小却又能避免算 法进入循环。禁忌表的这 种特性非常类似于“短期记忆”，因而人们把禁忌表称作短期记 忆函数。 禁忌表另一个作用是通过调整禁忌表的大小使搜索发散或。初始搜索时，为提高 解的分散性，扩大搜索区域，使搜索径多样化，经常希望禁忌表长度小。相反当搜索过程 接近最优解时，为提高解的集中性，减少分散，缩小搜索区域，这时通常希望禁忌表长度大。 为达到这样的目的，最近越来越多的人们允许禁忌表的大小和结构随搜索过程发生改变，即 使用动态禁忌表，实验结果表明了动态禁忌表往往比固定禁忌表获得更好的解。 禁忌长度就是每个禁忌对象在禁忌表中的时间，也成为禁忌对象的任期；每一个 禁忌对象加入禁忌表的时候，设置任期为禁忌长度值，搜索过程没迭代一次，禁忌表中的各 个禁忌对象的任期自动减一，当某一禁忌对象任期为0 时，将其从禁忌表中删除；任期不为 的禁忌对象处于禁忌状态，不能被搜索过程选为新解。长期表，短期记忆用来避免最近所作的一些移动被重复，但是在很多的情况下短期记 忆并不足以把算法搜索带到能够改进解的区域。因此 在实际应用中常常短期记忆与长期记 忆相结合使用，以保持局部的强化和全局多样化之间的平衡，即在加强与好解有关性质的同 时还能把搜索带到未搜索过的区域。 在长期记忆中，频率起着非常重要的作用，使用频率的目的就是通过了解同样的选择 在过去做了多少次来重新指导局部选择。当在非禁忌移动中找不到可以改进的解时用长期记 忆更有效。 目前长期记忆函数主要有两种形式，一种通过惩罚的形式，即用一些评价函数来惩罚 在过去的搜索中用得最多或最少的那些选择，并用一些方法来产生新的初始点。用这种 方式获得的多样性可以通过保持惩罚一段时间来得到加强，然后取消惩罚，禁忌搜索继续按 照正常的评价规则进行。另一种形式采用 频率矩阵，使用两种长期记忆，一种是基于最小 频率的长期记忆，另一种是基于最大频率的长期记忆。通过使用基于最小频率的长期记忆， 可以在未搜索的区域产生 新的序列;而使用基于最大频率的长期记忆，可以在过去的搜索中 认为是好的可行区域内产生不同的序列。在整个搜索过程中频率矩阵被不断的修改。 3.4 选择策略 选择策略即择优规则，是对当前的邻域移动选择一个移动而采用的准则。择优规则可 以采用多种策略，不同的策略对算法的性能影响不同。一个好的选择策略应该是既解的 质量又计算速度。当前采用最广泛的两类策略是最好解优先策略和第一个改进解优先策 最好改进解优先策略就是对当前邻域中选择移动值最好的移动产生的解，作为下一次迭代的开始。而第一个改进解优先策略是搜索邻域移动时选择第一改进当前解的邻域移动产 生的解作为下一次迭代的开始。 最好改进解优先策略相当于寻找最陡的下降，这种择优规则效果比较好，但是它需要 更多的计算时间;而最快的下降对应寻找第一个改进解的移动，由于它 无需搜索整个一次邻 域移动，所以它所花计算时间较少，对于比较大的邻域，往往比较适合。 3.5 破禁策略 相关文献亦称准侧、准则、准侧等；破禁策略通常指渴望水平(Aspiration) 函数选择，当一个禁忌移动在随后T 次的迭代内再度出现时，如果它能把搜索带到一个从未 搜索过的区域，则应该接受该移动即破禁，不受禁忌表的。衡量标准就是定义一个渴望 水平函数，渴望水平函数通常选取当前迭代之前所获得的最好解的目标值或此移动禁忌时的 目标值作为渴望水平函数。 破禁准侧了搜索过程在全部候选解被禁或者是有优于当前 最优解的候选解被禁时，能够特定的解，从而实现全局优化搜索。 3.6 停止规则 停止规则亦称终止准则，即算法在何种条件下停止搜索过程；在禁忌搜索中停止规则 通常有如下四种： （1）是把最大迭代数作为停止算法的标准，而不以全局最优为停止规则； （2）是在给定数目的迭代内所发现的最好解无法改进或无法离开它时，算法停止； （3）最优解的目标函数值小于指定误差； （4）最优解的禁忌频率达到指定值。 在实际应用中，无法使用禁忌长度充分大的条件实现状态空间的遍历这一理论条 禁忌搜索算法的流程简单TS 算法的基本步骤是：建立并初始化一个禁忌表，给定一个当前解（初始解）和 一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so r”状态，则忽视其禁忌特性，用其替代当前解和“best so r”状态，并将相应的 对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解 中选择非禁忌的最佳状态为新的当前解，而它与当前解的优劣，同时将相应的对象加入 禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则， 流程如图4.1 所示，简单禁忌搜索的算法步骤可描述如下： （1）给定算法参数，随机产生初始解x，置禁忌表为空。 （2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以 下步骤。 （3）利用当前解工的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。 （4）对候选解判断准则是否满足？若成立，则用满足准则的最佳状态y 替代 成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同 替换“bestso r”状态，然后转步骤6；否则，继续以下步骤。 （5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状 态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。 （6）转到步骤（2）。 图4.1 禁忌搜索流程 伪代码可表达如下： procedure tabu search; begin initialize stringvc random,clearup tabulist; cur:=vc; repeat select newstring vn tabulist} begin cur:=va; let va take place oldeststring tabulist; best_to_r:=va; end else begin cur:=vn; let vn take place oldeststring tabulist; end; until (termination-condition); end; 禁忌搜索算法的特点由于TS 算法具有灵活的记忆功能和准则，并且在搜索过程中可以接受 劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间 的其他区域，从而增强获得更好的全局最优解的概率，新解不是在当前解的邻域 中随机产生，而或是优于“best so r”的解，或禁忌的最佳解，因此选 取优良解的概率远远大于其他解。所以TS 算法是一种局部搜索能力很强的全局 迭代寻优算法。与传统的优化算法相比，TS 算法的主要特点是： 1．从移动规则看，每次只与最优点比较，而不与经过点比较，故可以爬出局部最优。 2．选优规则始终保持曾经达到的最优点，所以即使离开了全局最优点也不会失去全局 最优性。 3．终止规则不以达到局部最优为终止规则，而以最大迭代次数、出现频率或者目 标值偏离成都为终止规则。 我们可以看到，邻域函数、禁忌对象、禁忌表和准则，构成了禁忌搜索算法的关 键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设 置，体现了算法避免迂回搜索的特点；准则，则是对优良状态的励，它是对禁忌策略 的一种放松。需要指出的是，上述算法仅是一种简单的禁忌搜索框架，对各关键环节复杂和 多样化的设计则可构造出各种禁忌搜索算法。同时，算法流程中的禁忌对象，可以是搜索状 态，也可以是特定搜索操作，甚至是搜索目标值等。 参考文献 董然，周慧.禁忌搜索算法评述.中国学术期刊电子出版社. 陈锋等.基于禁忌搜索算法的网格任务调度.计算机工程.2007.Abstract：This introduces basicidea tabusearch algorithm, algorithmprocess itsrealization pseudo-code. Tabu Search algorithm (Tabu get get,abbreviation Taboo TS algorithm) globalneighborhood Search algorithm which can effectively solve combinatorial optimization problem, guidealgorithm jump out localoptimal solution, turning globaloptimal solution. Keywords：Tabu search algorithm, Combinatorial optimization, Approximate algorithm, Neighborhood search

　　推荐：