禁忌搜索算法摘录.doc

禁忌( Tabu Search )算法是一种亚启发式(meta-heuristic) 随机搜索算法 1, 它从一个初始可行解出发, 选择一系列的特定搜索方向( 移动) 作为试探, 选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解, TS 搜索中采用了一种灵活的“记忆”技术, 对已经进行的优化过程进行记录和选择, 指导下一步的搜索方向, 这就是 Tabu 表的建立。为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目, 不见泰山。禁忌搜索就是对于找到的一部分局部最优解, 有意识地避开它(但不是完全隔绝) ,从而获得更多的搜索区间。兔子们找到了泰山, 它们之中的一只就会留守在这里, 其他的再去别的地方寻找。就这样, 一大圈后, 把找到的几个山峰一比较, 珠穆朗玛峰脱颖而出。当兔子们再寻找的时候, 一般地会有意识地避开泰山, 因为他们知道, 这里已经找过, 并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表( tabu list )”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度, 需要重新考虑, 这个归队时间,在禁忌搜索里面叫做“禁忌长度( tabu length )”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方, 兔子们就不得不再次考虑选中泰山,也就是说,当一个没有兔子留守的地方优越性太突出, 超过了“ best so far ”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来, 这就叫“特赦准则( aspiration criterion )”。这三个概念是禁忌搜索和一般搜索准则最不同的地方, 算法的优化也关键在这里。伪码表达 procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va isa string in the tabu list} begin cur:=va; let va take place of the oldest string in the tabu list; best_to_far:=va; end else begin cur:=vn; let vn take place of the oldest string in the tabu list; end; until (termination-condition); end; 以上程序中的关键(1) 禁忌对象: 可以选取当前的值( cur ) 作为禁忌对象放进 tabu list , 也可以把和当前值在同一“等高线”上的都放进 tabu list 。(2 )为了降低计算量,禁忌长度和禁忌表的集合不宜太大,但是禁忌长度太小容易循环搜索,禁忌表太大容易陷入“局部极优解”。(3 )上述程序段中对 best_to_far 的操作是直接赋值为最优的“解禁候选解”, 但是有时候会出现没有大于 best_to_far 的, 候选解也全部被禁的“死锁”状态, 这个时候, 就应该对候选解中最佳的进行解禁, 以能够继续下去。(4 )终止准则:和模拟退火, 遗传算法差不多,常用的有:给定一个迭代步数; 设定与估计的最优解的距离小于某个范围时, 就终止搜索;当与最优解的距离连续若干步保持不变时,终止搜索; (5) 邻域: 由伪码 select a new string vn in the neighborhood of vc,可以看出, 系统总是在初始点的邻域搜索可能的解的, 因而必须定义适合的邻域定义, 如果解空间的存在一个最优解 X*, 初始搜索点为 S0, 那么如果S0 不存在到达 X* 的通路, 就会使搜索陷入S0 的邻域的局部最优解。可以证明如果邻域满足对称性条件, 则在假设禁忌表足够长的情况下必然可搜索到全局最优解。其他智能算法禁忌搜索是对人类思维过程本身的一种模拟, 它通过对一些局部最优解的禁忌( 也可以说是记忆) 达到接纳一部分较差解, 从而跳出局部搜索的目的. 遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。蚂蚁算法是群体智能可用于解决其他组合优化问题, 比如有 n个城市,需要对所有 n 个城市进行访问且