模拟退火算法在贷款组合优化决策中的运用90810.docx

《模拟退火算法在贷款组合优化决策中的运用90810.docx》由会员分享，可在线阅读，更多相关《模拟退火算法在贷款组合优化决策中的运用90810.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模拟退火算算法在贷款款组合优化化决策中的的应用刘则毅 刘灿（天津大学学数学系，天天津 30000722）摘要 针针对贷款组组合优化决决策模型的的求解问题题，本文提提出了一种种改进的模模拟退火算算法。数值值计算的结结果表明，该该算法具有有很强的适适用性。关键词 贷款组合合 模拟拟退火 全局优化化 随机机搜索1 引言言风险贷款组组合配给决决策，是在在综合考虑虑贷款收益益和风险的的前提下，从从众多的贷贷款对象中中选择一组组合适的贷贷款对象的的过程。文献1中建立了了基于单位位风险收益益最大原则则的贷款组组合优化决决策模型。该该问题的求求解过程在在规模较小小时是简单单易行的，但但随着问题题规模的增增大，

2、其计计算量随之之呈指数型型增长。因因此，需要要设计出一一种兼顾解解的质量以以及运行时时间的较好好算法。模拟退火算算法是800年代初期期发展起来来的一种求求解大规模模组合优化化问题的随随机性方法法。它以优优化问题的的求解与物物理系统退退火过程的的相似性为为基础，利利用Mettropoolis算算法并适当当的控制温温度的下降降过程实现现模拟退火火，从而达达到求解全全局优化问问题的目的的。它具有有描述简单单、使用灵灵活、运用用广泛、运运行效率高高和较少受受初始条件件限制等优优点。模拟拟退火算法法在搜索策策略上与传传统的随机机搜索方法法不同，它它不仅引入入了适当的的随机因素素，而且还还引入了物物理系统

3、退退火过程的的自然机理理。这种自自然机理的的引入使模模拟退火算算法在迭代代过程中不不仅接受使使目标函数数值变“好”的试探点点，而且还还能够以一一定的概率率接受使目目标函数值值变“差”的试探点点，接受概概率随着温温度的下降降逐渐减小小。模拟退退火算法的的这种搜索索策略有利利于避免搜搜索过程因因陷入局部部最优解而而无法自拔拔的弊端，有有利于提高高求得全局局最优解的的可靠性。本文提出了了一种求解解上述模型型的改进模模拟退火算算法，数据据结果表明明该算法计计算效率高高，稳定性性好。2 模型型 本模型的建建立基于以以下三个原原则：（1）单位位风险收益益最大原则则 通过计计算组合投投资的平均均收益与组组合

4、风险之之比来判断断组合方案案的优劣，比比值大的组组合方案代代表其单位位风险所获获得的收益益也大。（2）贷款款剩余资源源最少原则则 如果仅仅依据单位位风险收益益最大原则则来决策，就就可能出现现只有很少少几个项目目被选中的的情况，这这样会造成成分配后的的剩余资金金过多。因因此，在贷贷款组合优优化决策中中，应在每每笔单项贷贷款可行的的基础上，增增加一个最最低贷款额额度Lb的约束条条件，以使使剩余资金金处于银行行可以接受受的水平。（3）可比比性原则 贷款项项目的使用用年限或寿寿命不尽相相同，若采采用净现值值（NPVV）作为评评价指标，则则不具有可可比性。为为使评价指指标具有可可比性，应应采用总净净现值

5、进行行评价。设为贷款款组合的标标准差，用用来衡量贷贷款组合的的总风险；m为申请贷贷款企业的的个数；TTNPVii ，TNPVVj分别为第第i个企业和和第j个企业新新建项目的的总净现值值；Xi =1为0-1变量量，Xi =0为第第i个贷款企企业未被选选中，Xi =1为第第i个贷款企企业被选中中；covv（TNPVVi Xi ，TNPVVjXj）为第i个项目总总净现值与与第j个项目总总净现值的的斜方差，即即二者的组组合风险；当Xi =0时，第第i个贷款企企业项目未未被选中，其其与第j个贷款企企业项目的的协方差为为0。则贷款款组合的总总风险为= ccov（TNPVVi Xi ，TNPVVjXj）=

6、XXi Xjcov（TNPVVi ，TNPVVj）贷款组合的的总效益为为TNPVV= TNNPViXi 根据上述原原则，设WW为贷款的的单位风险险收益，则则决策模型型目标函数数为maxxW=TNNPV/。设L为银行行贷款总额额，Li为i第个企业业新建项目目所需贷款款额，La为银行中中长期贷款款的可用头头寸，Lb为银行中中长期贷款款组合的最最低配给额额。根据上上述原则，资资金约束为为LbLLa ， L=LiXi综合上述内内容，可得得到贷款风风险组合优优化决策模模型如下：obj mmaxW=TNPVV/s.t. LiXiLaLiXiiLb （）其中TNPV= TNNPVi Xi= XXi Xjco

