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

Presentation on theme: "模拟退火算法学习及试验分析."— Presentation transcript:

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

2 大纲 1. 介绍 2. Six-hump camel back function 试验
3. Schwefel‘s function 试验对比 4. 试验总结 5. 结论与未来工作 6. 参考 为了理解和运用, 人们通常会采用易懂的方式来理解和掌握知识, 所以我的重点是通过简单的例子和比较多的图和文字来描述问题, 而不是堆上一堆数学公式.

3 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 也被称为: performance measure, cost function, objective function,fitness function, or criterion etc. 基本上有2类一般性的问题, 另一类是求解等式 g(x)=0 for some vector-valued function g(x) 这2者可以相互转换. 也有人叫 energy, 能量.

4 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) <= C(Si) ) then S=Si else if( exp(C(S)-C(Si))/kt > random[0,1) ) then Reduce Temperature t until ( no change in C(S) ) C(S): Cost or Loss function of Solution S. 理论上全局最优指每一温度迭代无穷多次,达到平稳分布条件,就可以找到全局最优解.

5 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)= ; (x1,x2)=( ,0.7126), (0.0898, ). 注: 在简单问题上成立的结论才有可能推广到更复杂的问题上. 需要说明的是, 这里的 x1, x2的范围只是一个人工限定的范围. 如果 x1,x2都取更大值的区间,如[-5,5] 也可以, 此时解最大可以到 6420多一些

6 2.1 函数值分布图 随着x1,x2范围的增大,函数值的区间也随之增大.[-5,5]时,函数最大值达到6420. 基本形状保持不变.

7 2.2 函数值分布底部区域局部

8 2 .3 与旅行商问题对比 f(x1,x2) (x1,x2 ) 坐标 f(x1,x2)最小 f(x1,x2)较小 优化问题术语
Six Camel function problem TSP(Traveling salesman problem) 损失(代价)函数值 f(x1,x2) 路径长度 初始解 (x1,x2 ) 坐标 初始城市排列 邻域结构 任选一维加上一个符合正态分布的随机数 e.g., 2-opt(2个元素交换) 或者 inversion, translation, and switching (部分反转,移动与交换的混合)等 全局最优解 f(x1,x2)最小 路径最短 局部最优解 f(x1,x2)较小 路径相对较短 邻域大小 增大或减少随机数的大小 相对上一个解变动较大. (e.g., 增大部分反转的比例,减少移动和交换的比例)

9 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%的概率处于[-0.02,0.02]) ‘InitTemp‘: %起始温度 ‘MaxTries‘: 300 %同一温度下的最大迭代次数 ‘StopTemp‘: 1e-8 %终止温度 … 随机数R 符合正态分布也就是 符合N(0,1)分布的随机数, 这意味着 随机变量落入[-1,1]内的概率是68.26%, 落入[-2,2]内的概率是 95.44% 落入[-3,3]内的概率是 99.72% 除以100之后,则处于 e-3量级的小数范围内. 68% [-0.01,0.01] 95% [-0.02,0.02] 99% [-0.03,0.03]

10 2.5 初始解的位置对最终解的影响 (R=randn/100)
可以看到,初始解的位置与最终解有极大关系. for x=-3:0.5:3 for y=-2:0.5:2 init=[x y]; [mini fval,ttotal]=anneal2(loss,init); end; Six-hump camel back function 极值分布的等高线图 x1,x2分别在区间[-3,3], [-2,2] 步长0.5进行grid 式的初始值设置,然后用模拟退火求最小值的结果( 每一点对应运行一次模拟退火算法之后得到的解) 可以看出, 在当前参数设置情况下,初始解的位置与局部极值的区域基本是一一对应的.也就是从初始解的位置出发,通过邻域搜索,往往落入最近的局部极值区域.

11 2.6 R=randn/100的3维效果图 处于局部极值区域的初始点往往陷入局部极值,处于全局极值区域的初始点则进入全局最小点区域.

12 2.7 R=randn/10 与 rand/1 的3维效果图 可以看出,与 rand/100相比,随着邻域的范围的扩大,进入全局极小值区域的概率也就越大.

13 2.8 R=randn*10 与 rand*40 的3维效果图

