文档介绍：禁忌搜索算法
2009210042李同玲 运筹学与控制论
搜索是人工智能的一个基本问题，一个问题的求解过程就是搜 索。人工智能在各应用领域中，被广泛的使用。现在，搜索技术渗透 在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索索的局部最优解的一些 对象，并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止 循环)，从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到编 码方式(Encode)、适值函数、移动(Moving)与领域(neighborhood)> 禁忌表(tabu list)、禁忌长度(tabu length)、选择策略(Selection Strategy)>候选解(candidate)、藐视准则(candidate)等概念，下面 将介绍一下这些概念
编码就是将实际问题的解用一种便于算法操作的形式来描述，通 常采用数学的形式；算法进行过程中活着算法结束之后，还需要通过 解码来还原到实际问题的解。
根据问题的具体情况，可以灵活地选择编码方式。下面介绍两种 编码。
编码1
各不相同的n件物品要分为m组，满足特定的约束条件，要达 到特定的目标函数。以自然数1-n分别代表n件物品，n个数加上 m-1个分割符号(例如用
0表示)混编在一起，随意排列，使得到一 种编码方式。例如，n=9, m=3,下面便是一个合法的编码：
1-3-4-0-2-6-7-5-0-8-9 这种可以成为带分隔符的顺序编码。
编码2
编码的每一位分别代表一件物品，而每一位的值代表该物品所 在得分组。同样是n=9,m=3的情况，可以给出如下形式的编码：
1-2-1-1-2-2-3-3
这种是一般的自然数编码。
不同编码形式通常是可以相互转化的，例如带分隔符的顺序编码 与一般的自然数编码就很容易相互转化。事实上，上面给出的两个编 码表示的是同一个解，也就是物品1， 3， 4分在第一组；物品2， 6, 7, 5分在第二组；其余的物品8, 9分在第三组。
将目标函数直接作为适值函数是最直接也是最容易理解的做法。 当然，对目标函数的任何变形都可以作为适值函数，只要这个变形是 严格单调的。例如，对于目标函数才c(x)，设适值函数用c’(x)表示，
r
那么C⑴= "(x))2顷 那么都是可以的，只要在选择的时候注意一下 kc(x)+b c(X)>0 ac (X) a >0, a 壬 1
...
这个变形应该和原来目标函数的大小顺序保持一致。
适值函数的选择主要考虑提高算法的效率、便于搜索的进行等因 素，以上给出的各种变形都是针对特定的目标函数形式为了简化算法 而设计的。
禁忌搜索算法可以随机给出初始解，也可以事先使用其他启发式 等算法给出一个较好的初始解。由于禁忌搜索算法主要是基于邻域搜 索的，初始解的好坏对搜索的性能影响很大。尤其是一些带有很复杂 约束的优化问题，如果随机给出初始解很可能是不行的，甚至通过多 步搜索也很难找到一个可行解，这个时候应该针对特定的复杂约束， 采用启发式方法或其它方法找出一个可行解作为初始解。
移动是从当前解产生新解的途径，从当前解可以进行的所有移动 构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。适 当的移动规则的设计，是取得高效的搜索算法的关键。
邻域移动是从一个解产生另一个解的途径。它是保证产生好的解 和算法搜索速度的最重要因素之一。邻域移动定义的方法很多，对于 不同的问题应采用不同的定义方法。通过移动，目标函数值将产生变 化，移动前后的目标函数值之差，称之为移动值。如果移动值是非负 的，则称此移动为改进移动;否则称作非改进移动。最好的移动不一 定是改进移动，也可能是非改进移动，这一点就保证搜索陷入局部最 优时，禁忌搜索算法能自动把它跳出局部最优。
不允许恢复即被禁止的性质称作Tabu。禁忌表的主要目的是阻止 搜索过程中出现循环和避免陷入局部最优，它通常记录前若干次的移 动，禁止这些移动在近期内返回。在迭代固定次数后，禁忌表释放这 些移动，重新参加运算，因此它是一个循环表，每迭代一次，将最近 的一次移动放在禁忌表的末端，而它的最早的一个移动就从禁忌表中
释放出来。为了节省记忆时间，禁忌表并不记录所有的移动，只记录 那些有特殊性质的移动，如记载能引起目标函数发生变化的移动。禁 忌表记载移动的方式主要有三种:*记录目标值；*移动前的状态；*移 禁忌搜索算法在冷藏供应链配送网络中的应用研究动本身。
禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影响 着搜索速度和解的质量。如果选择的好，可有助于识别出曾搜索过的 区域。实验表明，如果禁忌表长