《专题资料（2021-2022年）0104079模拟退火算法在贷款组合优化决策中的应用.doc》由会员分享，可在线阅读，更多相关《专题资料（2021-2022年）0104079模拟退火算法在贷款组合优化决策中的应用.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、模拟退火算法在贷款组合优化决策中的应用刘则毅刘灿（天津大学数学系，天津 300072）摘要针对贷款组合优化决策模型的求解问题，本文提出了一种改进的模拟退火算法。数值计算的结果表明，该算法具有很强的适用性。关键词贷款组合模拟退火全局优化随机搜索1 1引言引言风险贷款组合配给决策，是在综合考虑贷款收益和风险的前提下，从众多的贷款对象中选择一组合适的贷款对象的过程。文献1中建立了基于单位风险收益最大原则的贷款组合优化决策模型。该问题的求解过程在规模较小时是简单易行的，但随着问题规模的增大，其计算量随之呈指数型增长。因此，需要设计出一种兼顾解的质量以及运行时间的较好算法。模拟退火算法是 80 年代初期
2、发展起来的一种求解大规模组合优化问题的随机性方法。它以优化问题的求解与物理系统退火过程的相似性为基础，利用 Metropolis 算法并适当的控制温度的下降过程实现模拟退火，从而达到求解全局优化问题的目的。它具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制等优点。模拟退火算法在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目标函数值变“好”的试探点，而且还能够以一定的概率接受使目标函数值变“差”的试探点，接受概率随着温度的下降逐渐减小。模拟退火算法的这种搜索策略有利于
3、避免搜索过程因陷入局部最优解而无法自拔的弊端，有利于提高求得全局最优解的可靠性。本文提出了一种求解上述模型的改进模拟退火算法，数据结果表明该算法计算效率高，稳定性好。2 2模型模型本模型的建立基于以下三个原则：（1）单位风险收益最大原则通过计算组合投资的平均收益与组合风险之比来判断组合方案的优劣，比值大的组合方案代表其单位风险所获得的收益也大。（2）贷款剩余资源最少原则如果仅依据单位风险收益最大原则来决策，就可能出现只有很少几个项目被选中的情况，这样会造成分配后的剩余资金过多。因此，在贷款组合优化决策中，应在每笔单项贷款可行的基础上，增加一个最低贷款额度 Lb的约束条件，以使剩余资金处于银行可
4、以接受的水平。（3）可比性原则贷款项目的使用年限或寿命不尽相同，若采用净现值（NPV）作为评价指标，则不具有可比性。为使评价指标具有可比性，应采用总净现值进行评价。设为贷款组合的标准差，用来衡量贷款组合的总风险；m为申请贷款企业的个数；TNPVi，TNPVj分别为第i个企业和第j个企业新建项目的总净现值；Xi=1 为 0-1 变量，Xi=0 为第i个贷款企业未被选中，Xi=1 为第i个贷款企业被选中；cov（TNPViXi，TNPVjXj）为第i个项目总净现值与第j个项目总净现值的斜方差，即二者的组合风险；当Xi=0 时，第i个贷款企业项目未被选中，其与第j个贷款企业项目的协方差为 0。则贷款
5、组合的总风险为=mi 1mj 1cov（TNPViXi，TNPVjXj）2/1=mi 1mj 1XiXjcov（TNPVi，TNPVj）2/1贷款组合的总效益为 TNPV=mi 1TNPViXi根据上述原则，设W为贷款的单位风险收益，则决策模型目标函数为 maxW=TNPV/。设L为银行贷款总额，Li为 i 第个企业新建项目所需贷款额，La为银行中长期贷款的可用头寸，Lb为银行中长期贷款组合的最低配给额。根据上述原则，资金约束为LbLLa，L=mi 1LiXi综合上述内容，可得到贷款风险组合优化决策模型如下：obj maxW=TNPV/s.t.mi 1LiXiLami 1LiXiLb（）其中T
6、NPV=mi 1TNPViXi=mi 1mj 1XiXjcov（TNPVi，TNPVj）2/1Xi=,0,1企业不选企业选iii=1m3 3改进的模拟退火算法改进的模拟退火算法上述组合优化问题属于 NP 完全问题，该问题的求解需要问题规模的指数阶时间。当有m 个企业申请贷款时，即问题规模为 m 时有 2m个解（含不可行解），找出最优解需要进行 2m-1次比较运算。用运算能力为 1Mflops(每秒一百万次浮点运算)的计算机进行求解，在 m=10时只需 1ms，而当 m=60 时，需用 366 世纪！因此，需要找出兼顾解的质量以及运算时间的较好算法。模拟退火算法是一种解大规模组合优化问题，特别是
7、 NP 完全问题的有效近似算法。它源于对固体退火过程的模拟；采用 Metropolis 接受准则；并用一种称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火算法的一般形式是：从选定的初始解开始，在借助于控制参数 t 递减时产生的一系列 Mapkob 链中，利用一个新解产生装置和接受准则，重复进行包括“产生新解计算目标函数差判断是否接受新解接受（或舍弃）新解”这四个任务的试验，不断对当前解迭代，从而达到使目标函数最优的执行过程。针对模型（），对模拟退火过程中的关键步骤说明如下：（1）新解产生装置。在 1m 之间随机选取 i 和 j，当前解中若第 i 个和第 j 个
8、企业获得贷款状态相同则改变第 i 个企业的贷款状态；若不同则交换其状态。即,1,11jiiijijjiiXXXXXXXXXX若若且（2）关于初始点的调整。由于模型约束条件中上下限的限制严格，对于一个离可行域比较远的初始点（例如取 X0=(0,0)），通过上述新解产生装置可能无法在初始点的“附近”找到可行解。因此，需进行一个快速调整的过程。即若LLb（贷款总额未达到最低限额）则依次选取未获贷款企业，改变其贷款状况使之获得贷款，重复这一过程直到符合条件。若贷款超额则依次取消某些企业的贷款使之符合条件。（3）接受准则。采取扩充的 Metropolis 接受准则判断是否接受新解。若新解可行且优于当前解
9、则接受；否则按 exp(W/t)或 0 的概率接受新解。即P=0,10),/exp(WWtW若可行且，若不可行0若可行且（4）停止准则。当控制参数 t 递减至设定值时停止算法。根据模拟退火思想设计适合模型（）的算法如下：步骤 1产生初始解 X0，其中=（x1,xm）|xi0,1为可能解集合，xi代表第 i 个企业是否获得贷款的状态。计算相应的目标函数值 W0；给出控制参数初值 t0,Mapkob 链长度 N 以及停止参数 K 和。步骤 2判断初始解的可行性。若不可行则快速调整，否则转步骤 3。步骤 3产生新解并计算新解与当前解的目标函数值之差W。然后由接受准则计算P(W,t)，取（0,1）上服
10、从均匀分布的随机数，若 P(W,t)接受新解，否则放弃新解。步骤 4累计重排次数 n。若 nN 转步骤 3，否则转步骤 5。步骤 5判断停止准则是否满足。若不满足则令 t=0.9t,n=0 转步骤 3，否则停止算法输出当前解。由于模拟退火算法的随机性，终止解可能不是整个过程所遇到的解中最优的。即使是最优的，虽然可证明算法对整体最优解的渐进收敛性，但终止解的可接受性也不能不遭到怀疑。另外，当终止解在最优解的附近时，算法本身不能迅速逼近或达到它。因此，对上述算法进行如下改进：（1）设置记忆器。设变量 X*和 W*分别用于记忆当前遇到的最优解及目标函数值。算法开始时令 X*和 W*分别等于初始解及其
11、目标函数值；以后每接受一个新解时，就将当前解的目标函数值与 W*作比较，若优于 W*就用当前解替换 X*和 W*。最后算法结束时，将所得最优解与记忆器中的解比较，取较优的一个作为当前最优解。（2）算法最后链接一个局部搜索过程。以上步所得当前最优点为起点，用新解产生装置产生新解，仅当优于当前解时接受。重复若干次后终止算法。经过上述改进后的模拟退火算法具有较好的稳定性，可以获得更好的近似解甚至整体最优解。4实例分析某银行新建项目的贷款头寸La为 300 万元，贷款最低完成任务Lb为 270 万元。现有十个企业申请基建贷款。有关信息如表一、表二所示。现在要求确定银行的贷款组合决策，以决定对哪些企业发
12、放贷款。表一贷款组合备选方案项 目投 资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.009
13、66.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.
14、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。在计算机上运
15、行后得到最优解 X*=(1,1,0,1,1,0,1,1,1,1)。结合这一实例对算法的主要性能分析如下：（1）按照上述参数设置，算法运行中总共比较了不到三百个方案（包括不可行解），而对 m=10 的模型共有 1024 个方案可供选择。由此可见这一算法极大的提高了计算效率，节省了计算时间。（2）将程序连续运行 10 次，其中有 9 次获得了理想的结果（即整体最优解），因而算法的稳定性能是非常好的。进一步分析可知，有五次运行是在常规算法阶段就得到了最优解，还有两次是在记忆器中得到的最优解，另有两次是在最后的局部搜索中才得到理想结果。由此可见，对原常规算法进行改进是必要的，也是可行的，这一改进保证了
16、算法的稳定性。5结论本文针对贷款组合优化决策模型的求解问题，提出了一种改进的模拟退火算法。数值计算的结果表明，该算法具有很强的适用性。将模拟退火算法运用于贷款组合优化决策模型的求解是完全可行的。参考文献1迟国泰、秦学志、朱战宇 基于单位风险收益最大原则的贷款组合优化决策模型.控制与决策，2000，4：469472。2康立山、谢云、尤矢勇、罗祖华.非数值并行算法模拟退火算法.北京：科学出版社，1998。3王强。模拟退火算法的改进及其应用.应用数学，1993，4：392397。An SimulatedAnnealingAlgorithm and ItsApplication inDecision-
17、making Model of Loans Portfolio OptimizationLiu ZeyiLiu Can(Department of Mathematics,Tianjin University.Tianjin 300072)AbstractTo solve the decision-making model of loans portfolio optimization,a improvedsimulated annealing algorithm is proposed in this paper.The numerical computation resultsindicate that this algorithm has good applicability.Keywordloans portfoliosimulated annealingglobal optimizationrandom search