王立平，肖樂意

(1.萍鄉(xiāng)學院，江西 萍鄉(xiāng)337000;2.長沙師范學院教務(wù)處，湖南 長沙410100)

0 引言

在科學、經(jīng)濟和工程領(lǐng)域中，許多最新的進展都依賴于全局優(yōu)化技術(shù)，即計算出相應(yīng)優(yōu)化問題的全局最優(yōu)解的數(shù)值技術(shù)［1］.在全局優(yōu)化技術(shù)中，啟發(fā)式搜索算法是目前比較流行且行之有效的一類優(yōu)化技術(shù).目前比較流行的啟發(fā)式搜索算法有粒子群優(yōu)化算法［2］、模擬退火算法［3］、類電磁機制算［4］、遺傳算法［5］、蟻群算法［6］、萬有引力算法［7］等.盡管該類算法為求解復(fù)雜優(yōu)化問題提供了較多有效的途徑，但其結(jié)果仍不能令人滿意，如算法易陷入局部最優(yōu)、解的精度不高等.而且多數(shù)啟發(fā)式算法沒有形成系統(tǒng)的理論，沒有統(tǒng)一的算法框架，有許多問題仍有待研究［8］.

萬有引力算法(A gravitational search algorithm，GSA)是伊朗的克曼大學教授Esmat Rashedi等于2009提出來的，該算法基于牛頓萬有引力定律，通過模擬粒子間相互作用的萬有引力指導(dǎo)粒子進行搜索，由文獻［7］可知萬有引力算法與中心力算法、粒子群算法相比，具有明顯的優(yōu)越性.然后，由于移動步驟具有一定盲目性，可能造成個體退化;且萬有引力算法無局部搜索機制，因而局部搜索能力較弱.

針對GSA的上述缺陷，本文提出了一種基于模擬退火的萬有引力算法(gravity algorithm based simulated annealing，GABSA)，該算法采用模擬退火算法的Metropolis準則對移動步驟進行判斷，從而減少移動的盲目性;同時通過采用模擬退火算法進行局部搜索，提高局部搜索能力.實驗結(jié)果表明:GABSA的優(yōu)化效果明顯優(yōu)于GSA.

1 模擬退火算法

模擬退火算法(simulated annealing，SA)的思想最早是由 Metropolis于1953年提出來的，1983年Kirkpatrick將其應(yīng)用于組合優(yōu)化問題，SA算法基于固體物質(zhì)的退火過程，是一種通用的優(yōu)化算法，已成功應(yīng)用于解決車輛路線優(yōu)化、TSP問題、車間調(diào)度問題等優(yōu)化問題［9－11］.

模擬退火算法基本思想是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性.模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu).

Metroplis準則:設(shè)粒子初始狀態(tài)為i，隨機攝動得到粒子的一個新狀態(tài)j.E(i)、E(j)分別為粒子在狀態(tài) i、j時的能量:

(i)若E(j)＜E(i)，則狀態(tài)轉(zhuǎn)換被接受;

(ii)若E(j)≥E(í)，則狀態(tài)轉(zhuǎn)換的概率為

Pij=exp(－(E(j)－E(i))(KT))，其中K為物理學中的玻耳茲曼常數(shù)，T為材料的溫度.對同樣的接受概率.模擬退火算法的基本步驟見文獻［12］.

2 萬有引力算法

萬有引力算法基于牛頓萬有引力定律:“任意2個質(zhì)點通過連心線方向上的力相互吸引.該引力的大小與它們的質(zhì)量乘積成正比，與它們距離的平方成反比，與2物體的化學本質(zhì)或物理狀態(tài)以及中介物質(zhì)無關(guān)”.用公式表示為

其中F為代表萬有引力的大小，G為引力常數(shù)，M1、M2為代表2個粒子的慣性質(zhì)量，R為2個粒子之間的歐氏距離.

粒子j對粒子i的吸引力在d維上的分量為［7］

因為實驗表明R比R2效果更好，所以采用R代替R2;Maj表示施力粒子j的質(zhì)量，Mpi表示受力粒子i的質(zhì)量;ε為一小常量，G(t)為時間 t下的引力常量:

其中G0為引力常量初始值，α為一常量，T為算法的總迭代次數(shù).

粒子i在d上的合力為

