基于模擬退火算法的設(shè)備配備優(yōu)化

?

基于模擬退火算法的設(shè)備配備優(yōu)化

陳爍1.2胡文剛2

1.中國人民解放軍72465部隊山東濟南2500222.軍械工程學(xué)院河北石家莊050003

[摘要]抽象提出了設(shè)備配備優(yōu)化數(shù)學(xué)模型和模型的約束條件，研究采用模擬退火算法尋求全局最優(yōu)解，并給出了算法步驟、程序模塊結(jié)構(gòu)和模擬退火部分程序。針對設(shè)備配備的復(fù)雜性，提出構(gòu)建設(shè)備與崗位的適應(yīng)度矩陣。為解決多目標組合優(yōu)化問題，采用線性加權(quán)方法科學(xué)構(gòu)建了評價函數(shù)。

[關(guān)鍵詞]設(shè)備配備；編配優(yōu)化；模擬退火

1、設(shè)備配備問題描述及數(shù)學(xué)模型

1.1配備問題描述

設(shè)備配備通常按照人員崗位編配，考慮引入適應(yīng)度矩陣。適應(yīng)度矩陣中的元素表示某一型號設(shè)備對某一崗位的適應(yīng)程度。適應(yīng)度矩陣由具有豐富經(jīng)驗的專家進行評估得來，是一組主觀數(shù)值。適應(yīng)度矩陣以表格形式表示見表1。

表1　設(shè)備與崗位適應(yīng)度矩陣表

設(shè)備配備通常還受崗位重要性、經(jīng)濟性和保障性等因素制約。其中崗位重要性是指設(shè)備配備的崗位的相對重要性。經(jīng)濟性是指配備的總成本，即配備設(shè)備的總價格。保障性是指配備的設(shè)備型號數(shù)量，總數(shù)量越少則保障越容易，保障性越高。

1.2定義數(shù)學(xué)模型

假設(shè)需要配備設(shè)備的崗位有n類，待分配的設(shè)備有m種，則定義分配矩陣X=[xij]mn。xij表示第i種設(shè)備配到第j類崗位的數(shù)量，其值為自然數(shù)。定義適應(yīng)度矩陣S=[sij]mn。sij表示第i種設(shè)備對第j類崗位的適應(yīng)程度，當(dāng)完全適應(yīng)時其值取1，當(dāng)不能適應(yīng)時取0。適應(yīng)度值根據(jù)設(shè)備新舊、替換使用性和需求匹配度等因素由專家經(jīng)驗確定。

設(shè)行n維向量K為崗位的效能權(quán)重向量，kj為第j類崗位的權(quán)重因子。則設(shè)備配備綜合效能目標函數(shù)可由式（1）表示。

考慮配備的經(jīng)濟性，要求總體價格成本要盡量低。設(shè)m維向量C為設(shè)備的成本向量，ci為第i種設(shè)備的采購價格。則成本目標函數(shù)可由式（2）表示[3]。

考慮設(shè)備的保障性，要求各崗位配備設(shè)備的型號數(shù)要盡量的少。為便于統(tǒng)計型號數(shù)量，需要對分配矩陣X進行適當(dāng)變換。

式中，Sgn(x )為符號函數(shù)，當(dāng)自變量大于0時函數(shù)值為1，等于0時函數(shù)值為0。此處用來消除同一種設(shè)備配備到多種崗位時產(chǎn)生的累加效果。

1.3約束條件

（1）各崗位僅分配一件或者不分配設(shè)備，即xij=1或0。（2）各崗位權(quán)重因子之和為1，即。

2、設(shè)備配備優(yōu)化算法設(shè)計

通過以上模型可以看出，設(shè)備配備優(yōu)化實際上是處理有限資源的多目標優(yōu)化問題，要在一定約束條件下尋找全局最優(yōu)解。模擬退火算法最早是由MetroPolis N等人借鑒統(tǒng)計熱力學(xué)中物質(zhì)退火方法而提出的，它在每一次修改模型的過程中，隨機產(chǎn)生一個新的狀態(tài)模型，然后以一定的概率選擇鄰域中能量值大的狀態(tài)。以概率接受新狀態(tài)的方式使模擬退火算法成為一種全局最優(yōu)算法，并得到理論證明和實際應(yīng)用的驗證[1]。

2.1模擬退火配備優(yōu)化算法

