- 导言
- 伪随机数产生方法
- 遗传算法(GA)
- 禁忌搜索(TS)
- 模拟退火(SA)
- 其他智能优化算法(神经网络,机器学习,深度学习等)
- Matlab与部分智能优化算法
参考书:
- 《智能优化方法》汪定伟 王俊伟 王洪峰 张瑞友 郭哲 编著,高等教育出版社
- 《智能优化算法原理与应用》李士勇 等编著, 哈尔滨工业 大学出版社
- Multi-Objective Optimization using Evolutionary Algorithms Kalyanmoy Deb, John Wiley & Sons, LTD
禁忌(Tabu Search)算法是一种亚启发式(meta-heuristic)随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向,这就是Tabu表的建立。
禁忌搜索(tabu search,TS)中的“Tabu”一词最早来源于汤加语,它的本意是指不能触摸的东西,因为它是神圣的。禁忌搜索由美国科罗拉多大学系统科学家Glover教授于1986年在一篇论文中首次提出。之后不久,Glover教授分别在1986年和1990年发表了两篇著名的标题为Tabu search的论文,提出了现在大家所熟知的禁忌搜索的大部分原理。
禁忌搜索的流行应归功与瑞士联邦理工学院Werra所带领的团队在20世纪80年代后期的开创性工作。因为在当时Glover的文章在没有“超启发式文化”的情况下并没有被很好地理解。正是由于Werra团队所发表的系列论文在学术界发挥的重要作用,才使禁忌搜索技术广为人知。1990年,随着介绍禁忌搜索的第一本专著的出版,禁忌搜索的研究达到了一个高峰。1997年,Glover与Laguna合著的第一本禁忌搜索专著正式出版,标志着禁忌搜索的相关研究日趋完善,并得到了同行的认可。
一.导言
二.TS的基本原理及步骤
三.TS的算法步骤
四.TS可以克服局优的分析
五.TS举例
六.TS的中、长期表的使用
七.TS表的应用举例
八.学习TS的几点体会
TS的提出:
1977年F.Glover提出TS ,90年代初得到广泛重视。是一种元启发式优化算法;模仿人类的记忆功能;禁忌搜索算法成功用于组合优化、生产调度、机器 学习、神经网络、电力系统以及通信系统。
TS的基本思想——避免在搜索过程中的循环:
1 只进不退的原则——用Tabu表锁住退路
2 不以局部最优作为停止准则
3 邻域选优的规则模拟了人类的记忆功能——找过的地方都记下来,不再找第二次
TS的要素构成:
1 禁忌表(Tabu List)
2 渴望水平函数(Aspiration Level Function)
3 移动规则——邻域选优
4 选优规则——保持历史上的最优解
5 停止准则——与GA相似
- 问题的描述及邻域的概念
TS仅用于离散优化,排斥实优化
2.邻域(自己定义)
局部邻域搜索:贪婪、持续在当前邻域中搜索,直至邻域中没有更好的解。 又称爬山启发式算法。 邻域搜索的过程就是从一个解移动到另一个解,移动用s表s(x)示,从当前解出发的所有移动得到的解集合用S(x)表示。
邻域的概念:x的邻域移动为s=x+ud, u为单位步长,d为方向,则:
,邻域S (x)是邻域移动可达到的解的集合。
邻域举例:
X=[0,1,0,0,1,0,0]
u=1, d=[0,0,1,0,0,0,0]
s(x)=x+ ud=[0,1,1,0,1,0,0]
注意:移动的意义是灵活的,目的是便于搜索。如: 排序问题中一次换位可称为一次移动,还可以定义为 选一个切点,两部分作交叉运算。
3. 禁忌表的概念
禁忌表的作用:防止搜索出现循环
- 记录前若干步走过的点、方向或目标值,禁止返回
- 表是动态更新的——把最新的解记入,最老的解从 表中释放(解禁)。
- 表的长度称为Tabu-Size,一般取5、 7 、11,表长越大分散性越好。
4. 邻域搜索规则:每一步移动到不在T表中的邻域中的最优解。
邻域搜索规则的作用:保证TS的优良局部搜索功能
5. 渴望水平函数
A(s,x)是一个取决于s和x的值,若有 C(s(x))<A(s,x)则 S(x)是不受T表限制。即使 s(x)∈T ,仍可取x=s(x) 渴望水平,一般为历史上曾经达到的最好A(s,x) 目标值。