Posted by on 2017年3月14日

今天来做个模拟退火(Simulated Annealing,百度百科点我!wikipedia click here!)的小实验。

模拟退火是一种通用概率算法,用来在固定时间内寻求在一个大的搜寻空间内找到的最优解。模拟退火是S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi在1983年所发明。而V. Černý在1985年也独立发明此算法。

我觉得它好玩的地方就在于该算法模拟了冶金中的退火过程,同时也让我重新认识到材料的退火其实也是一个最优化的过程。退火通过反复地升温和降温(淬火),不断地寻找分子化学式的全局最优解,同时也避免最终状态局限在局部最优。

模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。

下面我们来做个简单的小实验吧。

我们的问题是:我们要规划一个最短的旅行路线可以达到地图上的所有城市。

首先我们随机生成一个地图如下:

地图上有20个城市,我们对他们随机进行标号,假设我们的初始路线是按照标号从1走到n=20,并计算初始总路长:

下面我们设置模拟退火的参数如下:

接下来就是最主要的模拟退火过程:

1.随着温度不断下降,我们每次随机调换两个城市的标号,并且计算前后的总路长。

2.如果路长变短则采用调整后的规划路线,但是有一定的概率不采取更短的路线,而是保持原有的更长的路线(“淬火”)。概率模型为 exp(-两次前后路程差/当时温度),温度越低,“淬火”概率越大;

3.每次调整后,温度都会以一定比率降低;

4.当温度达到容忍值时,终止程序.

具体的code如下:

其中
计算总路长的函数如下:

画图函数如下:

随机城市排列的函数如下:

最终我们的规划路线如下图

总路长为:

其中模拟退火计算过程中的总路长动态如下:

可以看出模拟退火(SA)算法的缺点也很明显,收敛速度慢,执行时间长。当然,计算最短路径的图算法还有很多,诸如Floyd-Warshall、Dijkstra‘s、Bellman-Ford、SPFA(Shortest Path Faster Algorithm)等,下次有机会再写。
【欢迎订阅并关注微信公众号“饱蠹阁BaoDuGe”】

Posted in: Academic 無涯齋
2 views
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...

Comments

  1. luo
    2017年3月15日

    觉得很实用,举例也很清晰,利用退火思想在一点时间内,求一个全局最优解而不是局部最优解,就像退火的目的就是为了使铸件内分子结构更加均匀化,而达到提高整个铸件的物理性能。很棒!!!谢谢楼主讲解。

Leave a Reply

返回顶部