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

模拟退火算法在贷款组合优化决策中的应用刘则毅刘灿（天津大学数学系，天津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。则贷款组合的总风险为σ=[mi1mj1cov（TNPVi·Xi，TNPVj·Xj）]2/1=[mi1mj1XiXj·cov（TNPVi，TNPVj）]2/1贷款组合的总效益为TNPV=mi1TNPVi·Xi根据上述原则，设W为贷款的单位风险收益，则决策模型目标函数为maxW=TNPV/σ。设L为银行贷款总额，Li为i第个企业新建项目所需贷款额，La为银行中长期贷款的可用头寸，Lb为银行中长期贷款组合的最低配给额。根据上述原则，资金约束为Lb≤L≤La，L=mi1LiXi综合上述内容，可得到贷款风险组合优化决策模型如下：objmaxW=TNPV/σs.t.mi1LiXi≤Lami1LiXi≥Lb（Ⅰ）其中TNPV=mi1TNPVi·Xiσ=[mi1mj1XiXj·cov（TNPVi，TNPVj）]2/1Xi={,0,1企业不选企业选iii=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个企业的贷款状态；若不同则交换其状态。即{,1,11jiiijijjiiXXXXXXXXXX若若且（2）关于初始点的调整。由于模型约束条件中上下限的限制严格，对于一个离可行域比较远的初始点（例如取X0=(0,…,0)），通过上述新解产生装置可能无法在初始点的“附近”找到可行解。因此，需进行一个快速调整的过程。即若L＜Lb（贷款总额未达到最低限额）则依次选取未获贷款企业，改变其贷款状况使之获得贷款，重复这一过程直到符合条件。若贷款超额则依次取消某些企业的贷款使之符合条件。（3）接受准则。采取扩充的Metropolis接受准则判断是否接受新解。若新解可行且优于当前解则接受；否则按exp(△W/t)或0的概率接受新解。即P={0,10),/exp(WWtW若可行且，若不可行0若可行且（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'sportfoliooptimization,aimprovedsimulatedannealingalgorithmisproposedinthispaper.