基于模擬退火算法的設備配備優化

?

基于模擬退火算法的設備配備優化

陳爍1.2胡文剛2

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

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

[關鍵詞]設備配備；編配優化；模擬退火

1、設備配備問題描述及數學模型

1.1配備問題描述

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

表1　設備與崗位適應度矩陣表

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

1.2定義數學模型

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

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

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

考慮設備的保障性，要求各崗位配備設備的型號數要盡量的少。為便于統計型號數量，需要對分配矩陣X進行適當變換。

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

1.3約束條件

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

2、設備配備優化算法設計

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

2.1模擬退火配備優化算法

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

2.2配備優化評價函數

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

2.3降溫管理和收斂準則

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

式中k≥O，為溫度下降次數；0

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

3、程序實現

3.1程序模塊結構

根據夜視裝備編配優化模擬退火算法，可設計程序模塊結構如圖1所示。

（1）主程序模塊。該模塊通過調用初始數據錄入模塊、產生初始解模塊、模擬退火處理模塊、評價函數計算模塊和運算結果輸出模塊，實現全部算法功能。

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

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

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

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

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

3.2模擬退火部分程序

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

4、結束語

設備配備優化是一個多目標組合優化問題，本文研究采用模擬退火算法尋找全局最優解，給出了具體算法步驟和程序實現方案。將智能算法應用于解決設備配備優化的問題，具有實踐指導意義。

參考文獻

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

[2]劉曉瑩.基于改進模擬退火算法的給水管網改擴建優化規劃[D].合肥:合肥工業大學,2009.