最近学习了模拟退火智能算法,顺便学习了一下matlab,顺带一提matlba真香,对矩阵的操作会比python的numpy操作要更加方便,这里我们是以TSP问题为例子,因为比较好理解。
模拟退火介绍
模拟退火总的来说还是一种优化算法,他模拟的是淬火冶炼的一个过程,通过升温增强分子的热运动,然后再慢慢降温,使其达到稳定的状态。
初始解
通常是以一个随机解作为初始解. 并保证理论上能够生成解空间中任意的解,也可以是一个经挑选过的较好的解,初始解不宜“太好”, 否则很难从这个解的邻域跳出,针对问题去分析。
扰动邻解
邻解生成函数应尽可能保证产生的侯选解能够遍布解空间,邻域应尽可能的小,能够在少量循环步中允分探测.,但每次的改变不应该引起太大的变化。
初始温度
- 初始温度应该设置的尽可能的高, 以确保最终解不受初始解
影响. 但过高又会增加计算时间. - 均匀抽样一组状态,以各状态目标值的方差为初温.
- 如果能确定邻解间目标函数(COST 函数) 的最大差值, 就可以确定出初始温度$T_{0}$,以使初始接受概率$P=e^{-|\Delta C|_{max}/T}$足够大。$|\Delta C|_{max}$ 可由随机产生一组状态的最大目标值差来替代.
- 在正式开始退火算法前, 可进行一个升温过程确定初始温度:逐渐增加温度, 直到所有的尝试尝试运动都被接受, 将此时的温度设置为初始温度.
- 由经验给出, 或通过尝试找到较好的初始温度.
等温步数
- 等温步数也称Metropolis 抽样稳定准则, 用于决定在各温度下产生候选解的数目. 通常取决于解空间和邻域的大小.
- 等温过程是为了让系统达到平衡, 因此可通过检验目标函数的均值是否稳定(或连续若干步的目标值变化较小) 来确定等温步数.
- 等温步数受温度的影响. 高温时, 等温步数可以较小, 温度较小时, 等温步数要大. 随着温度的降低, 增加等温步数.
- 有时为了考虑方便, 也可直接按一定的步数抽样。
Metropolis法则
Metropolis法则是SA接受新解的概率。
$$P(x=>x’)=
\begin{cases}
1 &\text{$,f(x’)<f(x)$} \\
e^{-\frac{f(x’)-f(x)}{T}} & \text{$,f(x’)>f(x)$}\
\end{cases}
$$
$x$是表示当前解,$x’$是新解,其实这也是模拟退火区别于贪心的一点,我们在更新新解的时候对于不满足条件的情况,我们也有一定的概率来进行选取,从而可以使得退火模拟可以跳出局部最优解。
降温公式
经典模拟退火算法的降温方式:
$$T(t)=\frac{T_0}{log(1+t)}$$
快速模拟退火算法的降温方式:
$$T(t)=\frac{T_0}{1+t}$$
常用的模拟退火算法的降温方式还有(通常$0.8<\alpha<0.99$)
$$T(t+\Delta t)=\alpha T(t)$$
终止条件自己设定阈值即可。
花费函数COST
这个基本就是分析题目,一般设置为我们需要求解的目标函数最值。
TSP问题
已知中国34 个省会城市(包括直辖市) 的经纬度, 要求从北京出发, 游遍34 个城市, 最后回到北京. 用模拟退火算法求最短路径。
1.main.m
主函数
|
2.distance.m
计算两点之间的距离
|
3.totaldistance.m
一条route路线的总路程,也是我们需要优化的目标函数
|
4.distancematrix.m
任意两点之间的距离矩阵
|
5.change.m
产生分子扰动,求当前解的邻解
|
6.plotcities.m
画出city
|
7.plotroute.m
画出路线
|
一开始的路径
最后运行出来的最优化路径
有需要的朋友可以下载相关的数据集下载链接