禁忌搜索

禁忌搜索是一种元启发式搜索方法，它采用用于数学优化的局部搜索方法。它由FredW.Glover于1986年创建并于1989年正式化。

本地（邻域）搜索采用问题的潜在解决方案并检查其直接邻居（即相似的解决方案，除了很少的小细节），以期找到改进的解决方案。局部搜索方法倾向于陷入次优区域或许多解决方案同样适合的高原。

禁忌搜索通过放宽其基本规则来增强本地搜索的性能。首先，如果没有可用的改进移动（例如当搜索卡在严格的局部最小值时），则在每一步都可以接受恶化移动。此外，还引入了禁令（以下称为禁忌词）以阻止搜索返回到先前访问过的解决方案。

禁忌搜索的实现使用描述访问过的解决方案或用户提供的规则集的内存结构。如果某个潜在解决方案在某个短期内之前曾被访问过或者它违反了规则，则将其标记为“禁忌”（禁止），以便算法不会重复考虑该可能性。

禁忌搜索(TS)是一种元启发式算法，可用于解决组合优化问题（需要最佳排序和选项选择的问题）。

TS的当前应用跨越资源规划、电信、VLSI设计、财务分析、调度、空间规划、能源分配、分子工程、物流、模式分类等领域、柔性制造、废物管理、矿产勘探、生物医学分析、环境保护和其他许多领域。近年来，各个领域的期刊都发表了教程文章和计算研究，这些文章和计算研究记录了禁忌搜索在扩展可以有效处理的问题的前沿方面取得的成功——产生的解决方案的质量通常xxx超过以前应用的方法获得的解决方案。完整的应用程序列表，包括从实际实现中获得的收益的摘要描述，可以在中找到最近的TS开发和应用程序也可以在禁忌搜索小插图中找到。

禁忌搜索与模拟退火有几个相似之处，因为两者都涉及可能的下坡移动。实际上，模拟退火可以看作是一种特殊形式的TS，其中我们使用“分级任期”，即一个移动以指定的概率成为禁忌。

禁忌搜索中使用的记忆结构大致可以分为三类：

• 短期：最近考虑的解决方案列表。如果潜在解决方案出现在禁忌列表中，则在达到到期点之前无法重新访问。
• 中期：旨在将搜索偏向搜索空间的有希望的区域的强化规则。
• 长期：推动搜索进入新区域的多样化规则（即当搜索陷入停滞或次优死胡同时的重置）。

短期、中期和长期记忆在实践中可以重叠。在这些类别中，可以通过诸如频率和所做更改的影响等措施进一步区分内存。

中期记忆结构的一个例子是禁止或鼓励包含某些属性的解决方案（例如，解决方案包含某些变量的不良或理想值）或防止或诱导某些移动的记忆结构（例如基于频率记忆适用于与过去发现的不吸引人或有吸引力的解决方案具有共同特征的解决方案）。在短期记忆中，最近访问过的解决方案中的选定属性被标记为“禁忌活动”。禁止含有禁忌元素的溶液。采用超越解决方案禁忌状态的吸气标准，从而在允许的集合中包含否则排除的解决方案（假设解决方案根据质量或多样性的度量“足够好”）。一个简单且常用的抽吸标准是允许比目前已知的最佳解决方案更好的解决方案。

单独的短期记忆可能足以获得优于传统局部搜索方法找到的解决方案，但中间和长期结构通常是解决更困难的问题所必需的。禁忌搜索通常以其他元启发式方法为基准——例如模拟退火、遗传算法、蚁群优化算法、反应式搜索优化、引导式本地搜索或贪婪随机自适应搜索。此外，禁忌搜索有时会与其他元启发式方法相结合以创建混合方法。最常见的禁忌搜索混合是通过将TS与ScatterSearch结合而产生的，一类基于群体的程序，其根源与禁忌搜索相同，通常用于解决大型非线性优化问题。