正文 字体大小： 中
禁忌搜索算法（TABU SEARCH） (2007-01-29 12:32:03)
禁忌搜索算法
一. 启发式搜索算法与传统的方法
Tabu Search
二．禁忌搜索与局部邻域搜索
禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁忌表中点的禁忌，而达到一些没有搜索的点，从而实现更大区域的搜索。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解，但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法保证全局优化型。针对局部邻域搜索，为了实现全局优化，可尝试的路径有：以可控性概率接受劣解来跳出局部极小，如模拟退火算法；扩大邻域搜索结构，如
三．禁忌搜索的影响因素
简单的禁忌搜索是在局部邻域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用特赦准则来奖励一些优良状态，其中邻域结构、候选解、禁忌长度、禁忌对象、特赦准则、终止准则等是影响禁忌搜索算法性能的关键。
1． 首先，由于TS是局部邻域搜索的一种扩充，因此邻域结构设计很关键，它决定了当前解的邻域解的产生形式和数目以及各个解之间的关系。
2． 其次，出于改善算法的优化时间性能考虑，如果邻域结构决定了大量的邻域解，则可仅尝试部分解互换的结构，而候选解也仅去其中的少量最佳状态（如TSP中可能会产生 个邻域解）。
3． 禁忌长度是一个很重要的关键参数，它决定禁忌对象的禁忌时间，其大小直接影响整个算法的搜索进程和行为。禁忌对象的替换可以采用FIFO方式，即先进先出，也可以采用其他方式甚至是动态自适应的方式。
4． 特赦准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。
5． 对非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的跳出。
6． 为了使算法具有优良的性能或时间性能，必须设置一个合理的终止准则来结束整个搜索过程。
此外，在许多场合禁忌对象的被禁次数越多也被用于搜索，以取得更大的搜索空间。禁忌次数越高，通常可认为出现循环搜索的概率越大。
四．TS的特点
1． 从移动规则看，每次只与最优点比较，而不与经过点比较，故可以爬出局部最优。
2． 选优规则始终保持曾经达到的最优点，所以即使离开了全局最优点也不会失去全局最优性。
3． 终止规则不以达到局部最优为终止规则，而以最大迭代次数、出现频率限制或者目标值偏离成都为终止规则。
分享
顶
阅读┊ ┊┊ ┊打印┊
加载中，请稍候......
前一篇：数据库密码资源
