人工智能/搜索/启发式搜索/禁忌搜索
禁忌搜索
禁忌搜索的概念最早由弗雷德·格洛弗在 20 世纪 60 年代初观察他的研究生同学尝试在计算机上模拟解决问题时提出的（Glover 1998）。在那段时间里，他注意到他的同事并没有使用形式逻辑来解决问题，而是通过避免以前尝试过的步骤来缩小问题空间，如果这些步骤被证明是不可取的（Glover 1998）。禁忌这个名字来自禁忌这个词，它恰当地描述了上述现象。禁忌搜索是一种启发式搜索算法，用于解决组合优化问题，其中一组离散的可行解是问题空间，目标是找到尽可能好的解（Glover 1989）。换句话说，它是一种元启发式算法，它可以帮助局部搜索启发式算法在搜索解决方案时达到最佳性能。禁忌搜索的独特之处之一是它灵活的记忆系统，与其他具有固定或无记忆系统的搜索方法不同（Glover 1990）。它还利用了一种约束和释放搜索的策略（即禁忌成分）。
工作原理：禁忌限制被用来防止搜索陷入局部最优解（Glover 1990）。这些约束被设置为防止禁忌搜索进行重复的移动。例如，如果两个位于附近的移动被认为是“最佳”的，那么搜索可能会在两者之间无限地反弹（Glover 1990）。因此，这些重复的移动被标记为“禁忌”，并且在周围的搜索空间中不会返回（Glover 1990）。禁忌限制的最终目标是从局部搜索空间中跳出来，同时保持找到最优解的可能性（Glover 1990）。为了做到这一点，采用了愿望标准来平衡禁忌限制的影响，并允许搜索扩展到更大的搜索范围（Glover 1990）。被标记为“禁忌”的解决方案可以在搜索离开之前有问题的局部最优值后删除其“禁忌”状态。这样一来，这些解决方案仍然会被视为找到全局最优解的可能性（Glover 1990）。
图示：以下是用流程图显示的通用禁忌过程。
Glover, Fred. (1990). 禁忌搜索：一个教程，数学规划实践特刊，接口，20，74-94。
Glover, Fred. (1998). 禁忌搜索——源泉与挑战。欧洲运筹学杂志，106，221-225。
Glover, Fred. (1989). 禁忌搜索——第一部分。ORSA 计算机期刊，1，190-206。