随机化算法

从洛谷迁移而来。

”随机化算法”，顾名思义，就是基于随机的算法。它们可以以较高的运行效率解决一些没有正确多项式算法者数据规模较大的问题，在OI中的提交答案题经常会用到随机化算法，在其他某些题目中也可能可以用随机化算法骗到较高的分数。

常见的随机化算法有两种：模拟退火和遗传算法。

模拟退火

模拟退火是一种常用的随机化算法。

思想

不断在当前最优解附近随机选取点，如果这个点比当前最优解优那么更行最优解并转移；否则以一定概率转移。

过程

我们定义退火过程中的温度 ，那么设当前状态与当前最优解的差为 ，则转移的概率为 。随着退火过程进行，温度会以一个倍率降低。

也可以根据实际情况进行调参。

实现

以P1337为例：

//此题要求的是带权费马点，因此估价函数为与到每个点的距离与重量之积的和
double calc(double x,double y){
    double ans=0.0;
    for(int i=1;i<=n;++i){
        double ds=sqrt((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y));
        ans+=ds*a[i].w;
    }
    return ans;
}
void SA(){
    for(double T=T1;T>eps;T*=DE){//初温，末温，降温倍率
        double nx=ax+(rand()*2-RAND_MAX)*T,ny=ay+(rand()*2-RAND_MAX)*T;
        double res=calc(nx,ny);
        if(ans>res)ans=res,ax=nx,ay=ny;
        else if(exp(-fabs(res-ans))/T*RAND_MAX>rand())ax=nx,ay=ny;
    }
}

遗传算法

遗传算法也是一种基于随机化的算法。

思想

定义每一种状态是“有利的”还是“有害的”，那么根据自然选择，“有害的”状态就会在迭代中趋向被淘汰。

过程

参考生物遗传，我们定义每一个状态为“基因”，每个基因有一个估价函数表示这个基因相对而言是优或劣。 我们首先随机产生一定数量的初始个体，然后开始迭代：

• 对于每个个体，我们根据其估价函数的优劣决定其产生后代个数（越优越多），然后在原基因的基础上随产生一些突变以产出每一个后代。
• 对所有产生的后代进行排序，选出最优的若干个进入下一次迭代，其余的淘汰。 迭代足够多轮。

两种算法的比较

一般而言，如果我们讨论每一个状态是公平的（指转移到其他状态的变异数较为均衡），那么模拟退火算法相而言较为合适；但是如果状态不公平或者产生后代的方式和生成基因的方式有较大的区别，那么遗传算法将会较大的概率找到更优解。

状态与估价函数设计

两种算法都离不开估价函数和状态，因此设计一个合理的估价函数和状态是很重要的。 我们认为满足以下要求的状态与估价函数更适合随机化：

• 能描述要最优化的值。
• 易于计算。
• 易于变异。
• 不会变异出非法状态（致死）。
• 是连续的。
• 有局部单调性与波动性。

此外：

• 估价函数并不一定只关于要最优化的值，还可以有关于其他可能有关于最优化值的部分，但是应当首先保答案的最优性。
• 可以通过优化变异方式以防止出现非法状态。