老饼讲解-神经网络 机器学习 神经网络 深度学习
启发式寻解

【原理】模拟退火-算法介绍

作者 : 老饼 发表日期 : 2022-09-14 19:00:46 更新日期 : 2023-11-11 11:18:14
本站原创文章,转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com



模拟退火算法(Simulated Annealing,SA)是求解策略中的一种随机寻优算法

通过本文可以初步掌握模拟退火算法,包括模拟退火算法的思想和具体的算法流程




  01. 模拟退火算法是什么   



本节通过介绍模拟退火解决什么问题,它的思想原理是什么,

以此来初步了解模拟退火算法是什么



    模拟退火算法解决什么问题    


模拟退火算法是一个借鉴物理退温过程设计的算法
它是一种用于寻找优秀解的算法
例如问题:已知, 求一 使得值最小
在无法求得精确解的情况下,则可用模拟退火算法对其寻找一个优秀解
 备注:(1)找到的不一定是最优的解,但至少局部最优                           
(2) 这里的 f(x) 不要求有表达式,可以是一个规则,更不要求可偏导



   模拟退火算法的背景意义   


物理退温原理
 
一个高温物体,如果一下子把物体温度降下来,这样的物体是比较脆的,
因为内部各个粒子并未找到一个能量较小的位置
但如果让它缓慢降温,
粒子会在温度缓慢下降过程中,不断寻找能量更低的位置,
最终,每个粒子都能找到一个能量较低的位置,从而使物体更加紧固
(物体能量低,要改变它的结构,就需要更大能量,也即更紧固)

为什么急速降温不行,而要缓慢降温呢?
因为急速降温每个粒子被迫马上收缩到一定位置
而缓慢降温过程则不相同,
当每个粒子温度还很高时,它可以转移到不同位置,哪怕是跃迁到能量更高的位置,
因为温度还很高,有足够的能量支持它的跃迁
但随着温度下降,它能跃迁的概率越来越小,
随着缓慢降温,粒子刚开始的时候比较活跃,后慢慢的更倾向于收缩
可以看到,缓慢降温时,每个粒子在整个过程中有足够多的机会去找到更好的位置
物理退温迁移到数学寻找极小值问题
借鉴这一思想,迁移到我们的问题来,就是
x 对应 粒子
目标函数 对应 能量           
我们的里的每个,就相当于物体的粒子,
刚开始的时候,设置一个温度,在温度高的时候,x的调整比较自由,哪怕x的调整会让目标函数值更高,我们也用一定的概率接受它
随着温度慢慢下降,接受更差的解的概率也降低,慢慢的,让每个x找到更好的位置,使整体目标函数值更小




   02.模拟退火算法流程   



本节展示模拟退火算法的具体流程



     模拟退火算法流程    


一、初始化                                                                                          
    1.1. 初始化初始解                                                                    
    1.2. 初始化温度                                                                      
二、外循环                                                                                        
2.1 内循环(直接循环N次):                                               
(1) 生成新解                                                                 
 从x的邻域随机选择一个x作为新解             
(2) 计算新解的能量                                               
(3) 根据能量差按概率接受新解                                     
(3.1) 计算新解与旧解的能量差                           
                 
(3.2) 根据能量差决定接受新解的概率                
           
                                                                    (3.3) 如果 则接受新解,否则放弃新解,进入下一轮                                   
      每次接受新解时,需要更新以下信息:    
👉更新当前解                              
👉更新当前能量                          
👉更新历史最优解                       
                                   👉更新本轮内循环找到的最优最差解所需的能量             
2.2 降温                                                                                
                      
2.3 判断终止条件                                                                   
                  如果本轮找到的最优、最差解的能量差异不大,则终止循环
三、输出历史找到的最优解                                                                 




    关于概率公式的解释   


在模拟退火算法中,对于是否接受新解使用了下述公式

  

该公式是非常巧妙的,下面我们分步讨论它的意义

当新解比旧解更优秀时
当新解比旧解更优秀时,即
而此时,则,
因此,不管随机数是多少,条件一定成立,
这意味着,只要新解不比旧解差,就一定接受新解

当新解比旧解更差时
当新解比旧解更差时,即时,
此时 
p的取值受当前温度T与能量差两者的影响
当新解越差时,能量差就越大,此时p越小
但同时,温度T作为分母,T越大时,p越大,
也就是说,当温度很高时,即使能量差很大,也有很大的概率接受新解
所以说,这个公式非常的巧妙,仅仅用一个公式,就蕴含了多个机制










  End  






联系老饼