一种改进的禁忌搜索算法及其在连续全局优化中的应用

摘要：禁忌搜索算法是一种元启发式的全局优化算法，是局部搜索算法的一种推广，已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题，提出了一种改进的禁忌搜索算法，并进行了理论分析和数值实验。数值实验表明，对于连续函数全局优化问题的求解该算法是可行有效的，并且结构简单，迭代次数较少，是一种较好的全局启发式优化算法。

关键词：运筹学；元启发式算法；禁忌搜索算法；连续全局优化

中图分类号：0229;TP301

文章标识码：A

文章编号：1007-3221(2007)04-0006-06

0　引言

禁忌搜索(Tabu search，简称TS)算法是由Glover于1986年首次提出的一种元启发式全局优化算法，该算法被成功地应用于许多组合优化问题。作为一种智能优化算法，其主要思想是采用禁忌技术，用一个禁忌表记录已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。随着计算机技术的发展，TS算法被成功地应用于许多领域内，有效地解决了许多实际的组合优化问题。例如生产调度问题、旅行商问题等。通过这些实际问题说明TS算法用于组合优化问题具有获得高质量解的能力。它已成为与模拟退火算法、遗传算法和蚁群算法等智能算法并行快速发展的全局优化算法。Cvijovic等将TS算法推广到解决连续函数的多极小问题，能够很快地跳出局部最优点，达到寻找全局最优解的目的。针对连续函数全局优化问题，虽然已经有不少研究，但TS算法在连续优化问题方面的研究，远不及在组合优化方面应用的广泛和成熟。

本文在分析组合优化问题及连续全局优化问题求解特点的基础上，提出了一种适用于有界闭区域上的连续函数全局优化问题的禁忌搜索算法，并进行了收敛性分析。所提出的算法主要在生成解和循环初始解的选取方面做了如下改进：(1)使用均匀分布产生随机扰动，得到一组解，其中使函数值最小且未被禁忌的解作为当前解，利用调节参数scale在探查搜索空间和开采最优解之间进行平衡；(2)在最初迭代时，使每个分量都更新，随着计算的深入，只使解的一个分量更新；(3)在循环初始点的选取上，在最初时，一组解中使函数值最小的解为当前初始点，随着计算的深入，使用出现过的最优解为初始点；(4)采用记忆机制以保留迭代过程中的最优解。通过数值实验和比较分析，发现本文算法具有结构简单、计算效率高、迭代次数少和收敛速度快等优点。对于有界闭区域上的连续函数全局优化问题，该算法是可行且有效的。

1　禁忌搜索算法

禁忌搜索算法的特征由禁忌对象和长度、候选集和评价函数、终止规则和一些计算信息组成。下面给出禁忌搜索算法的一般描述：

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

由表3和表4可以看出，本文算法ITS迭代次数较少，且具有较高的成功率。其中GP的成功率为75％，BR的成功率为74％，Hn3的成功率为98％，Hn6的成功率为74％，RA的成功率为85％，SH的成功率为100％。通过表3中的数据比较，可以看出对于6个测试函数ITS的计算结果明显优于其它几种算法的结果。可见本文算法对于求解有界闭区域上的连续函数全局优化问题是可行且有效的。

4　结论

本文给出了可用于一类连续函数全局优化问题的禁忌搜索算法，并进行了收敛性分析。所提出的算法主要在生成解和循环初始解的选取方面做了一些改进。数值实验表明，本文算法调用函数次数明显少于其它几种算法。本文算法结构简单，迭代次数较少，到达最优点效率较高。对于有界闭区域上的连续函数全局优化问题的求解，改进的禁忌搜索是可行且有效的，是一种较好的全局启发式优化算法。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

推荐访问:全局 禁忌 算法 改进 优化