禁忌搜索
三张网图简要概述
一些概念的解释
禁忌对象 (TO)
是指禁忌表中被禁的那些变化元素。禁忌对象的选择可以根据具体问题而制定。例如在旅行商问题中可以将交换的城市对作为禁忌对象，也可以将总路径长度作为禁忌对象。
禁忌表（TL）
是用来存放（记忆）禁忌对象的表。它是禁忌搜索得以进行的基本前提。禁忌表本身是有容量限制的，它的大小对存放禁忌对象的个数有影响，会影响算法的性能。
禁忌期限(TT)
也叫禁忌长度，指的是禁忌对象不能被选取的周期。禁忌期限过短容易出现循环，跳不出局部最优，长度过长会造成计算时间过长。
渴望准则(AC)
也称为特赦规则。当所有的对象都被禁忌之后，可以让其中性能最好的被禁忌对象解禁，或者当某个对象解禁会带来目标值的很大改进时，也可以使用特赦规则。
中期表
也称为频数表或者频率表，对从一个解到另一个解的移动被禁忌的次数进行记录，对被禁忌次数较多的移动实行一定的惩罚策略。
长期表：
引入长期表以后，禁忌搜索算法就成为了多阶段禁忌搜索算法。如果经过多次迭代仍然不能更新历史最优解，可以重新给出初始解，在一个新的区域开始搜索，这种记录多个初始解的表称为长期表。
邻域搜索规则
每一步移动到不在T表中的邻域中的最优解。
$C(S_k(x)) = best{}$
禁忌搜索的特点
- 适合离散问题的优化，不适合实优化
- 局部贪心原则。在领域中选择局部最优解更新当前状态。