基于模擬退火局部優化的萬有引力搜索算法

謝峰　林潔云　林其鋒　彭鴻鑫　陳育興

摘 要：為了有效地避免算法陷入局部最優解，使用模擬退火算法進行局部擴展搜索，進一步提高解的質量；有效提高萬有引力搜索算法的搜索效率，最后通過仿真對比，得出結合模擬退火算法的萬有引力搜索算法具有收斂速度快，精度高的特點這一結論。

關鍵詞：萬有引力搜索算法（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