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

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