文档介绍：禁忌搜索( Tabu Search 或 Taboo Search ,简称 TS )的思想最早由 Glover(1986) 提出, 它是对局部领域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。 TS 算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索, 并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法, T 是又一种搜索特点不同的 meta-heuristic 算法。迄今为止, TS 算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功, 近年来又在函数全局优化方面得到较多的研究, 并大有发展的趋势。本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内容。 1. 引言局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索,虽然算法通用易实现,且容易理解,但其搜索性能完全依赖于领域结构和初解,尤其会陷入局部极小而无法保证全局优化性。针对局部领域搜索,为了实现全局优化,可尝试的途径有:以可控性概率接受劣解来逃逸局部极小,如模拟退火算法;扩大领域搜索结构,如 TSP 的 2opt 扩展到 k-opt ;多点并行搜索,如进化计算;变结构领域搜索( Mladenovic et al,1997 ) ;另外,就是采用 TS 的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小突跳策略。禁忌搜索是人工智能的一种体现,是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环), 从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到领域( neighborhood )、禁忌表( tabu list )、禁忌长度( tabu l ength )、候选解( candidate )、藐视准则( candidate ) 等概念,我们首先用一个示例来理解禁忌搜索及其各重要概念,而后给出算法的一般流程。 2. 禁忌搜索示例组合优化是 TS 算法应用最多的领域。置换问题,如 TSP 、调度问题等,是一大批组合优化问题的典型代表,在此用它来解释简单的禁忌搜索算法的思想和操作。对于 n 元素的置换问题, 其所有排列状态数为 n!,当n 较大时搜索空间的大小将是天文数字, 而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。首先, 我们对置换问题定义一种邻域搜索结构, 如互换操作( SWAP ), 即随机交换两个点的位置, 则每个状态的邻域解有 C n 2 =n (n一1) /2 个。称从一个状态转移到其邻域中的另一个状态为一次移动( move ) ,显然每次移动将导致适配值(反比于目标函数值)的变化。其次,我们采用一个存储结构来区分移动的属性,即是否为禁忌“对象”在以下示例中:考虑 7 元素的置换问题,并用每一状态的相应 21 个邻域解中最优的 5 次移动(对应最佳的 5 个适配值)作为候选解; 为一定程度上防止迂回搜索, 每个被采纳的移动在禁忌表中将滞留 3步( 即禁忌长度), 即将移动在以下连续 3 步搜索中将被视为禁忌对象;需要指出的是,由于当前的禁忌对象对应状态的适配值可能很好,因此在算法中设置判断,若禁忌对象对应的适配值优于“ best so far ”状态, 则