文档介绍：by谢广明,2005~2006学年度第一学期1第五章禁忌搜索(I)Tabu Search, TSby谢广明,2005~2006学年度第一学期2简介?TSA属于随机模拟算法–是对局部邻域搜索的一种扩展,是一种全局逐步寻优、高效启发式优化技术和对人类智力过程的一种模拟. TS 算法通过引入一个灵活的存储结构和相应的禁忌准则,以避免迂回搜索,并通过藐视准则赦免一些被禁忌的优良状态,进而保证多样化的有效搜索,最终实现全局优化.–禁忌就是禁止重复前面的操作?鼻祖–Fred W. Glover教授 1986年建立–美国University of Coloradoby谢广明,2005~2006学年度第一学期3简介?. Glover–/~glover–fred.******@?Book:Tabu Search–F. Glover and M. Laguna, Kluwer Academic Publishers: Boston, ISBN: 0-7923-8187-4, 408 pp. by谢广明,2005~2006学年度第一学期4内容?提出依据?基本概念?算法机制?算法流程?算法特点?算法基础理论?应用领域?简单演示by谢广明,2005~2006学年度第一学期5提出依据?局部邻域搜索的缺点–基于贪婪思想持续地在当前解的邻域中进行搜索,算法通用易实现,且容易理解。–但其搜索性能完全依赖于邻域结构和初始解,尤其容易陷入局部极小而无法保证全局优化性。by谢广明,2005~2006学年度第一学期6提出依据?针对局部邻域搜索,为了实现全局优化,已经尝试的途径有:–以可控性概率接受劣解来逃逸局部极小,如SA;–扩大邻域搜索结构,如TSP的2opt扩展到k-opt;–多点并行搜索,如GA;–变结构邻域搜索;?但是算法有时候会又回到某个局部最小解无法跳出by谢广明,2005~2006学年度第一学期7提出依据?人类在选择过程中具有记忆功能,比如走迷宫时,当发现有可能又回到某个地点的时候会有意识的避开先前选择的方向而选择其它的可能性,这样就可以确定性的避开迂回搜索。?借鉴人类的智能思考特性,采用禁忌策略尽量避免迂回搜索,就构成了禁忌搜索算法,它是一种确定性的局部极小突跳策略。by谢广明,2005~2006学年度第一学期8提出依据?禁忌搜索是人类智能的一种人工体现,是局部邻域搜索的一种扩展。?禁忌搜索核心思想是标记对应已搜索到的局部最优解的一些操作或对象,并在进一步的迭代搜索中尽量避开这些操作或对象(而不是绝对禁止),从而保证对不同的有效搜索途径的探索。by谢广明,2005~2006学年度第一学期9TS基本概念?禁忌搜索的基本概念:–邻域(neighborhood)–禁忌表(tabu list)和禁忌长度(tabu length)–best so far 状态–候选解(candidate)–藐视准则(aspiration criterion) –禁忌频率(frequency)by谢广明,2005~2006学年度第一学期10TS基本概念?邻域–对组合优化问题,必须设计合理的邻域–TS是局部邻域搜索的一种扩充,因此邻域结构的设计很关键,它决定了当前解的邻域解的产生模式和数目,以及各个解之间的联系。–出于改善算法的优化时间性能的考虑,若邻域结构决定了大量的邻域解,则可以仅尝试部分互换的结果,而候选解也仅取其中的少量最佳状态。