退火算法学习笔记

初创建于 2022-02-09 00:29

前段时间学习了一下退火算法。

这里简单记一下踩过的坑~

退火算法是一种搜索算法，我认为其核心思想便是”以一定的概率接受一个更差的解“，这样可以避免过早陷入局部最优解，有更大的概率找到全局最优解。

首先，是”温度“，在算法执行过程中，温度会不断降低，当温度降低到一个值时算法结束，而随着温度的降低接受更差的解的概率会不断减小

如果当前的温度为T，计算当前的解的代价为C(i)，新解的的代价为C(i+1)z，则

当C(i+1)<C(i)时，接受新的解

当C(i+1)>C(i)时，以exp( ( C(i+1)-C(i) )/T )的概率接受新的解

/**
 * 退火算法框架
 */
while (T>Tmin) {
    // 计算当前解的代价C(i)
    // 获新的解，计算其代价C(i+1)
    
    dE = C(i)-C(i+1); // 计算代价之差
    if (dE>0) {
        // 接受新的解
    } else {
        if ((double)(rand()%RAND_MAX)/RAND_MAX<exp( dE/T ))
    }
    
    T *= r; // r是降温速率，是一个小于 1 的实数
}

例题

吊打XXX

退火算法十分玄学，有时候需要反复调试参数才能得到预期结果，因此需要谨慎选用。