禁忌搜索算法浅析

1、禁忌搜索算法浅析摘要：本文介绍了禁忌搜索算法的根本思想、算法流程及其实现的伪代码.禁忌搜索算法(TabuSearch或TabooSearch,简称TS算法)是一种全局性邻域搜索算法,可以有效地解决组合优化问题,引导算法跳出局部最优解,转向全局最优解的功能.关键词：禁忌搜索算法；组合优化；近似算法；邻域搜索1禁忌搜索算法概述禁忌搜索算法(TabuSearch)是由美国科罗拉多州大学的FredGlover教授在1986年左右提出来的,是一个用来跳出局部最优的搜寻方法.在解决最优问题上,一般区分为两种方式：一种是传统的方法,另一种方法那么是一些启发式搜索算法.使用传统的方法,我们必须对每一个问题都去

2、设计一套算法,相当不方便,缺乏广泛性,优点在于我们可以证实算法的正确性,我们可以保证找到的答案是最优的；而对于启发式算法,针对不同的问题,我们可以套用同一个架构来寻找答案,在这个过程中,我们只需要设计评价函数以及如何找到下一个可能解的函数等,所以启发式算法的广泛性比拟高,但相对在准确度上就不一定能够到达最优,但是在实际问题中启发式算法那有着更广泛的应用.禁忌搜索是一种亚启发式随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动.为了防止陷入局部最优解,TS搜索中采用了一种灵活的“记忆技术,对已经进行的优化过程进行记录和选择,指

3、导下一步的搜索方向.TS是人工智能的一种表达,是局部领域搜索的一种扩展.禁忌搜索是在领域搜索的根底上,通过设置禁忌表来禁忌一些已经历的操作,并利用藐视准那么来奖励一些优良状态,其中涉及邻域(neighborhood)、禁忌表(tabulist)、禁忌长度(tabulength)、候选解(candidate)、藐视准那么(candidate)等影响禁忌搜索算法性能的关键因素.迄今为止,TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有开展的趋势.2禁忌搜索算法的根本思想禁忌搜索最重要的思想是标记对应已搜索的局部最优解

4、的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环),从而保证对不同的有效搜索途径的探索,TS的禁忌策略尽量防止迂回搜索,它是一种确定性的局部极小突跳策略.禁忌搜索是对局部邻域搜索的一种扩展,是一种全局逐步寻求最优算法.局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索,虽然算法通用易实现,且容易理解,但搜索性能完全依赖于邻域结构和初解,尤其会陷入局部极小而无法保证全局优化型.禁忌搜索算法中充分表达了集中和扩散两个策略,它的集中策略表达在局部搜索,即从一点出发,在这点的邻域内寻求更好的解,以到达局部最优解而结束,为了跳出局部最优解,扩散策略通过禁忌表的功能来实现.禁忌

5、表中记下已经到达的某些信息,算法通过对禁忌表中点的禁忌,而到达一些没有搜索的点,从而实现更大区域的搜索.TS算法作为一种全局性邻域搜索算法,模拟人类具有记忆功能的寻优特征.它通过局部邻域搜索机制和相应的禁忌准那么来防止迂回搜索,并通过破禁水平来释放一些被禁忌的优良状态,进而保证多样化的有效探索,以最终实现全局优化.考虑最优化问题X,对于x中每一个解x,定义一个邻域N(x),禁忌搜索算法首先确定一个初始可行解x,初始可行解x可以从一个启发式算法获得或者在可行解集合X中任意选择,确定完初始可行解后,定义可行解x的邻域移动集s(x),然后从邻域移动中挑选一个能改良当前解x的移动sW日,s(x),再从

