随机化算法在OI中的应用

好像之前有个论文就是这个标题不过无所谓了

又重新回来学了几天OI把之前看的模拟退火看了一下(可惜去年NOIP)，又看了看网上dalao们的博客学习了一点遗传算法想来写一些东西。于是干脆把学过的两个随机算法都写一写

ps:模拟退火的笔记是以前写的

模拟退火

个人觉得模拟退火更适合在OI赛场上用(因为它短啊！！)

退火算法其实是一种随机化算法，拥有一个很稳定(玄学)的时间复杂度，取决于你所定的初温和降温次数(这两个之后会讲)

我们可以想象一桶水，我们把他从200°C逐渐降低到-100°C，这桶水中的水分子会渐渐从无序状态趋于稳定，等到整个桶结冰之后整个系统的状态就会稳定下来。模拟退火算法也是这样,对于程序我们每次会有一个初温，伴随着整个温度的降低每次取到的近似最优解也会趋于稳定，多次从高温降到低温后取得的近似最优解也就是最优解

实际上就是是运用了物理上的热力学的部分知识来解计算机中的问题

在热力学中的退火过程大致是变温物体缓慢降温而达到分子之间能量最低的状态。设热力学系统 SS 中有有限个且离散的 nn 个状态，状态 ii 的能量为 EiE_{i} ，在温度 TkT_{k} 下，经过一段时间达到热平衡，这时处于状态 ii 的概率为

Pi(Tk)=Ck⋅exp⁡(−EiTk)P_{i}\left(T_{k} \right) = C_{k}\cdot \exp(-\frac{E_{i}}{T_{k}})

exp为以自然对数为底的指数函数
其实上面这一段都可以不看，仅仅是为了装逼而写

用一个比较直观的图来解释就是这样的，随着温度降低寻找的近似最优越来越稳定且趋近实际最优值
退火温度
可以看到随着温度(temperature)的减小，红线的随机度也在减小，最后到达了最高点

操作

模拟退火的操作很少一般情况下模拟退火能够解决一些DP题，而且代码量也很小

关于操作同样也用一道题来方便讲解

题目

线型网络

题目描述

有 N ( <=20 ) 台 PC 放在机房内，现在要求由你选定一台 PC，用共 N-1 条网线从这台机器开始一台接一台地依次连接他们，最后接到哪个以及连接的顺序也是由你选定的，为了节省材料，网线都拉直。求最少需要一次性购买多长的网线。（说白了，就是找出 N 的一个排列 P1 P2 P3 …PN 然后 P1 -> P2 -> P3 -> … -> PN 找出 |P1P2|+|P2P3|+…+|PN-1PN| 长度的最小值)

输入

第一行 N ，下面 N 行，每行分别为机器的坐标(x,y) ( 实数 -100<=x,y<=100 )

输出

最小的长度，保留两位小数。

分析

PS：哈密顿序列指在一条哈密顿路上依次从头到尾的所有结点按顺序组成的序列

我第一次看这道题以为是一道最小生成树的模板题，仔细一看发现并不是，每台电脑需要用一条链连接起来，并不是一棵树。
也就是说每个结点最后有且只有两条边与其他结点连接，也就是一个哈密顿路(一笔连完所有结点)。因此就有一个哈密顿序列，整个哈密顿序列需要的消耗(总网线长度):

W=∑i=1n−1(Xi−Xi+1)2+(Yi−Yi+1)2W= \sum_{i=1}^{n-1} \sqrt{ {(X_{i}-X_{i+1} )}^{2}+{(Y_{i}-Y_{i+1} )}^{2} }

使用模拟退火每次随机打乱哈密顿序列，求出当前序列与之前序列的差值，如果小于00则这个序列要比之前的序列要更优，就需要接受这个新的近似最优解，如果不是则需要下面的accept操作来判断是否需要接受

随机化操作

随机化操作顾名思义就是随机打乱当前的序列(不一定非要是序列，只要是所求最后的解就可以随机)，代码比较清晰

