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

模擬退火算法在貸款組合優(yōu)化決策中的應(yīng)用1引言風(fēng)險(xiǎn)貸款組合配給決策，是在綜合考慮貸款收益和風(fēng)險(xiǎn)的前提下，從眾多的貸款對(duì)象中選擇一組合適的貸款對(duì)象的過程。文獻(xiàn)［1］中建立了基于單位風(fēng)險(xiǎn)收益最大原則的貸款組合優(yōu)化決策模型。該問題的求解過程在規(guī)模較小時(shí)是簡單易行的，但隨著問題規(guī)模的增大，其計(jì)算量隨之呈指數(shù)型增長。因此，需要設(shè)計(jì)出一種兼顧解的質(zhì)量以及運(yùn)行時(shí)間的較好算法。模擬退火算法是80年代初期發(fā)展起來的一種求解大規(guī)模組合優(yōu)化問題的隨機(jī)性方法。它以優(yōu)化問題的求解與物理系統(tǒng)退火過程的相似性為基礎(chǔ)，利用Metropolis算法并適當(dāng)?shù)目刂茰囟鹊南陆颠^程實(shí)現(xiàn)模擬退火，從而達(dá)到求解全局優(yōu)化問題的目的。它具有描述簡單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受初始條件限制等優(yōu)點(diǎn)。模擬退火算法在搜索策略上與傳統(tǒng)的隨機(jī)搜索方法不同，它不僅引入了適當(dāng)?shù)碾S機(jī)因素，而且還引入了物理系統(tǒng)退火過程的自然機(jī)理。這種自然機(jī)理的引入使模擬退火算法在迭代過程中不僅接受使目標(biāo)函數(shù)值變“好”的試探點(diǎn)，而且還能夠以一定的概率接受使目標(biāo)函數(shù)值變“差”的試探點(diǎn)，接受概率隨著溫度的下降逐漸減小。模擬退火算法的這種搜索策略有利于避免搜索過程因陷入局部最優(yōu)解而無法自拔的弊端，有利于提高求得全局最優(yōu)解的可靠性。本文提出了一種求解上述模型的改進(jìn)模擬退火算法，數(shù)據(jù)結(jié)果表明該算法計(jì)算效率高，穩(wěn)定性好。2模型本模型的建立基于以下三個(gè)原則：（1）單位風(fēng)險(xiǎn)收益最大原則通過計(jì)算組合投資的平均收益與組合風(fēng)險(xiǎn)之比來判斷組合方案的優(yōu)劣，比值大的組合方案代表其單位風(fēng)險(xiǎn)所獲得的收益也大。貸款剩余資源最少原則如果僅依據(jù)單位風(fēng)險(xiǎn)收益最大原則來決策，就可能出現(xiàn)只有很少幾個(gè)項(xiàng)目被選中的情況，這樣會(huì)造成分配后的剩余資金過多。因此，在貸款組合優(yōu)化決策中，應(yīng)在每筆單項(xiàng)貸款可行的基礎(chǔ)上，增加一個(gè)最低貸款額度Lb的約束條件，以使剩余資金處于銀行可以接受的水平。可比性原則貸款項(xiàng)目的使用年限或壽命不盡相同，若采用凈現(xiàn)值(NPV)作為評(píng)價(jià)指標(biāo)，則不具有可比性。為使評(píng)價(jià)指標(biāo)具有可比性，應(yīng)采用總凈現(xiàn)值進(jìn)行評(píng)價(jià)。設(shè)為貸款組合的標(biāo)準(zhǔn)差，用來衡量貸款組合的總風(fēng)險(xiǎn)；山為申請貸款企業(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)為=[]E欄cov(TNPVi-Xi，TNPVj?Xj)]1/2i=1j=1=[2E產(chǎn)XiXj?cov(TNPVi，TNPVj)]1/2i=1j=1貸款組合的總效益為TNPV=￡TNPVi-Xii=1根據(jù)上述原則，設(shè)W為貸款的單位風(fēng)險(xiǎn)收益，則決策模型目標(biāo)函數(shù)為maxW=TNPV/。設(shè)L為銀行貸款總額，Li為i第個(gè)企業(yè)新建項(xiàng)目所需貸款額，La為銀行中長期貸款的可用頭寸，Lb為銀行中長期貸款組合的最低配給額。根據(jù)上述原則，資金約束為綜合上述內(nèi)容，Lb^L^La，L=￡LiXii=1可得到貸款風(fēng)險(xiǎn)組合優(yōu)化決策模型如下：objmaxW=TNPV/s.t.￡LiXi^La￡LiXiNLb(I)i=1i=1其中TNPV=￡TNPVi?Xii=1Z=[YYXiXj?cov(TNPVi，TNPVj)]1/2i=1j=1Xi={0,不選i企業(yè)i=1?m1,選i企業(yè)3改進(jìn)的模擬退火算法上述組合優(yōu)化問題屬于NP完全問題，該問題的求解需要問題規(guī)模的指數(shù)階時(shí)間。當(dāng)有m個(gè)企業(yè)申請貸款時(shí)，即問題規(guī)模為m時(shí)有2m個(gè)解（含不可行解），找出最優(yōu)解需要進(jìn)行2m-1次比較運(yùn)算。用運(yùn)算能力為1Mflops（每秒一百萬次浮點(diǎn)運(yùn)算）的計(jì)算機(jī)進(jìn)行求解，在m=10時(shí)只需1ms,而當(dāng)m=60時(shí)，需用366世紀(jì)!因此，需要找出兼顧解的質(zhì)量以及運(yùn)算時(shí)間的較好算法。模擬退火算法是一種解大規(guī)模組合優(yōu)化問題，特別是NP完全問題的有效近似算法。它源于對(duì)固體退火過程的模擬；采用Metropolis接受準(zhǔn)則；并用一種稱為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似最優(yōu)解。模擬退火算法的一般形式是：從選定的初始解開始，在借助于控制參數(shù)t遞減時(shí)產(chǎn)生的一系列Mapkob鏈中，利用一個(gè)新解產(chǎn)生裝置和接受準(zhǔn)則，重復(fù)進(jìn)行包括“產(chǎn)生新解一一計(jì)算目標(biāo)函數(shù)差——判斷是否接受新解——接受（或舍棄）新解”這四個(gè)任務(wù)的試驗(yàn)，不斷對(duì)當(dāng)前解迭代，從而達(dá)到使目標(biāo)函數(shù)最優(yōu)的執(zhí)行過程。針對(duì)模型（I），對(duì)模擬退火過程中的關(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)。即{乂,=1"=乂尸X=1-X且X=1-X，若X豐Xiijjij關(guān)于初始點(diǎn)的調(diào)整。由于模型約束條件中上下限的限制嚴(yán)格，對(duì)于一個(gè)離可行域比較遠(yuǎn)的初始點(diǎn)(例如取X0=(0,?,0))，通過上述新解產(chǎn)生裝置可能無法在初始點(diǎn)的“附近”找到可行解。因此，需進(jìn)行一個(gè)快速調(diào)整的過程。即若LvLb(貸款總額未達(dá)到最低限額)則依次選取未獲貸款企業(yè)，改變其貸款狀況使之獲得貸款，重復(fù)這一過程直到符合條件。若貸款超額則依次取消某些企業(yè)的貸款使之符合條件。接受準(zhǔn)則。采取擴(kuò)充的Metropolis接受準(zhǔn)則判斷是否接受新解。若新解可行且優(yōu)于當(dāng)前解則接受；否則按exp(AW/t)或0的概率接受新解。即(1,若可行且△w>0P二exp(△W/1),若可行且△W<00，若不可行停止準(zhǔn)則。當(dāng)控制參數(shù)t遞減至設(shè)定值￡時(shí)停止算法。根據(jù)模擬退火思想設(shè)計(jì)適合模型(I)的算法如下：步驟1產(chǎn)生初始解X0EQ，其中Q={(x,…，x)|x^{0,1}}為可能解1mi集合，x.代表第i個(gè)企業(yè)是否獲得貸款的狀態(tài)。計(jì)算相應(yīng)的目標(biāo)函數(shù)值W0；給出控制參數(shù)初值t0,Mapkob鏈長度N以及停止參數(shù)K和￡。步驟2判斷初始解的可行性。若不可行則快速調(diào)整，否則轉(zhuǎn)步驟3。步驟3產(chǎn)生新解并計(jì)算新解與當(dāng)前解的目標(biāo)函數(shù)值之差A(yù)W。然后由接受準(zhǔn)則計(jì)算P(AW,t)，取(0,1)上服從均勻分布的隨機(jī)數(shù)0，若P(AW,t)N0接受新解，否則放棄新解。步驟4累計(jì)重排次數(shù)n。若nVN轉(zhuǎn)步驟3,否則轉(zhuǎn)步驟5。步驟5判斷停止準(zhǔn)則是否滿足。若不滿足則令t=0.9t,n=0轉(zhuǎn)步驟3,否則停止算法輸出當(dāng)前解。由于模擬退火算法的隨機(jī)性，終止解可能不是整個(gè)過程所遇到的解中最優(yōu)的。即使是最優(yōu)的，雖然可證明算法對(duì)整體最優(yōu)解的漸進(jìn)收斂性，但終止解的可接受性也不能不遭到懷疑。另外，當(dāng)終止解在最優(yōu)解的附近時(shí)，算法本身不能迅速逼近或達(dá)到它。因此，對(duì)上述算法進(jìn)行如下改進(jìn)：(1)設(shè)置記憶器。設(shè)變量X*和W*分別用于記憶當(dāng)前遇到的最優(yōu)解及目標(biāo)函數(shù)值。算法開始時(shí)令X*和W*分別等于初始解及其目標(biāo)函數(shù)值；以后每接受一個(gè)新解時(shí)，就將當(dāng)前解的目標(biāo)函數(shù)值與W*作比較，若優(yōu)于W*就用當(dāng)前解替換X*和W*。最后算法結(jié)束時(shí)，將所得最優(yōu)解與記憶器中的解比較，取較優(yōu)的一個(gè)作為當(dāng)前最優(yōu)解。(2)算法最后鏈接一個(gè)局部搜索過程。以上步所得當(dāng)前最優(yōu)點(diǎn)為起點(diǎn)，用新解產(chǎn)生裝置產(chǎn)生新解，僅當(dāng)優(yōu)于當(dāng)前解時(shí)接受。重復(fù)若干次后終止算法。經(jīng)過上述改進(jìn)后的模擬退火算法具有較好的穩(wěn)定性，可以獲得更好的近似解甚至整體最優(yōu)解。4實(shí)例分析某銀行新建項(xiàng)目的貸款頭寸La為300萬元，貸款最低完成任務(wù)Lb為270萬元?，F(xiàn)有十個(gè)企業(yè)申請基建貸款。有關(guān)信息如表一、表二所示?，F(xiàn)在要求確定銀行的貸款組合決策，以決定對(duì)哪些企業(yè)發(fā)放貸款。表一貸款組合備選方案項(xiàng)目IIIIIIVHW伽IXXxn投資352839.931.55626.25632124.511.2TN47.45.25.72.22.20.96.43.43.22.PVi18224086457776014242表二總凈現(xiàn)值TNPV的協(xié)方差矩陣cov(TNPVi,TNPVj)123456789101600.00400.001200.00500.001500.00980.001300.00700.00640.00400.009400.00266.67800.00333.331000.00653.33866.67466.67426.67266.67

212003.00800.002600.00966.673100.002100.002300.001433.331413.33746.674500.00333.33966.67422.221233.33793.331133.33577.78511.11342.22l15005.001000.003100.001233.333800.002520.003100.001766.671666.67973.33尸980.b00653.332100.00793.332520.001698.671913.331166.671138.67616.0071300.00866.672300.001133.333100.001913.333266.671466.671186.67946.67o700.800466.671433.33577.781766.671166.671466.67822.22768.89457.78c640.900426.671413.33511.111666.671138.671186.67768.89771.56391.1101400.00266.67746.67342.22973.33616.00946.67457.78391.11280.89運(yùn)用MATLAB軟件，可以根據(jù)上述算法編制相應(yīng)程序?qū)υ搯栴}進(jìn)行求解。其中相關(guān)參數(shù)的設(shè)置為：X0=（0,0,0,0,0,0,0,0,0,0），t0=1，N=5,e=0.02。在計(jì)算機(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è)方案可供選擇。由此可見這一算法極大的提高了計(jì)算效率，節(jié)省了計(jì)算時(shí)間。（2）將程序連續(xù)運(yùn)行10次，其中有9次獲得了理想的結(jié)果（即整體最優(yōu)解），因而算法的穩(wěn)定性能是非常好的。進(jìn)一步分析可知，有五次運(yùn)行是在常規(guī)算法階段就得到了最優(yōu)解，還有兩次是在記憶器中得到的最優(yōu)解，另有兩次是在最后的局部搜索中才得到理想結(jié)果。由此可見，對(duì)原常規(guī)算法進(jìn)行改進(jìn)是必要的，也是可行的，這一改進(jìn)保證了算法的穩(wěn)定性。5結(jié)