6、新解x开始,重复搜索.如果邻域移动中只接受比当前解x好的解,搜索就可能陷入循环的危险.为防止陷入循环和局部最优,构造一个短期循环记忆表一一禁忌表(TabuList),禁忌表中存放刚刚进行过的1丁1(1丁称为禁忌表长度)个邻域移动,这些移动称作为禁忌移动(TabuMove).对于当前的移动,在以后的T次循环内是禁止的,以防止回到原先的解,171次以后释放该移动.禁忌表是一个循环表,搜索过程中被循环的修改,使禁忌表始终保存着|7|个移动.即使引入了一个禁忌表,禁忌搜索算法仍有可能出现循环.因此必须给定停止准那么以防止算法出现循环.当迭代内所发现的最好解无法改良或无法离开它时,那么算法停止.3禁忌搜

7、索算法构成要素简单的禁忌搜索是在局部邻域搜索的根底上,通过设置禁忌表来禁忌一些已经历的操作,并利用特赦准那么来奖励一些优良状态,其中邻域结构、候选解、禁忌长度、禁忌对象、特赦准那么、终止准那么等是影响禁忌搜索算法性能的关键.禁忌搜索算法是一种由多种策略组成的混合启发式算法.每个策略均是一个启发式过程,它们对整个禁忌搜索起着关键的作用.3.1 初始解确实定禁忌搜索对初始解的依赖较大,不同的初始解,在搜索过程中消耗时间和资源往往不同,同一邻域结构,不同的初始点会得到不同的计算结果,好的初始解往往会提升最终的优化效果.一个直观的结论就是：如果初始点选择的足够好,总可以计算出全局最优解.初始解的构造可

8、以随机产生,但效果往往不够理想,常用方法是基于问题的特征信息,借助一下启发式方法产生的,这样可以保证初始解的性能.3.2 邻域移动邻域移动亦称邻域操作,邻域变换等；邻域移动是从一个解产生另一个解的途径.它是保证产生好的解和算法搜索速度的最重要因素之一.邻域移动定义的方法很多,对于不同的问题应采用不同的定义方法.通过移动,目标函数值将产生变化,移动前后的目标函数值之差,称之为移动值.如果移动值是非负的,那么称此移动为改良移动；否那么称作非改良移动.最好的移动不一定是改良移动,也可能是非改良移动,这一点就保证搜索陷入局部最优时,禁忌搜索算法能自动把它跳出局部最优.邻域移动的涉及策略既要保证变化的有

9、效性,还要保证变化的平滑性,即产生的邻域解和当前解有不同,又不能差异太大.不同会使搜索过程向前进行,不能差异太大保证搜索是有序而非随机的搜索.QQ垓己主3.3 xft心、i禁忌表是用来存放禁忌对象的一个容器,放入禁忌表中的禁忌对象在解禁之前不能被再次搜索.禁忌表模拟了人的记忆机制,主要目的是阻止搜索过程中出现循环和防止陷入局部最优,进而探索更多搜索空间；禁忌表可以使用数组、队列、栈、链表等顺序结构实现.它通常记录前假设干次的移动,禁止这些移动在近期内返回.在迭代固定次数后,禁忌表释放这些移动,重新参加运算,因此它是一个循环表,每迭代一次,将最近的一次移动放在禁忌表的末端,而它的最早的一个移动就

10、从禁忌表中释放出来.为了节省记忆时间,禁忌表并不记录所有的移动,只记录那些有特殊性质的移动,如记载能引起目标函数发生变化的移动.禁忌表是禁忌搜索算法的核心,禁忌表的大小在很大程度上影响着搜索速度和解的质量.如果选择的好,可有助于识别出曾搜索过的区域.实验说明,如果禁忌表长度过小,那么搜索过程就可能进入死循环,整个搜索将围绕着相同的几个解徘徊；相反,如果禁忌表长度过大,那它将在相当大的程度上限制了搜索区域,好的解就有可能被跳过,同时,不会改良解的效果反而增加算法运算时间.因此一个好的禁忌表长度应该是尽可能小却又能防止算法进入循环.禁忌表的这种特性非常类似于“短期记忆,因而人们把禁忌表称作短期记忆

