随机化笔记 24-02-04

---

写在前面

非正解思路
并且C*F不接受申诉和重测

---

策略

该拿到的分都拿到了，会出现“罚坐”现象。
随机化——多拿一点分
有的不是正解，只能拿一般分

---

瞎子爬山

单峰山，局部择优，深搜改进。
如果新方案更好就转移到新方案。

每一步爬多长？一开始步子大一点，越往后步子更小。
步长减小可以按比例减小，随机化更平缓一些。
当步长足够小的时候，可以结束算法。

伪代码：

void climb() {
	node new=rand();
	int flag=1;
	double step=初始值, delta=0.985 //delta belong to [0.985,0.999]
	while (flag) {
		node best=new;
		for (每一个方向, f) {
			node nxt=walk(now, f, step);
			best=max(best, nxt);
		}
		if (best!=now) now=best, flag=1;
		else flag=0;
		step*=delta;
	}
	printf("%d\n", now);
}

---

反例

瞎子爬山爬到最优解就不会往前走了。多峰就不会找到最优解。

改进：
1.多个瞎子一起爬，或一个瞎子爬多次。
2.加一点随机性或突变。

---

模拟退火

灵感来源：中世纪铁匠打铁。
烧铁、很好延展性和韧性。
打铁，每一次形变很大，敲出大体形状。
低温，形变很小，适合制作更精细形状。

设置温度（步长），温度逐渐往下降，设置突变概率，找到最优解。到后期温度越低就很少遇到最劣解了。

如何选择合适突变概率$p$？
1.新状态与原状态差不太多，则应该有相对较大的概率跳过去。
2.越是退火的早期，越可能接受差的突变，越是退火的后期，越不能接受更差的改变。

温度$T$，新老状态差值为$\Delta E$，发生转移（修改最优解）概率为：
$$
P(\Delta E)=
\begin{cases}
1,\ \text{新状态更优}\\
e^\frac{-\Delta E}{T},\ \text{新状态更劣}
\end{cases}
$$
$\Delta E$越大，越容易突变；$T$越大，越不容易突变。

初始温度$T_0$，降温系数$d<1$，终止温度$T_k>0$。
首先温度$T=T_0$，每一次$T=d\cdot T$，当$T<T_k$时结束。

伪代码：

void simulate_anneal() {
	node now=rand();
	double T=1e5, d=0.985;
	while (T>1e-3) {
		node nxt=Go(now, 随机方向走一个距离);
		double delta=del(nxt, now);
		if (exp(-delta/t)>random(0,1)) now=nxt;
		T*=d;
	}
	for (若干次) ans=max(ans, Go(now, 随机方向走一个距离));
}

---

实战：最小圆覆盖

二维平面随机撒点，找半径最小的圆，使得所有$n$个点在圆内。问圆心坐标和半径。

思路：
找到圆心就可以$O(n)$算出来。
对圆心进行模拟退火，对每一个圆心找到最小半径。

每一次$x$和$y$随机走，计算最小半径（最大距离），乘上突变概率。

---

遗传算法（简化版）

多个瞎子扔到山脉中，多个瞎子一起爬。

一群猪扔到岛上，如果猪没死完，会怎样？（生物角度）

伪代码：

void 猪群() {
	for (每一个周期) {
		1.身体不好，无法适应环境的猪大概率挂掉。
		2.活下来的猪们生出了一群小猪。
			2.1.一部分小猪继承了父母的特点，
				在这个基础上产生了微小变异。
			2.2.一部分小猪继承了父母的特点，
				在这个基础上产生了大量变异。
	}
}

100代以后，肯定比第一批更适应岛上的环境的。

遗传算法：
1.一个样本容纳量，每一个个体自然繁衍多少后代、后代突变概率和方式。
2.适当调整模拟轮数及样本容纳量的关系，以取得较好效果。（经验）
小猪定型后，可以代数减少，样本更多。
没突变完，就需要减少样本量，增加代数。

伪代码：

void 遗传算法() {
	int limit=1000, tot=limit; //样本总量&繁衍后的总样本
	for (int i=1; i<=limit; ++i) a[i]=rand(); //随机生成样本
	for (每一个周期) {
		sort(a+1, a+tot+1, cmp);
		tot=limit; //保留优秀的
		for (int i=1; i<=limit; ++i) {
			for (int j=1; j<=10; ++j) a[++tot]=born1(a[i]); //遗传
			for (int j=1; j<=3; ++j) a[++tot]=born2(a[i]); //变异
		}
	}
	for (int i=1; i<=tot; ++i) ans=max(ans, a[i]);
}

问题：
某一个随机样本特别好，几轮后就会发现所有样本都是它的孩子。
一个高原/一个山峰，山峰更高，生在高原上的小猪全部活下来，生在山脚下的小猪全死了。
解决方法：
给小猪编一个姓氏，每一个样本限制每个姓氏的个数，保证多样性。

---

什么情况

什么情况适合基于概率的演化算法？
1.先找正解，罚坐的时候才可以用。
2.需要决策的状态空间较小，或者看起来最优解比较密集。
例如，最小圆覆盖只有$x$和$y$两个维度，或者看起来最优解分布比较密集。
3.没有绑定subtask或多组数据才行，可能会被卡每组最后一个数据。

---

实战：方差 NOIP2021 T3

原题传送门
给定一个长度为$n$的非严格递增正整数序列。
你每次可以选择一个位置$1<i<n$，使得$a_i=a_{i+1}+a_{i-1}-a_i$。
问：这个序列的方差最少是多少。

算法1

完全随机，每次小概率大次数完成大概率。
代码：

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int ll;

inline ll read() {
	ll x=0, f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}

#define N 10005
#define INF 0x7fffffff
int n;
int s, ss;
int b[N], a[N];
ll best=INF;

void simulation() {
	s=0, ss=0;
	for (int i=1; i<=n; ++i) b[i]=a[i], s+=b[i], ss+=b[i]*b[i];
	ll now=n*ss-s*s;
	for (int turn=1; turn<=30000; ++turn) {
		int id=rand()%(n-2)+2;
		ll nxt=b[id-1]+b[id+1]-b[id];
		if (nxt==b[id]) continue;
		ll t=s-b[id]+nxt, tt=ss-b[id]*b[id]+nxt*nxt;
		if (now>=n*tt-t*t || turn<=2000) {
			b[id]=nxt, s=t, ss=tt, now=n*tt-t*t, best=min(best, now);
		}
	}
}

int main() {
	n=read();
	for (int i=1; i<=n; ++i) a[i]=read();
	while ((double)clock()/CLOCKS_PER_SEC<0.99) { //极限卡时
		simulation();
	}
	printf("%d\n", best);
	return 0;
}

Luogu 72pts
评测记录

算法2

当取得最优解后，查分数组一定先变小再变大，发现：
1.每次操作相当于交换了查分数组；
2.答案最小时，差分数组总会是单独的。
状态空间显著变小，只可能往左放或往右放。

代码：

for (double T=1000; T>1e-8; T*=0.996) {
	int p=rad(2,n-1);
	vis[p]^=1;
	int t=calc();
	ans=min(ans, t);
	if ((exp(1.0*fabs(ans-t)/T)>=rad2(0,1))) vis[p]^=1;
	else now=t;
}

纯随机化可以拿到满分。