陶庆云



基于多重网格的模拟退火算法

陶庆云*

(湖南文理学院 数学与计算科学学院, 湖南 常德, 415000)

为了提高模拟退火算法的收敛速度, 提出了一种基于多重网格的模拟退火算法(SAM), 用于求解高维函数优化问题, 并分析了其收敛性. 13个著名的测试函数对SAM算法进行数值实验, 结果表明SAM算法具有良好的搜索能力和收敛速度.

模拟退火算法; 多重网格法; 函数优化问题

模拟退火算法(Simulated Annealing)[1]在1982年由Kirkpatrick等人首次提出, 是一种基于Monte Carlo迭代求解法的启发式随机搜索算法. 它能够有效的避免局部搜索算法易陷入局部最优的通病, 是一种和遗传算法一样被广泛应用的优秀全局搜索算法. 然而理论研究表明模拟退火算法实现全局收敛的时间性能很差[2], 大量实验也表明在求解高维函数优化问题时其搜索能力非常有限.

多重网格法[3]被认为是求解偏微分方程组收敛速度最快的数值方法之一. 它由多层粗细不同的网格组成, 在粗网格上, 数值算法快速收敛, 但解的质量较差, 在细网格上算法收敛到高精度的解, 但收敛速度较慢. 粗细网格的结合, 使得数值算法能以较短的时间收敛到高精度的解. 已有不少研究者将多重网格法与智能算法相结合用于求解复杂函数优化问题[4—6]等, 文献[6]详细讨论了多重网格法与演化算法结合的应用模式及其收敛性. 本文提出了一种基于多重网格的模拟退火算法, 以文献[6]中13个著名的测试函数为例对SAM算法进行数值……