0104079模拟退火算法在贷款组合优化决策中的应用

0104079模拟退火算法在贷款组合优化决策中的应用刘则毅刘灿（天津大学数学系，天津300072）摘要针对贷款组合优化决策模型的求解咨询题，本文提出了一种改进的模拟退火算法。数值运算的结果表明，该算法具有专门强的适用性。关键词贷款组合模拟退火全局优化随机搜索1引言风险贷款组合配给决策，是在综合考虑贷款收益和风险的前提下，从众多的贷款对象中选择一组合适的贷款对象的过程。文献[1]中建立了基于单位风险收益最大原则的贷款组合优化决策模型。该咨询题的求解过程在规模较小时是简单易行的，但随着咨询题规模的增大，其运算量随之呈指数型增长。因此，需要设计出一种兼顾解的质量以及运行时刻的较好算法。模拟退火算法是80年代初期进展起来的一种求解大规模组合优化咨询题的随机性方法。它以优化咨询题的求解与物理系统退火过程的相似性为基础，利用Metropolis算法并适当的操纵温度的下降过程实现模拟退火，从而达到求解全局优化咨询题的目的。它具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制等优点。模拟退火算法在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅同意使目标函数值变“好”的试探点，而且还能够以一定的概率同意使目标函数值变“差”的试探点，同意概率随着温度的下降逐步减小。模拟退火算法的这种搜索策略有利于幸免搜索过程因陷入局部最优解而无法自拔的弊端，有利于提升求得全局最优解的可靠性。本文提出了一种求解上述模型的改进模拟退火算法，数据结果表明该算法运算效率高，稳固性好。2模型本模型的建立基于以下三个原则：（1）单位风险收益最大原则通过运算组合投资的平均收益与组合风险之比来判定组合方案的优劣，比值大的组合方案代表其单位风险所获得的收益也大。（2）贷款剩余资源最少原则如果仅依据单位风险收益最大原则来决策，就可能显现只有专门少几个项目被选中的情形，如此会造成分配后的剩余资金过多。因此，在贷款组合优化决策中，应在每笔单项贷款可行的基础上，增加一个最低贷款额度Lb的约束条件，以使剩余资金处于银行能够同意的水平。（3）可比性原则贷款项目的使用年限或寿命不尽相同，若采纳净现值（NPV）作为评判指标，则不具有可比性。为使评判指标具有可比性，应采纳总净现值进行评判。设σ为贷款组合的标准差，用来衡量贷款组合的总风险；m为申请贷款企业的个数；TNPVi，TNPVj分别为第i个企业和第j个企业新建项目的总净现值；Xi=1为0-1变量，Xi=0为第i个贷款企业未被选中，Xi=1为第i个贷款企业被选中；cov（TNPVi·Xi，TNPVj·Xj）为第i个项目总净现值与第j个项目总净现值的斜方差，即二者的组合风险；当Xi=0时，第i个贷款企业项目未被选中，其与第j个贷款企业项目的协方差为0。则贷款组合的总风险为σ=[cov（TNPVi·Xi，TNPVj·Xj）] =[XiXj·cov（TNPVi，TNPVj）]贷款组合的总效益为TNPV=TNPVi·Xi按照上述原则，设W为贷款的单位风险收益，则决策模型目标函数为maxW=TNPV/σ。设L为银行贷款总额，Li为i第个企业新建项目所需贷款额，La为银行中长期贷款的可用头寸，Lb为银行中长期贷款组合的最低配给额。按照上述原则，资金约束为Lb≤L≤La，L=LiXi综合上述内容，可得到贷款风险组合优化决策模型如下：objmaxW=TNPV/σs.t.LiXi≤La LiXi≥Lb（Ⅰ）其中TNPV=TNPVi·Xiσ=[XiXj·cov（TNPVi，TNPVj）]Xi={i=1～m3改进的模拟退火算法上述组合优化咨询题属于NP完全咨询题，该咨询题的求解需要咨询题规模的指数阶时刻。当有m个企业申请贷款时，即咨询题规模为m时有2m个解（含不可行解），找出最优解需要进行2m-1次比较运算。用运算能力为1Mflops(每秒一百万次浮点运算)的运算机进行求解，在m=10时只需1ms，而当m=60时，需用366世纪！因此，需要找出兼顾解的质量以及运算时刻的较好算法。模拟退火算法是一种解大规模组合优化咨询题，专门是NP完全咨询题的有效近似算法。它源于对固体退火过程的模拟；采纳Metropolis同意准则；并用一种称为冷却进度表的参数操纵算法进程，使算法在多项式时刻里给出一个近似最优解。模拟退火算法的一样形式是：从选定的初始解开始，在借助于操纵参数t递减时产生的一系列Mapkob链中，利用一个新解产生装置和同意准则，重复进行包括“产生新解——运算目标函数差——判定是否同意新解——同意（或舍弃）新解”这四个任务的试验，持续对当前解迭代，从而达到使目标函数最优的执行过程。针对模型（Ⅰ），对模拟退火过程中的关键步骤讲明如下：（1）新解产生装置。在1～m之间随机选取i和j，当前解中若第i个和第j个企业获得贷款状态相同则改变第i个企业的贷款状态；若不同则交换其状态。即（2）关于初始点的调整。由于模型约束条件中上下限的限制严格，关于一个离可行域比较远的初始点（例如取X0=(0,…,0)），通过上述新解产生装置可能无法在初始点的“邻近”找到可行解。因此，需进行一个快速调整的过程。即若L＜Lb（贷款总额未达到最低限额）则依次选取未获贷款企业，改变其贷款状况使之获得贷款，重复这一过程直到符合条件。若贷款超额则依次取消某些企业的贷款使之符合条件。（3）同意准则。采取扩充的Metropolis同意准则判定是否同意新解。若新解可行且优于当前解则同意；否则按exp(△W/t)或0的概率同意新解。即P=（4）停止准则。当操纵参数t递减至设定值ε时停止算法。按照模拟退火思想设计适合模型（Ⅰ）的算法如下：步骤1产生初始解X0∈，其中={（x1,…,xm）|xi∈{0,1}}为可能解集合，xi代表第i个企业是否获得贷款的状态。运算相应的目标函数值W0；给出操纵参数初值t0,Mapkob链长度N以及停止参数K和ε。步骤2判定初始解的可行性。若不可行则快速调整，否则转步骤3。步骤3产生新解并运算新解与当前解的目标函数值之差△W。然后由同意准则运算P(△W,t)，取（0,1）上服从平均分布的随机数δ，若P(△W,t)≥δ同意新解，否则舍弃新解。步骤4累计重排次数n。若n＜N转步骤3，否则转步骤5。步骤5判定停止准则是否满足。若不满足则令t=0.9t,n=0转步骤3，否则停止算法输出当前解。由于模拟退火算法的随机性，终止解可能不是整个过程所遇到的解中最优的。即使是最优的，尽管可证明算法对整体最优解的渐进收敛性，但终止解的可同意性也不能不遭到怀疑。另外，当终止解在最优解的邻近时，算法本身不能迅速靠近或达到它。因此，对上述算法进行如下改进：（1）设置经历器。设变量X*和W*分别用于经历当前遇到的最优解及目标函数值。算法开始时令X*和W*分别等于初始解及其目标函数值；以后每同意一个新解时，就将当前解的目标函数值与W*作比较，若优于W*就用当前解替换X*和W*。最后算法终止时，将所得最优解与经历器中的解比较，取较优的一个作为当前最优解。（2）算法最后链接一个局部搜索过程。以上步所得当前最优点为起点，用新解产生装置产生新解，仅当优于当前解时同意。重复若干次后终止算法。通过上述改进后的模拟退火算法具有较好的稳固性，能够获得更好的近似解甚至整体最优解。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.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软件，能够按照上述算法编制相应程序对该咨询题进行求解。其中有关参数的设置为：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次获得了理想的结果（即整体最优解），因而算法的稳固性能是专门好的。进一步分析可知，有五次运行是在常规算法时期就得到了最优解，还有两次是在经历器中得到的最优解，另有两次是在最后的局部搜索中才得到理想结果。由此可见，对原常规算法进行改进是必要的，也是可行的，这一改进保证了算法的稳固性。5结论本文针对贷款组合优化决策模型的求解咨询题，提出了一种改进的模拟退火算法。数值运算的结果表明，该算法具有专门强的适用性。将模拟退火算法运用于贷款组合优化决策模型的求解是完全可行的。参考文献1迟国泰、秦学志、朱战宇基于单位风险收益最大原则的贷款组合优化决策模型.操纵与决策，2000，4：469～472。2康立山、谢云、尤矢勇、罗祖华.非数值并行算法—模拟退火算法.北京：科学出版社，1998。3王强。模拟退火算法的改进及其应用.应用数学，1993，4：392～397。AnSimulatedAnnealingAlgorithmandItsApplicationinDecision-makingModelofLoan'sPortfolioOptimizationLiuZeyiLiuCan(DepartmentofMathematics,TianjinUniversity.Tianjin300072)AbstractTosolvethedecision-makingmodelofloan's