模拟退火算法理论＋Python解决函数极值＋C＋实现解决TSP问题

简述

根据上次发出推送后大家的反应和回复，发现大家对模拟退火算法很感兴趣，这次就介绍模拟算法的使用吧~

算法理论部分

用粒子的排列或相应的能量表示物体所处的状态，在温度T下，物体(系统)所处的状态具有一定的随机性。主流趋势是系统向能量较低的状态发展，但粒子的不规则热运动妨碍系统准确落入低能状态。

简单来说就是，在温度T下，有两种可能

， 那没得说有更好的肯定选更好的。

，这个时候我们也有一定的概率选这个。

概率为

其中K为玻尔兹曼常数（在这个算法上，我们经常使用数值1代替这个）

K > 0，一般设置为 K = 1

T > 0，我们在递减的过程中，终止的T，一般认为是T = 1

变量简单分析

不难看出，随着T下降，这个状态转移的概率是下降的。

原因：

物理上解释：

因为之前的这个转移概率，认为是，在高温情况下，分子可能会产生较为不稳定的随机运动。且温度越高，这个分子不规则运动的可能是更大的。这是在模拟这个过程。

所以，我们称这个算法为，模拟退火算法

从状态转移概率到状态概率

这个分析过程，其实是类似于推理马尔可夫链的过程。

之前给给出的其实是条件概率。

我们假设第n个状态为，那么现在就是考虑下一个状态的概率。

我们用，表示第n个状态。

用条件概率公式得到

而解这个过程，就用到了以前解马尔科夫过程的方法，这里我需要假设一个均衡态，在这种状态下，经过任意次状态转移之后，整个模型的概率保持一致。

得到结果是

只是一个归一化的因子而已，就是把所有的这样的分子的数值求个和。使得概率和为一而已。

这个分布称之为Boltzmann分布。

推导

理解当温度收敛到接近0的时候，收敛到结果

其实只需要理解下面这个函数的导数就可以了

关于T求导。

那么，这就是这个变量关于T的变化导数。再考虑关于函数值

这个函数是关于的单调减函数。的情况下。

所以说，函数值稍微小的数值所对应的状态概率，受到T的减小而导致的减小的幅度，其实是较为小的。

那么当T趋于0的时候，就可以得到，状态概率，会集中在函数值较为小的数值点上（数值小的点的概率大）

也就是说，当模拟退火，温度越低，越有可能收敛到正确解。而且，这是收敛的。

理论部分的后记

这里，我们证明了，当温度越小，越会收敛到正确解。这只是在理论上的证明。但是我们都知道，当T趋于0，但是特别小的时候，作为分母时，这个精度就会变得非常低了（计算机上是离散的）。

所以，为了简单，我们一般设置T到1就截止了。

python实现

先尝试解决下面的这个图

python实现模拟退火解极值

先在这个区间上随机生成一个起始点

每次在给定点的一个邻近区域（自己设置），找到一个新的点。

然后这两个点做比较。通过概率模拟来确定是否发生位置迁移。

直到温度下降到一定的数值。

基本上准确~

C++实现解函数值问题

对于上面一个问题的C++解法

但是C++的精度似乎没有Python的好。这个可以适当调节参数来获得更高的精度，反正C++的速度也快很多。

TSP问题求解

代码详细解释定义了两个宏，主要是为了加速运算

第一个是RAND(b,e)生成在这个区间上的整数

第二个是RANDFLOAT()是为了生成(0,1)之间的数。

定义全局变量

Mat是来存储距离矩阵的

Path存储路径

Value存储路劲所对应的函数。这里考虑的是具体的数值

N表示有多少个点

所有前面加了temp都表示临时变量。

函数解释

函数用于给输入的路劲下，求对应的value值。

将temp的数组和具体数值恢复。为了下一次的考虑

覆盖掉原来的路劲。进行存储。

初始化路径。并算出初始值。

给一组数据和结果

输出：

后记

现在我们提供以下服务：

数学题、算法题、项目（语言c++，Python，java，JavaScript，matlab，html，mysql）、课程（数据结构，计组，操作系统，计网，数据库）

debug，若有以上需要可以发送给后台进行商讨哦！

排版|Shane

作者|Sean

审稿|威锅