启发式算法

启发式算法一、组合优化问题二、启发式算法三、模拟退火算法四、遗传算法•解决离散的优化问题运筹学分支。通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等诸多领域。一.组合优化问题1.1组合优化问题的基本概念•一般模型目标函数约束函数min()fx..()0,.stgxxDD是有限个点构成的集合•0-1背包问题（KnapsackProblem）•加工调度问题（SchedulingProblem）•旅行商问题（TravellingSalesmanProblem--TSP）•装箱问题（BinPackingProblem）•图着色问题（GraphColoringProblem）经典的组合优化问题：•0-1背包问题设有一个容积为b的背包，n件体积分别为，价值分别为的物品，如何以最大的价值装包？11max..,0i1niiiniiiizcxstaxbx若第种物品没选上,，否则.iaic•旅行商问题给定n个城市和每两个城市间的距离。一个货郎自某一城市出发巡回售货，问这个货郎应该如何选择路线，使每个城市经过一次且仅一次，并且路径长度最短。基于图论的0-1规划模型1.2计算复杂性的概念例：TSP枚举法的基本计算量是n！,随着n的增加，计算量急剧增加。算法复杂性分析NP问题•这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难；•其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。组合优化问题的特点：兼顾解的质量以及运行时间的较好算法：（1）设计平均形态良好的概率算法（2）设计求近似最优解的近似算法1.3邻域结构与局部最优如何求解全局最优解？•基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解决优化问题每个实例的一个可行解，该可行解与最优解的偏差不一定事先可以估计。•启发式算法是一种技术，在可接受的计算费用内去寻找最好的解，但不一定能保证解的可行性与最优性，多数情况下无法描述该解与最优解的近似程度。•特点（与传统优化方法不同）：不考虑算法所得解与最优解的偏离程度。二.启发式算法例：TSP的近似算法：最近邻法、最近插入法、最小支撑树法、局部搜索法等算法（最近邻法）：(1)任选一个城市c1为出发点；(2)根据与出发城市最近的原则，在c1以外的n-1个城市中选取第二个经过城市；(3)再以c2为出发城市，在尚未经过的按最近邻原则选取c3，如此重复，直至所有城市都被经过，最后到达的城市是cn；（4）从cn返回c1，构成一条路径。例：0-1背包问题：greedyalgorithm启发式算法的优点与缺点•数学模型本身是实际问题的简化•有些难的组合优化问题还没有最优算法或过于复杂•一些启发式算法可用在最优算法中•简单易行，比较直观•速度快•多数情况下，程序简单，易于修改•不能保证求得最优解•表现不稳定•算法的好坏依赖于实际问题、经验和设计者的技术•一步算法•改进算法•数学规划算法•解空间松弛算法•现代优化算法启发式算法的分类现代优化算法：上世纪80年代初兴起•禁忌搜索（tabusearch）•模拟退火（simulatedannealing）•遗传算法（geneticalgorithms）•神经网络（neuralnetworks）•蚁群算法（antalgotithms）•其他方法局部搜索算法：Step2：当或满足其他停止运算准则时,输出计算结果，停止运算；否则，从P中选一集合S，得到S中的最优解；Pnowx()(),nowbestfxfx若则:,();bestnowbestxxPNx;PPS否则重复step2.Step1：选定一个初始可行解；记录当前最优解，令0:bestxx();bestPNx0x改善局部搜索算法性能的途径：(1)对大量初始解执行算法，再从中选优(2)引入更复杂的邻域结构，使算法能对解空间的更大范围进行搜索(3)改变局部搜索算法只接受优化解迭代的准则，在一定限度接受恶化解。禁忌搜索：是一种人工智能算法，是局部搜索算法的扩展。其重要思想是标记已得到的局部最优解，并在进一步的迭代中避开这些局部最优解。三.模拟退火算法3.1起源：固体退火过程类比：组合优化问题解最优解费用函数金属物体状态能量最低的状态能量(simulatedannealingalgorithm)1983，Kirkpatrick成功应用于组合优化问题3.2模拟退火算法流程：1）随机产生一个初始解，令，并计算目标函数值2）设置初始温度t=T(0)，终止温度降温系数3）whiletTmini)forj=1:kii)对当前最优解按照某一邻域函数,产生一新的解计算新的目标函数值并计算目标函数值的增量;()().newbestEExEx0bestxx0x0();Exmin,T,bestx.newx(),newExiii)如果则iv）如果则如果否则v）endfor0,E0,Eexp(/)[0,1],,bestnewEtrandomxx4）降温5）endwhile6）输出当前最优点，计算结束。*tt;bestnewxx.bestbestxx3.3模拟退火算法要素1）状态空间与状态生成函数（邻域函数）•搜索空间（状态空间）：由经过编码的可行解的集合所组成•状态生成函数（邻域函数）应尽可能保证产生的候选解遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布•候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得•概率分布可以是均匀分布、正态分布、指数分布等等2）状态转移概率（接受概率）p•状态转移概率是指从一个状态xold（一个可行解）向另一个状态xnew（另一个可行解）的转移概率•通俗的理解是接受一个新解为当前解的概率•它与当前的温度参数T有关，随温度下降而减小•一般采用Metropolis准则1,()().()()exp,()()newoldnewoldnewoldifExExpExExifExExT3）冷却进度T(t)冷却进度表是指从某一高温状态T0向低温状态冷却时的降温管理表。0()lg(1)TTtt假设时刻t的温度用T(t)表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：0()1TTtt这两种方式都能使模拟退火算法收敛。4）初始温度T0实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折中考虑优化质量和优化效果。5）内循环终止准则或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。6）外循环终止准则即算法终止准则，常用的包括：•设置终止温度的阀值•设置外循环迭代次数•算法搜索到的最优值连续若干步保持不变•检查系统熵是否稳定3.4模拟退火算法实验性能分析：1）模拟退火法与局部搜索算法的差异2）优点：高效、健壮、通用、灵活3）不足：返回一个高质量近似解的时间花费较多，当问题规模不可避免增大时，难于承受的运行时间将使算法丧失可行性。如何改进？3.5模拟退火算法的matlab实现利用模拟退火算法求函数极小：无约束或有界约束x=simulannealbnd(fun,x0)x=simulannealbnd(fun,x0,lb,ub)x=simulannealbnd(fun,x0,lb,ub,options)[x,fval]=simulannealbnd(...)[x,fval,exitflag]=simulannealbnd(...)[x,fval,exitflag,output]=simulannealbnd(...)dejong5fcnx0=[00];[x,fval]=simulannealbnd(@dejong5fcn,x0)Optimizationterminated:changeinbestfunctionvaluelessthanoptions.TolFun.x=0.0216-31.9955fval=2.9821Optimizationterminated:changeinbestfunctionvaluelessthanoptions.TolFun.x=-15.9669-31.9749fval=1.9920exitflag=1output=iterations:1608funccount:1621message:[1x80char]randstate:[625x1uint32]randnstate:[2x1double]problemtype:'unconstrained'temperature:[2x1double]totaltime:0.8268[x,fval,exitflag,output]=simulannealbnd(@dejong5fcn,[0,0])x0=[00];lb=[-64-64];ub=[6464];[x,fval]=simulannealbnd(@dejong5fcn,x0,lb,ub)Optimizationterminated:changeinbestfunctionvaluelessthanoptions.TolFun.x=-32.0169-31.9879fval=0.9980fun=@(x)3*sin(x(1))+exp(x(2));x=simulannealbnd(fun,[1;1],[00])Optimizationterminated:changeinbestfunctionvaluelessthanoptions.TolFun.x=896.92340.0000options=saoptimset('PlotFcns',{@saplotbestf,@saplottemperature,@saplotf,@saplotstopping});simulannealbnd(@dejong5fcn,x0,lb,ub,options);options=saoptimset('InitialTemperature',[30050]);options=saoptimset(options,'TemperatureFcn',@temperaturefast);options=saoptimset(options,'ReannealInterval',50);options=saoptimset(options,'Display','iter','DisplayInterval',400);options=saoptimset(options,'TolFun',1e-5);相关函数：[x,fval]=threshacceptbnd(@objfun,x0)1）加载数据表129个城市的坐标城市序号12345678910X坐标1150.0630.040.0750.0750.01030.01650.01490.0790.0710.0Y坐标1760.01660.02090.01100.02030.02070.0650.01630.02260.01310.0城市序号11121314151617181920X坐标840.01170.0970.0510.0750.01280.0230.0460.01040.0590.0Y坐标550.02300.01340.0700.0900.01200.0590.0860.0950.01390.0城市序号212223242526272829X坐标830.0490.01840.01260.01280.0490.01460.01260.0360.0Y坐标1770.0500.01240.01500.0790.02130.01420.01910.01980.03.6模拟退火算法对TSP的应用inputcities=[1150.0630.040.0750.0750.01030.01650.01490.0...790.0710.0840.01170.0970.