14 2.9 R=randn/100,randn/10,randn/1 的数据比较
最终解平均值 最终解标准差sd 总计迭代次数平均值 总迭代次数标准差sd Randn/100 0.0048 1.2351 6731.6 627.6 Randn/10 0.5410 10705 1082.7 Randn/1 0.0001 11412 1515.3 Randn*10 0.0122 1707.3 Randn*40 0.1001 1422.2 可见,随着邻域的范围的增大, 跳出局部极小区域,最终进入全局极小区域的概率越来越大, 但是代价是总的迭代次数增加. 但是随着邻域范围的增大,会出现所谓的在极值附近来回”振荡”而无法落入极值点的现象. 可以推测,随着邻域范围的进一步增大及其随机特性,模拟退火算法将退化到随机寻找极值并进行记录极值的算法. 注: 当 randn*10, rand*40的时候超出我们限定的搜索范围[-3,3],[-2,2]的概率增大很多,与前3个试验在某种程度上不具备可比性, 尽管如此,仍然具有启发性的意义.

15 2.10 更改降温速率后的运行结果(改为0.95) Mean_fvale Std_fvalue total Std_total Randn/100 0.0922 1.2630 24843 2378.2 Randn/10 0.3579 39835 2431.3 Randn/1 40637 3986.5 而 0.8的温度下降速率和1e-8的终止温度 意味着, 不同的温度最多运行80次就达到终止温度. >> 1*(0.8)^80 ans = e-008 >> 1*(0.8)^70 ans = e-007 >> 1*(0.8)^60 ans = e-006 >> 1*(0.95)^350 ans = e-008 >> 1*(0.95)^310 ans = e-007 >> 1*(0.95)^260 ans = e-006 可见,随着邻域的范围的增大, 效果与前一个试验类似,区别在于 由于速率放缓, 经历了更多的迭代次数才达到最终解. 而且从中间的图可以看出，进入全局极值的点的初始位置分布较散,这是因为随着迭代次数的增多,以及邻域结构的随机向外伸展性质,由初始位置导致陷入临近局部极值的可能性降低,进入全局极值区域的可能性增大.

16 2.11 其他参数尝试 起始温度(提高到1000) 每个温度时的最大迭代次数(提高到3000) 限于时间,更多参数和变化形式没有进行尝试.
得到的试验结论与前面基本相同,只是在初始解的临近位置周围略有微小的变化. 所以, 在一个合适的参数设置情况下,对寻找最优解起主要作用的重要因素有2个: 初始解的起始位置 邻域解的构造结构 合适 如何定义,可能需要进行多次尝试.

17 2.12 与Native Brute Force Search比较
Fvalue Total_iteration S=1 35 S=0.5 -0.75 117 S=0.01 241001 Mean_fvalue Mean_total_iteration Randn/100 0.0048 6731.6 Randn/10 10705 Rand/1 11412 降温速率0.8时模拟退火试验结果 暴力搜索的试验结果 x1,x2以 s的步长在[-3,3],[-2,2]的区间内进行 Brute Force Search, 判断搜索过程中的最小值并记录下来. 在解的搜索空间范围较小时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大.( 本试验中达到同样的精度是模拟退火的21倍.) 假设x1,x2以 0.02的步长在[-3,3],[-2,2]的区间内进行 Brute Force Search, 那么程序需要运行 (2*3/0.02+1)*(2*2/0.02+1)=60501的次数才能找到全局最优解的邻近解 [3,3] [-2,2] step 0.02 i = mini = [3,3] [-2,2] step 0.01 i = mini = [3,3] [-2,2] step =0.5 i = 117 mini = [3,3] [-2,2] step =1 i = 35 mini = 0

18 3. 2-d Schwefel‘s function 试验对比
Function defination: 特点是有非常密集的极小值区域.

19 3.1 初始解位置(step=40)与最终解值分布图
Randn/1, T=0.8T Randn*40 , T=0.8T Randn*100, T=0.8T mean_fvalue fvalue_std mean_total_iter total_std Randn/1 228.4 11444 881.4 Randn*40 160.3 12169 1569.5 Randn*100 287.5 11789 1760.5 for x=-500:40:500 for y=-500:40:500 init=[x y]; [mini fval,ttotal]=anneal2(loss,init); end 另外注意, 这3个图的坐标轴的颜色轴大小不一致! 观察到了在 Six hump camle function 中同样的试验效果. 区别在于由于解空间的较多个极值区域的存在,迭代次数变化不像只有6个极值区域时为达到全局极值而明显地增加了总的迭代次数. 注1: 由于定义域范围增大,解空间增大,所以将邻域范围设大,从/1到*100. 注2: 由于邻域范围放大之后,处于自定义域边界的初始解生成的第一次邻域解以95%的概率落在[-700,700]范围之内, 也就得到[500,500]之外函数极值,所以第3个图中的最小值明显比第1,2个图中的函数值要小,这说明在原定义域外存在更小的极值点 注3: 因为画图的原因,3个图的纵轴的坐标是不一致的, 数值依次降低.也就是跳出了原来的局部极小区域.

