SA算法学习笔记

发布于 2018-07-08  219 次阅读


最近闲的无聊,学了一个模拟退火算法...

定义

首先,我们来了解一下这些算法的来历和用处。

人们在做一些复杂度为指数级别的题目时,忍受不住这种高复杂度的方法,于是发明了各种随机算法来获得近似最优解,例如爬山算法,模拟退火,遗传算法和蚁群算法等。

那么我们先来看一下最容易理解的爬山算法。

爬山算法

定义

所谓的爬山算法实际上就是简单的贪心算法,贪心算法通过从当前解的临近空间选择一个最优的解作为新的当前解,因此这个解很有可能是局部最优解,而不是全局最优的。因为领域周围没有比他更优的解了。

就是说,爬山算法的劣势在于容易陷入局部最优解。

那么,为了解决这种问题,从物理学出发,出现了模拟退火。

模拟退火

定义

模拟退火这个算法之所以不容易陷入局部最优解,是因为它在选择状态时,给被淘汰的状态一个“复活”的机会。这个机会是随机决定的,且越往后越小。所以说模拟退火是一种~看人品~随机算法。

总而言之,模拟退火的随机因素就是:这个随机因素就是:以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。

大致实现过程

  1. 选定一个初始的符合题意的状态,选定一个温度T。

  2. 当温度大于边界时:

   {
       随机变换状态;

       计算新状态与旧状态的差delta;

       如果新状态更优,就替换;

       否则以exp(delta/T)的概率来替换;

       温度乘上一个小于1的系数;
   }

不难看出,随着时间不断飞逝,温度不断降低,接受一个更劣的解的可能性降低,解更稳定。

## 注意事项

  1. 温度的设置问题。过高,时间效率下降;过低,准确度下降。
  2. 退火的速度。
  3. 温度的管理问题。

大部分还要看人品。
注意:考试的时候srand()不要用time(NULL)来初始化,要自己随机选择一个种子,可以是特殊纪念的生日,不要选过于大众化的。这一点同时适用于hash算法。

例题

接下来我们以一道题目为主。
Luogu
虽然难度比较奇怪,但是这一题真的很简单......
堪称模拟退火的模板题。

思路就是不断的退火随机得到答案,然后变换答案。
由于模拟退火的随机性,不保证一遍能AC。(我是一遍A了)

详情见代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cmath>
#include <cstdlib>

const int MAXN = 50 + 5;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
const double EPS = 1e-15;

int N,M,C;
int p[MAXN];
int E[MAXN];
int A[25][25],B[25][25],sum,ans = 100000000;
int out[25][25];

int get(int x,int y){
    int ret = 0;
    for(int i = 0;i < 4;i++){
        if(A[x][y] != A[x + dx[i]][y + dy[i]])
            ret++;
    }
    return B[x][y] = ret;
}

void update(int x){
    if(ans <= x) return;
    ans = x;
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)
            out[i][j] = A[i][j];
}

double Rand(){
    return 1.0*(rand()%100000000)/100000000;
}

void SA(double T){
    while(T > EPS){  //温度不为零时执行
        T *= 0.99999; //降温
        int x1 = 1 + rand() % N,x2 = 1 + rand() % N;
        int y1 = 1 + rand() % M,y2 = 1 + rand() % M;
        std::swap(A[x1][y1],A[x2][y2]); //随机生成一组新的状态
        int t = sum;
        t -= B[x1][y1] + B[x2][y2];
        t += get(x1,y1) + get(x2,y2); //计算新状态的值
        if(t < sum || exp((sum-t)/T) > Rand()){
            update(sum = t);
            continue;
        }
        std::swap(A[x1][y1],A[x2][y2]);
        get(x1,y1);get(x2,y2);  //考虑是否要替换
    }
}

int main(){
    srand(19260817);  //种子看运气随便取
    scanf("%d%d%d",&N,&M,&C);
    for(int i = 1;i <= C;i++)
        scanf("%d",&p[i]);
    int round = 5;  //次数越多,得到的答案越接近正确答案,但同时时间耗费越多
    while(round--){
        for(int i = 1;i <= C;i++) E[i] = p[i];
        for(int i = 1;i <= N;i++)
            for(int j = 1,x = 1;j <= M;j++){
                x = 1 + rand()%C;
                while(!E[x]) x = rand()%C + 1;
                A[i][j] = x;E[x]--;
            }  //生成一组随机初始状态
        sum = 0;
        for(int i = 1;i <= N;i++)
            for(int j = 1;j <= M;j++)
                sum += get(i,j);   //获取该初始状态的值
        update(sum);
        SA(100000000);  //进行模拟退火
    }
    for(int i = 1;i <= N;i++,puts(""))
        for(int j = 1;j <= M;j++)
            printf("%d ",out[i][j]);  //输出
    return 0;
}

一个OIer。