Simulated_Annealing

发表于 更新于 分类于
模拟退火

  1. 首先牢记：$e^{\frac{nowans-f(x)}{t}}$。exp((ans-now)/T)>(double)(rand()/RAND_MAX)。似乎下面的温度作为除数的话还可以再除一些常数以增大或减少接受解的概率。

  2. T 的调控最重要。T 比较高则解优的可能性更大，并且跳出局部最优解的可能性更大，时间上会有更多消耗。

  3. 降温速度 delta 主要是调控时间。

  4. 可以更换多个状态函数/整合不同的状态函数比较。

  5. 注意避免迂回重复于某个解。

  6. 初态不要太随意，注意构造。

  7. 扰动是有技巧的。

  8. 分块模拟退火。

  9. 喀什卡时：clock_t s=clock();while((double)(clock()-st)/CLOCKS_PER_SEC<0.8)。

  10. 注意 Linux 下的种种问题，RAND_MAX 等于 $2^{31}-1$，而 Windows 下只有 $2^{15}-1$。

  11. mt19937：C++11 开始使用，使用范例（本机好像用不了）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <ctime>
    #include <iostream>
    #include <random>
    using namespace std;
    int main() {
        mt19937 myrand(time(0));
        cout << myrand() << endl;
        return 0;
    }

  12. 线性同余算法，定义常数 A，C，M，均匀性高，缺点是周期较短：

    1
    s[i]=(s[i-1]*A+C)%M;

最后，其实大部分时间 SA 都是信仰算法。。。RP 才是 SA 高分的最重要因素。。。