陳爍 胡文剛

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

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

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

1.1配備問題描述

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

設(shè)備配備通常還受崗位重要性、經(jīng)濟(jì)性和保障性等因素制約。其中崗位重要性是指設(shè)備配備的崗位的相對(duì)重要性。經(jīng)濟(jì)性是指配備的總成本，即配備設(shè)備的總價(jià)格。保障性是指配備的設(shè)備型號(hào)數(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è)備對(duì)第j類崗位的適應(yīng)程度，當(dāng)完全適應(yīng)時(shí)其值取1，當(dāng)不能適應(yīng)時(shí)取0。適應(yīng)度值根據(jù)設(shè)備新舊、替換使用性和需求匹配度等因素由專家經(jīng)驗(yàn)確定。

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

（1）

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

（2）

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

設(shè)m維向量U，令，則配備設(shè)備型號(hào)總數(shù)目標(biāo)函數(shù)可由式（3）表示。

（3）

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

1.3約束條件

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

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

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

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

在模擬退火算法中，從一個(gè)隨機(jī)解X0開始探測(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

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

將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題的方法很多，本文采取線性加權(quán)和法。配備優(yōu)化模型中有配備綜合效能P、配備總體成本C和配備型號(hào)總數(shù)量Y三個(gè)目標(biāo)函數(shù)，其中配備總體成本C和配備型號(hào)總數(shù)量Y具有不同量綱，且函數(shù)值在量級(jí)上有較大差異，需要先轉(zhuǎn)化為無量綱且等量級(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)。可以看出，Cz、Yz均無量綱且值在[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）表示。

F（X）=α·P+β·Cz+γ·Yz （6）

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

（1）降溫管理。在產(chǎn)生新解的過程中，當(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）所示的等比率下降方法，也即每一步溫度以相同的比率下降。

Tk+1=d·Tk （7）

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

（2）收斂準(zhǔn)則。算法的收斂準(zhǔn)則設(shè)為多次迭代都沒有新解產(chǎn)生或者控制參數(shù)小到一定程度，即經(jīng)過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）主程序模塊。該模塊通過調(diào)用初始數(shù)據(jù)錄入模塊、產(chǎn)生初始解模塊、模擬退火處理模塊、評(píng)價(jià)函數(shù)計(jì)算模塊和運(yùn)算結(jié)果輸出模塊，實(shí)現(xiàn)全部算法功能。

（2）初始數(shù)據(jù)錄入模塊。該模塊用于輸入問題的已知條件和算法運(yùn)行參數(shù)，問題的已知條件包括設(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ù)問題的已知條件，計(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語言實(shí)現(xiàn)，下面給出模擬退火部分程序片段。

while（T>T_end）

{ dF=J（F（i+1））-J（F（i））；

if（dF>=0） //表達(dá)擾動(dòng)后得到更優(yōu)解，則總是接受擾動(dòng)

F（i+1）=F（i）； //接受從F（i）到F（i+1）的擾動(dòng)

else

{ if（exp（dF/T）>random（0，1））

F（i+1）=F（i）； //接受從F（i）到F（i+1）的擾動(dòng)

}

T*=d； //降溫退火 ，0

i++；}

4、結(jié)束語

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

參考文獻(xiàn)

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

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