局部搜索算法

⑴ 禁忌搜索局部领域搜索

局部领域搜索，基于贪婪策略，简单易行，易于理解，但它在搜索性能上受限于初始解和领域结构。它容易陷入局部最优，而非全局最优。为了克服这个问题，可以采取多种策略：如模拟退火算法，通过可控概率接受较差解来逃离局部极小；TSP的2opt方法可以扩展到k-opt，扩大搜索范围；进化计算则提倡多点并行搜索；变结构领域搜索（Mladenovic等人，1997）也提供了一种创新方法。禁忌策略在TS中起着关键作用，它通过标记已探索的局部最优，避免重复搜索，采用确定性的策略来跳出局部极小，这是一种对不同有效搜索路径的积极探索。

禁忌搜索作为人工智能的一个分支，是对局部领域搜索的扩展。其核心理念是记录已搜索过的局部最优解，并在后续搜索中避开它们，而非彻底禁止。这个过程涉及到临域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）以及藐视准则（aspiration criterion）等关键概念，它们共同作用于提升搜索的全局优化性能。

禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的 meta-heuristic算法。