解读最优化算法之模拟退火

2018 06 21

模拟退火算法

模拟退火算法 ( simulated anneal , SA) 求解最优化问题常用的算法,今天应用 SA 解决一元多次函数最小值的例子解释 SA 算法。

1 算法思想

  1. 初始化:初始温度T,初始解状态S,是算法迭代的起点;
  2. 产生新解S′
  3. 计算增量ΔT = C(S′,S),其中C为评价函数: 若ΔT < 0,则接受 S′ 作为新的当前解, 否则以概率 exp(-ΔT/kT) 接受 S′ 作为新的当前解
  4. 如果满足终止条件则输出当前解作为最优解,结束程序,终止条件通常取为连续若干个新解都没有被接受时终止算法。

上述关键点:以一定概率exp(-ΔT/kT) 接受一个不好的解,这是SA区别于爬山算法的地方。

2 SA 算法应用

应用 模拟退火SA 算法求解以下函数的最小值:

y = np.sin(5np.pi(x-0.05)) + np.cos(np.pi*(x-0.04)), 0<x<1

先plot 下函数:

这是有意选取的一个多峰值函数,观察SA算法是否陷入局部极小;爬山算法是怎么陷入局部极小的,SA又是怎么跳出局部极小的。

3 SA 算法代码

代码详细解释 sa函数的参数 y 代表 一元多次函数,后面3个为算法的调节参数,break_cond是连续多少次没有搜索到好解时的跳出条件, k 控制选择概率,step是迭代时步的控制参数。T,T_max 是解空间的取值范围,i 是迭代次数,best是初始最优解,设为在 T处,break_i是控制跳出的次数,每当取到最优解则置为0. 评价函数选用min(s,s').

以下两行是展示搜索过程的代码,不是算法的代码。

save_list.append([T, y(T)])

print('step = %d, T = %f, y = %f' % (i, T, y(T)))

 1def sa(y, break_cond = 30,k=10,step=0.005):
 2    T, T_max = 1e-3, 1.0
 3    k = 10
 4    i = 0
 5    best = y(T)
 6    break_i = 0
 7    while T_max > T:
 8        T += step
 9        de = y(T) - y(T-step)
10        if de < 0:
11            best = min(best, y(T))
12            break_i = 0
13        else:
14            if np.exp(-de / (k*T)) > np.random.random
15
16(1):  # 以一定概率接受不好的解
17                best = min(best, y(T))
18                break_i = 0
19            break_i += 1
20            if break_i > break_cond:  # 如果连续找不到
21
22好解
23                break
24        i += 1
25        save_list.append([T, y(T)])
26        print('step = %d, T = %f, y = %f' % (i, T, y
27
28(T)))
29
30    return best

4 SA 搜索模拟

为了更清楚的展示SA搜索的过程,制作搜素动画。

 1import matplotlib.pyplot as plt
 2import numpy as np
 3import matplotlib.animation as animation
 4
 5def f(x):
 6    y = np.sin(5*np.pi*(x-0.05)) + np.cos(np.pi*(x-0.04))
 7    return y
 8
 9save_list = []
10
11
12def sa(y, break_cond = 30):
13    T, T_max = 1e-3, 1.0
14    k = 10
15    i = 0
16    best = y(T)
17    break_i = 0
18    while T_max > T:
19        T += 0.005
20        de = y(T) - y(T-0.01)
21        if de < 0:
22            best = min(best, y(T))
23            break_i = 0
24        else:
25            if np.exp(-de / (k*T)) > np.random.random(1):  # 以一定概率接受不好的解
26                best = min(best, y(T))
27                break_i = 0
28            break_i += 1
29            if break_i > break_cond:  # 如果连续找不到好解
30                break
31        i += 1
32        save_list.append([T, y(T)])
33        print('step = %d, T = %f, y = %f' % (i, T, y(T)))
34
35    return best
36
37# 模拟退火, 打印结果
38print (sa(f))
39
40fig = plt.figure()
41wind = fig.add_subplot(111)
42x = np.linspace(0, 1, 200)
43wind.plot(x, f(x))
44
45def update(data):
46    wind.scatter(data[0], data[1])
47    return
48
49ani = animation.FuncAnimation(fig, update, save_list, interval= 200)
50plt.show()

通过动画可以看出,应用SA算法,搜索时可以成功跳出局部极小点,并且成功找到最小值大约为 -1.6.

5 爬山算法搜索模拟

这主要得益于SA以一定概率接收不好的解,如果标注这部分,可以认为为爬山算法。再看下,爬山算法的搜索过程,陷入局部最小,搜索提前终止,所能找到的最小值为-0.5.

6 总结

因此,同等条件下,SA算法更有可能不会陷入局部最小值,进而找到全局最值。

原文发布于微信公众号 - Python与机器学习算法频道(alg-channel)

原文发表时间:2018-06-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

学会判断机器学习模型的性能——开发基线模型技能

这是初学者常问到的问题。作为一个初学者,你经常会去寻找这个问题的答案,比如你希望别人为你解答,x%的准确性或者x的误差分数是否有效。这篇文章将告诉你如何自己来回...

1233
来自专栏大数据文摘

机器学习的5种“兵法”;

2485
来自专栏机器之心

专栏 | 自动选模型+调参:谷歌AutoML背后的技术解析

57510
来自专栏量子位

业内最大规模多标签图像数据集开源 | GitHub资源

上个月,腾讯AI实验室宣布开源多标签图像数据集ML-Images,以及业内目前同类深度学习模型中精度最高的深度残差网络ResNet-101.

3231
来自专栏AI科技大本营的专栏

AI 技术讲座精选:ChainerMN 分布式深度学习的性能

2017深度学习峰会于今年1月在旧金山落下帷幕。会上,PFN 发布了其在多节点环境下使用 Chainer 的分布式深度学习所取得的进展。在今天的这篇文章中,我会...

38812
来自专栏鸿的学习笔记

深度神经网络的实践效果分析

由于深度神经网络(DNN)作为计算机视觉领域的突出技术的出现,ImageNet分类在推进最新技术方面发挥了重要作用。 虽然准确度在稳定增加,但获胜模型的资源利用...

791
来自专栏量子位

伯克利新算法:想涂什么颜色,AI立刻给你涂好(Paper+Code)

王新民 编译整理 量子位 报道 | 公众号 QbitAI 最近,来自加州大学伯克利分校的RICHARD ZHANG、JUN-YAN ZHU、PHILLIP IS...

3385
来自专栏机器之心

学界 | 用DL实现Bug自动归类:微软研究院提出DBRNN-A

32412
来自专栏机器之心

学界 | OpenAI推出机器人新系统:机器可通过VR演示自主学习新任务

选自OpenAI 作者:PETER WELINDER等人 机器之心编译 参与:晏奇、黄小天 近日,OpenAI 官方博客上发表了一篇名为《自主学习的机器人(R...

3598
来自专栏量子位

谷歌发布轻量级视觉架构MobileNetV2,速度快准确率高

虽然深度学习在图像分类、检测等任务上颇具优势,但提升模型精度对能耗和存储空间的要求很高,移动设备通常难以达到要求。

851

扫码关注云+社区

领取腾讯云代金券