基于退火算法的物流配送網(wǎng)的求優(yōu)研究

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

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

1 前言

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

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

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

爬山算法是完完全全的貪心算法，每次都以較小的步長選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火算法其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會(huì)以一定的概率接受到D的移動(dòng)。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)E點(diǎn)，于是就跳出了局部最大值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è)來說會(huì)節(jié)省資金，增加配送速度;對貨物接收方來說能夠在較為合理的時(shí)間內(nèi)接收物品，從而節(jié)省生產(chǎn)成本或消費(fèi)成本。

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

若

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

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

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

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

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

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

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

3.1 模擬退火算法流程

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

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

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

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

J(y):在狀態(tài)y時(shí)的評價(jià)函數(shù)值;Y(i):表示當(dāng)前狀態(tài);Y(i+1):表示新的狀態(tài);r:用于控制降溫的快慢;T:系統(tǒng)的溫度，系統(tǒng)初始應(yīng)該要處于一個(gè)高溫的狀態(tài);T_min:溫度的下限，若溫度 T達(dá)到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)解的可能會(huì)較高，但搜索的過程也就較長。若r過小，則搜索的過程會(huì)很快，但最終可能會(huì)達(dá)到一個(gè)局部最優(yōu)值

*/

i++;}

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

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

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

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

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

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

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

4.2 計(jì)算進(jìn)行步驟

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

第二步，在溫度T下局部搜索，直到“平衡”;降溫時(shí)機(jī)用在同一溫度下反復(fù)進(jìn)行Metropolis［3］演算，假設(shè)次數(shù)為3，搜尋法則，隨機(jī)改變某一位的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，計(jì)算接受概率 P(T)=exp((10－13)/10)≈0.741，在(0，1)范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)，如果隨機(jī)數(shù)小于接受概率，則接受j為新解，否則不接受。

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

4.3 計(jì)算結(jié)果

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

5 結(jié)語

模擬退火算法同其他各類人工智能算法相似，是一種隨機(jī)算法，該算法并不一定能找到全局的最優(yōu)精確解，但是可以比較快地找到問題的近似最優(yōu)解，這是由算法本身決定的。但是作為一種在物流配送路徑中的最優(yōu)預(yù)測模型，可以認(rèn)為是比較好的工具。模擬退火算法缺點(diǎn)在于如果參數(shù)設(shè)置不當(dāng)，很容易造成得到結(jié)果耗費(fèi)大量的時(shí)間，這無疑近似于窮舉算法，這是科研工作者不希望看到的，故此參數(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］.運(yùn)籌與管理，2003，12(2):124－126.

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