3.1 禁忌搜索算法的原理和实现步骤

1.禁忌搜索算法的原理

禁忌搜索算法是解决组合优化问题的另一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。该算法可以克服爬山算法全局搜索能力不强的弱点。

在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的邻域中搜索若干个解，取其中的最好解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。

2.禁忌搜索算法的实现步骤

用禁忌搜索算法求解组合优化问题时，其实现步骤如下（以目标函数求最小为例）。

第一步：选定一个初始解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 ）中满足禁忌要求的解包括两类，一类是那些没有被禁忌的解，另一类是可以被解除禁忌的解。 Se7vlLAI+FQo7saNAdzjkvbBtNPbpuQ4yFSuyg0ySy9AJMDeGaLQD/+lMGkPkBiN