文档介绍：禁忌搜索算法 2009210042 李同玲运筹学与控制论搜索是人工智能的一个基本问题,一个问题的求解过程就是搜索。人工智能在各应用领域中, 被广泛的使用。现在, 搜索技术渗透在各种人工智能系统中, 可以说没有哪一种人工智能的应用不用搜索方法。禁忌搜索算法(Tabu Search 或 Taboo Search, 简称 TS) 的思想最早由 Glover ( 美国工程院院士,科罗拉多大学教授)在 1977 年提出,它是对局部邻域搜索的一种扩展, 是一种全局邻域搜索算法, 是人工智能的一种体现, 是一种全局逐步寻优算法, 是对人类智力过程的一种模拟。 TS 算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索, 并通过藐视准则来赦免一些被禁忌的优良状态, 进而保证多样化的有效探索以最终实现全局优化。迄今为止, TS 算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功, 近年来又在函数全局优化方面得到较多的研究, 并大有发展的趋势。 引言 局部邻域搜索局部邻域搜索是基于贪婪思想持续地在当前的邻域中进行搜索, 虽然算法通用易实现, 且容易理解, 但其搜索性能完全依赖于邻域结构和初始解,尤其容易陷入局部极小而无法保证全局优化性。局部搜索的算法可以描述为: 1、选定一个初始可行解: 0x ; 记录当前最优解 0 best x x ?, ( ) best T N x ?; 2、当\ best T x ??时,或满足其他停止运算准则时,输出计算结果, 停止运算;否则,从 T 中选一集合 S ,得到 S 中的最好解 nowx ; 若( ) ( ) now best f x f x ?,则 best now x x ?, ( ) best T N x ?;否则, \ T T S ?; 重复 2 ,继续搜索这种邻域搜索方法容易实现理解, 容易实现, 而且具有很好的通用性, 但是搜索结果完全依赖于初始解和邻域的结构, 而且只能搜索到局部最优解。为了实现全局搜索, 禁忌搜索采用允许接受劣解来逃离局部最优解。针对局部领域搜索, 为了实现全局优化, 可尝试的途径有:以可控性概率接受劣解来逃逸局部极小,如模拟退火算法;扩大领域搜索结构,如 TSP 的 2-opt 扩展到 k-opt ;多点并行搜索,如进化计算; 变结构领域搜索( Mladenovic et al,1997 ); 另外, 就是采用 TS 的禁忌策略尽量避免迂回搜索, 它是一种确定性的局部极小突跳策略。 禁忌搜索算法的基本思想禁忌搜索算法的基本思想就是在搜索过程中将近期的历史上的搜索过程存放在禁忌表( Tabu List )中, 阻止算法重复进入, 这样就有效地防止了搜索过程的循环。禁忌表模仿了人类的记忆功能, 禁忌搜索因此得名,所以称它是一种智能优化算法。具体的思路如下:禁忌搜索算法采用了邻域选优的搜索方法,为了能逃离局部最优解, 算法必须能够接受劣解, 也就是每一次迭代得到的解不必一定优于原来的解。但是。一旦接受了劣解, 迭代就可能陷入循环。为了避免循环, 算法将最近接受的一些移动放在禁忌表中, 在以后的迭代中加以禁止。即只有不在禁忌表中的较好解( 可能比当前解差) 才能接受作为下一次迭代的初始解。随着迭代的进行, 禁忌表不断更新, 经过一定迭代次数后, 最早进入禁忌表的移动就从禁忌表中解禁退后。为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目, 不见泰山。禁忌搜索就是对于找到的一部分局部最优解, 有意识地避开它(但不是完全隔绝) ,从而获得更多的搜索区间。兔子们找到了泰山, 它们之中的一只就会留守在这里, 其他的再去别的地方寻找。就这样, 一大圈后, 把找到的几个山峰一比较, 珠穆朗玛峰脱颖而出。当兔子们再寻找的时候, 一般地会有意识地避开泰山, 因为他们知道, 这里已经找过, 并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表( tabu list )”的含义。那只留在泰山的兔子一般不会就安家在那里了, 它会在一定时间后重新回到找最高峰的大军, 因为这个时候已经有了许多新的消息, 泰山毕竟也有一个不错的高度, 需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度( tabu length )”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方, 兔子们就不得不再次考虑选中泰山, 也就是说, 当一个有兔子留守的地方优越性太突出, 超过了“ best to far ”的状态, 就可以不顾及有没有兔子留守, 都把这个地方考虑进来,这就叫“特赦准则