模拟退火算法与遗传算法

第二章狭义计算智能——优化计算/82确定性优化算法2020/5/262Incomputerscience,adeterministicalgorithmisanalgorithmwhich,givenaparticularinput,willalwaysproducethesameoutput,withtheunderlyingmachinealwayspassingthroughthesamesequenceofstates.给定初始条件后，搜索策略、过程和结果均确定。数值计算法确定性优化算法2020/5/26《计算智能》3NP完全问题的计算复杂度1lg(n)nnlg(n)n^2...n^k...2^n/822.3启发式优化算法4混合优化证券投资组合：证券品种选择属于组合优化问题，买入卖出价位及时机决策属于函数（来自于数据挖掘的预测函数）优化问题。思考：我们不可能掌握全部有用信息，也不可能建立这些信息对后市影响的明确的函数关系，那么如何投资？/82启发式优化算法5股票投资的启发式规则历史数据社会心理K线走势宏观经济情况国家政策……/82启发式优化算法6股票投资的结果跑赢大盘跑赢一年定期存款利率……当然不是最优结果，但已经值得满意/82启发式优化算法2020/5/26《计算智能》7定义（Heuristics）一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题的一个满意的可行解，该可行解与最优解的偏离程度一般不能被预计。Wikipedia:Heuristicreferstoexperience-basedtechniquesforproblemsolving,learning,anddiscoverythatfindasolutionwhichisnotguaranteedtobeoptimal,butgoodenoughforagivensetofgoals.Wheretheexhaustivesearchisimpractical,heuristicmethodsareusedtospeeduptheprocessoffindingasatisfactorysolutionviamentalshortcutstoeasethecognitiveloadofmakingadecision./82启发式优化算法8特点启发式搜索规则：Strategiesthatguidethesearchprocess随机性：每次计算都带有随机性，结果不保证综合优势：以利用较小的计算资源得到较好的可行解为目标NoFreeLunchTheorems假设有A、B两种任意（随机或确定）算法，对于所有问题集，它们的平均性能是相同的（性能可采用多种方法度量，如最优解、收敛速率等）。因此，要根据具体问题和性能要求选择合适的算法及其启发式搜索规则。TheonlyviableoptionforavarietyofcomplexoptimizationproblemsinNP-hardness经验、自然界、仿生…/82启发式优化算法9发展研究热点算法的启发式规则不同有些算法缺乏严格证明共性首先提出一个（组）候选解依据某些适应性条件测算这个（些）候选解的适应度（性能指标）根据适应度保留某些候选解，放弃其他候选解对保留的候选解进行某些操作，生成新的候选解/82启发式优化算法10分类搜索策略：局部搜索or全局搜索确定机制or学习机制迭代方法：单一解or群体解计算流程：serialorparallelorhybrid/82启发式优化算法11分类1:搜索策略对简单局部搜索的改进•simulatedannealing(SA)•tabusearch•iteratedlocalsearch•variableneighborhoodsearch•GRASP具有学习机制•antcolonyoptimization(ACO)•geneticalgorithms(GA)•Simulatedevolutionarycomputation(SEC),模拟进化计算局部搜索从一个初始解出发，搜索它的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。优点是简单、灵活及易于实现；缺点是容易陷入局部最优，且解的质量与初始解和邻域的结构密切相关。张雷,范波.计算智能理论与方法[M].北京:科学出版社.2013:13./82启发式优化算法12分类2:迭代方法Singlesolution•simulatedannealing•iteratedlocalsearchPopulation-based•Inheritance:−GA−harmonysearch(HS)•Contemporaries:−particleswarmoptimization(PSO)−differentialevolution(DE)•Environment:−antcolonyoptimization(ACO)−binarybeesalgorithm(BBA)S.Xu,F.Yu,Z.Luo,Z.Ji,D.T.Pham,R.Qiu.AdaptiveBeesAlgorithm–Bioinspirationfromhoneybeeforagingtooptimizefueleconomyofasemi-trackair-cushionvehicle[J].TheComputerJournal.2011,54(9):1416-1426./82启发式优化算法2020/5/26《计算智能》13代表性算法simulatedannealing(SA)：模拟退火算法geneticalgorithms(GA)：遗传算法antcolonyoptimization(ACO)：蚁群算法particleswarmoptimization(PSO)：粒子群算法Beesalgorithm(BA)anditsvariants：蜜蜂算法/82启发式优化算法2020/5/26《计算智能》14函数优化问题算例二元函数求最小值，精确到4位小数Rosenbrockfunction/82启发式优化算法2020/5/26《计算智能》15组合优化问题算例Berlin52旅行商问题（TSP）——有一个推销员，要到n个城市推销商品。各城市之间的距离已知，要求以最短路线将每个城市访问且只访问1次(exactlyonce)，最终回到起点。即找出一条包含所有n个城市的具有最短路程的环路。5252D52个城市的位置坐标/82模拟退火算法16启发式规则模拟退火算法来源于固体退火原理。将固体加热至充分高温后，让其慢慢冷却。加热时，固体内部粒子随温升变为无序状，内能增大；而慢慢冷却时粒子渐趋有序，在每个温度都有可能达到平衡态，最后在常温时达到基态，内能减为最小。/82模拟退火算法2020/5/2617启发式规则在温度T达到平衡态的概率为𝑒−𝛥𝐸𝑘𝑇•T为当前温度•k为Boltzmann常数•E为粒子能量•DE为能量的变化收敛于当前解x的概率为𝑒−𝛥𝑓𝑡•x为当前解•t为控制参数，是关于搜索进程的递减函数•f为关于x的目标函数值•Df为目标函数值的变化𝑡(𝑛)=𝑡0lg(1+𝑛)𝑡(𝑛)=𝑡01+𝑛/82模拟退火算法18算法流程及要素自变量空间中解x的更新机制•目标函数值改进，绝对接受优化进展•目标函数值恶化，概率接受摆脱局部最小值陷阱控制参数t的更新机制•逐渐收敛，但具体方式多样•劣解接受概率与t正相关振荡范围逐渐变小，趋于稳定邻域定义及其更新机制思考：如何在算法/程序中实现？/8219算例1.4结果初值x0=1.745，步长f~xx~nf~n结果：x=1.6516，f=3.6494，n=16结论：与固定步长相比，在收敛速度和计算精度之间求平衡。[0.01,0.0001]思考：这种随机步长选择策略是否有问题？是否还有其他更好的步长选择策略，使收敛速度与计算精度的平衡性更好？/82模拟退火算法20算法评价优点•具有渐进收敛性，概率性地收敛于全局最优解缺点•参数（初始值、控制参数的更新机制等）敏感•振荡范围单向收缩•收敛速度与求全局最优解的要求相矛盾全局搜索算子与局部搜索算子不独立/82模拟退火算法21算法改进根据具体问题的特点，合理设计更具启发性的算法机制，例如当前解在解空间中的振荡范围不仅与搜索进程有关，还应该与解的更新效率与收益率有关增加重升温过程，动态调整当前解在解空间中的振荡范围，从而避免算法在局部极小解处停滞不前或在计算后期收敛速度太慢增加记忆功能，避免当前最优解衰退参考群智能的思想，针对每一个当前状态x，采用多次搜索策略，以概率方式进行当前最优解的更新，而非传统的单次比较/82模拟退火算法22算例1二元函数求最小值，精确到4位小数定义域[-2,2]初始温度：100温度衰减系数：0.95同一温度下计算次数：50邻域范围系数：0.2终止条件：温度降低到1以下算例x.1:初值x10=0.5,x20=0.5算例x.2:初值x10=-0.5,x20=0.5/82模拟退火算法23算例1.1实验结果x1*=0.9837,x2*=0.9684,F*=3.1438e-4,n*=10/82模拟退火算法2020/5/2624算例1.1重复实验结果计算次数x1*x2*F*n*10.98370.96843.1438e-41021.01701.03688.9150e-4531.04591.09280.0022840.96800.93240.00321250.98470.97860.008212/82模拟退火算法25算例1.2实验结果x1*=1.0288,x2*=1.0577,F*=8.7113e-4,n*=20/82模拟退火算法2020/5/2626算例1.2重复实验结果计算次数x1*x2*F*n*11.02881.05778.7113e-42020.99130.98201.1681e-41831.00501.00660.00121140.98100.96183.8874e-41451.02211.04505.0343e-414/82模拟退火算法2020/5/2627算例1结果分析由于是单值迭代，且渐进收敛，因此存在早熟收敛的问题，表现为以上计算均没有找到全局最优解初值对迭代结果无明显影响/82模拟退火算法28算例2二元函数求最小值，精确到4位小数定义域[-10,10]初始温度：100温度衰减系数：0.95同一温度下计算次数：50邻域范围系数：0.2终止条件：温度降低到1以下算例x.1:初值x10=0.5,x20=0.5算例x.2:初值x10=-0.5,x20=0.5/82模拟退火算法29算例2.1实验结果x1*=1.1089,x2*=1.2319,F*=0.0124,n*=6/82模拟退火算法2020/5/2630算例2.1重复实验结果计算次数x1*x2*F*n*11.10891.23190.0124620.95350.92210.0186930.86350.74870.0196541.09761.19850.0135850.92190.83730.02218/82模拟退火算法31算例2.2实验结果x1*=0.9209,x2*=0.8505,F*=0.0068,n*=6/82模拟退火算法2020/5/2632算例2.2重复实验结果计算次数x1*x2*F*n*10.92090.85050.0068620.90390.82320.0130831.01951.03240.0052741.11921.27180.0509751.00481.01440.002411/82模拟退火算法2020/5/2633算例2结果分析与算例1相比，初值改变后，迭代次数没有