写在前面
在大大的花园里面挖呀挖呀挖,挖大大的坑呀寻大大的WA。
官方解释
利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程。(这个解释不美丽.......)
诡异的故事法解释
那是一个暴风雨之夜,伴随着一声巨响,空气开始震动,狂风忽然吹向东方,比先前任何一场气流都猛烈,在没有蜡烛的黑夜之中,一切都变得影影绰绰,墨黑色的天空下有一团浓厚的黑色向外扩张,某种仿佛无定形烟云般的东西流星般向东方坠落,化作数百只小wa,在花园之中寻找遗失的宝藏......
小wa们为了提高效率,会时时汇报自己的进展,给整个wa群提供自己目前探测到的最有可能找到宝藏的方向,多方建议的汇合会为全体小wa指引方向,每一只小wa又有自己的想法,所以每只小wa都会既向全局已知最优方向行走又向个体认为的最优方向行走。
基本原理
假设在\(D\)维的目标搜索空间中,有\(N\)个粒子形成粒子群,
第\(i\)个粒子表示为一个\(D\)维向量 \(X_i=(x_{i_1},x_{i_2}. . . x_{i_D})\)
第\(i\)个粒子的飞行速度为一个\(D\)维向量 \(V_i=(v_{i_1},v_{i_2}. . . v_{i_D})\)
在第\(t\)代的第\(i\)个粒子向第\(t+1\)代进化时$$v_{ij}(t+1)=wv_{ij}(t)+[p_{ij}(t)-x_{ij}(t)]+[p_{gj}-x_{ij}]$$ $$x_{ij}(t+1)=x_{ij}(t)+v_{ij}(t+1)$$
应用
在一定定义域求一个函数最大或最小值
局限性
易收敛为局部最优,迭代后期收敛速度慢。
例题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
double Rand()
{
return (double)rand() / RAND_MAX;
}
struct vec
{
double x,y;
vec operator + (vec a)
{
return {x+a.x,y+a.y};
}
vec operator - (vec a)
{
return {x-a.x,y-a.y};
}
vec operator * (double a)
{
return {x*a,y*a};
}
vec operator / (double a)
{
return {x/a,y/a};
}
};
struct node
{
vec v,s,ps;
double f,pf,w;
};
node e[510];
vec a,b,c,d,ba,cd;
double p,q,r;
double allf=1e18;
vec alls;
double dis(vec x,vec y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double f(double x,double y)
{
return x+y+dis(a+ba*x,d+cd*y)/r;
}
double xx,yy;
void update(int a)
{
e[a].v=e[a].v*e[a].w+alls+e[a].ps-e[a].s*2;
e[a].s=e[a].s+e[a].v;
if(e[a].s.x<0) e[a].s.x=0,e[a].v.x=-e[a].v.x;
if(e[a].s.y<0) e[a].s.y=0,e[a].v.y=-e[a].v.y;
if(e[a].s.x>xx) e[a].s.x=xx,e[a].v.x=-e[a].v.x;
if(e[a].s.y>yy) e[a].s.y=yy,e[a].v.y=-e[a].v.y;
e[a].f=f(e[a].s.x,e[a].s.y);
if(e[a].f<e[a].pf) e[a].ps=e[a].s,e[a].pf=e[a].f;
}
int main()
{
srand(time(0));
scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
scanf("%lf%lf%lf",&p,&q,&r);
xx=dis(b,a)/p;
yy=dis(d,c)/q;
ba=b-a;
cd=c-d;
if(!xx)
{
ba.x=ba.y=0;
}
else
{
ba=ba/xx;
}
if(!yy)
{
cd.x=cd.y=0;
}
else
{
cd=cd/yy;
}
for(int i=1;i<=500;i++)
{
e[i].w=Rand();
e[i].s.x=e[i].ps.x=Rand()*xx;
e[i].s.y=e[i].ps.y=Rand()*yy;
e[i].f=e[i].pf=f(e[i].s.x,e[i].s.y);
e[i].v.x=e[i].v.y=0;
if(allf>e[i].pf)
{
allf=e[i].pf;
alls=e[i].ps;
}
}
for(int i=1;i<=900;i++)
{
for(int j=1;j<=500;j++)
{
update(j);
if(allf>e[j].pf)
{
allf=e[j].pf;
alls=e[j].ps;
}
}
}
printf("%.2lf",allf);
}