算法思想

该算法，通过追随当前搜索到的最优值来寻找全局最优

试着想一下一群鸟在寻找食物，在这个区域中只有一只虫子，所有的鸟都不知道它在哪。但是它们知道自己的当前位置距离食物有多远，它们通过相互联系，知道离食物最近的鸟的位置，同时各只鸟在位置不停变化时候离食物的距离也不断变化。

现在把鸟抽象为粒子。

  1. 粒子仅具有两个属性：速度V和位置X。粒子i在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)。
  2. 它们知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi
  3. 每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)

最终，粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

粒子速度和位置的更新

该公式是从上面公式中的一个改进，增加了一个惯性因子。

这两条公式称为标准的PSO算法。

算法实现

举例y=-x*(x-2) 该函数，让PSO寻找该顶点的y值

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
85
86
87
88
89
public class AlgorithmPSO {
    int n=2; //粒子个数
    
    double[] y;
    double[] x;//每个粒子位置
    double[] v;//每个粒子速度v
    //学习因子
    double c1=2;
    double c2=2;

    double pbest[];//每个粒子走过的最好位置
    double gbest;//是pbest中最好的值
    double vmax=0.1; //速度最大值


    //适应度计算函数，每个粒子都有它的适应度
    public void fitnessFunction(){
        for(int i=0;i<n;i++){
            y[i]=-1*x[i]*(x[i]-2);
        }
    }


    public void init(){ //初始化
        x=new double[n];
        v=new double[n];
        y=new double[n];
        pbest=new double[n];
        /***
         * 本来是应该随机产生的，为了方便演示，我这里手动随机落两个点，分别落在最大值两边
         */
        x[0]=0.0;
        x[1]=2.0;
        v[0]=0.01;
        v[1]=0.02;
        fitnessFunction();
        //初始化当前个体最优位置，并找到群体最优位置
        for(int i=0;i<n;i++){
            pbest[i]=y[i];
            if(y[i]>gbest) gbest=y[i];
        }
        System.out.println("算法开始，起始最优解:"+gbest);
        System.out.print("\n");
    }


    public double getMAX(double a,double b){
        return a>b?a:b;
    }


    //粒子群算法
    public void PSO(int max){
        for(int i=0;i<max;i++){//迭代次数max
            double w=0.4;//惯性因子
            for(int j=0;j<n;j++){
                //更新位置和速度
                v[j]=w*v[j]+c1*Math.random()*(pbest[j]-x[j])+c2*Math.random()*(gbest-x[j]);
                if(v[j]>vmax) 
                    v[j]=vmax;//控制速度不超过最大值

                x[j]+=v[j];//位置变化
                
                //越界判断，范围限定在[0, 2]
                if(x[j]>2) x[j]=2;
                if(x[j]<0) x[j]=0;
                
            }
            fitnessFunction();//更改y值
            //更新pbest和gbest
            for(int j=0;j<n;j++){
                pbest[j]=getMAX(y[j],pbest[j]);
                if(pbest[j]>gbest) 
                    gbest=pbest[j];
                System.out.println("粒子n"+j+": x = "+x[j]+"  "+"v = "+v[j]);
            }
            System.out.println("第"+(i+1)+"次迭代，全局最优解 gbest = "+gbest);
            System.out.print("\n");
        }
        
    }
    
    public static void main(String[] args){
    	AlgorithmPSO ts=new AlgorithmPSO();
        ts.init();
        ts.PSO(100);
    }

}

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
算法开始，起始最优解:0.0

粒子n0: x = 0.004  v = 0.004
粒子n1: x = 0.0  v = -5.50216355503498
第1次迭代，全局最优解 gbest = 0.007984

粒子n0: x = 0.014336945856940293  v = 0.010336945856940293
粒子n1: x = 0.0  v = -2.187807943275182
第2次迭代，全局最优解 gbest = 0.02846834369737575

...

粒子n0: x = 0.9999999999963437  v = -7.097994640685072E-12
粒子n1: x = 1.0000000000000309  v = 4.865719800421376E-14
第100次迭代，全局最优解 gbest = 1.0