禁忌搜索算法.ppt

禁忌搜索算法
主要内容
背景及意义
国内外研究现状
基本原理
应用举例
互动问题
背景及意义
工程领域内存在大量的优化问题,实际的优化问题之所以难以求解,归纳起来有以下一些原因:
⑴搜索空间中可能解的数目太多以至于无法采用穷举搜索法去找到最优解;
⑵问题是如此以至于为了得到任何解答,不得不采用问题的简化模型,而实际上所得的结果是无用的;
⑶可能接都被严格约束以至于构造哪怕一个可行解都是困难的,更不用说找到最优解了;
⑷求解问题的人没有做好充分的准备或存在某种心理障碍使得他们难以找到答案。
因此对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。
TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化。
国内外研究现状
Glover教授分别在1989年和1990年发表了两篇著名的标题为Tabu search的论文,提出了现在大家熟知的禁忌搜索算法的大部分原理。
其中一些原理在学术界长期没有突破。事实上,在20世纪90年代前半叶,大部分工作局限在关于禁忌搜索技术的非常有限区域,如禁忌表和基本的藐视准则。
20世纪80年代后期 Werra团队所发表的系列论文在学术界发挥的重要作用使得禁忌搜索技术广闻人知。
20世纪90年代初期,禁忌搜索算法传到加拿大,准确的说,位于蒙特利尔的运输研究中心,来自Werra团队的博士后人员在此从事该领域的研究。在此过程中,形成禁忌搜索的有一个研究中心,该算法很快在相关领域得到了成功的应用。1990年,随着一本介绍禁忌搜索的专著的出版,禁忌搜索的研究达到了一个高峰。
1997年,Glover与Laguna合著的第一本禁忌搜索专著正式出版,标志着关于禁忌搜索的相关研究日趋完善,并得到了同行的认可。
目前关于TS的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题。