




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索,它不能保
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030中国野营塑胶用品行业产业运行态势及投资规划深度研究报告
- 2025至2030中国自缷车行业市场现状分析及竞争格局与投资发展报告
- 2025至2030中国自卸拖车行业产业运行态势及投资规划深度研究报告
- 2025至2030中国自动化油箱清洁系统行业发展趋势分析与未来投资战略咨询研究报告
- 2025至2030中国脂联素检测行业发展趋势分析与未来投资战略咨询研究报告
- 2025至2030中国网络游戏行业市场深度调研及竞争格局与投资报告
- 2025高三上学期班主任学生档案管理计划
- 2025至2030中国织物基层压板(SRBF)行业产业运行态势及投资规划深度研究报告
- 2025至2030中国组合健身器械行业市场深度研究及发展前景投资可行性分析报告
- 小学入队仪式流程模板他
- 2025年金融科技企业估值方法与投资策略在金融科技企业并购中的应用案例报告
- 农文旅项目可行性研究报告
- 《无人机介绍》课件
- 2025-2030中国硼酸行业市场发展现状及竞争格局与投资研究报告
- 学校中层干部选拔聘用实施方案中层干部选聘实施方案2
- 生物必修1教师用书
- 园艺植物育种学知到课后答案智慧树章节测试答案2025年春浙江大学
- 《电力机车制动系统检修与维护》课件 项目二任务四检修中继阀
- GB/T 15683-2025粮油检验大米直链淀粉含量的测定
- 2025吉林省安全员C证考试(专职安全员)题库及答案
- 电钻清洗消毒流程
评论
0/150
提交评论