0104079模擬退火算法在貸款組合優(yōu)化決策中的應(yīng)用

0104079模擬退火算法在貸款組合優(yōu)化決策中的應(yīng)用劉則毅劉燦（天津大學(xué)數(shù)學(xué)系，天津300072）摘要針對(duì)貸款組合優(yōu)化決策模型的求解咨詢(xún)題，本文提出了一種改進(jìn)的模擬退火算法。數(shù)值運(yùn)算的結(jié)果表明，該算法具有專(zhuān)門(mén)強(qiáng)的適用性。關(guān)鍵詞貸款組合模擬退火全局優(yōu)化隨機(jī)搜索1引言風(fēng)險(xiǎn)貸款組合配給決策，是在綜合考慮貸款收益和風(fēng)險(xiǎn)的前提下，從眾多的貸款對(duì)象中選擇一組合適的貸款對(duì)象的過(guò)程。文獻(xiàn)[1]中建立了基于單位風(fēng)險(xiǎn)收益最大原則的貸款組合優(yōu)化決策模型。該咨詢(xún)題的求解過(guò)程在規(guī)模較小時(shí)是簡(jiǎn)單易行的，但隨著咨詢(xún)題規(guī)模的增大，其運(yùn)算量隨之呈指數(shù)型增長(zhǎng)。因此，需要設(shè)計(jì)出一種兼顧解的質(zhì)量以及運(yùn)行時(shí)刻的較好算法。模擬退火算法是80年代初期進(jìn)展起來(lái)的一種求解大規(guī)模組合優(yōu)化咨詢(xún)題的隨機(jī)性方法。它以?xún)?yōu)化咨詢(xún)題的求解與物理系統(tǒng)退火過(guò)程的相似性為基礎(chǔ)，利用Metropolis算法并適當(dāng)?shù)牟倏v溫度的下降過(guò)程實(shí)現(xiàn)模擬退火，從而達(dá)到求解全局優(yōu)化咨詢(xún)題的目的。它具有描述簡(jiǎn)單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制等優(yōu)點(diǎn)。模擬退火算法在搜索策略上與傳統(tǒng)的隨機(jī)搜索方法不同，它不僅引入了適當(dāng)?shù)碾S機(jī)因素，而且還引入了物理系統(tǒng)退火過(guò)程的自然機(jī)理。這種自然機(jī)理的引入使模擬退火算法在迭代過(guò)程中不僅同意使目標(biāo)函數(shù)值變“好”的試探點(diǎn)，而且還能夠以一定的概率同意使目標(biāo)函數(shù)值變“差”的試探點(diǎn)，同意概率隨著溫度的下降逐步減小。模擬退火算法的這種搜索策略有利于幸免搜索過(guò)程因陷入局部最優(yōu)解而無(wú)法自拔的弊端，有利于提升求得全局最優(yōu)解的可靠性。本文提出了一種求解上述模型的改進(jìn)模擬退火算法，數(shù)據(jù)結(jié)果表明該算法運(yùn)算效率高，穩(wěn)固性好。2模型本模型的建立基于以下三個(gè)原則：（1）單位風(fēng)險(xiǎn)收益最大原則通過(guò)運(yùn)算組合投資的平均收益與組合風(fēng)險(xiǎn)之比來(lái)判定組合方案的優(yōu)劣，比值大的組合方案代表其單位風(fēng)險(xiǎn)所獲得的收益也大。（2）貸款剩余資源最少原則如果僅依據(jù)單位風(fēng)險(xiǎn)收益最大原則來(lái)決策，就可能顯現(xiàn)只有專(zhuān)門(mén)少幾個(gè)項(xiàng)目被選中的情形，如此會(huì)造成分配后的剩余資金過(guò)多。因此，在貸款組合優(yōu)化決策中，應(yīng)在每筆單項(xiàng)貸款可行的基礎(chǔ)上，增加一個(gè)最低貸款額度Lb的約束條件，以使剩余資金處于銀行能夠同意的水平。（3）可比性原則貸款項(xiàng)目的使用年限或壽命不盡相同，若采納凈現(xiàn)值（NPV）作為評(píng)判指標(biāo)，則不具有可比性。為使評(píng)判指標(biāo)具有可比性，應(yīng)采納總凈現(xiàn)值進(jìn)行評(píng)判。設(shè)σ為貸款組合的標(biāo)準(zhǔn)差，用來(lái)衡量貸款組合的總風(fēng)險(xiǎn)；m為申請(qǐng)貸款企業(yè)的個(gè)數(shù)；TNPVi，TNPVj分別為第i個(gè)企業(yè)和第j個(gè)企業(yè)新建項(xiàng)目的總凈現(xiàn)值；Xi=1為0-1變量，Xi=0為第i個(gè)貸款企業(yè)未被選中，Xi=1為第i個(gè)貸款企業(yè)被選中；cov（TNPVi·Xi，TNPVj·Xj）為第i個(gè)項(xiàng)目總凈現(xiàn)值與第j個(gè)項(xiàng)目總凈現(xiàn)值的斜方差，即二者的組合風(fēng)險(xiǎn)；當(dāng)Xi=0時(shí)，第i個(gè)貸款企業(yè)項(xiàng)目未被選中，其與第j個(gè)貸款企業(yè)項(xiàng)目的協(xié)方差為0。則貸款組合的總風(fēng)險(xiǎn)為σ=[cov（TNPVi·Xi，TNPVj·Xj）] =[XiXj·cov（TNPVi，TNPVj）]貸款組合的總效益為T(mén)NPV=TNPVi·Xi按照上述原則，設(shè)W為貸款的單位風(fēng)險(xiǎn)收益，則決策模型目標(biāo)函數(shù)為maxW=TNPV/σ。設(shè)L為銀行貸款總額，Li為i第個(gè)企業(yè)新建項(xiàng)目所需貸款額，La為銀行中長(zhǎng)期貸款的可用頭寸，Lb為銀行中長(zhǎng)期貸款組合的最低配給額。按照上述原則，資金約束為L(zhǎng)b≤L≤La，L=LiXi綜合上述內(nèi)容，可得到貸款風(fēng)險(xiǎn)組合優(yōu)化決策模型如下：objmaxW=TNPV/σs.t.LiXi≤La LiXi≥Lb（Ⅰ）其中TNPV=TNPVi·Xiσ=[XiXj·cov（TNPVi，TNPVj）]Xi={i=1～m3改進(jìn)的模擬退火算法上述組合優(yōu)化咨詢(xún)題屬于NP完全咨詢(xún)題，該咨詢(xún)題的求解需要咨詢(xún)題規(guī)模的指數(shù)階時(shí)刻。當(dāng)有m個(gè)企業(yè)申請(qǐng)貸款時(shí)，即咨詢(xún)題規(guī)模為m時(shí)有2m個(gè)解（含不可行解），找出最優(yōu)解需要進(jìn)行2m-1次比較運(yùn)算。用運(yùn)算能力為1Mflops(每秒一百萬(wàn)次浮點(diǎn)運(yùn)算)的運(yùn)算機(jī)進(jìn)行求解，在m=10時(shí)只需1ms，而當(dāng)m=60時(shí)，需用366世紀(jì)！因此，需要找出兼顧解的質(zhì)量以及運(yùn)算時(shí)刻的較好算法。模擬退火算法是一種解大規(guī)模組合優(yōu)化咨詢(xún)題，專(zhuān)門(mén)是NP完全咨詢(xún)題的有效近似算法。它源于對(duì)固體退火過(guò)程的模擬；采納Metropolis同意準(zhǔn)則；并用一種稱(chēng)為冷卻進(jìn)度表的參數(shù)操縱算法進(jìn)程，使算法在多項(xiàng)式時(shí)刻里給出一個(gè)近似最優(yōu)解。模擬退火算法的一樣形式是：從選定的初始解開(kāi)始，在借助于操縱參數(shù)t遞減時(shí)產(chǎn)生的一系列Mapkob鏈中，利用一個(gè)新解產(chǎn)生裝置和同意準(zhǔn)則，重復(fù)進(jìn)行包括“產(chǎn)生新解——運(yùn)算目標(biāo)函數(shù)差——判定是否同意新解——同意（或舍棄）新解”這四個(gè)任務(wù)的試驗(yàn)，持續(xù)對(duì)當(dāng)前解迭代，從而達(dá)到使目標(biāo)函數(shù)最優(yōu)的執(zhí)行過(guò)程。針對(duì)模型（Ⅰ），對(duì)模擬退火過(guò)程中的關(guān)鍵步驟講明如下：（1）新解產(chǎn)生裝置。在1～m之間隨機(jī)選取i和j，當(dāng)前解中若第i個(gè)和第j個(gè)企業(yè)獲得貸款狀態(tài)相同則改變第i個(gè)企業(yè)的貸款狀態(tài)；若不同則交換其狀態(tài)。即（2）關(guān)于初始點(diǎn)的調(diào)整。由于模型約束條件中上下限的限制嚴(yán)格，關(guān)于一個(gè)離可行域比較遠(yuǎn)的初始點(diǎn)（例如取X0=(0,…,0)），通過(guò)上述新解產(chǎn)生裝置可能無(wú)法在初始點(diǎn)的“鄰近”找到可行解。因此，需進(jìn)行一個(gè)快速調(diào)整的過(guò)程。即若L＜Lb（貸款總額未達(dá)到最低限額）則依次選取未獲貸款企業(yè)，改變其貸款狀況使之獲得貸款，重復(fù)這一過(guò)程直到符合條件。若貸款超額則依次取消某些企業(yè)的貸款使之符合條件。（3）同意準(zhǔn)則。采取擴(kuò)充的Metropolis同意準(zhǔn)則判定是否同意新解。若新解可行且優(yōu)于當(dāng)前解則同意；否則按exp(△W/t)或0的概率同意新解。即P=（4）停止準(zhǔn)則。當(dāng)操縱參數(shù)t遞減至設(shè)定值ε時(shí)停止算法。按照模擬退火思想設(shè)計(jì)適合模型（Ⅰ）的算法如下：步驟1產(chǎn)生初始解X0∈，其中={（x1,…,xm）|xi∈{0,1}}為可能解集合，xi代表第i個(gè)企業(yè)是否獲得貸款的狀態(tài)。運(yùn)算相應(yīng)的目標(biāo)函數(shù)值W0；給出操縱參數(shù)初值t0,Mapkob鏈長(zhǎng)度N以及停止參數(shù)K和ε。步驟2判定初始解的可行性。若不可行則快速調(diào)整，否則轉(zhuǎn)步驟3。步驟3產(chǎn)生新解并運(yùn)算新解與當(dāng)前解的目標(biāo)函數(shù)值之差△W。然后由同意準(zhǔn)則運(yùn)算P(△W,t)，?。?,1）上服從平均分布的隨機(jī)數(shù)δ，若P(△W,t)≥δ同意新解，否則舍棄新解。步驟4累計(jì)重排次數(shù)n。若n＜N轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟5。步驟5判定停止準(zhǔn)則是否滿(mǎn)足。若不滿(mǎn)足則令t=0.9t,n=0轉(zhuǎn)步驟3，否則停止算法輸出當(dāng)前解。由于模擬退火算法的隨機(jī)性，終止解可能不是整個(gè)過(guò)程所遇到的解中最優(yōu)的。即使是最優(yōu)的，盡管可證明算法對(duì)整體最優(yōu)解的漸進(jìn)收斂性，但終止解的可同意性也不能不遭到懷疑。另外，當(dāng)終止解在最優(yōu)解的鄰近時(shí)，算法本身不能迅速靠近或達(dá)到它。因此，對(duì)上述算法進(jìn)行如下改進(jìn)：（1）設(shè)置經(jīng)歷器。設(shè)變量X*和W*分別用于經(jīng)歷當(dāng)前遇到的最優(yōu)解及目標(biāo)函數(shù)值。算法開(kāi)始時(shí)令X*和W*分別等于初始解及其目標(biāo)函數(shù)值；以后每同意一個(gè)新解時(shí)，就將當(dāng)前解的目標(biāo)函數(shù)值與W*作比較，若優(yōu)于W*就用當(dāng)前解替換X*和W*。最后算法終止時(shí)，將所得最優(yōu)解與經(jīng)歷器中的解比較，取較優(yōu)的一個(gè)作為當(dāng)前最優(yōu)解。（2）算法最后鏈接一個(gè)局部搜索過(guò)程。以上步所得當(dāng)前最優(yōu)點(diǎn)為起點(diǎn)，用新解產(chǎn)生裝置產(chǎn)生新解，僅當(dāng)優(yōu)于當(dāng)前解時(shí)同意。重復(fù)若干次后終止算法。通過(guò)上述改進(jìn)后的模擬退火算法具有較好的穩(wěn)固性，能夠獲得更好的近似解甚至整體最優(yōu)解。4實(shí)例分析某銀行新建項(xiàng)目的貸款頭寸La為300萬(wàn)元，貸款最低完成任務(wù)Lb為270萬(wàn)元?，F(xiàn)有十個(gè)企業(yè)申請(qǐng)基建貸款。有關(guān)信息如表一、表二所示?，F(xiàn)在要求確定銀行的貸款組合決策，以決定對(duì)哪些企業(yè)發(fā)放貸款。表一貸款組合備選方案項(xiàng)目ⅠⅡⅢⅤⅥⅦⅧⅨⅩⅫ投資352839.931.55626.25632124.511.2TNPVi47.1845.2225.4072.8622.4520.7796.7643.0143.4222.42表二總凈現(xiàn)值TNPV的協(xié)方差矩陣cov（TNPVi，TNPVj）123456789101600.00400.001200.00500.001500.00980.001300.00700.00640.00400.002400.00266.67800.00333.331000.00653.33866.67466.67426.67266.6731200.00800.002600.00966.673100.002100.002300.001433.331413.33746.674500.00333.33966.67422.221233.33793.331133.33577.78511.11342.2251500.001000.003100.001233.333800.002520.003100.001766.671666.67973.336980.00653.332100.00793.332520.001698.671913.331166.671138.67616.0071300.00866.672300.001133.333100.001913.333266.671466.671186.67946.678700.00466.671433.33577.781766.671166.671466.67822.22768.89457.789640.00426.671413.33511.111666.671138.671186.67768.89771.56391.1110400.00266.67746.67342.22973.33616.00946.67457.78391.11280.89運(yùn)用MATLAB軟件，能夠按照上述算法編制相應(yīng)程序?qū)υ撟稍?xún)題進(jìn)行求解。其中有關(guān)參數(shù)的設(shè)置為：X0=(0,0,0,0,0,0,0,0,0,0)，t0=1，N=5,ε=0.02。在運(yùn)算機(jī)上運(yùn)行后得到最優(yōu)解X*=(1,1,0,1,1,0,1,1,1,1)。結(jié)合這一實(shí)例對(duì)算法的要緊性能分析如下：（1）按照上述參數(shù)設(shè)置，算法運(yùn)行中總共比較了不到三百個(gè)方案（包括不可行解），而對(duì)m=10的模型共有1024個(gè)方案可供選擇。由此可見(jiàn)這一算法極大的提升了運(yùn)算效率，節(jié)約了運(yùn)算時(shí)刻。（2）將程序連續(xù)運(yùn)行10次，其中有9次獲得了理想的結(jié)果（即整體最優(yōu)解），因而算法的穩(wěn)固性能是專(zhuān)門(mén)好的。進(jìn)一步分析可知，有五次運(yùn)行是在常規(guī)算法時(shí)期就得到了最優(yōu)解，還有兩次是在經(jīng)歷器中得到的最優(yōu)解，另有兩次是在最后的局部搜索中才得到理想結(jié)果。由此可見(jiàn)，對(duì)原常規(guī)算法進(jìn)行改進(jìn)是必要的，也是可行的，這一改進(jìn)保證了算法的穩(wěn)固性。5結(jié)論本文針對(duì)貸款組合優(yōu)化決策模型的求解咨詢(xún)題，提出了一種改進(jìn)的模擬退火算法。數(shù)值運(yùn)算的結(jié)果表明，該算法具有專(zhuān)門(mén)強(qiáng)的適用性。將模擬退火算法運(yùn)用于貸款組合優(yōu)化決策模型的求解是完全可行的。參考文獻(xiàn)1遲國(guó)泰、秦學(xué)志、朱戰(zhàn)宇基于單位風(fēng)險(xiǎn)收益最大原則的貸款組合優(yōu)化決策模型.操縱與決策，2000，4：469～472。2康立山、謝云、尤矢勇、羅祖華.非數(shù)值并行算法—模擬退火算法.北京：科學(xué)出版社，1998。3王強(qiáng)。模擬退火算法的改進(jìn)及其應(yīng)用.應(yīng)用數(shù)學(xué)，1993，4：392～397。AnSimulatedAnnealingAlgorithmandItsApplicationinDecision-makingModelofLoan'sPortfolioOptimizationLiuZeyiLiuCan(DepartmentofMathematics,TianjinUniversity.Tianjin300072)AbstractTosolvethedecision-makingmodelofloan's