学习基于Java的高斯分布逃逸的粒子群算法_java 计算list高斯分布

学习基于Java的高斯分布逃逸的粒子群算法

前言

在之前的文章里，初步的介绍并实现了基于JAVA的标准粒子群算法，详情见：学习基于Java面向对象的标准粒子群算法 。粒子群算法具备简单、收敛快、计算复杂度低等优点，但同时也存在以下问题：多样性丢失、容易陷入局部最优等。因此，粒子群算法也在不断被研究优化改进方案，最近看了一些相关的文献，从中学习到了一点点，这里也和各位有兴趣的童鞋分享下

粒子群算法的优化方向

目前针对粒子群效果的改进主要分为下面三个方面

• 参数调整
• 组合算法
• 算法调整

参数调整：顾名思义，就是针对具体的问题，了解其特征，对应调整粒子群算法的参数，如迭代次数，种群数量，学习因子等
组合算法：就是将粒子群算法结合其他优化算法 如遗传算法，模拟退化算法等，一般算法混合方式，是追求互补性为目的，提升算法的效果
算法调整：同样顾名思义，就是针对标准粒子群算法，分析特征与收敛性，研究改进的算法步骤，如结合逃逸策略，免疫策略等优化算法

粒子群算法的分析

本文的思路，是基于算法调整方面，因此先初步分析下粒子群算法（下面简称PSO）的特征与文献分析。

粒子的拓扑方式

从前文的简要介绍可知，PSO主要依赖群体信息共享机制这一特点，使群体有统一的行为方向。这里结合文献《具有自适应逃逸的环状全互连结构粒子群算法》的说法，这种信息共享机制的传播可抽象为粒子交互拓扑结构。常见的粒子的拓扑结构有以下四种

• 全互连
• 环形结构
• 冯．诺依曼型结构
• 四簇结构

全互连拓扑结构中的粒子与其他粒子直接相连，这种拓扑结构具有最小的直径、最短的平均路径长度，所以这种结构的寻优速率很快，缺点是会陷入局部收敛的问题．环形结构中的种群粒子只与相近的两个邻居粒子通信传递信息，其较大的直径和平均长度使得消息传播很慢，在算法的效率上环形结构有很好的寻优效果但是寻优速率很慢．冯．诺伊曼型拓扑结构和四簇拓扑结构都是一种立体结构．在粒子的收敛速度上，相比于环形结构，这两种结构表现要好；而且也能够更好的利用粒子的多样性．但是这两种结构自身也存在很多缺点．相关图如下：

粒子的分布方式

PSO算法，初始化分布基于解空间的随机分布，后根据最优解进行逐步搜索。这里结合文献《基于高斯变异和自适应参考点的MOPSO优化算法》的说法，标准PSO优化算法在更新个体最优值和全局最优值的过程中，粒子通常会表现出早熟的现象，整个粒子群中的粒子提早终止变异，陷入部分极值。研究发现，在粒子位置更新过程中，适当地添加一些扰动，很容易使某些解值跳出局部最优。

算法的流程

有前文得知，粒子群算法具有局部收敛特征，因此对于算法陷入局部最优解的感知和跳出策略也是改进方向之一，这里主要参考文献《具有自适应逃逸的环状全互连结构粒子群算法》与《改进的粒子群算法及收敛性分析》的相关描述总结：：当算法运行过程中，连续N代变化幅度低时，说明此时算法出现停滞且种群多样性较差，需采用逃逸策略来产生新一代的粒子群，跳出局部极值。

高斯分布的逃逸粒子群算法

基于上述方面的分析与相关文献的学习，本次对其两个维度的进行改进求解（分布方式，算法流程）。

算法思路

首先还是按照标准粒子群算法，初始化种群位置与速度，计算适应度。然后开始迭代，迭代过程中，当连续几次种群最优值变化幅度小于设定波动阈值，且连续次数小于设定次数阈值，则判断种群进入局部最优，进行逃逸策略，逃逸策略主要包括，种群分组：适应度排序，前n个粒子和剩余粒子分为AB两组，分别计算，A组粒子保持当前逻辑，进行局部搜索，B组粒子添加扰动项（本文选择高斯分布扰动，分布样本才用A组的优质粒子信息，保留种群的先前经验），跳出局部极值，进行全局搜索，最后当达到最大迭代次数，算法结束。

算法改动点

算法新增了以下参数

算法的迭代流程改动

速度更新加入扰动项
$$\hat{\mu }=\overline{x}=\frac{1}{n}\sum _{i=1}^n{x}_i$$
$$\widehat{{\delta }^2}=\frac{1}{n}\sum _{i=1}^n(x_i-\overline{x})$$
$$gaussian=N(\hat{\mu }，\widehat{{\delta }^2})$$
$$v=w\ast v+c1\ast rand()\ast (pbest-x)+c2\ast rand()\ast (gbest-x)+c3\ast rand()\ast (gaussian-x)$$

示例

对于一个50维的sphere函数
$$y=\sum _{i=1}^n{x}_i^2$$
$$(-100<x_i<100)$$
$$n=50$$
求其最小值，一眼便知道其最小值为0，解为（0，0，0，0，0，0，0）
我们假设：粒子群总数为30 ，速度权重在0.9-0.4之间，学习因子c1=1.2，c2=1.5，c3=2.7，最大迭代次数200，波动阈值500，次数阈值5，a组数量10
多次执行标准粒子群与高斯粒子群算法，算法运行图如下：

红色为标准粒子群算法，橙色为高斯分布逃逸粒子群算法

后记

本期的内容对应的代码库：swarmIntelligence
从运行结果图，高斯分布逃逸粒子群算法前期收敛速度略慢与标准粒子群算法，但在高维问题中，后期收敛优于标准粒子群算法，可以跳出局部极值。