模擬退火算法的并行化策略研究

摘要：模擬退火算法是一種能應(yīng)用到求最小值問題或連續(xù)更新的學(xué)習(xí)過程（隨機(jī)或決定性的）。在此過程中，每一步更新過程的長度都與相應(yīng)的參數(shù)成正比，這些參數(shù)扮演著溫度的角色。標(biāo)準(zhǔn)模擬退火算法僅進(jìn)行串行優(yōu)化，其效率很難提高。因此，考慮引入多種群群體優(yōu)化機(jī)制構(gòu)造并行算法，并對接受準(zhǔn)則進(jìn)行討論。

關(guān)鍵詞：模擬退火；并行計算MPI

中圖分類號：TP311文獻(xiàn)標(biāo)識碼： A文章編號：1009-3044(2008)25-1523-02

The Research on Parallel Algorithm of Simulation Annealing

WANG Wei

(Mathematic and Information Science College Gansu Lianhe University， Lanzhou 730000， China)

Abstract: Simulation Annealing is a technique which can be applied to any minimization or learning process based on successive update steps (either random or deterministic) where the update step length is proportional to an arbitrarily set parameter which can play the role of a temperature. Simulation annealing only use serial optimize method， it's difficult to improve efficiency. So， we try to use multi-colony optimize mechanism to form parallel algorithm， and discussed accept rule.

Key words: simulation annealing; parallel compute; MPI

1 引言

模擬退火算法是從某一較高初溫開始，采用具有概率突跳特性的接受準(zhǔn)則在解空間中進(jìn)行隨機(jī)搜索，隨著溫度的下降重復(fù)抽樣，整個過程直到各溫度下的抽樣穩(wěn)定，最終得到問題的全局最優(yōu)解。其實質(zhì)結(jié)構(gòu)為內(nèi)外兩層循環(huán)。外層循環(huán)控制溫度的下降，內(nèi)部的循環(huán)則在當(dāng)前溫度下重復(fù)抽樣，直到抽樣穩(wěn)定為止。標(biāo)準(zhǔn)模擬退火算法僅對一個解進(jìn)行串行優(yōu)化，其效率很難提高。因此，考慮引入多種群群體優(yōu)化機(jī)制，構(gòu)造出并行模擬退火算法PSA[1]，以提高算法的使用效率。

2 模擬退火算法

在實際的應(yīng)用中，由計算機(jī)隨機(jī)的產(chǎn)生一組解，計算其目標(biāo)函數(shù)值的方差作為初始溫度[2]。溫度更新函數(shù)Ti+1=λTi，λ∈(0，1)，為使溫度下降不至過快，λ取值一般接近于1?；玖鞒虉D的描述[3]如圖1所示。

3 并行策略及算法描述

3.1 并行的策略

在PSA中，首先初始化過程隨機(jī)產(chǎn)生k個規(guī)模為M的進(jìn)化種群，并計算種群中每個解的目標(biāo)函數(shù)值，將每個種群中的最優(yōu)解保存后，狀態(tài)產(chǎn)生函數(shù)在每個解的領(lǐng)域內(nèi)產(chǎn)生kM個候選解，并計算候選解的目標(biāo)函數(shù)值。若候選解的目標(biāo)函數(shù)值大于當(dāng)前的解，則取而代之，不則根據(jù)接受準(zhǔn)則判斷是否接受。這樣形成了新一代種群。若k個新種群中有優(yōu)于歷史最優(yōu)解的個體則保留此個體。隨后繼續(xù)重復(fù)抽樣過程直到當(dāng)前溫度下的抽樣穩(wěn)定后進(jìn)行退溫操作，當(dāng)溫度低于某個終止溫度時算法結(jié)束。再從K個種群最優(yōu)解中選出一個最優(yōu)解作為最終得到的全局最優(yōu)解。

3.2 算法描述

初始化：產(chǎn)生k個規(guī)模為M的種群

并行計算每個初始解的目標(biāo)函數(shù)值并保留各種群的最優(yōu)解

While (T>Tc)//Tc是循環(huán)終止的溫度值

