• 导言
鸣也：智能优化算法(1)
  • 伪随机数产生方法
鸣也：智能优化方法——伪随机数生成算法
  • 遗传算法(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相似

  1. 问题的描述及邻域的概念

\\begin{array}{l}\\min C(x) \\\\ \ ext{ s.t. }x \\in X \\subset \\mathrm{R}^{\\mathrm{n}}\\quad \\mathrm{X}\ ext{ 是离散值空间 }\\end{array}

TS仅用于离散优化，排斥实优化

2.邻域（自己定义）

局部邻域搜索:贪婪、持续在当前邻域中搜索，直至邻域中没有更好的解。 又称爬山启发式算法。 邻域搜索的过程就是从一个解移动到另一个解，移动用s表s(x)示，从当前解出发的所有移动得到的解集合用S(x)表示。

邻域的概念：x的邻域移动为s=x+ud， u为单位步长，d为方向，则:
S(x )=\\{s| s=x+ud,s \\in X \\} ，邻域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) 目标值。