02禁忌搜索TS.doc

导言
禁忌搜索(Tabu Search或Taboo Search,简称TS)算法是继遗传算法之后出现的又一种元启发式(Meta-Heuristic)优化算法,最早于1977年由Glover提出。
禁忌搜索算法模仿人类的记忆功能,使用禁忌表来封锁刚搜索过的区域来避免迂回搜索,同时赦免禁忌区域中的一些优良状态,进而保证搜索的多样性,从而达到全局优化。
迄今为止,禁忌搜索算法已经成功应用于组合优化、生产调度、机器学****神经网络、电力系统以及通信系统等领域。
基本思想
禁忌搜索算法的基本思想就是在搜索过程中将近期的历史上的搜索过程存放在禁忌表(Tabu List)中,阻止算法重复进入,这样就有效的防止了搜索过程的循环。禁忌表模仿了人类的记忆功能,禁忌搜索因此得名,所以称它是一种智能优化算法。
具体思路如下:禁忌搜索算法采用了领域选优的搜索方法,为了能逃离局域最优解,算法必须能够接受劣解,也就是每一次迭代得到的解不必一定优于原来的解。但是,一旦接受了劣解,迭代就可能陷入循环。为了避免循环,算法将最近接受的一些移动放在禁忌表中,在以后的迭代中加以禁止。即只有不在禁忌表中的较好解(可能比当前解差)才被接受作为下一次迭代的初始解。随着迭代的进行,禁忌表不断更新,经过一定迭代次数后,最早进入禁忌表的移动就从禁忌表中解禁退出。
相对于普通领域搜索而言,禁忌搜索算法最大的特点是可以接受劣解,这是避免陷入局部最优的首要条件。
算法的构成要素
禁忌搜索算法中很多构成要素对搜索的速度与质量至关重要,包括:
编码方式(Encode):使用禁忌算法求解一个问题之前,需要选择一种编码方法。根据问题的具体情况,可以灵活的选择编码方式。对同一个问题,也可以有多种编码方式可供选择。不同编码形式通常是可以相互转化的。实际应用中,希望编码空间尽可能和解空间一样大小,也就是说编码和解具有严格的一一对应关系。然而,对于许多的实际问题,这并不是一件容易的事情。
适值函数:适值函数的选择主要考虑提高算法的效率、便于搜索的进行等因素。
解得初始化:禁忌搜索算法可以随机给出初始解,也可以事先使用其他启发式等算法给出一个较好的初始解。
移动(Moving)与领域(Neighborhood):移动式是从当前解产生新解的途径,也可以理解为从当前解经过“一步”可以到达的区域。适当的移动规划设计,是取得高效的搜索算法的关键。领域移动的方法很多,求解不同的问题需要设计不同的移动规则。禁忌搜索算法中的领域移动规则和遗传算法中的交叉算子和变异算子相似,需要根据特定的问题来设计。
禁忌表(Tabu List):在禁忌搜索算法中,禁忌表是用来防止搜索过程中出现循环,避免陷入局部最优的。它通常记录最近接受的若干次移动,在一定次数之内禁止再次被访问;过了一定次数之后,这些移动从禁忌表中退出,又可以重新被访问。禁忌表是禁忌搜索算法中的核心,它的功能和人类的短期记忆能力十分相似,因此由称为“短期表”。
选择策略(Selection Strategy):选择策略就是从领域中选择一个比较好的解作为下一次迭代初始解得方法。要根据问题的性质和适值函数的形式,在候选解集中选择一个最好的解。
渴望水平(Aspiration Level):在某些特定的条件下,不管某个移动是否在禁忌表中,都接受这个移动,并更新当前解