e小白

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 171|回复: 0

数学建模--智能优化算法--模拟退火理论

[复制链接]

4

主题

4

帖子

47

积分

新手上路

Rank: 1

积分
47
发表于 2021-4-29 01:35:46 | 显示全部楼层 |阅读模式
本帖最后由 上帝果冻 于 2021-4-29 01:39 编辑

0 前言


   本文重点讨论模拟退火算法的简单应用,对理论仅进行一些简单介绍,本文对算法的实现使用python语言。前面简介偏理论,如果不感兴趣可以直接跳转到代码和流程部分。


1 模拟退火算法简介


   模拟退火算法(Simulated Annealing,SA)是一种全局搜索算法。其理论来自于物理退火过程,物理退火分为三个部分“升温过程”,“降温过程”和“等温过程”.


1.1 升温过程
   升温过程,在物理过程中是将固体加热到液体状态,打破固体中可能的非均匀状态,使得它降温后可以建立起新的平衡。过渡到数学模型中,也就是打破当前这个非最优解的状态,使得它在降温过程中可以逐步趋向最优解。
1.2 降温过程
   降温过程,是使得高温液体逐步趋向低温状态从而达到新的有序状态(目标是希望新状态的固体是均匀的),如果降温过程太快会导致只能冷凝成非均匀状态的亚稳态。过渡到数学中就是降温过程是希望非最优解能够最终降到最优状态,而降温速度过快,会导致得出的解仍然是局部最优解或者就是一个劣解。
1.3 等温状态
   该过程保证了在每个温度下都能达到平衡。这个的数学概念和算法设计稍后再谈。


   在模拟退火算法中需要引入组合优化方法中的Metropolis准则,这个准则保证了算法具有全局搜索能力,即在一定的概率上接受一个比当前解要差的解,从而提高寻找到更优解的可能性。
1.4 Metropolis准则(物理学描述)
   假设热力学系统S有n个离散状态,其中i状态的能量为。假设在温度下达到热平衡,此时状态i的概率为其中C为已知参数;exp()为一自然常数e为底的指数函数。根据公式可以知道在同一个温度下,能量低的概率是大于能量高的概率的。


1.4 Metropolis准则(数学描述)


   在同一个参数T下,如果解X1对应的适应度函数值F(X1)<F(X0),X0为初始解,则接受X1作为新的解,否则以概率exp(-(F(X1)-F(X0))/T)来接受X1作为新的解。其中以概率接受的方法可以使用随机数的方式实现。




2 模拟退火算法流程及简单应用


2.1 算法流程(不包含等温过程)



STEP 1 :设置适应度函数,初始温度,终止温度,初始解

STEP 2 :循环,在当前温度下根据初始解在一定的范围内随机产生新的解,并根据Metropolis准则判断是否接受新的解。判断是否终止循环,如果终止输出解,否则进行降温。



2.2 简单应用



求解f(x) = x^2 的最小值点。

  1. import numpy as np

  2. #定义适应度函数
  3. def fun(x):
  4.     y = x**2
  5.     return y

  6. #设置初始变量
  7. T = 100     # 初始温度
  8. a = 0.99    # 温度变化率
  9. t = 1       # 终止温度
  10. x0 = np.random.uniform(-10,10,1) # 产生初始解

  11. #执行退火流程

  12. while T>t:
  13.     # 根据初始解在一定范围内产生新解
  14.     x1 = x0 + np.random.uniform(-1,1)
  15.     # 计算新解和初始解的差值
  16.     df = fun(x1)-fun(x0)
  17.     # 执行Metropolis准则
  18.     if df<0:
  19.         x0 = x1
  20.     elif np.random.rand()< np.exp(-df/T):
  21.         x0 = x1
  22.     # 进行降温
  23.     T *= a

  24. print(x0)
复制代码
试验结果为: [0.15110473],与真实结果0相比已经十分精确了。

注:退火算法每次计算的结果不一定相同,也不一定都可以收敛到最优解处。所以应该多使用几次较好。



2.3 算法流程(包含等温过程)

对算法2.1进行改进,考虑等温过程,也就是在每一个温度下都进行相当多次的求解



STEP 1 :设置适应度函数,初始温度,终止温度,初始解
STEP 2 :内循环,在当前温度下根据初始解在一定的范围内随机产生新的解,并根据Metropolis准则判断是否接受新的解。判断是否终止循环。
STEP 3 :外循环,判断是否低于最低温度,如果否,则减低温度继续循环,否则退出循环。


2.4 简单应用


同样求解f(x) = x^2 的最小值点。
#注:请注意上下两段代码的差异,增加了内循环,并且降低了最低温度。
  1. import numpy as np

  2. #定义适应度函数
  3. def fun(x):
  4.     y = x**2
  5.     return y

  6. #设置初始变量
  7. T = 100     # 初始温度
  8. a = 0.99    # 温度变化率
  9. t = 1e-10       # 终止温度
  10. n = 100     # 内循环次数
  11. x0 = np.random.uniform(-10,10,1) # 产生初始解

  12. #执行退火流程

  13. while T>t:
  14.     for i in range(n):
  15.         # 根据初始解在一定范围内产生新解
  16.         x1 = x0 + np.random.uniform(-1,1)
  17.         # 计算新解和初始解的差值
  18.         df = fun(x1)-fun(x0)
  19.         # 执行Metropolis准则
  20.         if df<0:
  21.             x0 = x1
  22.         elif np.random.rand()< np.exp(-df/T):
  23.             x0 = x1
  24.     # 进行降温
  25.     T *= a
  26. print(x0)
复制代码
求解结果:[4.42470702e-06]。在精度上提高了很多个数量级。


最后,本次只是简单地实现了退火算法,这其实不是它的全貌,退火算法作为一个优秀的优化算法,可以解决N维的规划类问题,可以解决最短路径问题,可以解决多元线性拟合和多项式拟合问题等。今天本文仅介绍性地做了一个十分简陋的模型。如果希望继续深入了解退火算法的全部实现,或者了解退火算法对其他问题的求解,欢迎留言。当然后面很有可能会接着写一些遗传算法,粒子群算法,鱼群算法这些的简单介绍。





本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|e小白

GMT+8, 2021-7-29 13:08 , Processed in 0.272230 second(s), 23 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表