7、v（TNPVVi ，TNPVVj）Xi= ii =1m3 改进进的模拟退退火算法上述组合优优化问题属属于NP完全问问题，该问问题的求解解需要问题题规模的指指数阶时间间。当有mm个企业申申请贷款时时，即问题题规模为mm时有2m个解（含含不可行解解），找出出最优解需需要进行22m-1次比比较运算。用用运算能力力为1Mfflopss(每秒一一百万次浮浮点运算)的计算机机进行求解解，在m=10时只只需1mss，而当mm=60时，需需用3666世纪！因因此，需要要找出兼顾顾解的质量量以及运算算时间的较较好算法。模模拟退火算算法是一种种解大规模模组合优化化问题，特特别是NPP完全问题题的有效近近似算法。它

8、它源于对固固体退火过过程的模拟拟；采用MMetroopoliis接受准准则；并用用一种称为为冷却进度度表的参数数控制算法法进程，使使算法在多多项式时间间里给出一一个近似最最优解。模拟退火算算法的一般般形式是：从选定的的初始解开开始，在借借助于控制制参数t递减时产产生的一系系列Mappkob链链中，利用用一个新解解产生装置置和接受准准则，重复复进行包括括“产生新解解计算目目标函数差差判断是是否接受新新解接受（或或舍弃）新新解”这四个任任务的试验验，不断对对当前解迭迭代，从而而达到使目目标函数最最优的执行行过程。针针对模型（），对模拟退火过程中的关键步骤说明如下：（1）新解解产生装置置。在1m之间

9、随随机选取ii和j，当前解解中若第ii个和第j个企业获获得贷款状状态相同则则改变第ii个企业的的贷款状态态；若不同同则交换其其状态。即即（2）关于于初始点的的调整。由由于模型约约束条件中中上下限的的限制严格格，对于一一个离可行行域比较远远的初始点点（例如取取X0=(0, ,0)），通通过上述新新解产生装装置可能无无法在初始始点的“附近”找到可行行解。因此此，需进行行一个快速速调整的过过程。即若若LLb（贷款总总额未达到到最低限额额）则依次次选取未获获贷款企业业，改变其其贷款状况况使之获得得贷款，重重复这一过过程直到符符合条件。若若贷款超额额则依次取取消某些企企业的贷款款使之符合合条件。（3）接

10、受受准则。采采取扩充的的Metrropollis接受受准则判断断是否接受受新解。若若新解可行行且优于当当前解则接接受；否则则按expp(W/t)或或0的概率率接受新解解。即P=（4）停止止准则。当当控制参数数t递减至至设定值时停止算算法。根据模拟退退火思想设设计适合模模型（）的算法法如下： 步骤1 产生初始始解X0，其中=（x1, xm）| xi0,11为可可能解集合合，xi代表第i个企业是是否获得贷贷款的状态态。计算相相应的目标标函数值WW0；给出控控制参数初初值t0, Mappkob链链长度N以以及停止参参数K和。步骤2 判断初始始解的可行行性。若不不可行则快快速调整，否否则转步骤骤3。步

11、骤3 产生新解解并计算新新解与当前前解的目标标函数值之之差W。然后由由接受准则则计算P(W, t)，取（00,1）上上服从均匀匀分布的随随机数，若P(W, t)接受新新解，否则则放弃新解解。步骤4 累计重排排次数n。若若nN转转步骤3，否否则转步骤骤5。步骤5 判断停止止准则是否否满足。若若不满足则则令t=00.9t,n=0转转步骤3，否否则停止算算法输出当当前解。由于模拟退退火算法的的随机性，终终止解可能能不是整个个过程所遇遇到的解中中最优的。即即使是最优优的，虽然然可证明算算法对整体体最优解的的渐进收敛敛性，但终终止解的可可接受性也也不能不遭遭到怀疑。另另外，当终终止解在最最优解的附附近时

12、，算算法本身不不能迅速逼逼近或达到到它。因此此，对上述述算法进行行如下改进进：（1）设置置记忆器。设设变量X*和W*分分别用于记记忆当前遇遇到的最优优解及目标标函数值。算算法开始时时令X*和和W*分别别等于初始始解及其目目标函数值值；以后每每接受一个个新解时，就就将当前解解的目标函函数值与WW*作比较较，若优于于W*就用用当前解替替换X*和和W*。最最后算法结结束时，将将所得最优优解与记忆忆器中的解解比较，取取较优的一一个作为当当前最优解解。（2）算法法最后链接接一个局部部搜索过程程。以上步步所得当前前最优点为为起点，用用新解产生生装置产生生新解，仅仅当优于当当前解时接接受。重复复若干次后后终

