谈谈禁忌搜索算法.doc

谈谈禁忌搜索算法
张淑荣 苏 兵 摘 要: 禁忌搜索算法是一种全局性邻域搜索算法,模拟人类具有记忆功能的寻优特征。它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索,并通过破禁水平来释放一些被禁忌的优良状态,进而保证多样化的有效谈谈禁忌搜索算法
张淑荣 苏 兵 摘 要: 禁忌搜索算法是一种全局性邻域搜索算法,模拟人类具有记忆功能的寻优特征。它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索,并通过破禁水平来释放一些被禁忌的优良状态,进而保证多样化的有效探索,以最终实现全局优化。本文主要介绍禁忌算法的基本思想、构成、流程、原理等内容。
关键词: 禁忌搜索 算法 基本思想 示例 流程

一、引言

局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索,虽然算法通用、易实现,且容易理解,但其搜索性能完全依赖于领域结构和初解,尤其窥陷入局部极小而无法保证全局优化性。其主要是针对一般的下降算法的缺点而出现的,一般的下降算法在搜索到一个局部最优解时,算法就容易自动停止,而禁忌搜索采用禁忌策略尽量避免已搜索过的对象,从而保证了对不同的搜索路径的探索。禁忌搜索算法(TS)以其独特的运行机制,同模拟退火算法、遗传算法等算法一样,不是搜索到局部最优解就停止搜索,而具有引导算法跳出局部最优解,进而转向全局最优解的功能。
针对局部领域搜索,为了实现全局优化,可尝试的途径有:以可控性概率接受劣解来逃逸局部极小,如模拟退火算法;扩大领域搜索结构,如TSP的2opt扩展到k-opt;多点并行搜索,如进化计算;变结构领域搜索(Mladenovic et al,1997);另外,就是采用TS的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小突跳策略。

二、禁忌搜索算法的基本思想

禁忌搜索是人工智能的一种体现,是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环),从而保证对不同的有效搜索途径的探索。禁忌搜索涉及领域(neighborhood)、禁忌表(tabu list)、禁忌长度(tabu length)、候选解(candidate)、藐视准则(candidate)等概念,我们首先用一个示例来理解禁忌搜索及其各重要概念,而后给出算法的一般流程。

三、禁忌搜索示例

组合优化是TS算法应用最多的领域。置换问题,如TSP、调度问题等,是一大批组合优化问题的典型代表,在此用它来解释简单的禁忌搜索算法的思想和操作。对于n元素的置换问题,其所有排列状态数为n!,当n较大时搜索空间的大小将是天文数字,而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。
首先,我们对置换问题定义一种邻域搜索结构,如互换操作(SWAP),即随机交换两个点的位置,则每个状态的邻域解有C2n=n(n-1)/2个。称从一个状态转移到其邻域中的另一个状态为一次移动(move),显然每次移动将导致适配值(反比于目标函数值)的变化。其次,我们采用一个存储结构来区分移动的属性,即是否为禁忌“对象”在以下示例中:考虑7元素的置换问题,并用每一状态的相应21个邻域解中最优的5次移动(对应