3-模拟退火算法工具箱及应用.ppt

* 1/15 1.理论基础 1.1 模拟退火算法工具箱（simulated annealing toolbox， SAT） 在R2009a版本中，MATLAB自带的遗传算法与直接搜索工 具箱集成了模拟退火算法。 基本原理：模拟退火算法来源于固体退火原理，将固体加温至 充分高，再让其徐徐冷却，加温时，固体内部粒子随温升 变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在 每个温度都达到平衡态，最后在常温时达到基态，内能减 为最小。 * 2/15 S A 算 法 结 构 示 意 图 * 3/15 simulannealbnd simulanneal simulannealcommon.m saengine solverData.running = ture? sacheckexit.m sanewpoint.m saupdates.m gadsplot.m 得到最优解 N Y SAT的使用只需要调用主函数simulannealbnd即可，函数 simulannealbnd则调用函数simulanneal对模拟退火问题进行求解。函 数simulanneal依次调用函数simulannealcommon和函数saengine，并 最终得到最优解。在函数saengine中，SA进行迭代搜索，直到满足 一定的条件才退出。在迭代过程中，函数sanewpoint和函数saupdates 是关键函数。 * 4/15 1.2 模拟退火的一些基本概念 l 目标函数（objective function）：即待优化的函数。在调用函数 simulannealbnd运行模拟退火算法时，需要编写该目标函数的M 文件。SAT是对目标函数取最小值进行优化的，对于最大值的 优化问题，只需要将目标函数乘以-1即可化为最小值优化问题。 l 温度(temperature): 是一个重要的参数，他随着算法的迭代逐步 下降，以模拟固体退火过程中的降温过程。一方面，温度用于 限制SA产生的新解与当前解之间的距离，即SA的搜索范围；另 一方面，温度决定了SA以多大的概率接受目标函数值比当前解 的目标函数值差的新解。 * 5/15 l 退火进度表（annealing schedule）：是指温度随算法迭代的下降 速度。退火过程越缓慢，SA找到全局最优解的机会就越大。退火 进度表包括初始温度（initial temperature）及温度更新函数（ temperature update function）的参数。 l Meteopolis准则： 是指SA接受新解的概率，对于目标函数取最小值的问题，SA接受 新解的概率为： * 6/15 案例分析 求解Rastrigin函数的最小值。 * 7/15 如何绘制 ？ 程 序： x1= -5:0.01:5; x2= -5:0.01:5; x1,x2 = meshgrid(x1,x2); x3 = 20+x12+x22-10*(cos(2*pi*x1)+cos(2*pi*x2); surfc(x1,x2,x3) colormap hsv * 8/15 解题步骤： lStart Toolboxes Global optimization Optimization tool * 9/15 loptimtool (simulannealbnd) 命令行方式使用SAT： x, fval = simulannealbnd (fun, x0, lb, ub, options) options = saoptimset (Param1,value1, Param2,value2,); * 10/1