1
2
3
int x=rand()%n+1,y=rand()%n+1;
while(x==y) x=rand()%n+1,y=rand()%n+1;
swap(now[x],now[y]);

accept操作

accept操作是模拟退火中最重要的，如果当前的变化量Δ<0\Delta<0也就是说当前的解更优因此需要接受，如果Δ≥0\Delta \geq 0就用rand()MAXRAND≤exp⁡(−ΔTemperature)\frac{rand\left( \right)}{MAXRAND} \leq \exp\left(-\frac{\Delta}{Temperature} \right)公式来判断当前的解程序是否接受，可以用数学证明当温度逐渐变小Δ\Delta不变的情况下exp⁡(−ΔTemperature)\exp\left(-\frac{\Delta}{Temperature} \right)会趋近与00所以随机度也越来越小,同理温度不变时Δ\Delta越大随机度也越小，也就是说只有当温度很高的时候或者Δ\Delta差距很小的时候才会接受这个新的答案，从而接近最优解，而不会在一个局部最优解徘徊，也就证明了模拟退火的正确性
虽然每道题的解法不一样，但退火的accept函数一般都是不会变的直接抄下来即可，其中MAX_RAND为常量表示最大能够RAND多少,exp函数在math库中有定义

1
2
3
4
bool accept(double delta,double temper)
{
    return delta<0 || rand()%MAX_RAND<=exp(-delta/temper)*MAX_RAND;
}

退火算法的操作也就只有这两个，剩下的都是求解操作，所以最后的代码贴出来(正解是用状压DP，模拟退火也是一种解法，但好像TSP问题的正解就是随机化算法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>

using namespace std;
const int maxn=50;
const double decl=0.999; //温度每次降低99.9%
const int max_rand=2333333; //定义最大rand
const double eps=0.0001; //温度最小区间

double x[maxn],y[maxn],mapp[maxn][maxn],T=100000,ans=1e10;
int la[maxn],now[maxn],n;

double cal(int i,int j) //求解i到j的距离
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])*1.0+(y[i]-y[j])*(y[i]-y[j])*1.0);
}

double work(int *p) //当前哈密顿序列的总长度
{
    double res=0;
    for(int i=1;i<n;i++) res+=mapp[p[i]][p[i+1]];
    return res;
}

int main()
{
    srand(19260817U); //听说随机种子用这个有奇特效果
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            mapp[i][j]=mapp[j][i]=cal(i,j); //初始化没个结点之间的长度
    double dis1,dis2;
    for(int i=1;i<=n;i++) la[i]=i; //初始化哈密顿序列
    dis1=work(la); //初始化总长度
    int tmp=150;
    while(tmp--) //多次退火保证正确性
    {
        T=23333;
        while(T>eps)
        {
            for(int i=1;i<=n;i++) now[i]=la[i];
            int x=rand()%n+1,y=rand()%n+1;
            while(x==y) x=rand()%n+1,y=rand()%n+1; //随机交换哈密顿序列中两个结点
            swap(now[x],now[y]);
            dis2=work(now); //求解交换后的总长度
            double delta=dis2-dis1; //当前的delta值
            if(delta<0 || rand()%max_rand<=exp(-delta/T)*max_rand) //accept操作，我这里只写了一个if
            {
                dis1=dis2;
                for(int i=1;i<=n;i++) la[i]=now[i];
            }
            if(dis1<ans) ans=dis1;
            T*=decl; //温度减小
        }
    }
    printf("%.2f",ans);
    return 0;
}

遗传算法(Genetic Algorithm)

和一般的随机化算法相似，遗传一般用来解决一些最优化问题，包括但不限于TSP问题。也可以用来做一些更高端的东西例如优化神经网络、PID调参但这些都是OI不会涉及的领域

概念

以下借鉴百度百科

遗传算法的基本思路是模拟生物上染色体的行为
借鉴进化学的"物竞天择,适者生存"原则，从问题的可能存在的解集开始演变，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际是其染色体的载体(实体)