11、函数.禁忌表另一个作用是通过调整禁忌表的大小使搜索发散或收敛.初始搜索时,为提升解的分散性,扩大搜索区域,使搜索路径多样化,经常希望禁忌表长度小.相反当搜索过程接近最优解时,为提升解的集中性,减少分散,缩小搜索区域,这时通常希望禁忌表长度大.为到达这样的目的,最近越来越多的人们允许禁忌表的大小和结构随搜索过程发生改变,即使用动态禁忌表,实验结果说明了动态禁忌表往往比固定禁忌表获得更好的解.禁忌长度就是每个禁忌对象在禁忌表中的生存时间,也成为禁忌对象的任期；每一个禁忌对象参加禁忌表的时候,设置任期为禁忌长度值,搜索过程没迭代一次,禁忌表中的各个禁忌对象的任期自动减一,当某一禁忌对象任期为0时,将

12、其从禁忌表中删除；任期不为0的禁忌对象处于禁忌状态,不能被搜索过程选为新解.长期表,短期记忆用来防止最近所作的一些移动被重复,但是在很多的情况下短期记忆并缺乏以把算法搜索带到能够改良解的区域.因此在实际应用中常常短期记忆与长期记忆相结合使用,以保持局部的强化和全局多样化之间的平衡,即在增强与好解有关性质的同时还能把搜索带到未搜索过的区域.在长期记忆中,频率起着非常重要的作用,使用频率的目的就是通过了解同样的选择在过去做了多少次来重新指导局部选择.当在非禁忌移动中找不到可以改良的解时用长期记忆更有效.目前长期记忆函数主要有两种形式,一种通过惩罚的形式,即用一些评价函数来惩罚在过去的搜索中用得最多

13、或最少的那些选择,并用一些启发方法来产生新的初始点.用这种方式获得的多样性可以通过保持惩罚一段时间来得到增强,然后取消惩罚,禁忌搜索继续按照正常的评价规那么进行.另一种形式采用频率矩阵,使用两种长期记忆,一种是基于最小频率的长期记忆,另一种是基于最大频率的长期记忆.通过使用基于最小频率的长期记忆,可以在未搜索的区域产生新的序列；而使用基于最大频率的长期记忆,可以在过去的搜索中认为是好的可行区域内产生不同的序列.在整个搜索过程中频率矩阵被不断的修改.3.4 选择策略选择策略即择优规那么,是对当前的邻域移动选择一个移动而采用的准那么.择优规那么可以采用多种策略,不同的策略对算法的性能影响不同.一个

14、好的选择策略应该是既保证解的质量又保证计算速度.当前采用最广泛的两类策略是最好解优先策略和第一个改良解优先策略.最好改良解优先策略就是对当前邻域中选择移动值最好的移动产生的解,作为下一次迭代的开始.而第一个改良解优先策略是搜索邻域移动时选择第一改良当前解的邻域移动产生的解作为下一次迭代的开始.最好改良解优先策略相当于寻找最陡的下降,这种择优规那么效果比拟好,但是它需要更多的计算时间；而最快的下降对应寻找第一个改良解的移动,由于它无需搜索整个一次邻域移动,所以它所花计算时间较少,对于比拟大的邻域,往往比拟适合.3.5 被禁策略相关文献亦称藐视准侧、特赦准那么、释放准侧等；破禁策略通常指渴望水平(

15、Aspiration)函数选择,当一个禁忌移动在随后T次的迭代内再度出现时,如果它能把搜索带到一个从未搜索过的区域,那么应该接受该移动即破禁,不受禁忌表的限制.衡量标准就是定义一个渴望水平函数,渴望水平函数通常选取当前迭代之前所获得的最好解的目标值或此移动禁忌时的目标值作为渴望水平函数.破禁准侧保证了搜索过程在全部候选解被禁或者是有优于当前最优解的候选解被禁时,能够释放特定的解,从而实现全局优化搜索.3.6 停止规那么停止规那么亦称终止准那么,即算法在何种条件下停止搜索过程；在禁忌搜索中停止规那么通常有如下四种：(1)是把最大迭代数作为停止算法的标准,而不以全局最优为停止规那么；(2)是在给定

