模拟退火算法理论+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

审稿|威锅

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181219G1345800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券