禁忌搜索算法.ppt

文档介绍：禁忌搜索 Tabu Search ?禁忌搜索( Tabu Search 或 Taboo Search , 简称 TS) 的思想最早由 Glover(1986) 提出, 它是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。禁忌搜索概述禁忌搜索概述? TS 算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。?相对于模拟退火和遗传算法, TS 是又一种搜索特点不同的算法。迄今为止, TS 算法在组合优化、生产调度、机器学****电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有发展的趋势。?特点– Neighborhood search + memory ? Neighborhood search ? Memory – Record the search history – Forbid cycling search Tabu Search 3的邻域搜索陷入循环 1的邻域 1 2的邻域 24的邻域 4 3在邻域中找到最好的解加入禁忌表,避免陷入循环禁忌表长度为 3:{①, ②, ③}规则:不得接受与禁忌表中相同的解禁忌表的变化: 第一步搜索时{ } 第二步搜索时{① } 第三步搜索时{①, ②, } 第四步搜索时{①, ②, ③} 避免循环的原理:当前解为④时,其领域中最好的解为①,原本下一步应为①,但其与禁忌表中的元素相同,所以选择次好的解⑤, 从而避免死循环 3的邻域 1的邻域 1 2的邻域 24的邻域 4 3 5禁忌表的更新更新原则:先进先出{①, ②, ③} { ②, ③, ④} { ③ , ④, ⑤} ….禁忌表中元素禁忌表中元素的可以是完整的解,可以是完整解的一部分,也可以是采取的一个生成相邻解的动作等等完整解: {12345,13245,31245} 生成相邻解的操作(如交换的动作): {32, 31} 从 12345 开始,取 3出来,插入 1245 每个位置前面禁忌表长度太短:计算速度快,但容易陷入死循环太长:计算速度慢在搜索过程中,禁忌表长度设为固定在搜索过程中,禁忌表长度可动态变化禁忌表长度: 5— 10