1、最新 精品 Word 歡迎下載 可修改模擬退火算法在貸款組合優化決策中的應用劉則毅 劉燦（天津大學數學系，天津 300072）摘要 針對貸款組合優化決策模型的求解問題，本文提出了一種改進的模擬退火算法。數值計算的結果表明，該算法具有很強的適用性。關鍵詞 貸款組合 模擬退火 全局優化 隨機搜索1 引言風險貸款組合配給決策，是在綜合考慮貸款收益和風險的前提下，從眾多的貸款對象中選擇一組合適的貸款對象的過程。文獻1中建立了基于單位風險收益最大原則的貸款組合優化決策模型。該問題的求解過程在規模較小時是簡單易行的，但隨著問題規模的增大，其計算量隨之呈指數型增長。因此，需要設計出一種兼顧解的質量以及運行時

2、間的較好算法。模擬退火算法是80年代初期發展起來的一種求解大規模組合優化問題的隨機性方法。它以優化問題的求解與物理系統退火過程的相似性為基礎，利用Metropolis算法并適當的控制溫度的下降過程實現模擬退火，從而達到求解全局優化問題的目的。它具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受初始條件限制等優點。模擬退火算法在搜索策略上與傳統的隨機搜索方法不同，它不僅引入了適當的隨機因素，而且還引入了物理系統退火過程的自然機理。這種自然機理的引入使模擬退火算法在迭代過程中不僅接受使目標函數值變“好”的試探點，而且還能夠以一定的概率接受使目標函數值變“差”的試探點，接受概率隨著溫度的下降逐漸減

3、小。模擬退火算法的這種搜索策略有利于避免搜索過程因陷入局部最優解而無法自拔的弊端，有利于提高求得全局最優解的可靠性。本文提出了一種求解上述模型的改進模擬退火算法，數據結果表明該算法計算效率高，穩定性好。2 模型 本模型的建立基于以下三個原則：（1）單位風險收益最大原則 通過計算組合投資的平均收益與組合風險之比來判斷組合方案的優劣，比值大的組合方案代表其單位風險所獲得的收益也大。（2）貸款剩余資源最少原則 如果僅依據單位風險收益最大原則來決策，就可能出現只有很少幾個項目被選中的情況，這樣會造成分配后的剩余資金過多。因此，在貸款組合優化決策中，應在每筆單項貸款可行的基礎上，增加一個最低貸款額度Lb

4、的約束條件，以使剩余資金處于銀行可以接受的水平。（3）可比性原則 貸款項目的使用年限或壽命不盡相同，若采用凈現值（NPV）作為評價指標，則不具有可比性。為使評價指標具有可比性，應采用總凈現值進行評價。設為貸款組合的標準差，用來衡量貸款組合的總風險；m為申請貸款企業的個數；TNPVi ，TNPVj分別為第i個企業和第j個企業新建項目的總凈現值；Xi =1為0-1變量，Xi =0為第i個貸款企業未被選中，Xi =1為第i個貸款企業被選中；cov（TNPVi Xi ，TNPVjXj）為第i個項目總凈現值與第j個項目總凈現值的斜方差，即二者的組合風險；當Xi =0時，第i個貸款企業項目未被選中，其與第

5、j個貸款企業項目的協方差為0。則貸款組合的總風險為= cov（TNPVi Xi ，TNPVjXj）= Xi Xjcov（TNPVi ，TNPVj）貸款組合的總效益為TNPV= TNPViXi 根據上述原則，設W為貸款的單位風險收益，則決策模型目標函數為maxW=TNPV/。設L為銀行貸款總額，Li為i第個企業新建項目所需貸款額，La為銀行中長期貸款的可用頭寸，Lb為銀行中長期貸款組合的最低配給額。根據上述原則，資金約束為LbLLa ， L=LiXi綜合上述內容，可得到貸款風險組合優化決策模型如下：obj maxW=TNPV/s.t. LiXiLaLiXiLb （）其中TNPV= TNPVi X

6、i= Xi Xjcov（TNPVi ，TNPVj）Xi= i =1m3 改進的模擬退火算法上述組合優化問題屬于NP完全問題，該問題的求解需要問題規模的指數階時間。當有m個企業申請貸款時，即問題規模為m時有2m個解（含不可行解），找出最優解需要進行2m-1次比較運算。用運算能力為1Mflops(每秒一百萬次浮點運算)的計算機進行求解，在m=10時只需1ms，而當m=60時，需用366世紀！因此，需要找出兼顧解的質量以及運算時間的較好算法。模擬退火算法是一種解大規模組合優化問題，特別是NP完全問題的有效近似算法。它源于對固體退火過程的模擬；采用Metropolis接受準則；并用一種稱為冷卻進度表的

7、參數控制算法進程，使算法在多項式時間里給出一個近似最優解。模擬退火算法的一般形式是：從選定的初始解開始，在借助于控制參數t遞減時產生的一系列Mapkob鏈中，利用一個新解產生裝置和接受準則，重復進行包括“產生新解計算目標函數差判斷是否接受新解接受（或舍棄）新解”這四個任務的試驗，不斷對當前解迭代，從而達到使目標函數最優的執行過程。針對模型（），對模擬退火過程中的關鍵步驟說明如下：（1）新解產生裝置。在1m之間隨機選取i和j，當前解中若第i個和第j個企業獲得貸款狀態相同則改變第i個企業的貸款狀態；若不同則交換其狀態。即（2）關于初始點的調整。由于模型約束條件中上下限的限制嚴格，對于一個離可行域比

