王立平，肖樂意

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

0 引言

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

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

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

1 模擬退火算法

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

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

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

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

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

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

2 萬有引力算法

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

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

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

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

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

粒子i在d上的合力為

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

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

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

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

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

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

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

由(12)式可見，粒子的位置更新具有一定的隨機性，從而使個體可能會從適應值高的位置移到適應值低的位置，這種現(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)為假設i的下一位置為i(t+1)時的適應值，rand為［0，1］上的隨機數(shù).

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

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

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

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

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

［1］王曉娟，高亮，陳亞洲.類電磁機制算法及其應用［J］.計算機應用研究，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］.計算機工程與應用，2010，46(5):44－85.

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

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