东拼西凑的一篇东西
算法思想
粒子群算法是模拟群体智能所建立起来的一种优化算法，粒子群算法可以用鸟类在一个空间内随机觅食为例，所有的鸟都不知道食物具体在哪里，但是他们知道大概距离多远，最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。
假如有5只鸟觅食，每个鸟都知道自己与食物的距离，并将此信息与其他鸟共享。一开始，5只鸟分散在不同的地方，每只鸟记下自己离食物最近的位置，称为pbest，pbest0,pbest1,..分别表示5只鸟的pbest，从这里面选一个gbest，组里最好的。每过一秒钟，鸟结合pbest和gbest更新自己的速度v和位置，然后以这个速度飞行1秒，再次更新，最终离食物越来越近。
更新公式如下：
标准粒子群优化算法
其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。
在第一个式子中，第一部分为微粒先前行为的惯性，第二部分为“认知（cognition）”部分，表示微粒本身的思考；第三部分为“社会（social）”部分，表示微粒间的信息共享与相互合作。
PSO速度更新公式各参数意义
PSO参数包括：群体规模m，惯性权重w，加速常数c1和c2，最大速度Vmax，最大代数Gmax。
Vmax决定在当前位置与最好位置之间的区域的分辨率（或精度）。如果Vmax太高，微粒可能会飞过好解，如果Vmax太小，微粒不能进行足够的探索，导致陷入局部优值。该限制有三个目的：防止计算溢出；实现人工学习和态度转变；决定问题空间搜索的粒度。
w惯性权重使微粒保持运动的惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。
c1和c2加速常数代表将每个微粒推向pbest和gbest位置的统计加速项的权重。低的值允许微粒在被拉回来之前可以在目标区域外徘徊，而高的值导致微粒突然的冲向或者越过目标区域。
如果没有后两部分，即c1= c2= 0，微粒将一直以当前的速度飞行，直到到达边界。由于它只能搜索有限的区域，将很难找到好的解。
如果没有第一部分，即w = 0，则速度只取决于微粒当前的位置和它们历史最好位置pbest和gbest，速度本身没有记忆性。假设一个微粒位于全局最好位置，它将保持静止。而其它微粒则飞向它本身最好位置pbest和全局最好位置gbest的加权中心。在这种条件下，微粒群将统计的收缩到当前的全局最好位置，更象一个局部算法。
在加上第一部分后，微粒有扩展搜索空间的趋势，即第一部分有全局搜索的能力。这也使得w的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。
如果没有第二部分，即c1= 0，则微粒没有认知能力，也就是“只有社会（social-only）”的模型。在微粒的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准版本更快，但是对复杂问题，比标准版本更容易陷入局部优值点。
如果没有第三部分，即c2= 0，则微粒之间没有社会信息共享，也就是“只有认知（cognition-only）”的模型。因为个体间没有交互，会陷入自身最优，一个规模为m的群体等价于m个单个微粒的运行。因而得到解的几率非常小。
标准PSO算法流程
- 初始化一群微粒（群体规模为m），包括随机的位置和速度；
- 评价每个微粒的适应度（也就是一个判断好坏标准的函数）；
- 对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；
- 对每个微粒，将它的适应值和全局所经历最好位置gbest的作比较，如果较好，则重新设置gbest的索引号；
- 根据方程（1）变化微粒的速度和位置；
- 如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到2）。
程序实例(转)
计算f(x) = x2 - 20x + 100 的最小值及取最小值时的x。
#define C1 2
#define C2 2
#define VMAX 5.0
#define MAX_ITERATIONS 100 //迭代次数
float rand01() //生成0~1的随机数
{
return (float) (rand()/(double)RAND_MAX);
}
struct particle{
float current;
float pbest;
};
float fitness(float x) //适应度函数
{
return x*x - 20*x + 100;
}
float gbest = 10000;
struct particle p[5]; //粒子位置
float v[5] = {0}; //粒子速度
void init_particles() //粒子信息初始化
{
int i;
for(i = 0; i < 5; i++)
{
p[i].current = -2+i; //随机给定初始位置及速度
p[i].pbest = p[i].current;
}
}
void find_gbest() //全局最优解
{
int i;
for(i = 0; i < 5; i++)
{
if(fitness(gbest) > fitness(p[i].current))
gbest = p[i].current;
}
}
void adjust_v() //速度更新函数
{
int i ;
for(i = 0; i < 5; i++)
{
v[i] = v[i] + C1*rand01()*(p[i].pbest - p[i].current) + C2*rand01()*(gbest - p[i].current);
if(v[i] > VMAX)
v[i] = VMAX;
}
}
void pso()
{
int i,iter_num;
iter_num = 1;
while(iter_num < MAX_ITERATIONS)
{
for(i = 0; i < 5; i++)
{
if(fitness(p[i].current) < fitness(p[i].pbest))
p[i].pbest = p[i].current;
}
find_gbest();
adjust_v();
//更新位置
for(i = 0; i < 5; i++)
p[i].current += v[i];
iter_num ++;
}
}
int main()
{
init_particles();
pso();
printf("After %d iterations,gbest is %f\n",MAX_ITERATIONS,gbest);
return 0;
}
写完这个就想写遗传算法了。。。。。
网友评论