最优化:Python3 模拟退火算法

背景

这个 TP 的背景是这样的:有一个商务旅行团需要去 n 个城市,怎样安排他们的行程可以使行程变得更短?行程的起点和终点都在巴黎。为了解决这个问题,可以使用两种算法:第一种就是最简单的求解 n 个城市 n!种行程的各个距离,然后选取最短的行程;第二种使用la méthode du recuit simulé 模拟退火算法

关于模拟退火算法

模拟退火算法的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,内部粒子处于快速无序运动。当温度慢慢降低的过程中,固体的内能减小,慢慢趋于有序。最终,当固体处于常温时,内能达到最小。此时,粒子最为稳定。

模拟退火算法从某一较高的温度出发,这个温度称为初始温度,伴随着温度参数的不断下降,算法中的解趋于稳定。但是,可能这样的稳定解是一个局部最优解。此时,模拟退火算法中会以一定的概率跳出这样的局部最优解,以寻找目标函数的全局最优解。

导入所需的模块

单个路程的总距离计算

随机打乱原有路程

计算退火新的温度(降温)

绘图函数

基本参数

用传统解决办法

用模拟退火法

参考资料

https://blog.csdn.net/google19890102/article/details/45395257

标签:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注