模拟退火算法学习及试验分析.ppt

1、模拟退火算法学习及试验分析,清华大学计算机系 李军 2007-4,大纲,1. 介绍 2. Six-hump camel back function 试验 3. Schwefels function 试验对比 4. 试验总结 5. 结论与未来工作 6. 参考,1.1 优化问题介绍,描述: Find the values of a vector that minimize a scalar valued loss function L(). : the domain of allowable values for a vector 注: loss function 也被称为: performanc

2、e measure, cost function, objective function,fitness function, or criterion etc.,1.2 模拟退火算法介绍,用于解决优化问题的一种启发式算法,理论上是一个全局最优算法. 以一定概率跳出局部极值区域从而增大了找到全局极值的概率. 伪码描述: Simulated-Annealing() Create initial solution S repeat for i=1 to iteration-length do Generate a random transition from S to Si If ( C(S) ra

3、ndom0,1) ) then S=Si Reduce Temperature t until ( no change in C(S) ) C(S): Cost or Loss function of Solution S.,2. Six-hump camel back function 试验,The 2-D Six-hump camel back function is a global optimization test function. global minimum: f(x1,x2)=-1.0316; (x1,x2)=(-0.0898,0.7126), (0.0898,-0.7126

4、). 注: 在简单问题上成立的结论才有可能推广到更复杂的问题上.,2.1 函数值分布图,2.2 函数值分布底部区域局部,2 .3 与旅行商问题对比,2.4 主要试验参数设置,CoolSched: (0.8*T) %温度下降速率0.8 Generator: 生成邻域: 从 x,y中随机地选择一个再加上一个随机数R , R = randn/100; (rand符合标准正态分布N(0,1)的伪随机数, 意味着 随机变量落入-1,1内的概率是68.26%, 落入-2,2内的概率是 95.44% 落入-3,3内的概率是 99.72%, 除以100以后也就是大概范围在e-3量级的小数,也就是大约以95%的

5、概率处于-0.02,0.02) InitTemp: 1 %起始温度 MaxTries: 300 %同一温度下的最大迭代次数 StopTemp: 1e-8 %终止温度 ,2.5 初始解的位置对最终解的影响 (R=randn/100),x1,x2分别在区间-3,3, -2,2 步长0.5进行grid 式的初始值设置,然后用模拟退火求最小值的结果( 每一点对应运行一次模拟退火算法之后得到的解),Six-hump camel back function 极值分布的等高线图,可以看出, 在当前参数设置情况下,初始解的位置与局部极值的区域基本是一一对应的.也就是从初始解的位置出发,通过邻域搜索,往往落入最

6、近的局部极值区域.,2.6 R=randn/100的3维效果图,2.7 R=randn/10 与 rand/1 的3维效果图,2.8 R=randn*10 与 rand*40 的3维效果图,2.9 R=randn/100,randn/10,randn/1 的数据比较,可见,随着邻域的范围的增大, 跳出局部极小区域,最终进入全局极小区域的概率越来越大, 但是代价是总的迭代次数增加. 但是随着邻域范围的增大,会出现所谓的在极值附近来回”振荡”而无法落入极值点的现象. 可以推测,随着邻域范围的进一步增大及其随机特性,模拟退火算法将退化到随机寻找极值并进行记录极值的算法. 注: 当 randn*10,

7、 rand*40的时候超出我们限定的搜索范围-3,3,-2,2的概率增大很多,与前3个试验在某种程度上不具备可比性, 尽管如此,仍然具有启发性的意义.,2.10 更改降温速率后的运行结果(改为0.95),可见,随着邻域的范围的增大, 效果与前一个试验类似,区别在于 由于速率放缓, 经历了更多的迭代次数才达到最终解. 而且从中间的图可以看出，进入全局极值的点的初始位置分布较散,这是因为随着迭代次数的增多,以及邻域结构的随机向外伸展性质,由初始位置导致陷入临近局部极值的可能性降低,进入全局极值区域的可能性增大.,2.11 其他参数尝试,起始温度(提高到1000) 每个温度时的最大迭代次数(提高到3

8、000) 限于时间,更多参数和变化形式没有进行尝试. 得到的试验结论与前面基本相同,只是在初始解的临近位置周围略有微小的变化. 所以, 在一个合适的参数设置情况下,对寻找最优解起主要作用的重要因素有2个: 初始解的起始位置 邻域解的构造结构,2.12 与Native Brute Force Search比较,x1,x2以 s的步长在-3,3,-2,2的区间内进行 Brute Force Search, 判断搜索过程中的最小值并记录下来. 在解的搜索空间范围较小时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大.(

9、本试验中达到同样的精度是模拟退火的21倍.),降温速率0.8时模拟退火试验结果 暴力搜索的试验结果,3. 2-d Schwefels function 试验对比,Function defination:,3.1 初始解位置(step=40)与最终解值分布图,观察到了在 Six hump camle function 中同样的试验效果. 区别在于由于解空间的较多个极值区域的存在,迭代次数变化不像只有6个极值区域时为达到全局极值而明显地增加了总的迭代次数. 注1: 由于定义域范围增大,解空间增大,所以将邻域范围设大,从/1到*100. 注2: 由于邻域范围放大之后,处于自定义域边界的初始解生成的第

