算法-模拟退火算法相关疑问

Question

为什么和起始点无关？算法是向一个方向遍历的，如果起始点本身就已经过了最值点，那不还是找不到么？

Answer 1

先看下面的过程:
1: 初始温度设定为T，算法结束温度为TMin，初始解为S[0]，评价函数为Value。
2: 既然是退火算法，那么将温度衰减设定为一个(0,1)之间的数值x，T= T*x。x如果比较小，那么降退火速度会比较快，可能陷入局部最优解; 如果x比较大，退火速度慢，搜索时间长，但是找到最优解的概率大。
3: 算法执行过程中的解状态S[i],S[i+1], 如果评价函数Value(S[i+1]) > Value(S[i]),说明找到了一个更好的解，无条件接受; 如果Value(S[i+1]) < Value(S[i]), 也不能完全不接受，不然就是鼠目寸光的爬山算法，这时候以一定的概率接受，设这个概率为P,但是这个P不能是一个恒定数值，那样造成求解过程不稳定，所以P要在算法执行过程中降低，和2中的T相关，T较高的时候，P也较大，可以接受差解，T较低的时候(算法趋于结束，求解过程要稳定一些了)，这时候P也降低，不再轻易的接受差解。

while(T>TMin)
{
if(Value(S[i+1]) > Value(S[i])){
// 移动到i+1的位置
}else{
// 一定概率接受差解
if(P(T)>random(0,1)){
// 移动到i+1的位置
}
}
T =T*x;
i++;
}

随着T的减小,接受差解的概率P(T)也在减小,最终得到一个近似最优解。

针对你的问题的几个结论:
1: 模拟退火是初始值不敏感的，而不是完全无关。
2: 算法可以遍历整个解空间，你所说的“向一个方向”是不对的，上面描述的S[i]到S[i+1]也不是一个固定的方向。
3: 如果起始点本身就已经过了最值点,也是可以找到的，因为模拟退火是初始值不敏感的，经过数次的跳跃之后，还是会找到一个近似的最值。

兔子喝醉了。它随机地跳了很长时间(当然不是固定方向)。这期间，它可能走向高处(接受更好的解)，也可能踏入平地(可能接受更差的解)。但是，它渐渐清醒了(P(T)接受差解的概率降低)并朝最高方向跳去(退化为爬山算法)。