在模擬退火算法中，從一個隨機解X0開始探測整個解空間，采取一定方式擾動此解產(chǎn)生一個新解Xn，按照 Metropolis準則判斷是否接受新解，并相應(yīng)的下降控制溫度。算法主要步驟描述如下：（1）初始化參數(shù)。設(shè)定初始溫度T=T0，溫度衰減因子為d；（2）隨機產(chǎn)生一個分配矩陣Xn，計算評價函數(shù)F(X0)；（3）設(shè)置循環(huán)計數(shù)器初值k=1，最大循環(huán)步數(shù)loopm；（4）對X0作一個隨機擾動，產(chǎn)生新的分配矩陣Xn，計算新分配矩陣的評價函數(shù)F(Xn)，并計算評價函數(shù)增量△F=F(Xn)-F(X0)；(5）如果△Fy≤0,接受Xn為新的最優(yōu)解。如果，計算exp(-△F/T)；如果exp(-△F/T)，則同樣接受Xn為新的最優(yōu)解。否則，X0不作改變；（6）循環(huán)計數(shù)，如果K＜loopm，則k=k+1, 轉(zhuǎn)到第（4）步；（7）如果不滿足收斂準則，則根據(jù)溫度管理函數(shù)T=T(n)更新溫度，降溫次數(shù)n=n+1，轉(zhuǎn)到第（3）步；如果滿足收斂準則，則輸出當(dāng)前最優(yōu)解，算法結(jié)束。

2.2配備優(yōu)化評價函數(shù)

將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題的方法很多，本文采取線性加權(quán)和法。配備優(yōu)化模型中有配備綜合效能P、配備總體成本C和配備型號總數(shù)量Y三個目標函數(shù)，其中配備總體成本C和配備型號總數(shù)量Y具有不同量綱，且函數(shù)值在量級上有較大差異，需要先轉(zhuǎn)化為無量綱且等量級的目標函數(shù)。設(shè)Cnax為編配最大成本，N為設(shè)備型號總數(shù)量，令Cz=1-C/Cnax，Yz=1-Y/N。式中Cz為經(jīng)濟性指標，Yz為保障性指標。可以看出，Cz、Yz均無量綱且值在[0,1]之間。成本C越低，則經(jīng)濟性指標越高；配備總型號數(shù)量Yz越少，則保障性指標Yz越高。設(shè)α、ΒΓ分為配備綜合效能、經(jīng)濟性和保障性指標的加權(quán)因子，則評價函數(shù)F（X）可由式（6）表示。

2.3降溫管理和收斂準則

（1）降溫管理。在產(chǎn)生新解的過程中，當(dāng)解的質(zhì)量變差的概率呈Boltzmann分布時，S．Geman和D．Geman從理論上證明了采用t(k)=K ／log(1+k)對數(shù)降溫方式可使模擬退火算法收斂于全局最優(yōu)解；當(dāng)解的質(zhì)量變差的概率呈Cahchy分布時，H．Szu和R．Hartley從理論上證明按t(k)=K(1+k)降溫方式可使模擬退火算法收斂于全局最優(yōu)解[2]。實際應(yīng)用中為了簡化計算，常采用一些簡單直觀的溫度下降方法。本文采用式（7）所示的等比率下降方法，也即每一步溫度以相同的比率下降。

式中k≥O，為溫度下降次數(shù)；0

（2）收斂準則。算法的收斂準則設(shè)為多次迭代都沒有新解產(chǎn)生或者控制參數(shù)小到一定程度，即經(jīng)過loopm次循環(huán)，按照Metropolis準則判斷，均不接受新解，或者溫度下降到終止溫度Tend。

3、程序?qū)崿F(xiàn)

3.1程序模塊結(jié)構(gòu)

根據(jù)夜視裝備編配優(yōu)化模擬退火算法，可設(shè)計程序模塊結(jié)構(gòu)如圖1所示。

（1）主程序模塊。該模塊通過調(diào)用初始數(shù)據(jù)錄入模塊、產(chǎn)生初始解模塊、模擬退火處理模塊、評價函數(shù)計算模塊和運算結(jié)果輸出模塊，實現(xiàn)全部算法功能。

（2）初始數(shù)據(jù)錄入模塊。該模塊用于輸入問題的已知條件和算法運行參數(shù)，問題的已知條件包括設(shè)備總數(shù)、崗位總數(shù)及權(quán)重、各型號設(shè)備價格、設(shè)備對崗位的適應(yīng)度矩陣、評價函數(shù)中的各分函數(shù)加權(quán)因子等；算法的運行參數(shù)包括初始溫度、終止溫度、溫度衰減系數(shù)、循環(huán)次數(shù)等。

（3）產(chǎn)生初始解模塊。用于按照矩陣排列的解的表示方法，隨機產(chǎn)生1個元素值均為0或1的m×n矩陣，該排列即為一個初始解，將該初始解作為當(dāng)前解。

（4）模擬退火處理模塊。該模塊用于在同一溫度下不斷執(zhí)行擾動操作，并按模擬退火算法的接受概率決定是否以擾動產(chǎn)生的新解代替當(dāng)前解。

（5）評價函數(shù)計算模塊。該模塊的作用是根據(jù)問題的已知條件，計算各目標函數(shù)值，并利用公式(6)計算出該解的評價值。

（6）運算結(jié)果輸出模塊。該模塊用于輸出程序的運算結(jié)果，即算法求得的最終解所對應(yīng)的分配矩陣和目標函數(shù)值。

3.2模擬退火部分程序

本文程序用C語言實現(xiàn)，下面給出模擬退火部分程序片段。

4、結(jié)束語

設(shè)備配備優(yōu)化是一個多目標組合優(yōu)化問題，本文研究采用模擬退火算法尋找全局最優(yōu)解，給出了具體算法步驟和程序?qū)崿F(xiàn)方案。將智能算法應(yīng)用于解決設(shè)備配備優(yōu)化的問題，具有實踐指導(dǎo)意義。

參考文獻

[1]林令娟.模擬退火微粒群混合算法的研究[D].濟南:山東師范大學(xué),2010.

[2]劉曉瑩.基于改進模擬退火算法的給水管網(wǎng)改擴建優(yōu)化規(guī)劃[D].合肥:合肥工業(yè)大學(xué),2009.