{ While(抽樣過程未達(dá)到穩(wěn)定)

{ For(i=1;i<=k M;i++)

{

在當(dāng)前解的鄰域內(nèi)產(chǎn)生一個候選解；

計算候選解的目標(biāo)函數(shù)并根據(jù)接受準(zhǔn)則判斷是否接受

}

判斷各種群中是否出現(xiàn)歷史最優(yōu)解，若有則保留之

判斷此溫度下是否達(dá)到抽樣穩(wěn)定；穩(wěn)定則跳出本循環(huán)

}

退溫操作；

判斷當(dāng)前溫度值是否等于或低于Tc，若是則跳出本循環(huán)

}

在k個歷史最優(yōu)解中選出一個最優(yōu)的解；

輸出結(jié)果，算法結(jié)束

4 算法討論

4.1 接受準(zhǔn)則選取

若準(zhǔn)則接收采取最優(yōu)解，則浪費大量的處理器時間，難以提高加速比。若準(zhǔn)則選取最早通過的解，則可能得到更好的加速比，但是不能保證解的質(zhì)量，而且很可能不如串行算法的解。因此，最好能夠?qū)ふ乙环N既能保持解的質(zhì)量又能提高時間效率的接受準(zhǔn)則。

我們提出一種最快結(jié)束準(zhǔn)則，即最快結(jié)束Metropolis循環(huán)的處理器給其它運行中的處理器發(fā)出停止運行信號，其它處理接收到信號后并不馬上停止運行，而是等待正在處理的局部解的過程結(jié)束之后才停止。這樣所以處理器結(jié)束之后都會得到一個解，設(shè)計一個進(jìn)程用來比較各個處理器得到的解，根據(jù)接受最優(yōu)解準(zhǔn)則，接受一個最優(yōu)解。將此最優(yōu)解保存在共享存儲器中，并發(fā)送給所有的處理器。很明顯這種方法不但可以得到滿意的加速比而且能夠很好的改善解的質(zhì)量。

4.2 變量與模型擾動的選擇

傳統(tǒng)的算法容易放棄在退火過程中找到的很好的解，而最終找到的解不一定比中間最優(yōu)解好[4]，因此在退火過程中尋求一個記憶功能的全局變量非常有意義，不改變接受準(zhǔn)則，但可以較快收斂過程。

采用文獻(xiàn)[5]中的方法產(chǎn)生新狀態(tài)，即依賴于溫度的似Cauchy方法，其特點是：在高溫情況下進(jìn)行大范圍的搜索，在低溫時僅在模型附近進(jìn)行搜索，因此，其易于迅速跳出局部極值，加快了收斂速度。

4.3 溫度更新

采用的控制溫度衰減函數(shù)為：Ti+1=λTi，λ∈(0，1) 退火過程是慢速降溫，允許的時間重新分布，達(dá)到溫度的狀態(tài)，因此符合金屬的降溫規(guī)律。

5 結(jié)論

此算法采用的并行策略，各處理器這間可以通過共享存儲器互相影響或改變，是一種完全異步的并行策略，具有很好的靈活性，能夠很好的發(fā)揮每個處理器的處理能力，其編程采用MPI與C語言相結(jié)合的方試。進(jìn)一步可以將粗粒度與細(xì)粒度的并行算法相結(jié)合，得到混合型的并行模擬退火算法，以提高算法的靈活性。

參考文獻(xiàn)：

[1] 李樹有，都志輝，吳夢月. 模擬退火算法的并行實現(xiàn)及應(yīng)用[J]. 物理學(xué)報，2001，50(7):24-27.

[2] 謝云.模擬退火算法的原理與實現(xiàn)[J]. 高等學(xué)校計算數(shù)學(xué)學(xué)報，1999，(3):212-216.

[3] 康立山，謝云.非數(shù)值并行算法—模擬退火算法[M]. 北京：科學(xué)出版社，2000.

[4] 王華秋，基于模擬退火的并行粒子群優(yōu)化研究[J]. 控制與決策，2005，(5):500-504.

[5] Ingber L. Very fast simulated reannealing[J]. Mathematical and Computer Modeling， 1989，12(8):967-980.