1、模拟退火算法学习及试验分析清华大学计算机系 李军2007-4大纲n 1. 介绍n 2. Six-hump camel back function 试验n 3. Schwefels function 试验对比n 4. 试验总结n 5. 结论与未来工作n 6. 参考1.1 优化问题介绍n 描述 :Find the values of a vector that minimize a scalar valued loss function L().: the domain of allowable values for a vector 注 : loss function 也被称 为 : perfo
2、rmance measure, cost function, objective function,fitness function, or criterion etc.1.2 模拟退火算法介绍n 用于解决优化问题的一种启发式算法 ,理论上是一个全局最优算法 .n 以一定概率跳出局部极值区域从而增大了找到全局极值的概率 .n 伪码描述 :Simulated-Annealing()Create initial solution Srepeatfor i=1 to iteration-length doGenerate a random transition from S to SiIf ( C(
3、S) random0,1) ) thenS=SiReduce Temperature tuntil ( no change in C(S) )C(S): Cost or Loss function of Solution S.2. Six-hump camel back function 试验n The 2-D Six-hump camel back function is a global optimization test function. n global minimum:f(x1,x2)=-1.0316; (x1,x2)=(-0.0898,0.7126), (0.0898,-0.71
4、26).n 注 : 在简单问题上成立的结论才有可能推广到更复杂的问题上 .2.1 函数值分布图2.2 函数值分布底部区域局部 2 .3 与旅行商问题对比优 化 问题术语 Six Camel function problem TSP(Traveling salesman problem)损 失 (代价 )函数 值 f(x1,x2) 路径 长 度初始解 (x1,x2 ) 坐 标 初始城市排列邻 域 结 构 任 选 一 维 加上一个符合正 态分布的随机数e.g., 2-opt(2个元素交 换 ) 或者 inversion, translation, and switching (部分反 转 ,移动
5、与交 换 的混合 )等全局最 优 解 f(x1,x2)最小 路径最短局部最 优 解 f(x1,x2)较 小 路径相 对较 短邻 域大小 增大或减少随机数的大小 相 对 上一个解 变动较 大 . (e.g., 增大部分反 转 的比例 ,减少移 动 和交 换 的比例 )2.4 主要试验参数设置n CoolSched: (0.8*T) %温度下降速率 0.8n Generator: 生成邻域 : 从 x,y中随机地选择一个再加上一个随机数 R , R = randn/100;(rand符合标准正态分布 N(0,1)的伪随机数 , 意味着 随机变量落入 -1,1内的概率是68.26%, 落入 -2,2
6、内的概率是 95.44% 落入 -3,3内的概率是 99.72%, 除以 100以后也就是大概范围在 e-3量级的小数 ,也就是大约以 95%的概率处于 -0.02,0.02)n InitTemp: 1 %起始温度n MaxTries: 300 %同一温度下的最大迭代次数n StopTemp: 1e-8 %终止温度n 2.5 初始解的位置对最终解的影响 (R=randn/100)x1,x2分别在区间 -3,3, -2,2 步长 0.5进行 grid 式的初始值设置 ,然后用模拟退火求最小值的结果 ( 每一点对应运行一次模拟退火算法之后得到的解 )Six-hump camel back function 极值分布的等高线图n 可以看出 , 在当前参数设置情况下 ,初始解的位置与局部极值的区域基本是一一对应的 .也就是从初始解的位置出发 ,通过邻域搜索 ,往往落入最近的局部极值区域 .