其中rand是為增加算法搜索的隨機性而增加的隨機量，其取值范圍為［0，1］.

由牛頓第二定律可知:在時間t時，粒子i在d上的加速度為

其中Mi(t)為粒子i的慣性質(zhì)量.在GSA算法中，使用以下公式更新粒子的慣性質(zhì)量為

其中fiti(t)為t時粒子i的適應(yīng)值，對于求最小值問題時，worst(t)、best(t)為

在GSA算法中，每次迭代都會按照牛頓運動定律對粒子的運動狀態(tài)進行更新，更新公式為

3 基于退火思想的算法改進

3.1 基于Metropolis準則的位置更新策略

由(12)式可見，粒子的位置更新具有一定的隨機性，從而使個體可能會從適應(yīng)值高的位置移到適應(yīng)值低的位置，這種現(xiàn)象稱為個體的退化;即可能造成fiti+1(t)＞fiti(t)(求最小值問題時)，這對問題的求解顯然是不利的.針對萬有引力算法的這一不足，本文提出一種基于Metropolis準則的粒子位置更新策略:(i)根據(jù)式(12)計算出粒子i下一個可能的位置i(t+1);(ii)根據(jù)Metropolis準則判斷是否接受i(t+1)作為i的下一個位置.具體如下:若fiti+1(t)≤fiti(t)或 rand≤exp(－fiti+1(t)－fiti(t)(KT))，則xi(t+1)=(t+1);否則xi(t+1)=xi(t).其中fiti+1(t)為假設(shè)i的下一位置為i(t+1)時的適應(yīng)值，rand為［0，1］上的隨機數(shù).

可見，當粒子從一個適應(yīng)值優(yōu)的位置移到一個適應(yīng)值更差的位置時，通過Metropolis準則的引導(dǎo)，只以一定概率接受差解，一定程度上避免了粒子的退化.

3.2 基于模擬退火的萬有引力算法

由文獻［7］可知，萬有引力算法全局搜索能力較強;但是從算法具體步驟可見，引力算法缺乏局部搜索機制，因此算法的局部搜索能力比較弱.而退火算法雖然前期的全局能力不強，卻具有快速搜索到局部最優(yōu)解的能力［13］.因此，本文將萬有引力算法與退火算法融合，使算法同時兼顧全局和局部搜索能力.

基于模擬退火的萬有引力算法以萬有引力算法框架為基礎(chǔ)［7］，采用基于Metropolis準則的粒子位置更新策略;同時在萬有引力算法操作完成后，采用退火算法對最優(yōu)個體進行操作，增加算法的局部尋優(yōu)能力.算法的具體步驟如下:(i)初始化操作.包括初始種群Q、引力常量初值G0、退火初始溫度T0、玻耳茲曼常數(shù)K、迭代次數(shù)N等;(ii)計算粒子適應(yīng)值;(iii)更新引力系數(shù)G(t)、最好值best(t)、最壞值worst(t)和粒子的慣性質(zhì)量Mi(t);(iv)按(4)式計算各粒子各方向上的力的總和;(v)分別按(5)式和(11)式計算各粒子的加速度和速度;(vi)(12)式計算各粒子下一步可能的位置，用基于Metropolis準則的粒子位置更新策略對粒子的位置進行更新;(vii)判斷是否迭代結(jié)束，如未結(jié)束，則返回步驟3)重復(fù)執(zhí)行;(viii)對最優(yōu)個體進行退火操作;(ix)輸出結(jié)果.流程圖如圖1所示.

4 算法性能測試

4.1 性能測試一

為了測試退火思想引入的有效性，將本文算法與文獻［7］萬有引力算法進行比較，表1為測試函數(shù)［14］，函數(shù) F1、F2的最大迭代次數(shù)為 50，F(xiàn)3的最大迭代次數(shù)為100，優(yōu)化精度為0.1，算法其它參數(shù)見表2，表3為本算法與文獻［7］GSA的性能比較.圖2～圖4分別為函數(shù)F1～F3優(yōu)化效果比較圖.

圖2 F1尋優(yōu)曲線

圖3 F2尋優(yōu)曲線

表1 測試函數(shù)一

表2 算法參數(shù)

表3 GABSA與GSA性能比較

圖4 F3尋優(yōu)曲線

