粒子群算法
喜欢我随机化算法吗
迭代公式
在 维空间中, 每个粒子有速度 , 位置为 , 以及个体最佳位置
还有全局最佳位置
注意是最佳位置, 存的是坐标, 最佳值另存, 只不过最佳值不出现在迭代公式里
那么第 个粒子的速度迭代公式为:
位置迭代公式为:
其中第一项是记忆项, 意为保留一部分原本的速度值
第二项为个体认知项，意为个体经验的影响
最后一项为群体认知项，意为群体经验的影响
一般可以取
其中， 可以采用线性下降，随着迭代轮数从 下降到
就像AI一样
P3382 三分法模板
可以初始化 个粒子，迭代 次得到解
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const long long P = 4e9 + 10;
const double w = 0.5, c1 = 2, c2 = 2;
struct node
{
double v, x, y, pbest, pbestval;
} b[N];
double a[N];
double l, r;
double gbest, gbestval;
std::mt19937 rd(time(0));
int n, m, k;
double Rand(){
return 1.0 * (rd() % P) / P;
}
double f(double x)
{
double now = 1;
double ret = 0;
for (int i = 0; i <= n; ++i)
{
ret += now * a[i];
now *= x;
}
return ret;
}
void update(int i)
{
b[i].v = b[i].v * w + c1 * Rand() * (b[i].pbest - b[i].x) + c2 * Rand() *(gbest - b[i].x);
b[i].x += b[i].v;
if (b[i].x < l)
b[i].x = l, b[i].v *= -1;
if (b[i].x > r)
b[i].x = r, b[i].v *= -1;
b[i].y = f(b[i].x);
if (b[i].y > b[i].pbestval)
{
b[i].pbestval = b[i].y;
b[i].pbest = b[i].x;
}
}
void solve()
{
gbestval = -1.0 * P, gbest = 0;
scanf("%d", &n);
scanf("%lf%lf", &l, &r);
for (int i = n; i >= 0; --i)
scanf("%lf", &a[i]);
m=100;
for (int i = 1; i <= m; ++i)
{
b[i].v = 0;
b[i].pbest = b[i].x = Rand() * (r - l) + l;
b[i].pbestval = b[i].y = f(b[i].x);
if (gbestval < b[i].y)
{
gbestval = b[i].y;
gbest = b[i].x;
}
}
k = 100;
for (int i = 1; i <= k; ++i)
{
for (int j = 1; j <= m; ++j)
{
update(j);
if (gbestval < b[j].y)
{
gbestval = b[j].y;
gbest = b[j].x;
}
}
}
printf("%.5lf\n", gbest);
}
int main()
{
solve();
return 0;
}
|