禁忌搜索算法的原理

    禁忌搜索算法（Tabu Search，TS）是解决组合优化问题的一种启发式方法。早在1977年，Golver就提出了禁忌搜索算法，并用来求解整数规划问题，随后又用禁忌搜索算法求解了典型的优化问题——旅行商问题（TSP）。它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法［171］［174］。禁忌搜索算法是人类智力过程的一种模拟。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证了多样化的有效搜索以帮助算法摆脱局部最优解，最终实现全局最优。

    用禁忌搜索算法求解组合优化问题时，其实现的基本步骤如下：

    第一步：初始化。给出初始解，将禁忌表设为空。

    第二步：判断是否满足停止条件。如果满足，则输出结果，算法停止；否则继续以下步骤。

    第三步：对于候选解集中的最好解，判断其是否满足渴望水平。如果满足，则更新渴望水平，更新当前解，转至第五步；否则继续以下步骤。

    第四步：选择候选解集中不被禁忌（不对应于禁忌表中的一个对象）的最好解作为当前解。

    第五步：更新禁忌表。

    第六步：转第二步。

    当然，这样的步骤不能概括禁忌搜索算法的各种情况，要根据问题的具体情况，给出更为具体的求解步骤。