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

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

關(guān)鍵詞：萬有引力搜索算法（GSA）； 模擬退火算法（SA）； 函數(shù)優(yōu)化

中圖分類號：N945.17 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-3315（2013）08-178-001

一、介紹

萬有引力搜索算法[1]（Gravitational Search Algorithm）是由E.Rashedi和H.Nezamabadi-pour等2009年提出的一種基于物理學(xué)牛頓萬有引力定律的優(yōu)化搜索，是通過群體中各個(gè)物體（agents）之間的萬有引力相互作用產(chǎn)生的群體智能指導(dǎo)優(yōu)化算法，本文通過結(jié)合模擬退貨算法，預(yù)防GSA在處理多峰函數(shù)問題時(shí)可能遇到的局部最優(yōu)的問題的出現(xiàn)。

詳細(xì)萬有引力搜索算法步驟參考[1]，詳細(xì)模擬退火算法步驟參考[2]。

二、改進(jìn)算法描述

結(jié)合模擬退火算法進(jìn)行更優(yōu)解搜索，有利于種群的多樣性，防止過早收斂而導(dǎo)致早熟；物體的適應(yīng)值影響質(zhì)量，慣性質(zhì)量大的對慣性質(zhì)量小的受力影響大，致使慣性質(zhì)量小的往慣性質(zhì)量大的移動的更多，這也印證了次優(yōu)解往更優(yōu)解移動而提高種群最優(yōu)，即質(zhì)量影響受力，受力影響速度，速度更新位置。新算法的改進(jìn)在于原始算法進(jìn)行初始化，適應(yīng)度和受力計(jì)算以及更新速度和位置后，使用模擬退火算法搜索局部更優(yōu)替換。

三、仿真

如上表數(shù)據(jù)所示，引入SA算法作為局部搜索有效提高搜索精度，不管是最優(yōu)，平均還是最差的值都有所提高，由此可知新算法的有效性，從算法收斂圖中可以看出引入SA算法后，有效防止局部收斂，陷入局部最優(yōu)，而是不斷索搜出更優(yōu)的值。

參考文獻(xiàn)：

[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