禁忌搜索算法中很多构成要素对搜索的速度与质量至关重要，需要对其进行合理的确定。下面简单地介绍这些构成要素：
1． 编码方法
使用禁忌搜索算法求解一个问题之前，需要选择一种编码方法。编码就是将实际问题的解用一种便于算法操作的形式来描述，通常采用数学的形式；算法进行过程中或者算法结束之后，还需要通过编码来还原到实际问题的解。根据问题的具体情况，可以灵活地选择编码方式。例如，对于背包问题，可以采用0—1编码，编码的某一位为0表示不选择这件物品，为1表示选择这件物品。对于实际优化问题，一般可以直接使用实数编码，编码的每一位就是解的相应维的取值。
2． 初始解和适值函数的构造
禁忌搜索算法可以随机给出初始解，也可以事先使用其他启发式算法得到一个较好的初始解。由于禁忌搜索算法主要是基于邻域搜索的，所以它对初始解有很高的要求，较好的初始解可帮助搜索到较好的解，而较差的初始解则可能会降低禁忌搜索算法的收敛速度。因此，我们在求解一些具体问题时，可以针对特定的复杂约束，采用其他精确方法或启发式方法生成质量比较高的初始解，然后再用禁忌搜索算法进行改进，这样可以提高搜索的质量和效率。
与遗传算法相似的是，禁忌搜索算法的适值函数也是用来对搜索状态进行评价的。目前，将目标函数直接作为适值函数是比较常用而且合适的。当然，也可以对目标函数做一些变形，然后作为适值函数。假如目标函数的计算比较复杂而且计算时间长，我们就可以采用反映问题目标的某些特征值来作为适值函数，这样可以改善算法的时间性能。此外，选取何种特征值要根据具体问题而定，但是必须要保证特征值的最佳性与目标函数的最优性一致。
3． 移动与领域移动
移动是从当前解产生新解的途径，例如某优化问题：minc（x）：x∈X⊂Rn中用移动s产生新解s（x）。从当前解可以进行的所有移动构成邻域，也可以理解为从当前解经过“一步”可以到达的区域。适当的移动规则的设计，是取得高效的搜索算法的关键。
领域移动的方法很多，目前，常用的方法有互换（Swap）、插入（Insert）、逆序（Inverse）等操作，具体的方法需要根据特定的问题来设计。
4． 禁忌表
在禁忌搜索算法中，禁忌表是用来防止搜索过程中出现循环，避免陷入局部最优的。它通常记录最近接受的若干次移动，在一定次数之内禁止再次被访问；过了一定次数之后，这些移动从禁忌表中退出，又可以重新被访问。
禁忌表一般包括禁忌对象和禁忌长度。所谓禁忌对象就是放入禁忌表中的那些元素，而禁忌的目的就是避免迂回搜索，尽量搜索一些有效的途径。可以有多种方式给出禁忌对象，但归纳起来，主要有如下三种：以状态的本身或者状态的变化作为禁忌对象；以状态分量或者状态分量的变化作为禁忌对象；采取类似于等高线的做法，将目标值作为禁忌对象。这三种做法中，第一种做法的禁忌范围适中，第二种做法的禁忌范围较小，第三种做法的禁忌范围较大。如果禁忌范围比较大，则可能陷入局部最优解；反之，则容易陷入循环。实际问题中，要根据问题的规模、禁忌表的长度等具体情况来确定禁忌对象。
所谓禁忌长度就是指禁忌对象在不考虑特赦准则的情况下不允许被选取的最大次数。一方面，禁忌长度可以是常数不变的，或者是设置为与问题规模相关的一个量；另一方面，禁忌长度也可以是动态变化的。例如，可以根据搜索性能和问题特征来设定禁忌长度的变化区间，而禁忌长度是可以按照某种规则或者公式在这个区间内变化，当然，这个变化区间的大小也可以随着搜索性能的变化而变化。
5． 选择策略
选择策略就是从邻域中选择一个比较好的解作为下一次迭代初始解的方法，用公式可以表示为
其中，x为当前解，x′为选出的邻域最好解，s（x）∈V为领域解， c′（s（x））为候选集s（x）的适值函数，V⊆S（x）称为候选解集，它是领域的一个子集。要根据问题的性质和适值函数的形式，在候选集中选择一个最好的解。然而，候选集的确定，与上面讨论的禁忌长度的大小相似，对搜索速度与性能影响都很大。候选解集一般为整个邻域，即V＝S（x）。这种选择策略就是从整个领域中选择一个最优的解作为下一次迭代的初始解。这种策略择优效果好，相当于选择了最速下降方向，但要扫描整个邻域，计算时间比较长，尤其对于大规模的问题，这种策略可能让人无法接受。这时候会在部分邻域中选择候选解集，这种策略虽然不一定得到了领域中的最好解，但是节省了大量的时间，可以进行更多次迭代，也可以找到很好的解。
6． 渴望水平
在某些特定的条件下，不管某个移动是否在禁忌表中，都接受这个移动，并更新当前解和历史最优解。这个移动满足的特定条件，称为渴望水平，或称为破禁水平、特赦准则、蔑视准则等。特赦准则的常用方式有：（1）基于适配值的原则。如果某个候选解的适配值优于历史最优值，也称为“Bestso Far”状态，那么无论这个候选集是否处于被禁忌状态，都会被接受。（2）基于搜索方向的准则。如果禁忌对象在被禁忌时，使候选集的适配值有所改善，并且目前该禁忌对象对应的候选解的适配值优于当前解，则对该禁忌对象解禁。（3）基于影响力的准则。在搜索过程中不同对象的变化对适配值的影响是有所不同的，而且这种影响力可以作为一种属性与禁忌长度和适配值来共同构造特赦准则。
7． 停止准则
和其他启发式算法一样，禁忌搜索算法不能保证找到问题的全局最优解，而且没有判断是否找到全局最优解的准则。因此，必须另外给出停止准则来停止搜索，常用的包括如下几种。
（1）给定最大迭代步数。这个方法简单、易操作，在实际中应用最为广泛。
（2）得到满意解。如果事先知道问题的最优解，而算法已经达到最优解，或者与最优解的偏差达到满意的程度，则停止算法。这种情况常应用于算法效果的验证，因为只有这个时候问题的最优解才可能是事先知道的。或者在实际应用中，用其他估界算法已经估算出问题的上界（目标函数是最大化）或者下界（目标函数是最小化），如果搜索得到的历史最优解与这些“界”的偏差满足要求，停止算法，其实这也是得到了满意解。
（3）设定某对象的最大禁忌频率。如果某对象的禁忌频率达到了事先给出的阈值，或者历史最优值连续若干步迭代得不到改善，则算法停止。
上一篇：“兀良哈”与蒙古草原之道
下一篇：会计信息质量要求及时性
