数学建模必备算法之模拟退火算法

￡神魔★判官ぃ 2023-01-18 04:19 161阅读 0赞

> 在2020年的全国大学生数学建模竞赛的A题中，第三问要确定面积最小的最优炉温曲线，这是一个有**五****个优化变量**的优化问题，由于优化变量太多，导致假若直接用搜索法求解的话，计算量会非常大。 
> 
> 一共5个优化变量，每个变量都进行20次搜索（搜索精度已经很小了）的话，就是要计算**205次**，假如计算一次需要0.05秒，也就是需要计算44小时以上。倘若再提高搜索的精度，则估计需要计算数天。
> 
> 解决这个问题的其中一类方法就是用**智能算法**，包括模拟退火、遗传算法、蚁群算法、粒子群算法等等。
> 
> 下面就来介绍一下比较适合于解这道题的**模拟退火算法**。

# 模拟退火算法 #

> 模拟退火算法是属于**贪心策略**的算法，所谓贪心策略，就是总是做出在当前看来是最好的选择。而不是从整体最优上考虑，它得到的是某种意义下的局部最优解。因此，这种算法不是对所有的问题都能得到整体最优解，关键是选择什么样的贪心策略。
> 
> 最基本的基于贪心策略的算法可以叫做**爬上法**，此算法是从当前解的附近解空间中去选择一个最优解作为当前解，一直这样重复，直到在附近的解空间中找不到更优解为止。因此这个算法很大的可能性找到的只能是局部最优解。
> 
> 如下图所示：假设当前解是在C点，爬山算法搜索到A点这个局部最优解后就会停止搜索，因为在A点时，无论向哪个方向去小幅度移动都不能得到更优的解。
> 
> ![图片][a51c720c910f37cde44824cd8b3c56d5.png]

> 而我们的模拟退火算法实际上也是基于贪心策略的，只不过它在爬山法这种纯粹的贪心策略的基础上，又在搜索过程中加上了随机因素。这个随机因素的具体表示就是：该算法会以一定的概率来接受一个比当前解要差的解。于是也就有了跳出爬山法的局部最优解的可能。
> 
> ![图片][eab1c77247eaf8451f986468e0fc560e.png]
> 
> 还是以上面爬山法的图为例，模拟退火算法在到达局部最优解A后，会以一定的概率向E去移动。到达E点后，就会有可能到达D点，从而依据爬上法的思想，就会到达真正的全局最优解B点了。
> 
> 模拟退火算法描述如下：
> 
> 若K(Y(i+1))>=K(Y(i))(即移动后的第i+1处得到了更优解)，则总是接受该移动。
> 
> 若K(Y(i+1))<K(Y(i))(即移动后i+1处的解比当前解要差)，则以一定的概率接受移动，且这个概率是随着时间推移逐渐降低（逐渐降低才能趋向稳定）。
> 
> 那么怎么定义这个“一定的概率”呢？
> 
> 实际上是参考了金属冶炼的退火过程，故而此算法被叫做模拟退火算法。
> 
> 根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：
> 
> **P(dE)=exp(dE/(kT))**
> 
> 其中k是一个常数，exp表示自然指数，且dE<0。
> 
> 此公式含义是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（因此叫退火），因此dE/kT<0，所以P(dE)的函数取值范围是(0,1)。
> 
> 随着温度T的降低，P(dE)会逐渐降低。
> 
> 我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。
> 
> 因此可以将模拟退火算法与爬山算法对比成：
> 
> **爬山算法：**一只兔子朝着比当下所处的位置更高的地方跳。它逐步地跳到了不远处的最高山峰。但是这座山峰不一定就是整个解空间所在区域的最高山峰，它只是这只兔子目光所及的这一块区域的最高山峰。
> 
> **模拟退火：**一只兔子喝醉了。它随机地向各个方向跳了很长时间。这期间，它可能跳向比当下更高的地方，也有可能跳入比当下更低的地方。但是，等它逐渐地清醒了，会朝着最高的方向跳去。这种跳法更有可能会跳向最高的山峰。
> 
> 此算法用**流程图**可以表示为：
> 
> ![图片][2597b22d9fdbc9bf611cefedcb8295a8.png]

> 用**伪代码**表示：
> 
> s:=s0;e:=E(s)        //设定目前状态为s0，其能量E(s0)
> 
> k:=0                 //评估次数k
> 
> while k<kmax and e>emax
> 
> //若还有时间（评估次数k还不到kmax）且结果还不够好（能量e不够低）则：
> 
> sn:=neighbour(s)     //随机选取一临近状态sn
> 
> en:=Esn)             //sn的能量为E(sn)
> 
> if random()<P(e,en,temp(k/kmax)) 
> 
> then                 //决定是否移至临近状态sn
> 
> s:=sn; e:=en        //移至临近状态sn
> 
> k:=k+1               //评估完成，次数k加一
> 
> returns              //回转状态s

> 模拟退火算法的应用非常广泛，在经典的0-1背包问题上、图着色问题上、物流配送里的调度问题等各类的调度问题上等等，都能够使用。
> 
> 在跨领域上，大规模集成电路设计（VLSI）问题里的布线布板等优化问题都会用到此算法。以及在最近几年非常火的神经网络上，如何避免梯度下降算法过程中陷入局部最优解很多时候都是可以用到模拟退火算法。还有图像处理以及各种组合优化问题都会用到。

[a51c720c910f37cde44824cd8b3c56d5.png]: /images/20221021/29784fb6cb7042729560507bf4e519dc.png
[eab1c77247eaf8451f986468e0fc560e.png]: /images/20221021/e70b7d64745844cf937c5561638d70e9.png
[2597b22d9fdbc9bf611cefedcb8295a8.png]: /images/20221021/b1af0850c0284afc93da348db0deca03.png