基于模拟退火局部优化的万有引力搜索算法

谢峰　林洁云　林其锋　彭鸿鑫　陈育兴

摘 要：为了有效地避免算法陷入局部最优解，使用模拟退火算法进行局部扩展搜索，进一步提高解的质量；有效提高万有引力搜索算法的搜索效率，最后通过仿真对比，得出结合模拟退火算法的万有引力搜索算法具有收敛速度快，精度高的特点这一结论。

关键词：万有引力搜索算法（GSA）； 模拟退火算法（SA）； 函数优化

中图分类号：N945.17 文献标识码：A 文章编号：1006-3315（2013）08-178-001

一、介绍

万有引力搜索算法[1]（Gravitational Search Algorithm）是由E.Rashedi和H.Nezamabadi-pour等2009年提出的一种基于物理学牛顿万有引力定律的优化搜索，是通过群体中各个物体（agents）之间的万有引力相互作用产生的群体智能指导优化算法，本文通过结合模拟退货算法，预防GSA在处理多峰函数问题时可能遇到的局部最优的问题的出现。

详细万有引力搜索算法步骤参考[1]，详细模拟退火算法步骤参考[2]。

二、改进算法描述

结合模拟退火算法进行更优解搜索，有利于种群的多样性，防止过早收敛而导致早熟；物体的适应值影响质量，惯性质量大的对惯性质量小的受力影响大，致使惯性质量小的往惯性质量大的移动的更多，这也印证了次优解往更优解移动而提高种群最优，即质量影响受力，受力影响速度，速度更新位置。新算法的改进在于原始算法进行初始化，适应度和受力计算以及更新速度和位置后，使用模拟退火算法搜索局部更优替换。

三、仿真

如上表数据所示，引入SA算法作为局部搜索有效提高搜索精度，不管是最优，平均还是最差的值都有所提高，由此可知新算法的有效性，从算法收敛图中可以看出引入SA算法后，有效防止局部收敛，陷入局部最优，而是不断索搜出更优的值。

参考文献：

[1]Rashedi E，Nezamabadi-pour H，Saryazdi S.GSA：A gravitational search algorithm[j]Information Science，2009，179（13）：2232-2248

[2]S.Kirkpatrick，C.D. Gelatt and M.P.Vechi， “Optimization by simulated annealing，”Science，vol.220，no.4509，pp.671-680，1983