由表1可見，GABSA在成功率、求解精度上比GSA好;圖2～圖4表明GABSA的收斂速度比GSA快，收斂精度比GSA高.退火思想的引入，使得GABSA具有更快的收斂速度、更高的成功率和求解精度.這是由于:(i)Metropolis準則的個體移動策略，一定程度避免了個體移向更差解;(ii)對最優(yōu)個體進行退火搜索，提高了算法收斂速度與搜索精度.

4.2 性能測試二

為了進一步對算法的性能進行測試，將本文算法與文獻［15］的一種群體遷移優(yōu)化算法(speciesmigrationbased optimization algorithm，SMOA)進行比較.為了更好地測試算法性能，選取文獻［15］的高維函數(shù)作為測試函數(shù)，實驗結(jié)果見表5，其中SMOA測試數(shù)據(jù)來自文獻［15］.實驗參數(shù):種群規(guī)模為30，進化代數(shù)為50，獨立運行50次.

表4 測試函數(shù)二

表5 GABSA與SMOA性能比較

由表5可見，對于高維函數(shù)的求解，GABSA比SMOA有更高的求解精度.故GABSA具有較好的收斂效果與求解精度，具有優(yōu)越的尋優(yōu)性能.

5 結(jié)束語

本文針對GSA算法存在的不足，通過采用基于Metropolis準則的個體移動策略，并對最優(yōu)個體進行退火操作，提出了一種基于模擬退火思想的萬有引力算法(GABSA).通過測試實驗，將GABSA與GSA進行比較，驗證退火思想引入的有效性;GABSA與文獻［15］的SMOA求解高維函數(shù)進行的比較，進一步驗證了GABSA的有效性.

［1］王曉娟，高亮，陳亞洲.類電磁機制算法及其應(yīng)用［J］.計算機應(yīng)用研究，2006，23(6):67－70.

［2］ Karakuzu J，Eberhart R C.Particle swarm optimization［J］.IEEEInternational Conference on Neural Networks，1995，4:1942－1948.

［3］Suman B，Kumar P.A survey of simulated annealing as tool for single andmuhiobjective optimization［J］.Journal of the Operational Research Society，2006，57(10):1143－1160.

［4］Birbil SI，F(xiàn)ang S C.An electromagnetism－likemechanism for global optimization ［J］.Journal of Global Optimozation，2003，25(3):263－282.

［5］Tang K S，Man K F，Kwong S，et al.Genetic algorithms and their applications［J］.IEEE Signal Processing Magazine 1996，13(6):22－37.

［6］Dorigo M，Birattari M，Stutzle T.Ant colony optimization artificial ants as a computational intelligence technique［J］.IEEE ComputationalIntelligence Magazine，2006，1(4):28－39.

［7］Esmat Rashedi，Hossein Nezamabadipour，Saeid Saryazdi.GSA:a gravitational search algorithm ［J］.Information Sciences，2009，179(13):2232－2248.

［8］謝麗萍，曾建湖.受擬態(tài)物理學啟發(fā)的全局優(yōu)化算法［J］.系統(tǒng)工程理論與實踐，2010，30(12):2276－2282.

［9］Suman B，Kumar P.A survey of simulated annealing as a tool for single andmultiobjective optimization［J］.Journal of the Operational Research Society，2006，57(10):1143－1160.

［10］ElBouriA，Azizi N，Zolfaghari S.A comparative study of a new heuristic based on adaptivememory programming and simulated annealing:the case of job shop scheduling［J］.European Journal of Operational Research，2007，177:1894－1910.

［11］Tan K C，Chew Y H，Lee L H.A hybridmulti－ob jective evolutionary algorithm for solving truck and trailer vehicle routing problems［J］.European Journal of Operational Research，2006，172:855－885.

［12］楊勇，譚淵，張曉發(fā)，等.基于模擬退火算法的陣列模型有源校正方法［J］.國防科技大學學報，2011，33(1):91－94.

［13］王銀年，葛洪偉.求解TSP問題的改進模擬退火遺傳算法 ［J］.計算機工程與應(yīng)用，2010，46(5):44－85.

［14］吳濤，金義富.基于云控制的自適應(yīng)遺傳算法［J］.計算機工程，2011，37(8):189－191.

［15］馬海平，李寰，阮謝永.一種群體遷移優(yōu)化算法及性能分析［J］.控制理論與應(yīng)用，2010，27(3):329－33.