段敬民，常躍軍，李贊祥，崔建明

(1.三門峽職業(yè)技術(shù)學院建筑工程系，河南三門峽472000;2.西南交通大學橋梁及結(jié)構(gòu)工程系，成都610031;3.河南工程技術(shù)學校建筑工程系，河南焦作454000;4.長安大學信息工程學院，西安710064)

1 前言

模擬退火算法［1］(simulated annealing，SA)原理就是模擬在某個溫度下，金屬分子停留在能量小的狀態(tài)時刻的概率要比停留在能量大的狀態(tài)的概率要大。

模擬退火算法與爬山算法對比，爬山算法是一種簡單的貪婪搜索算法，該算法每次從當前解的臨近解空間中選擇一個最優(yōu)解作為當前解，直到達到一個局部最優(yōu)解。

爬山算法的主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1所示:假設(shè)C點為當前解，爬山算法搜索到A點這個局部最優(yōu)解就會停止搜索，因為在A點無論向哪個方向小幅度移動都不能得到更優(yōu)的解。

爬山算法是完完全全的貪心算法，每次都以較小的步長選擇一個當前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火算法其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會以一定的概率接受到D的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達E點，于是就跳出了局部最大值A(chǔ)的范圍。

圖1 最優(yōu)解搜索最優(yōu)示意圖Fig.1 Schematic diagram of search for the optimal solution

在物流的配送網(wǎng)絡(luò)中［2］，存在尋優(yōu)的網(wǎng)絡(luò)方案，如果采用這種優(yōu)選方案，對物流配送企業(yè)來說會節(jié)省資金，增加配送速度;對貨物接收方來說能夠在較為合理的時間內(nèi)接收物品，從而節(jié)省生產(chǎn)成本或消費成本。

2 模擬退火算法數(shù)學描述

若

即移動后得到更優(yōu)解，則總是接受該移動;若

即移動后的解比當前解要差，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低(逐漸降低才能趨向穩(wěn)定)。這里的“一定的概率”的計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。根據(jù)熱力學的原理，在溫度為T時，出現(xiàn)能量差為dE的降溫的概率為P(dE)，可表示為

其中，k是一個常數(shù)，e表示自然指數(shù)，且dE＜0。

公式是指:溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大;溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE總是小于0(這是模擬退火的本質(zhì)決定的)，因此dE/kT＜0，所以P(dE)的函數(shù)取值范圍是(0，1)，隨著溫度T的降低，P(dE)會逐漸降低。

將一次向較差解的移動看做一次溫度跳變過程，以概率P(dE)來接受這樣的移動。

終止條件:設(shè)置一個接近于0的較小的值，例如 0.3。

3 模擬退火算法的程序語言描述

3.1 模擬退火算法流程

模擬退火算法流程如圖2所示。

圖2 模擬退火算法流程Fig.2 Process of simulated annealing

3.2 參數(shù)與函數(shù)定義

在計算程序中的各個參數(shù)與函數(shù)的定義說明如下:

J(y):在狀態(tài)y時的評價函數(shù)值;Y(i):表示當前狀態(tài);Y(i+1):表示新的狀態(tài);r:用于控制降溫的快慢;T:系統(tǒng)的溫度，系統(tǒng)初始應(yīng)該要處于一個高溫的狀態(tài);T_min:溫度的下限，若溫度 T達到T_min，則停止搜索。

3.3 模擬退火算法偽代碼

//函數(shù)exp(dE/T)的取值范圍是(0，1)，dE/T越大，則exp(dE/T)也變大。

}

T=r* T; //降溫退火 ，0＜r＜1。r越大，降溫越慢;r越小，降溫越快

/*

＊若r過大，則搜索到全局最優(yōu)解的可能會較高，但搜索的過程也就較長。若r過小，則搜索的過程會很快，但最終可能會達到一個局部最優(yōu)值

*/

i++;}

4 模擬退火算法在區(qū)域交通流預(yù)測示例

4.1 區(qū)域物流配送示例

圖3為一簡單配送網(wǎng)絡(luò)圖，該網(wǎng)絡(luò)表示在一個區(qū)域中進行配送分配問題，等同于最優(yōu)化問題，表述模型表達式見式(4)。

圖3 配送網(wǎng)絡(luò)圖Fig.3 Network diagram of distribution and delivery

式(4)中，q為OD(origin-destination)量;xa為路線a上的流量;Ca為路線a的路阻函數(shù)。

用退火算法解決此類問題，假設(shè)道路損耗的時間和經(jīng)濟價值如(2，3，5，1，4)和(2，5，8，3，6)。

可行解采用0和1的序列表示，如i=(10101)表示選擇1，3，5線路，不選擇2和4。

4.2 計算進行步驟

第一步，初始化，假設(shè)初始解i=(11001)，初始溫度為10℃，計算開始。

第二步，在溫度T下局部搜索，直到“平衡”;降溫時機用在同一溫度下反復(fù)進行Metropolis［3］演算，假設(shè)次數(shù)為3，搜尋法則，隨機改變某一位的0，1或交換某兩位0，1的值。假設(shè)產(chǎn)生新解j=(11100)，f(j)=2+5+8=15＞13，所以接受新解。假設(shè)產(chǎn)生的新解j=(11010)，f(j)=2+5+3=10 ＜13，計算接受概率 P(T)=exp((10－13)/10)≈0.741，在(0，1)范圍內(nèi)產(chǎn)生一個隨機數(shù)，如果隨機數(shù)小于接受概率，則接受j為新解，否則不接受。

第三步，降溫，假設(shè)溫度降為T=T－1，如果沒有達到結(jié)束標準，則返回第二步繼續(xù)執(zhí)行。

4.3 計算結(jié)果

通過以上步驟的計算，i=(10010)，即選擇線路1和4作為最優(yōu)解。存在2個最優(yōu)的原因是結(jié)束過早，如果把成本計算進行的終止條件設(shè)置為0.03，則結(jié)果將是i=(00010)，即結(jié)果4為最優(yōu)解。

5 結(jié)語

模擬退火算法同其他各類人工智能算法相似，是一種隨機算法，該算法并不一定能找到全局的最優(yōu)精確解，但是可以比較快地找到問題的近似最優(yōu)解，這是由算法本身決定的。但是作為一種在物流配送路徑中的最優(yōu)預(yù)測模型，可以認為是比較好的工具。模擬退火算法缺點在于如果參數(shù)設(shè)置不當，很容易造成得到結(jié)果耗費大量的時間，這無疑近似于窮舉算法，這是科研工作者不希望看到的，故此參數(shù)設(shè)置將是模擬退火算法需要注重的一步。

［1］Kathleen M Carley，David M Svoboda.Modeling organizational adaptation as a simulated annealing process［J］.Sociological Methods Research ，1996，25(1):138 －168.

［2］池 潔，李 莉.物流中配送區(qū)域與配送路線的網(wǎng)絡(luò)優(yōu)化法［J］.運籌與管理，2003，12(2):124－126.

［3］Beichl I，Sullivan F.The metropolis algorithm［J］.Computer in Science ＆ Engineering，2000，2(1):65 －69.