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