一种模拟退火的优化

· · 算法·理论

前言

在使用模拟退火抢 P10447 的最优解时，发现常规的退火在接受一个更劣解进行下一步搜索时，很难再找回原先的更优解。

于是就有了这篇文章。

算法思想

在接受更劣解时，标记当前的更优解。接下来的运行中在超过一个时间阈值时进行回溯。如果找到了比原更优解更优的解，则取消回溯计时。

算法流程：（无跳转则顺序执行）

  1. 生成一个邻域解并计算其价值。
  2. 判断其是否优于当前解，若不优，跳 6。
  3. 判断其是否优于回溯点的解，若优于，则取消回溯计时。
  4. 更新当前解。
  5. 降温，跳 1。
  6. 根据一个概率判断是否接受，若接受，且没有回溯点，添加回溯点，接受就跳 4，不接受则跳 5。

时间复杂度证明

模拟退火要什么时间复杂度。

示例

这里以 P10447 为例。

题意简述

给出一张图，有 n 个点 \frac{n(n-1)}{2} 条边，边无向有权，求不重不漏经过每个点的以 0 号点为起始，n-1 号点为终点的最短路径。

思路

这里先实现常规模拟退火。

见到这种路径经过点数确定的题目（TSP）（数据范围还很小qwq），可以想到模拟退火。

模拟退火的主要步骤是

  1. 先初始化温度，当前解和当前答案。
  2. 如果温度小于最终温度，跳 6，否则跳 3。
  3. 由当前解生成一个临时的新解，并计算新的答案。
  4. 判断是否接受该临时解，接受则更新解和答案，不接受则回退到上个解。
  5. 降温，跳 2。
  6. 输出答案，结束。

模拟退火的核心是 Metropolis 准则，它决定了如何接受当前解的邻域解。在温度 T 下，对于一个新解与当前解的目标函数差值 \varDelta E=E_{new}-E_{old}，Metropolis 准则的接受概率为：

1 &\text{}\varDelta E \le 0\\ e^{-\frac{\varDelta E}{T}} &\text{}\varDelta E \gt 0 \end{cases}

其中：

  • 当 \varDelta E \le 0 时，接受新解，因为新解比当前解更优。
  • 当 \varDelta E \gt 0 时，接受新解的概率是 e^{-\frac{\varDelta E}{T}}，即接受差解的概率随温度降低而减小。

在高温时，算法允许接受较差的解，从而探索更广泛的解空间。随着温度降低，算法更倾向于只接受更优的解，减少“跳出局部最优”的概率。

将解定义为一条从 0 到 n-1 的路径，代价定义为路径长度。就可以愉快地模拟退火了。

具体实现

请自行卡时和调参（我给的代码极大概率能过，但并不优）。

存图直接用邻接矩阵：

int dist[21][21];

求邻域解：

vector<int> get_solve(vector<int> a) {
    int i = rand() %(a.size()-2)+1, j = rand() % (a.size()-2)+1;//防止交换起点和终点
    while (i == j) j = rand() % (a.size()-2)+1;//防止交换同样的点
    swap(a[i], a[j]);
    return a;
}

求代价：

int get_dist(vector<int> a) {
    int ret =0;
    for (int i = 1; i < a.size(); i++) {
        ret += dist[a[i - 1]][a[i]];//顺序求解，n只有20，不用考虑什么奇怪O(1)
    }
    return ret;
}

模拟退火主要代码：

vector<int> SA(int n) {
    vector<int> a;
    double t = 10000, alpha =1-1e-3, e = 1e-4;//参数分别为初始温度，衰减因子，温度下限
    for (int i = 0; i < n; i++) {
        a.push_back(i);
    }
    vector<int> best_path = a;
    int best_dist = get_dist(a);

    while (t > e) {
        for(int i=0;i<200;i++){
            vector<int> neighbor = get_solve(a);//创建邻域解并计算代价
            int distn = get_dist(neighbor);
            int disto = get_dist(a);
            if (distn<disto/*如果更优直接接受*/||exp((disto-distn)/t)>(rand()/(RAND_MAX + 1.0))/*如果不更优则根据一个概率（取决于与当前解代价的差距）接受*/) {
                a = neighbor;
                if(distn<best_dist){//如果比最优解还优就更新
                    best_dist = distn;
                    best_path = a;
                }
            }
        }
        t *= alpha;//降温
    }

    return best_path;
}

主函数部分就输入图然后跑退火，跑完退火根据返回路径求出代价输出。

就不贴代码了。

优化

考虑到在极限卡时时模拟退火的正确性会大打折扣。

所以我们可以用这篇文章的思想来优化，大体流程在上文已给出。

具体的，定义一个布尔变量来表示是否开启回溯计时器。以及一个计时器变量和回溯解和回溯代价。

仅需修改模拟退火主要代码：

vector<int> SA(int n) {
    vector<int> a,mark;
    double t = 10000, alpha =1-1e-3, e = 1e-4;
    for (int i = 0; i < n; i++)a.push_back(i);
    vector<int> best_path = a;
    int best_dist = get_dist(a),mark_dist = get_dist(a),cnt;
    bool flag=false;
    while (t > e) {
        for(int i=0;i<200;i++){
            if(flag){
                cnt--;//计时器
                if(cnt<=0){//归零，回溯
                    flag=false;
                    a=mark;
                }
            }
            vector<int> neighbor = get_solve(a);
            int distn = get_dist(neighbor);
            int disto = get_dist(a);
            if (distn < disto) {
                if(distn < markdist)flag = false;
                a = neighbor;
                if(distn<best_dist){
                    best_dist = distn;
                    best_path = a;
                }
            }else if(exp((disto-distn)/t)>(rand()/(RAND_MAX + 1.0))){
                mark_dist = disto;
                mark = a;
                a = neighbor;
                flag = true;
                cnt = 5 * sqrt(t);//可以温度越小回溯计时越小。卡时
            }
        }
        t *= alpha;
    }
    return best_path;
}

那么这道题就愉快地做完了。

例题

P10447，P1433，P1171