粒子群算法入门

922 阅读4分钟
原文链接: www.jianshu.com

算法描述

粒子群算法是模拟鸟群蜂群的觅食行为的一种算法。

基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。

试着想一下一群鸟在寻找食物,在这个区域中只有一只虫子,所有的鸟都不知道食物在哪。但是它们知道自己的当前位置距离食物有多远,同时它们知道离食物最近的鸟的位置。想一下这时候会发生什么?

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++)

结果


代码地址

Github