模拟退火算法概述

模拟退火算法(Simulated Annealing，简称SA)的思想最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。

模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：

加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态

等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行的，当自由能达到最小时，系统达到平衡状态。

冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。

加温过程相当于对算法设定初值，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。

这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。

其中Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。

SA算法的Metropolis准则允许接受一定的恶化解，具体来讲，是以一定概率来接受非最优解。

举个例子，相当于保留一些“潜力股”，使解空间里有更多的可能性。对比轮盘赌法，从概率论来讲，它是对非最优解给予概率0，即全部抛弃。

模拟退火本身是求一个最小值问题，但可以转化为求最大值问题，只需要对目标函数加个负号或者取倒数。

算法步骤

其中，P为算法选择较差解的概率；T 为温度的模拟参数；

当T很大时，图片，此时算法以较大概率选择非当前最优解；P的值随着T的减小而减小；

当T趋于0时，图片，此时算法几乎只选择最优解，等同于贪心算法。

算法特点

• 与遗传算法、粒子群优化算法和蚁群算法等不同，模拟退火算法不属于群优化算法，不需要初始化种群操作。

• 收敛速度较慢。原因在于

（1）它初始温度一般设定得很高，而终止温度设定得低，这样才符合物体规律，认为物质处于最低能量平衡点；

（2）它接受恶化解，并不是全程都在收敛的过程中。这一点可以类比GA中的变异，使得它不是持续在收敛的，所以耗时更多一些。

• 温度管理（起始、终止温度）、退火速度（衰减函数）等对寻优结果均有影响。比如T的衰减速度如果太快，就会导致可能寻找不到全局最优解。

模拟退火算法MATLAB实现

【例1】一元/多元函数优化

一元函数：x = [1,2]范围内 y = sin(10*pi*x) / x 的极值

二元函数：

在x,y都是[-5,5]范围内找z = x.^2 + y.^2 - 10*cos(2*pi*x) - 10*cos(2*pi*y) + 20 的极值

【例2】TSP问题

我们的TSP中城市是自己虚拟的14座城市。

main.m:

计算距离的函数Distance.m：

画出路径的函数DrawPath.m：

输出路径函数OutputPath.m：

PathLength.m:

增加随机扰动产生新解NewAnswer.m：

我们的做法是随机产生两个城市让他们交换位置，从而得到一个新的路径。当然，这只是这个问题的一个做法，也有其他“增加随机扰动”的做法，而且对于多元函数问题更加简单，只要在当前解的附近增加一些小的值即可。

Metropolis准则的实现：

程序结果：

【例3】

选择30个点作为仿真研究对象，它们在坐标平面的坐标 (Location)如表1所示。

采用上述程序中随机排列的方法产生初始路径 ，其 排列结果如图1所示 。选择接受函数为Boltzmann 概率分布函数，温度的起始值为70，温度下降律为0.5，经过运行最终得到结果如图2所示，由该 图可知经过优化后找到了最小路径。