P5544 [JSOI2016] 炸弹攻击1 题解
Link_Cut_Y · · 题解
这是一篇遗传算法的题解，截止到 2023.09.23 是最优解。
如果不知道遗传算法，欢迎到我的博客阅读：浅谈遗传算法。
希望能够借这篇题解普及一下遗传算法。
简要题意
给定平面上
题目分析
既然要使用遗传算法，就必然要考虑下面三点：
-
染色体设计：显然，我们需要存储当前圆的圆心坐标、半径。
-
适应度函数（
\text{calc\_fitness} ）：对于一个个体，其能炸毁的敌人越多，其适应度（\text{fitness} ）越大，该个体越优。这部分显然可以O(m) 实现。 -
交配函数（
\text{mate} ）：可以随机两个向量\overrightarrow{dx}, \overrightarrow{dy} ，然后将圆心向这两个向量方向平移即可。
写完以后交上去，你会惊喜的发现，这个算法收敛速度并不符合预期。因此需要一些奇特优化：
-
普通优化：玄学调参们。
我不会告诉你我调了九页的。 -
奇技淫巧：我们发现对于位移向量
\overrightarrow{dx}, \overrightarrow{dy} ，如果直接随机两个，可能导致变异过大，导致收敛精度过低。因此，我们参考模拟退火，设计一个温度T 。每次随机时，向量模长都在[-T, T] 范围内随机，而T 随着迭代次数的增加而递减。这样，就可以提高收敛精度了。
事实证明，这个优化力度非常大。轻松跑到了最优解。
代码如下：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#define x first
#define y second
#define db double
#define TIMES 30
#define POPULATION 300
using namespace std;
const int N = 10010;
const double eps = 1e-6;
int n, m; db R, lim = 1e4;
//这里的 lim 就是用来调整随机向量的模长的。
struct Enemies {
db x, y;
}Enemy[N];
struct Buildings {
db x, y, r;
}Build[N];
int random(int l, int r) { // 产生从 l 到 r 之间的随机整数
return rand() % (r - l + 1) + l;
}
double rand_db(double l, double r) {
return (double)rand() / RAND_MAX * (r - l) + l;
}
db dist(db x1, db y1, db x2, db y2) {
db dx = x1 - x2;
db dy = y1 - y2;
return sqrt(dx * dx + dy * dy);
}
// 下面正式进入遗传算法
struct Individual { // 存储个体信息的结构体
db x, y, r; // 个体的横纵坐标和半径
int fitness; // 适应度
db calc_r(db x, db y);
Individual(db x, db y);
Individual mate(); // 交配
int calc_fitness(); // 计算适应度
bool operator < (const Individual& tmp)const {
return fitness > tmp.fitness;
}
};
db Individual::calc_r(db x, db y) {
double r = R;
for (int i = 1; i <= n; i ++ )
r = min(r, dist(x, y, Build[i].x, Build[i].y) - Build[i].r);
r = max(r, 0.0);
return r;
}
Individual::Individual(db x, db y) {
this -> x = x, this -> y = y, this -> r = calc_r(x, y);
this -> fitness = calc_fitness();
}
Individual Individual::mate() {
db chx = x, chy = y;
db dx = rand_db(0, lim), dy = rand_db(0, lim);
int opx = rand() & 1, opy = rand() & 1;
chx += dx * (opx ? 1 : -1), chy += dy * (opy ? 1 : -1);
return Individual(chx, chy);
}
int Individual::calc_fitness() {
int cnt = 0;
for (int i = 1; i <= m; i ++ )
if (dist(this -> x, this -> y, Enemy[i].x, Enemy[i].y) - this -> r <= eps)
cnt ++ ; return cnt;
}
int main() {
srand(998244353);
scanf("%d%d%lf", &n, &m, &R);
for (int i = 1; i <= n; i ++ )
scanf("%lf%lf%lf", &Build[i].x, &Build[i].y, &Build[i].r);
for (int i = 1; i <= m; i ++ )
scanf("%lf%lf", &Enemy[i].x, &Enemy[i].y);
db sx = 0.0, sy = 0.0;
for (int i = 1; i <= m; i ++ )
sx += Enemy[i].x, sy += Enemy[i].y;
sx = (db)sx / m, sy = (db)sy / m;
vector<Individual> population;
for (int i = 0; i < POPULATION; i ++ ) {
db x = rand_db(0.0, sx * 5.0) * (rand() & 1 ? 1 : -1);
db y = rand_db(0.0, sy * 5.0) * (rand() & 1 ? 1 : -1);
population.push_back(Individual(x, y));
}
for (int i = TIMES; i >= 1; i -- ) { // 这里的 i 被当做了 t
sort(population.begin(), population.end());
vector<Individual> new_population;
int s = (10 * POPULATION) / 100;
for (int i = 0; i < s; i ++ ) // 保留精英种子
new_population.push_back(population[i]);
s = POPULATION - s;
while (new_population.size() < POPULATION) {
int len = population.size();
Individual p = population[random(0, 100)];
Individual q = p.mate();
double delta = q.fitness - p.fitness;
if (delta < 0) new_population.emplace_back(q);
else if ((double)exp(delta / i) > (double)rand() / RAND_MAX)
new_population.emplace_back(q); // 概率接受
}
population = new_population; lim *= 0.75;
}
printf("%d\n", population[0].fitness);
return 0;
}物竞天择，适者生存。这才是算法真正的意义。