模拟退火算法
1. 简介
模拟退火法（SAA）基本思想是：在一定温度下，搜索从一个状态随机的变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解。它有四个基本概念：（1）目标函数，对于最大值问题，使目标函数乘以-1即可（2）温度，它随着算法的迭代逐步下降。一方面，温度用于限制SA产生的新解与当前解之间的距离，即SA的搜索范围；另一方面，温度决定了SA以多大的概率接受目标函数值比当前解的目标函数值差的新解（3）退火进度表，指代温度随算法迭代的下降速度，退火过程越缓慢，找到全局最优解的机会就越大，它包括初始温度及温度更新函数的参数（4）Meteopolis准则，它是指SA接受新解的概率，对于目标函数取最小值的问题，SA接受新解的概率为
2. 基本步骤
1：初始化温度T，初识解状态S，每个T值的迭代次数L
2：对k=1，……，L做第三步到第六步
3：产生新解S’
4：计算增量
δ
(
t
′
)
=
C
(
S
′
)
−
C
(
S
)
\delta(t')=C(S')-C(S)
δ(t′)=C(S′)−C(S)，其中C为评价函数
5：使用Meteopolis准则
6：如果满足终止条件则输出当前解，结束程序，终止条件通常取为连续若干个新解都没有被接受时的终止算法
7：T逐渐减少，且T趋于0，然后做第二步
3. 应用
它的所有调用格式如下
x = simulannealbnd(fun,x0)
x = simulannealbnd(fun,x0,lb,ub)
x = simulannealbnd(fun,x0,lb,ub,options)
x = simulannealbnd(problem)
[x,fval] = simulannealbnd(___)
[x,fval,exitflag,output] = simulannealbnd(___)
| exitflag | 说明 |
|---|---|
| 1 | 迭代次数达到限制值，目标函数值平均变化小于TolFun |
| 5 | 达到目标函数最小期望值 |
| 0 | 由于目标函数检查步数达到最大或迭代步数达到最大而退出 |
| -1 | 用户自定义函数引起的退出 |
| -2 | 未搜索到可行点 |
| -5 | 超过时间限制 |
options可设置的参数太多，就不一一介绍了，它通过saoptimset进行设置。接下来用一个例子简单说明，求如下函数最小值
f=@(x)x(1)^2+x(2)^2+5*sin(x(1)*x(2))
[x,fval,exitflag,output]=simulannealbnd(f,rand(1,2))
Optimization terminated: change in best function value less than options.FunctionTolerance.
x =
1.0770 -1.0768
fval =
-2.2640
exitflag =
1
output =
包含以下字段的 struct:
iterations: 1966
funccount: 1983
message: 'Optimization terminated: change in best function value less than options.FunctionTolerance.'
rngstate: [1×1 struct]
problemtype: 'unconstrained'
temperature: [2×1 double]
totaltime: 3.1875
由此可见对于一个简单的函数而言，模拟退火需要迭代1966次，耗时3.1875秒，因此智能寻优算法一般都是比较耗时的。