粒子群算法入门及实践
2017-05-31 本文已影响4222人
草稿纸反面
算法描述
粒子群算法是模拟鸟群蜂群的觅食行为的一种算法。
基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。
试着想一下一群鸟在寻找食物，在这个区域中只有一只虫子，所有的鸟都不知道食物在哪。但是它们知道自己的当前位置距离食物有多远，同时它们知道离食物最近的鸟的位置。想一下这时候会发生什么？
鸟A：哈哈哈原来虫子离我最近！
鸟B,C,D：我得赶紧往 A 那里过去看看！
同时各只鸟在位置不停变化时候离食物的距离也不断变化，所以一定有过离食物最近的位置，这也是它们的一个参考。
鸟某某：我刚刚的位置好像靠近了食物，我得往那里靠近！
综上，影响鸟的运动状态变化有下面两个因素：
- 离食物最近的鸟的位置
- 自己之前达到过的离食物最近的位置
而鸟每次的位置变化除了考虑上面两个因素还有一个因素: 惯性！
所以考虑这三个因素，位置变化量 v 的公式如下：
可以预见的是，经过不断的调整，鸟群会向食物方向聚集，达到目标。
学一个算法最好的方法是找个题，把它写出来
实践
用粒子群算法求下面函数的最大值（注：这次我用 java 写的）
思路
函数的极值用遗传算法来解，主要分成五步
① 初始化位置
② 计算每只鸟的适应度
③ 找到每只鸟自己的极值，以及整个鸟群的极值
④ 计算位置变化量，改变位置
⑤ 重复步骤 2~4 一个较大的次数使得它趋于稳定
位置类
写一个位置类保存粒子的位置以及粒子在该位置的适应度。
class Posiotion{
private double x;
private double y;
private double f;
Posiotion(double x,double y){
this.x=x;
this.y=y;
}
public double getX() {
return x;
}
public double getY() {
return y;
}
public double getF() {
return f;
}
public void setF(double f) {
this.f = f;
}
public void setX(double x) {
this.x = x;
}
public void setY(double y) {
this.y = y;
}
public String toString(){
return " x: "+x+" y: "+y+" f: "+f;
}
}
适应函数
很好理解，就是把 x,y 带入 f(x,y) 的返回值。
public void fitnessFunction(){//适应函数
for(int i=0;i<n;i++){
double x=p[i].getX();
double y=p[i].getY();
if (x<30&&y<30){
p[i].setF(30*x-y);
}else if (x<30&&y>=30){
p[i].setF(30*y-x);
}else if (x>=30&&y<30){
p[i].setF(x*x-y/2);
}else if (x>=30&&y>=30){
p[i].setF(20*y*y-500*x);
}
}
}
步骤一 初始化位置
随机初始化 n 个粒子，并在范围内随机粒子的位置，计算并保存粒子的适应度。
注意，这里 n 不能太小，太小可能位置变化会限定在一个范围内而一直找不到最优值。
public void init(){ //初始化
p=new Posiotion[n];
v=new Posiotion[n];
pbest=new Posiotion[n];
gbest=new Posiotion(0.0,0.0);
/***
* 初始化
*/
for(int i=0;i<n;i++){
p[i]=new Posiotion(Math.random()*60,Math.random()*60);
v[i]=new Posiotion(Math.random()*vmax,Math.random()*vmax);
}
fitnessFunction();
//初始化当前个体极值，并找到群体极值
gbest.setF(Integer.MIN_VALUE);
for(int i=0;i<n;i++){
pbest[i]=p[i];
if(p[i].getF()>gbest.getF()){
gbest=p[i];
gbest.setF(p[i].getF());
}
}
System.out.println("start gbest:"+gbest);
}
步骤二 计算每只鸟的适应度
调用方法就好了
fitnessFunction();
步骤三 找到每只鸟自己的极值，以及整个鸟群的极值
for (int j=0;j<n;j++){
if (pbest[j].getF()<p[j].getF()){
pbest[j]=p[j];
}
if(p[j].getF()>gbest.getF()){
gbest=p[j];
gbest.setF(p[j].getF());
}
}
步骤四 计算位置变化量，改变位置
用上面说的公式算出位置变化量，并且改变位置。
同时由于 速度 v 以及 位置 x,y 是有范围的，我加上了范围检测，若超出边界则直接设为边界值。
for(int j=0;j<n;j++){
//更新位置和速度
double vx=w*v[j].getX()+c1*Math.random()*(pbest[j].getX()-p[j].getX())+c2*Math.random()*(gbest.getX()-p[j].getX());
double vy=w*v[j].getY()+c1*Math.random()*(pbest[j].getY()-p[j].getY())+c2*Math.random()*(gbest.getY()-p[j].getY());
if (vx>vmax) vx=vmax;
if (vy>vmax) vy=vmax;
// System.out.println("======"+(i+1)+"======vx:"+vx);
v[j]=new Posiotion(vx,vy);
// System.out.println("======"+(i+1)+"======v[j]:"+v[j]);
p[j].setX(p[j].getX()+v[j].getX());
p[j].setY(p[j].getY()+v[j].getY());
//越界判断
if(p[j].getX()>=60) p[j].setX(59.9);
if(p[j].getX()<=0) p[j].setX(0.1);
if(p[j].getY()>=60) p[j].setY(59.9);
if(p[j].getY()<=0) p[j].setY(0.1);
}
步骤五 重复步骤 2~4 一个较大的次数使得它趋于稳定
用 for 循环完成想要的迭代次数，这里我设定 max =10000
for(int i=0;i<max;i++)
结果
