下载掌阅APP，畅读海量书库
立即打开
禁忌搜索算法是解决组合优化问题的另一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。该算法可以克服爬山算法全局搜索能力不强的弱点。
在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的邻域中搜索若干个解，取其中的最好解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。
用禁忌搜索算法求解组合优化问题时，其实现步骤如下（以目标函数求最小为例）。
第一步：选定一个初始解x now ；令禁忌表H=φ。
第二步：若满足终止准则，转第四步；否则，在x now 的邻域N（x now ）中选出满足禁忌要求的候选集Can_N（x now ），转第三步。
第三步：在Can_N（x now ）中选一个评价值最好的解x best ，令x now =x best ，更新禁忌表H，转第二步。
第四步：输出计算结果，停止。
禁忌搜索算法的第二步中，x now 的邻域N（x now ）中满足禁忌要求的解包括两类，一类是那些没有被禁忌的解，另一类是可以被解除禁忌的解。