8、較遠的初始點（例如取X0=(0, ,0)），通過上述新解產生裝置可能無法在初始點的“附近”找到可行解。因此，需進行一個快速調整的過程。即若LLb（貸款總額未達到最低限額）則依次選取未獲貸款企業，改變其貸款狀況使之獲得貸款，重復這一過程直到符合條件。若貸款超額則依次取消某些企業的貸款使之符合條件。（3）接受準則。采取擴充的Metropolis接受準則判斷是否接受新解。若新解可行且優于當前解則接受；否則按exp(W/t)或0的概率接受新解。即P=（4）停止準則。當控制參數t遞減至設定值時停止算法。根據模擬退火思想設計適合模型（）的算法如下： 步驟1 產生初始解X0，其中=（x1, xm）| xi0

9、,1為可能解集合，xi代表第i個企業是否獲得貸款的狀態。計算相應的目標函數值W0；給出控制參數初值t0, Mapkob鏈長度N以及停止參數K和。步驟2 判斷初始解的可行性。若不可行則快速調整，否則轉步驟3。步驟3 產生新解并計算新解與當前解的目標函數值之差W。然后由接受準則計算P(W, t)，取（0,1）上服從均勻分布的隨機數，若P(W, t)接受新解，否則放棄新解。步驟4 累計重排次數n。若nN轉步驟3，否則轉步驟5。步驟5 判斷停止準則是否滿足。若不滿足則令t=0.9t,n=0轉步驟3，否則停止算法輸出當前解。由于模擬退火算法的隨機性，終止解可能不是整個過程所遇到的解中最優的。即使是最優的

10、，雖然可證明算法對整體最優解的漸進收斂性，但終止解的可接受性也不能不遭到懷疑。另外，當終止解在最優解的附近時，算法本身不能迅速逼近或達到它。因此，對上述算法進行如下改進：（1）設置記憶器。設變量X*和W*分別用于記憶當前遇到的最優解及目標函數值。算法開始時令X*和W*分別等于初始解及其目標函數值；以后每接受一個新解時，就將當前解的目標函數值與W*作比較，若優于W*就用當前解替換X*和W*。最后算法結束時，將所得最優解與記憶器中的解比較，取較優的一個作為當前最優解。（2）算法最后鏈接一個局部搜索過程。以上步所得當前最優點為起點，用新解產生裝置產生新解，僅當優于當前解時接受。重復若干次后終止算法。

11、經過上述改進后的模擬退火算法具有較好的穩定性，可以獲得更好的近似解甚至整體最優解。4 實例分析某銀行新建項目的貸款頭寸La為300萬元，貸款最低完成任務Lb為270萬元。現有十個企業申請基建貸款。有關信息如表一、表二所示。現在要求確定銀行的貸款組合決策，以決定對哪些企業發放貸款。表一 貸款組合備選方案項 目投 資352839.931.55626.25632124.511.2TNPVi47.1845.2225.4072.8622.4520.7796.7643.0143.4222.42表二 總凈現值TNPV的協方差矩陣cov（TNPVi ，TNPVj）123456789101600.00400.0

12、01200.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.

13、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.6

14、7342.22973.33616.00946.67457.78391.11280.89運用MATLAB軟件，可以根據上述算法編制相應程序對該問題進行求解。其中相關參數的設置為：X0=(0,0,0,0,0,0,0,0,0,0)，t0=1，N=5,=0.02。在計算機上運行后得到最優解X*=(1,1,0,1,1,0,1,1,1,1)。結合這一實例對算法的主要性能分析如下：（1）按照上述參數設置，算法運行中總共比較了不到三百個方案（包括不可行解），而對m=10的模型共有1024個方案可供選擇。由此可見這一算法極大的提高了計算效率，節省了計算時間。（2）將程序連續運行10次，其中有9次獲得了理想的結果

15、（即整體最優解），因而算法的穩定性能是非常好的。進一步分析可知，有五次運行是在常規算法階段就得到了最優解，還有兩次是在記憶器中得到的最優解，另有兩次是在最后的局部搜索中才得到理想結果。由此可見，對原常規算法進行改進是必要的，也是可行的，這一改進保證了算法的穩定性。5 結論本文針對貸款組合優化決策模型的求解問題，提出了一種改進的模擬退火算法。數值計算的結果表明，該算法具有很強的適用性。 將模擬退火算法運用于貸款組合優化決策模型的求解是完全可行的。參考文獻1 遲國泰、秦學志、朱戰宇 基于單位風險收益最大原則的貸款組合優化決策模型. 控制與決策，2000，4：469472。2 康立山、謝云、尤矢勇、

16、羅祖華. 非數值并行算法模擬退火算法. 北京：科學出版社， 1998。3 王強。模擬退火算法的改進及其應用. 應用數學，1993，4：392397。An Simulated Annealing Algorithm and Its Application in Decision-making Model of Loans Portfolio OptimizationLiu Zeyi Liu Can(Department of Mathematics, Tianjin University.Tianjin 300072)Abstract To solve the decision-making model of loans po