20 3.2 与Native Brute Force Search比较
Mean_fvalue Mean_total_iteration Rand/1 11,444 Rand*40 12,169 Rand*100 11,789 Fvalue Total_iteration S=100 121 S=40 676 S=1 [-500,500] S=1 [-700,700] S=1 [-800,800] S=1 [-1300,1300] 1430.1 1,002,001 1,962,801 2,563,201 6,765,201 降温速率0.8时模拟退火试验平均结果 暴力搜索的试验结果 x1,x2以 s的步长在[-500,500],[-500,500]的区间内进行 Brute Force Search, 判断搜索过程中的最小值并记录下来. 同上一个试验结论相同, 在以非常粗的粒度进行解的搜索时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大.( 本试验中达到接近的精度所需迭代次数是模拟退火的573倍.), 进而计算时间也大大增加. 在我的笔记本上迅驰1.6G, matlab7, 512M 内存,同时打开ppt, word, SA vs BF 小于1s s

21 3.3 3-d Schwefel‘s function
x1,x2,x3以 80的步长在[-500,500],[-500,500],[-500,500]的区间内进行模拟退火求极小值, randn*40, 降温速率0.8. 由图中可以看出,较大的解多集中在中间的球形区域,外围的值则要小一些, 这是由于变量以0为中心的区域是相对于外围空间的局部极小值区域,所以从中间区域出发通过模拟退火找到的解也相对于外围要大一些. 得到的结论仍同前面的试验结果相同. 注: 这个图同前几个图不同,Z轴代表变量x3, 颜色的变化代表找到的解的值的大小.

22 4. 试验总结 在2个toy problem 上得到的结论: 在其他参数合适的情况下,初始解的位置与邻域结构是2个重要因素.
初始解的位置与邻域结构的设计之间对于找到最优解的问题而言存在依赖关系. 随着邻域的范围的增大, 跳出局部极小区域,最终进入全局极小区域的概率越来越大, 同时也可能会产生振荡,无法落入极值区域. 模拟退火本质上也是一种 暴力搜索,只不过是利用随机的性质和局部极值区域连续(也取决于求解问题中邻域的结构)的特性避免了大量计算.进而在较短时间内从某种概率上逼近局部最优值和全局最优值. 局部极值区域是否连续,是一个问题,肯定有不连续的例子. 也许大部分问题的局部极值区域是连续的,与邻域结构是什么样具体的关系, 这个需要讨论.

23 4.2 试验总结 问题本身解空间的性质也会影响求解. 如果全局最优解不在连续的空间上,(isolated point)那么将非常难以找到.

24 5.1 结论与未来工作1 本试验结论能否推广到更高维空间的问题上,对于不同性质的问题是否有同样的结论还有待更多的试验及数据分析.
例如更改邻域结构,使用tsp问题来分析,使用更高维的实际问题等. 现实问题是复杂的,不同问题的解空间的性质也是仍需探索的. 对问题本身建模,以及构造合适的邻域结构,是解决问题的关键因素.再加上某种程度的初始解的grid式的粗遍历并应用模拟退火或其他类似算法, 或许可以解决很多问题. 对问题本身建模,以及构造合适的邻域结构,是解决问题的关键因素. 再加上某种程度的初始解的grid式的粗遍历并应用模拟退火或其他类似算法, 或许可以解决很多问题.

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

26 6. 参考 1. 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. 刑文训 谢金星 现代优化计算方法 Brute force program, less bugs, no human miss. Deep blue proved Bruteforce is sufficent. Go could be “Solvable” with the next 5 years. The reasons against brute force searching for Go are not that valid. --Fengxiong Xun

27 附录1. TSP的邻域的一种构造方法示例 The Inversion, translation, and switching operations are selected randomly with probabilities 0.75, 0.125, and 0.125 Tour: (Inversion) (Translation) (Switching) 2-opt Select the best from neighborhood. Neighborhood ( )={( ),( ),( ),( )} 返回

28 附录2. 遗传算法特性 由于遗传算法的交叉变异等特性,在合适的参数设置情况下,所以不存在像模拟退火那样严重依赖于初始点的位置和邻域结构.
From Slides for Introduction to Stochastic Search and Optimization (ISSO) by J. C. Spall

29 附录3. 优化算法笔记(部分转载) 局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻： 为了找出地球上最高的山，一群有志气的兔子们开始想办法。 1．兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。 2．兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。 3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。 4.兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。 From