10、一次邻域解以95%的概率落在-700,700范围之内, 也就得到500,500之外函数极值,所以第3个图中的最小值明显比第1,2个图中的函数值要小,这说明在原定义域外存在更小的极值点 注3: 因为画图的原因,3个图的纵轴的坐标是不一致的, 数值依次降低.也就是跳出了原来的局部极小区域.,Randn/1, T=0.8T Randn*40 , T=0.8T Randn*100, T=0.8T,3.2 与Native Brute Force Search比较,x1,x2以 s的步长在-500,500,-500,500的区间内进行 Brute Force Search, 判断搜索过程中的最小值并记录下

11、来. 同上一个试验结论相同, 在以非常粗的粒度进行解的搜索时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大.( 本试验中达到接近的精度所需迭代次数是模拟退火的573倍.), 进而计算时间也大大增加.,降温速率0.8时模拟退火试验平均结果 暴力搜索的试验结果,3.3 3-d Schwefels function,x1,x2,x3以 80的步长在-500,500,-500,500,-500,500的区间内进行模拟退火求极小值, randn*40, 降温速率0.8. 由图中可以看出,较大的解多集中在中间的球形区域,外围

12、的值则要小一些, 这是由于变量以0为中心的区域是相对于外围空间的局部极小值区域,所以从中间区域出发通过模拟退火找到的解也相对于外围要大一些. 得到的结论仍同前面的试验结果相同. 注: 这个图同前几个图不同,Z轴代表变量x3, 颜色的变化代表找到的解的值的大小.,4. 试验总结,在2个toy problem 上得到的结论: 在其他参数合适的情况下,初始解的位置与邻域结构是2个重要因素. 初始解的位置与邻域结构的设计之间对于找到最优解的问题而言存在依赖关系. 随着邻域的范围的增大, 跳出局部极小区域,最终进入全局极小区域的概率越来越大, 同时也可能会产生振荡,无法落入极值区域. 模拟退火本质上也是

13、一种 暴力搜索,只不过是利用随机的性质和局部极值区域连续(也取决于求解问题中邻域的结构)的特性避免了大量计算.进而在较短时间内从某种概率上逼近局部最优值和全局最优值.,4.2 试验总结,问题本身解空间的性质也会影响求解.,如果全局最优解不在连续的空间上,(isolated point)那么将非常难以找到.,5.1 结论与未来工作1,本试验结论能否推广到更高维空间的问题上,对于不同性质的问题是否有同样的结论还有待更多的试验及数据分析. 例如更改邻域结构,使用tsp问题来分析,使用更高维的实际问题等. 现实问题是复杂的,不同问题的解空间的性质也是仍需探索的. 对问题本身建模,以及构造合适的邻域结构

14、,是解决问题的关键因素.再加上某种程度的初始解的grid式的粗遍历并应用模拟退火或其他类似算法, 或许可以解决很多问题.,5.2 结论与未来工作2,对工程实践的启发性意义 先进行粗粒度的搜索, 找到一个较优的解,然后在这个解的周围,利用设计合适的邻域结构,进而找到比这个解更优的解. 理论中通过迭代无穷次达到平稳分布,其实也就是是相当于遍历了所有的解空间. 某种程度的”brute force”(less bugs,no human miss)是解决当前组合优化问题的一种有效途径. E.g., 1997年深蓝(或许是当时最快的计算机)打败世界国际象棋冠军是暴力搜索的结果. -许丰雄,6. 参考,1

15、. matlab code url: 2. Minimizes a function url: 3. Steven Skiena The Algorithm Design Manual 4. James C. Spall Introduction to Stochastic Search and Optimization 5. 刑文训 谢金星 现代优化计算方法,附录1. TSP的邻域的一种构造方法示例,The Inversion, translation, and switching operations are selected randomly with probabilities 0.7

16、5, 0.125, and 0.125 Tour: 1 2 3 4 5 6 7 8 1 5 4 3 2 6 7 8 (Inversion) 1 6 2 3 4 5 7 8 (Translation) 1 5 3 4 2 6 7 8 (Switching) 2-opt Select the best from neighborhood. Neighborhood (1 2 3 4)=(1 2 3 4),(1 3 2 4),(1 4 3 2),(1 2 4 3) 返回,附录2. 遗传算法特性,由于遗传算法的交叉变异等特性,在合适的参数设置情况下,所以不存在像模拟退火那样严重依赖于初始点的位置和邻域结构.,From Slides for Introduction to Stochastic Search and Optimization (ISSO) by J. C. Spall,附录3. 优化算法笔记(部分转载),局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：为了找出地球上最高的山，一群有志气的兔子们开始想办法。1兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保