从爬山算法到模拟退火（C++）

爬山算法

峰顶是指，向任何一个方向走都在向下行进的地方。这句看似显然的话构成了爬山算法的基本理论：只要向上走，就可以到达峰顶。

实现也相当简单，这里以二维上山的情况举例：

class Position{
public:
    double x,y;
    void step(){
        // 自定义前进函数
    }
}pos;
void climb(Position &pos){
    double height = pos.y;
    while (true) {
        pos.step(); 
        if (pos.y < height) break; 
        // 前进后如果发现高度下降则退出
        height = pos.y;
    }
}

爬山算法的缺点也是相当明显。虽说找到了峰顶，可那只是一个局部极值，在全局范围上或许还存在着更加优秀的解，但爬山算法一旦找到一个极值便无力继续寻求。因此这个算法还有改进空间。

模拟退火

我们很容易想到这样一种优化：要是爬山算法中的那个爬山者能够一步跨越一个山峰，到达另一个山峰就好了。这个思路有效解决了爬山算法陷入局部极值的问题，实现了全局的求解。

为了让位置更有全局性，模拟退火一般会通过随机算法从全局中获取一个位置。然后，比较该位置高度和当前位置的高度。如果该位置高度高于当前位置（假设是上山），那么就将当前位置转移过去；如果该位置高度低于或者等于当前位置，则按照温度数据和高程差构造的函数来确定转移概率，温度越小、高程差越大，则转移概率越小。其中，每一轮计算都会降低温度。

我不在这里引入计算，但是可以想象，随着时间推进，由于温度的下降，转移到更低处的概率越来越低，因此整体更有可能转移到高处。由于在早期高温时的跳跃的存在，模拟退火算法很难在最后取得局部极值；即使最后温度已经非常低，只要随机到的位置高度高于当前位置，还是能够跳跃过去。这就是模拟退火算法的优势。

假想有函数 $f(x)$ 的一段需要找到其全局极大值，采用模拟退火算法（$e^\frac{-\Delta E}{T}$ 很好地满足了转移概率函数的要求，此处采用此公式来计算转移概率，其中 $e$ 为自然常数，$\Delta E$ 为高差，$T$ 为温度）：

class Position{
public:
    double x,y;
}pos;
void annealing(){
    double T = 1000; // 初始温度
    while (T > 0.001){ // 终止温度
        Position nxt = next(); // 函数 next 随机获取一个位置
        double delta = abs(nxt.y - pos.y);
        if (nxt.y > pos.y) pos = nxt;
        else {
            if (exp(-delta / T) > ((double)rand()/RAND_MAX)) pos = nxt;
        }
        T *= 0.97;
    }
}

小生境方法

并非一定要模拟退火才可以优化爬山算法，实际上，我们也可以找来一群人爬山。

小生境方法通过构造一个种群，让位置均匀地散布于全局，最终结果是大量初始位置通过爬山算法聚集于所有峰顶，最终找到真正的全局最大值。不过这种方法的问题在于，当种群个体数目太多时，可能会导致运算速度的下降，因此，种群的大小的选择是需要考虑的问题。

在模拟退火算法中也可以同时采用小生境方法。