13、止算法法。经过上述改改进后的模模拟退火算算法具有较较好的稳定定性，可以以获得更好好的近似解解甚至整体体最优解。4 实例例分析某银行新建建项目的贷贷款头寸LLa为3000万元，贷贷款最低完完成任务LLb为2700万元。现现有十个企企业申请基基建贷款。有有关信息如如表一、表表二所示。现现在要求确确定银行的的贷款组合合决策，以以决定对哪哪些企业发发放贷款。表一 贷贷款组合备备选方案项 目投 资352839.931.55626.255632124.511.2TNPVii47.18845.22225.40072.86622.45520.77796.76643.01143.42222.422表二 总总净现

14、值TTNPV的的协方差矩矩阵covv（TNPVVi ，TNPVVj）123456789101600.000400.0001200.00500.0001500.00980.0001300.00700.000640.000400.0002400.000266.667800.000333.3331000.00653.333866.667466.667426.667266.66731200.00800.0002600.00966.6673100.002100.002300.001433.331413.33746.6674500.000333.333966.667422.2221233.33793.33

15、31133.33577.778511.111342.22251500.001000.003100.001233.333800.002520.003100.001766.671666.67973.3336980.000653.3332100.00793.3332520.001698.671913.331166.671138.67616.00071300.00866.6672300.001133.333100.001913.333266.671466.671186.67946.6678700.000466.6671433.33577.7781766.671166.671466.67822.2227

16、68.889457.7789640.000426.6671413.33511.1111666.671138.671186.67768.889771.556391.11110400.000266.667746.667342.222973.333616.000946.667457.778391.111280.889运用MATTLAB软软件，可以以根据上述述算法编制制相应程序序对该问题题进行求解解。其中相相关参数的的设置为：X0=(0,0,0,0,0,0,0,0,0,0)，t0=1，N=5,=0.022。在计算算机上运行行后得到最最优解X*=(1,1,0,1,1,0,1,1,1,1)。结结合这一实实

17、例对算法法的主要性性能分析如如下：（1）按照照上述参数数设置，算算法运行中中总共比较较了不到三三百个方案案（包括不不可行解），而而对m=10的的模型共有有10244个方案可可供选择。由由此可见这这一算法极极大的提高高了计算效效率，节省省了计算时时间。（2）将程程序连续运运行10次次，其中有有9次获得得了理想的的结果（即即整体最优优解），因因而算法的的稳定性能能是非常好好的。进一一步分析可可知，有五五次运行是是在常规算算法阶段就就得到了最最优解，还还有两次是是在记忆器器中得到的的最优解，另另有两次是是在最后的的局部搜索索中才得到到理想结果果。由此可可见，对原原常规算法法进行改进进是必要的的，也是

18、可可行的，这这一改进保保证了算法法的稳定性性。5 结论论本文针对贷贷款组合优优化决策模模型的求解解问题，提提出了一种种改进的模模拟退火算算法。数值值计算的结结果表明，该该算法具有有很强的适适用性。 将模拟退退火算法运运用于贷款款组合优化化决策模型型的求解是是完全可行行的。参考文献1 迟国国泰、秦学学志、朱战战宇 基于于单位风险险收益最大大原则的贷贷款组合优优化决策模模型. 控控制与决策策，20000，4：469472。2 康立立山、谢云云、尤矢勇勇、罗祖华华. 非数值值并行算法法模拟退火火算法. 北京：科学出版版社， 19998。3 王强强。模拟退退火算法的的改进及其其应用. 应用数学学，19

19、993，4：392397。An Siimulaated Anneealinng Allgoriithm and Its Appllicattion in DDecission-makiing MModell of Loanns PPortffolioo OpttimizzatioonLiu ZZeyi Liiu Caan(Depaartmeent oof Maathemmaticcs, TTianjjin UUniveersitty.Tiianjiin 30000722)Abstrract To solvve thhe deecisiion-mmakinng moodel of lloans

20、poortfoolio optiimizaationn, a imprrovedd simmulatted aanneaalingg alggoritthm iis prropossed iin thhis ppaperr. Thhe nuumeriical compputattion resuults indiicatee thaat thhis aalgorrithmm hass goood apppliccabillity.Keywoord loanns pportffolioo siimulaated anneealinng gglobaal opptimiizatiion randdom ssearcch