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

?

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

陳爍1.2胡文剛2

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

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

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

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

1.1配備問(wèn)題描述

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

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

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

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

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

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

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

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

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

1.3約束條件

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

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

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

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

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

2.2配備優(yōu)化評(píng)價(jià)函數(shù)

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

2.3降溫管理和收斂準(zhǔn)則

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

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

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

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

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

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

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

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

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

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

（5）評(píng)價(jià)函數(shù)計(jì)算模塊。該模塊的作用是根據(jù)問(wèn)題的已知條件，計(jì)算各目標(biāo)函數(shù)值，并利用公式(6)計(jì)算出該解的評(píng)價(jià)值。

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

3.2模擬退火部分程序

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

4、結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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