16、数目的迭代内所发现的最好解无法改良或无法离开它时,算法停止；(3)最优解的目标函数值小于指定误差；(4)最优解的禁忌频率到达指定值.在实际应用中,无法使用禁忌长度充分大的条件实现状态空间的遍历这一理论收敛条件.4禁忌搜索算法的流程简单TS算法的根本步骤是：建立并初始化一个禁忌表,给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定假设干候选解；假设最正确候选解对应的目标值优于“bestsofar状态,那么无视其禁忌特性,用其替代当前解和“bestsofar状态,并将相应的对象参加禁忌表,同时修改禁忌表中各对象的任期；假设不存在上述候选解,那么选择在候选解中选择非禁忌的最正确状态为新的当

17、前解,而无视它与当前解的优劣,同时将相应的对象参加禁忌表,并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程,直至满足停止准那么,流程如图4,1所示,简单禁忌搜索的算法步骤可描述如下:(1)给定算法参数,随机产生初始解x,置禁忌表为空.(2)判断算法终止条件是否满足假设是,那么结束算法并输出优化结果；否那么,继续以下步骤.(3)利用当前解工的邻域函数产生其所有(或假设干)邻域解,并从中确定假设干候选解.(4)对候选解判断藐视准那么是否满足假设成立,那么用满足藐视准那么的最正确状态y替代x成为新的当前解,即x=y,并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“bestsof

18、ar状态,然后转步骤6;否那么,继续以下步骤.(5)判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象对应的最正确状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素.图4.1禁忌搜索流程伪代码可表达如下:proceduretabusearch;begininitializeastringvcatrandom,clearupthetabulist;cur:=vc;repeatselectanewstringvnintheneighborhoodofvc;ifva>best_to_farthenvaisastringinthetabulistbegincur:

19、=va;letvatakeplaceoftheoldeststringinthetabulist;best_to_far:=va;endelsebegincur:=vn;letvntakeplaceoftheoldeststringinthetabulist;end;until(termination-condition);end;5禁忌搜索算法的特点由于TS算法具有灵活的记忆功能和藐视准那么,并且在搜索过程中可以接受劣解,所以具有较强的“爬山水平,搜索时能够跳出局部最优解,转向解空间的其他区域,从而增强获得更好的全局最优解的概率,新解不是在当前解的邻域中随机产生,而或是优于“bestsofa

20、r的解,或是非禁忌的最正确解,因此选取优良解的概率远远大于其他解.所以TS算法是一种局部搜索水平很强的全局迭代寻优算法.与传统的优化算法相比,TS算法的主要特点是：1 .从移动规那么看,每次只与最优点比拟,而不与经过点比拟,故可以爬出局部最优.2 .选优规那么始终保持曾经到达的最优点,所以即使离开了全局最优点也不会失去全局最优性.3 .终止规那么不以到达局部最优为终止规那么,而以最大迭代次数、出现频率限制或者目标值偏离成都为终止规那么.我们可以看到,邻域函数、禁忌对象、禁忌表和藐视准那么,构成了禁忌搜索算法的关键.其中,邻域函数沿用局部邻域搜索的思想,用于实现邻域搜索；禁忌表和禁忌对象的设置,表达了算法防止迂回搜索的特点；藐视准那么,那么是对优良状态的奖励,它是对禁忌策略的一种放松.需要指出的是,上述算法仅是一种简单的禁忌搜索框架,对各关键环节复杂和多样化的设计那么可构造出各种禁忌搜索算法.同时,算法流程中的禁忌对象,可以是搜索状态,也可以是特定搜索操作,甚至是搜索目标值等.参考文献1 .董宗然,周慧.禁忌搜索算法评述.中国学术期刊电子出版社.2 .任小康,代文征.基于禁忌搜索算法的旅行售货员问题.佳木斯大学学报,2005.3 .孙