普通粒子群算法和优化方法

粒子群优化(PSO, particle swarm optimization) 是由Kennedy和Eberhart在1995年提出的一 种群智能优化方法。

优点：好理解容易实现，适合解决极值问题

缺点：容易过早收敛，容易陷入局部最优解，（如果初始点选的不好，可能就会被某个粒子带偏了= =/）

（Java实现）:

package pso;

import java.util.Random;

/**
 * 粒子类
 * 
 * @see dimension
 * @author Flyuz
 */
public class Particle {
    // 维数
    public int dimension = 2;
    // 粒子的位置
    public double[] X = new double[dimension];
    // 粒子的速度
    public double[] V = new double[dimension];
    // 局部最好位置
    public double[] pbest = new double[dimension];
    // 最大速度
    public double Vmax = 2;
    // 最大位置
    public double[] Xmax = { 2, 2 };
    // 最小位置
    public double[] Xmin = { -2, -2 };
    // 适应值
    public double fitness;

    /**
     * 根据当前位置计算适应值 本例子求式子最大值
     * 
     * @return newFitness
     */
    public double calculateFitness() {

        double newFitness = 0;
        if (X[0] == 0 && X[1] == 0)
            newFitness = Math.exp((Math.cos(2 * Math.PI * X[0]) + Math.cos(2 * Math.PI * X[1])) / 2) - 2.71289;
        else
            newFitness = Math.sin(Math.sqrt(Math.pow(X[0], 2) + Math.pow(X[1], 2)))
                    / Math.sqrt(Math.pow(X[0], 2) + Math.pow(X[1], 2))
                    + Math.exp((Math.cos(2 * Math.PI * X[0]) + Math.cos(2 * Math.PI * X[1])) / 2) - 2.71289;
        return newFitness;
    }

    /**
     * 初始化自己的位置和pbest
     */
    public void initialX() {
        for (int i = 0; i < dimension; i++) {
            X[i] = new Random().nextDouble() * (Xmax[i] - Xmin[i]) + Xmin[i];
            pbest[i] = X[i];
        }
    }

    /**
     * 初始化自己的速度
     */
    public void initialV() {
        for (int i = 0; i < dimension; i++) {
            V[i] = new Random().nextDouble() * Vmax * 0.5;
        }
    }
}

针对缺点，提出了 Multi-start PSO 算法，即每迭代若干次后，都保留历史优粒子，粒子全部初始化，以提高粒子的多样性，扩大搜索 空间。又提出了一种动态惯性权重的粒子群优化算法，惯性权重随着迭代次数的增加而降低，在开始阶段具有较强的全局搜索能力，而在后期以 较小的惯性权重能够收敛到优解。

package pso;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class NormalPSO {

    private static double[] gbest;// 全局最优位置
    private static double gbest_fitness = -0x3f3f3f;// 全局最优位置对应的fitness
    private static int particle_num = 10;// 粒子数
    private static int N = 100;// 迭代次数
    private static int c1, c2 = 2;
    private static double w = 1.4;// 惯性因子
    private static List<Particle> particles = new ArrayList<Particle>();// 粒子群

    /**
     * 初始化所有粒子
     */
    public static void initialParticles() {
        for (int i = 0; i < particle_num; i++) {
            Particle particle = new Particle();
            particle.initialX();
            particle.initialV();
            particle.fitness = particle.calculateFitness();
            particles.add(particle);
        }
    }

    /**
     * 更新 gbest
     */
    public static void updateGbest() {
        double fitness = -0x3f3f3f;
        int index = 0;
        for (int i = 0; i < particle_num; i++) {
            if (particles.get(i).fitness > fitness) {
                index = i;
                fitness = particles.get(i).fitness;
            }
        }
        if (fitness > gbest_fitness) {
            gbest = particles.get(index).pbest.clone();
            gbest_fitness = fitness;
        }
    }

    /**
     * 更新每个粒子的速度
     */
    public static void updateV() {
        for (Particle particle : particles) {
            for (int i = 0; i < particle.dimension; i++) {
                double v = w * particle.V[i] + c1 * rand() * (particle.pbest[i] - particle.X[i])
                        + c2 * rand() * (gbest[i] - particle.X[i]);
                if (v > particle.Vmax)
                    v = particle.Vmax * rand();
                else if (v < -particle.Vmax)
                    v = -particle.Vmax * rand();
                particle.V[i] = v;// 更新Vi
            }
        }
    }

    /**
     * 更新每个粒子的位置和pbest
     */
    public static void updateX() {
        for (Particle particle : particles) {
            for (int i = 0; i < particle.dimension; i++) {
                particle.X[i] = particle.X[i] + particle.V[i];
                if (particle.X[i] > particle.Xmax[i])
                    particle.X[i] = new Random().nextDouble() * (particle.Xmax[i] - particle.Xmin[i])
                            + particle.Xmin[i];
                if (particle.X[i] < particle.Xmin[i])
                    particle.X[i] = new Random().nextDouble() * (particle.Xmax[i] - particle.Xmin[i])
                            + particle.Xmin[i];
            }
            double newFitness = particle.calculateFitness();// 新的适应值
            if (newFitness > particle.fitness) {
                particle.pbest = particle.X.clone();
                particle.fitness = newFitness;
            }
        }
    }

    /**
     * 算法主要流程
     */
    public static void process() {
        int n = 0;
        initialParticles();
        updateGbest();
        while (n++ < N) {
            /*
             * Multi-start PSO 算法，即每迭代若干次后，都保留历史优粒子， 粒子全部初始化，以提高粒子的多样性，扩大搜索 空间。
             */
            if (n == N / 2) {
                initialParticles();
                updateGbest();
            }
            updateV();
            updateX();
            updateGbest();
            w -= 0.01; // 动态惯性权重
            System.out.println(n + ". 当前gbest:(" + gbest[0] + "," + gbest[1] + ")  fitness = " + gbest_fitness);
        }
    }

    public static double rand() {
        return new Random().nextDouble();
    }

    public static void main(String[] args) {
        process();
    }
}

改进后，虽然有一定的效果，但是效果不太明显。

后来又提出许多混合粒子群算法，比如遗传粒子群（BPSO）、免疫粒子群（IPSO）、混沌粒子群等（CPSO），针对不同的领域，需选用适合的优化算法。