模拟退火算法

蒙特卡罗模拟算法（解决简单问题）

问题如下：

1.求一个给定函数的最值问题（函数在[-3,3]内的最大值）

蒙特卡罗模拟算法思想：暴力搜索（随机取多个点代入试值，取最值）

缺点在于时间复杂度高，时间复杂度越高，求解花费时间越长（例如30个变量）

时间复杂度：简单理解就是一个算法或是一个程序在运行时，所消耗的时间（或者代码被执行的总次数）

可以参考博客：https://cloud.tencent.com/developer/news/841465

2.TSP（旅行商问题）

其时间复杂度为n的阶乘

3.书店买书问题

4.背包问题

需要解决的问题：某个目标函数的最值（最大值给目标函数添加负号即转换为求最小值问题）

蒙特卡罗模拟与穷举法都是暴力取点代入法，而穷举法是按照一定规则穷举整个空间

刚属于盲目搜索（随机取点代入试验），所以我们需要用启发式算法

盲目搜索：按照预定的策略实行搜索，搜索过程中获取中间信息不能用来改进策略

启发式算法：利用中间得到的信息改进搜索策略称为启发式算法，有助于找到问题的最优解，有助于加速求解过程并找到较优解。（例如蚁群算法可以用在路径规划中）

爬山法的缺点是容易找到局部最优值（初始值选择的不确定造成的）

容易陷入局部最优解的原因是搜索到局部最优解就停止了，其是一种眼光狭隘的贪心算法，其也属于启发式算法

模拟退火会以一定概率接受一个比当前解差的值，有几率跳出局部最优解，跳出全局最优解

模拟退火在新解与旧解的比较中不是完全拒绝旧的解，而是以一定的概率接受

若，则接受新解，若，我们以一定概率接受

接下来，我们对于开始讨论：

定义一个接受概率p，其位于[0,1]之间，p=0，为不接受的爬山法，p=1，为随机取点的蒙特卡洛算法

为新值与旧值的距离，所以我们构造函数使得

p，距离越大愿意接受新值的概率越小

要求前期接受新值概率要大（全局），后期概率要小（局部）

对前期式子进行一个变形，加入时间相关的系数：

是正比于t变化的

模拟退火算法的流程（例如求解最大值）：

看计算出来的概率是否落入随机生成的置信区间内，落入则取其值，否则重新生成一个新解（重复第二步）

对于第二种情况：原先的解A也要保留到一个矩阵里， 怕错过

模拟退火的核心问题：在A的附近如何随机生成一个新解B（可以加入约束条件的地方）

还有一种加入约束条件的方式：对目标函数进行增加或者减小一项变为罚函数，使其值内生到约束条件范围之内

在A的附近如何随机生成一个新解：

Matlab优化工具箱模拟退火给出的找到新解的算法：

为新解，随着T的变化（下降），新解的左右邻域在不断缩小

退火的温度很重要，加热到一定温度保持足够时间，以适宜温度冷却，关系到产品的质量

对于的定义：与温度有关，所以

所定义的初始温度不是固定的，后续初始温度的设定会详细说

对图的解释：图为随温度变化的图，温度越高，更容易接受新解，从右向左看，随着温度的减小，接受新解的概率也在减小（收敛），到达局部搜索。

说明：

中的t可以看成迭代的次数（循环）

为保证搜索过彻底，同一温度下，我们需要进行多次搜索（例如重复上述流程次），再降低温度，再来进行新的一轮搜索（外循环）

停止搜索的准则：1.达到指定迭代次数，例如迭代200次

2.达到指定温度，例如温度小于0.000001

3.我们找到的最优解连续M次迭代都没有变化

对于TSP旅行商问题：

产生新解的方法：

与求函数极值问题不同的是寻找最优解的部分不一样

Matlab有调用模拟退火的内置函数，其只能求解给定函数的极值问题，不能求解TSP等其他问题

对于书店买书问题：

产生新解的方法是：

对于背包问题：

概率准则改为：

注意刚开始的取值对于背包不能超重（所以初始值都设置为0）

 注：本文引用清风建模学习课程资料，如有详细了解，可以关注清风建模课程与公众号