基于精英高斯学习的改进鱼群粒子群混合算法

康朝海, 王博宇, 杨永英

(1. 东北石油大学 电气信息工程学院, 黑龙江 大庆 163318； 2. 大庆油田矿区服务事业部 物业管理一公司, 黑龙江 大庆 163000)

0 引 言

在现实生活中, 许多数学和工程问题都可以简化成在可行域内的高维函数寻优问题, 如磨矿过程控制[1], 车辆调度[2], 控制器参数整定[3]等。对此如人工鱼群算法[4], 粒子群算法[5], 蚁群算法[6]等群智能算法被广泛应用解决此类问题。

人工鱼群算法(AFSA： Artificial Fish Swarm Algorithm)是由李晓磊等[4]于2002年基于自然环境中鱼类行为提出的一种仿生智能优化群算法。该算法具有对搜索空间适应能力强, 全局寻优能力良好, 操作实现简单且鲁棒性较好等优点。目前人工鱼群算法除了用于求解函数寻优问题, 还应用于其他多个领域, 并取得一定成果, 如故障诊断[7]、 图像检测识别[8]、 路径规划[9]和网络覆盖优化[10]等。但该算法前期全局搜索盲目性大、 后期收敛速度慢、 虽然能寻找到最优值所在的大致区域但很难找到高精度的最优值。

粒子群算法(PSO： Particle Swarm Optimization)是Kennedy等[5]于1995年通过对聚集生物觅食行为研究后提出的一种群体智能优化算法。该算法具有参数少, 易于实现, 计算速度快, 局部搜索能力强等优点。目前已应用于众多领域, 如电力系统优化[11]、 模式识别[12]和目标跟踪[13]等。但该算法存在全局搜索性能差、 易陷入局部最优、 迭代时易出现停滞现象等缺点。

笔者根据优势互补的改进思想, 用人工鱼群算法的全局搜索性好的优点克服粒子群算法全局搜索性能差的缺点, 同时用粒子群局部搜索能力强的优点克服人工鱼群算法局部搜索性能差的缺点, 提出一种鱼群粒子群混合算法。将两种算法的优点相结合, 解决全局搜索与局部搜索平衡欠佳的问题, 并对2种算法本身存在的初始种群分布不均、 搜索效率欠佳和最终结果精度低的问题采取对应的改进措施。

1 基本人工鱼群算法与标准粒子群算法

1.1 基本人工鱼群算法

通过观察自然界中的鱼类生活习性, 发现鱼群通常会向营养丰富的区域移动, 通过模拟鱼群这一行为特点, 以实现全局寻优, 即基本人工鱼群算法。该算法通过模拟鱼类的觅食、 聚群、 追尾、 随机等行为在搜索区域中进行寻优。4种行为的位置更新公式如下

其中S表示人工鱼最大移动步长,Xi为人工鱼当前所在的位置,Xj为视野范围内食物浓度最高的位置。

1.2 标准粒子群算法

标准粒子群算法是一种典型的群体智能优化算法, 其思想源自于对鸟群觅食模型的研究与行为模拟。算法的搜索机理就是随机初始化一个粒子种群, 每个粒子通过追随局部最优粒子和全局最优粒子的位置实现自我位置的更新, 这种基于最优引导的粒子更新机制贯穿整个算法, 随种群的不断迭代, 粒子群逐渐向最优解靠拢, 直至最终找到最优解。每个粒子通过

2 基于精英高斯学习的改进鱼群粒子群混合算法

人工鱼群算法和粒子群算法都具有结构简单、 容易实现且调节参数少的优点, 因此易于组成混合算法。通过学者们的大量研究, 目前主要有两类算法混合思想： 一类是基于融合思想; 将其中一种算法的公式或操作引入到另一种算法中, 达到全局搜索与局部搜索兼顾的目的[14,15]； 另一类是基于组合思想, 初期用鱼群负责全局的粗搜索, 确定最优值的大致区域, 后期用粒子群算法负责精搜索, 提升最终解的精度[16,17]。笔者采用第2类改进思想并对混合算法进行改进。

2.1 改进的鱼群算法

2.1.1 均匀初始化

针对鱼群算法随机初始化在一定程度上会导致部分初始个体距离过密, 在维度空间上的某些区域分布不均, 进而影响算法在初期搜索全局搜索效率的缺点, 笔者采用一种维度空间均匀初始化的方法对种群进行初始化操作。与采用Logistic混沌映射和Tent映射进行初始化相比, 均匀初始化减少不必要的约束条件和循环操作次数, 保障初始种群在空间内均匀分布的同时, 提高初期搜索效率。其操作方法如下。

1) 根据种群个体总数, 子空间内种群密度系数ρ以及种群个体在各个维度分量的上界Xmax与下界Xmin, 将整个种群所在的空间均匀划分为K个子空间。

2) 在每个子空间内, 随机生成M个种群个体, 通过

建立欧氏距离矩阵, 根据该矩阵及子空间内种群密度系数ρ, 若Dij<ρ‖Xmax-Xmin‖, 则表明xi与xj两个个体距离过近, 剔除其中1个体根据欧式距离矩阵并重新生成一个新的个体代替这个旧个体。其中Dij表示M个种群个体中任意两个体xi=(xi1,xi2,…,xin)与xj=(xj1,xj2,…,xjn)的空间欧式距离,n为种群个体的维数。

3) 最后由这K×M个种群个体构成初始种群, 完成种群初始化。

2.1.2 分组搜索方式

为克服基本人工鱼群算法全局搜索盲目性大, 搜索效率低的不足, 同时强化鱼群算法部分的全局寻优能力。笔者通过一定概率向每次迭代结果反馈较好的方向进行引导[18]和动态种群协作[19,20]相结合的方式, 采用仿照蛙跳算法的分组方式进行分组, 同时对组内优秀个体和一般个体使用不同的位置更新公式, 以及视野和步长的动态调整策略。对优秀个体使用幂函数型自适应函数调整视野及步长, 且对位置更新公式引入全局最优值的扰动变量； 对一般个体使用线性函数型调整, 且对位置更新公式引入组内最优值的扰动变量。此种方法的优点如下。

1) 分组操作可提高并行搜索效率, 同时通过不同组之间的种群个体之间的混合重新分组, 实现不同子群间的信息交流, 提高全局搜索能力。

2) 蛙跳算法的分组方式与根据种群平均适应度值分组相比, 具有更好种群丰富度和全局性[21,22]。

3) 采用不同的优秀个体进行引导, 可增加全局搜索对可行域的覆盖, 提高搜索的遍历性。

4) 幂函数型和线性函数型调整策略的引入, 可使优秀个体更快收敛的同时保证一般个体探索性, 在保障全局搜索能力的同时降低算法的运行时间。

具体的实现方法如下。

1) 分组方式。对初始鱼群所有N条人工鱼, 按适应度值从小到大排序, 将排好序的人工鱼个体分成m组, 每组含p条人工鱼, 满足N=mp, 分组方法为： 第1条人工鱼放入第1组, 第2条人工鱼放入第2组, 类推第m条放入第m组, 第m+1条放入第1组, 依次类推直到划分完毕。每次迭代之后均按此方法排序分组。

2) 视野和步长的动态调整。对于每组内的所有个体, 定义前20%的个体为优秀个体, 其余的为一般个体。对优秀个体, 其视野及步长调整如下

S=VA

(6)

对于组内剩余个体, 其步长及视野调整如式(6)和下式所示

其中Vmax表示视野初始值,Vmin表示视野终止值,iter表示当前迭代次数,Gmax表示最大迭代次数,A∈[0.5,1]的随机数。

3) 组内个体位置更新公式。以聚群行为为例, 优秀个体位置更新公式及其他个体更新公式, 形式如下

其中Xi为人工鱼的位置状态,Xc为但组内人工鱼的中心位置,XB为组内最优人工鱼的位置状态,R为扰动影响因子调节全局或组内最优值对移动方向的影响大小, 对于优秀个体时XG为全局最优人工鱼的位置状态, 对于其他个体时XG为组内最优人工鱼的位置状态。对追尾行为和觅食行为的公式改进方式与聚群行为相同。

2.2 改进的精英高斯学习策略

针对粒子群算法迭代时易出现最优值停滞和最终结果精度低的问题, 笔者采用一种改进精英高斯学习跳出停滞状态, 从而提高最终结果的精度。精英高斯学习[23]是以引入高斯分布为基础, 在原有的最优个体上随机选取某一维加上一个高斯随机扰动项, 且其他维度上保持不变, 从而得到一个新个体, 若新个体适应度值优于原来的个体, 则保留新个体, 否则不保留。其学习方式如下

Pd=Pd+(Xmax-Xmin)Gaussian(μ,σ2)

(9)

d=random(1,D)

(10)

其中P表示最优个体的位置状态,d表示该个体的一个随机维度,Xmax和Xmin为维度分量的上界和下界,μ为高斯分布的均值,σ2为高斯分布的方差,D为总维数。

精英高斯学习也存在变异结果随机性较大, 导致变异的成功率不高[24], 以及在对最优个体进行学习时, 过多的盲目学习对收敛精度提升不稳定且影响算法的运行速度[25]等缺点。针对以上不足, 笔者在已有的精英高斯学习基础上进行以下两个方面的改进。

1) 调整精英高斯学习的调用时机和适用个体。当全局最优值连续3代无变化时, 对全局最优个体和本次迭代中最优的前10%个体进行精英高斯学习,在扩大学习对象的同时降低多次学习对整体算法运行速度的影响。

2) 对精英群体进行有方向的学习。先对个体的所有维度逐一进行高斯学习, 并对每一个维度的结果汇总排序, 选出排名前dbest个维度作为学习方向, 之后对该个体这dbest个维度进行T次高斯学习取最优值, 最优值优于全局最优则替换, 否则不保留, 其他精英个体同样采用此方法处理。通过对学习方向的确定, 降低随机学习过程中的不确定性, 提高精英高斯学习的执行效率。

2.3 混合算法的步骤

综上所述, 基于精英高斯学习的改进鱼群粒子群混合算法的步骤如下。

Step1 设置混合算法中的各个参数。

Step2 根据2.1节改进进行种群位置初始化。

Step3 对种群进行适应度计算并排序分组。

Step4 各组内的前20%优秀个体和普通个体, 各自按照视野及步长的动态调整策略和改进的位置更新公式, 进行聚群、 追尾和觅食等行为。

Step5 判断是否达到全局最优值小于10-4或迭代次数达到最大迭代次数的结束条件, 满足则将全局最优值和公告板中各组前20%个体作为粒子群算法部分的初始粒子, 执行Step6； 否则, 继续执行Step3。

Step6 按照粒子群更新公式更新粒子, 寻找全局最优值。

Step7 判断全局最优值是否连续3代无变化, 满足则按照对全局最优值和本次迭代最优的前10%个体进行改进的精英高斯学习； 否则继续执行Step6。

Step8 判断是否达到最大迭代次数终止条件, 满足则输出最终的全局最优值； 否则, 继续执行Step6。

3 数值仿真实验

3.1 标准测试函数及参数设置

为证明笔者改进算法的优化效果, 选取表1中的6个标准函数进行仿真实验测试对比, 其中Sphere和Rosenbrock为单峰函数, Griewank, Rastringin, Schaffer和Ackley均为复杂的多峰函数。

表1 标准测试函数

与此同时引入标准粒子群算法PSO, 基本人工鱼群算法AFSA以及文献[14]提出的粒子群改进鱼群算法PSO-FSA进行对比, 各算法的参数设置如表2所示, 其中步长按式(6)变化, 惯性权重因子ω按如下所示

ω(t)=[-iter(ωmax-ωmin)/Gmax]+ωmax

(11)

其中ωmax表示惯性权重因子ω的最大值,ωmin表示惯性权重因子的最小值,iter表示当前迭代次数,Gmax表示最大迭代次数。

表2 算法参数设置

3.2 笔者算法与其他算法结果对比分析

为准确比较算法的寻优性能, 将各算法的最大迭代次数设为1 000, 种群规模大小设为81, 维数为30, 4种算法各自独立运行30次, 并通过实验数据和平均寻优结果(适应度值)迭代曲线两种方式说明。表3列出了各算法分别独立运行30次寻优结果的平均值和30次独立运行中出现过的最好结果, 标准差及平均耗时。图1为各算法平均寻优结果(适应度值)的迭代曲线对比图, 横坐标表示迭代次数, 纵坐标为更直观显示, 取平均寻优结果以10为底的对数值。

图1 标准函数适应度值对数迭代曲线对比Fig.1 The standard function fitness value log iteration curve comparison

函数性能指标PSOAFSAPSO-FSA笔者算法Sphere平均值8.74×10-31.93×10-43.14×10-78.92×10-9最好结果7.82×10-51.20×10-55.22×10-82.05×10-10标准差1.43×10-22.09×10-41.53×10-71.70×10-9平均耗时/s7.4339.3769.4678.536Rosenbrock平均值3.50×1003.08×10-43.65×10-31.04×10-5最好结果1.04×1002.69×10-64.38×10-51.14×10-6标准差2.28×1005.41×10-44.13×10-31.05×10-5平均耗时/s8.68612.54110.42310.505Griewank平均值1.48×1002.00×10-21.62×10-41.38×10-6最好结果1.23×10-11.15×10-38.40×10-51.09×10-6标准差2.46×10-11.29×10-21.32×10-41.10×10-6平均耗时/s8.97715.35011.76511.098Rastringin平均值7.67×10-14.94×10-22.91×10-32.00×10-5最好结果6.57×10-15.24×10-51.29×10-64.35×10-7标准差6.80×10-25.41×10-34.13×10-42.38×10-5平均耗时/s10.64014.95712.45312.488Schaffer平均值1.07×10-17.35×10-24.26×10-24.12×10-3最好结果7.82×10-21.22×10-29.72×10-35.30×10-5标准差2.67×10-26.12×10-23.44×10-23.61×10-4平均耗时/s11.05416.19313.91214.031Ackley平均值3.44×10-31.44×10-36.81×10-52.02×10-5最好结果1.57×10-34.00×10-41.16×10-55.64×10-6标准差1.51×10-31.20×10-37.28×10-51.39×10-5平均耗时/s9.78315.0809.84110.082

由图1和表3可知, 对于高维标准函数的极值寻优, 在相同的种群规模和迭代次数下, 标准粒子群算法除了在Sphere函数上能相对收敛, 在其他5个标准函数上均无法收敛到全局最优值。基本人工鱼群算法相比于粒子群算法, 在6个标准函数上寻优精度均优于标准粒子群算法, 但对于复杂的多峰函数其收敛速度相对较慢且易出现停滞现象, 即全局最优值在多次迭代过程中无明显变化, 导致其寻优精度无法提升, 在一定程度上影响算法的计算稳定性。粒子群改进鱼群算法, 由于引入了粒子群算法的相关概念对鱼群算法的行为模式进行优化, 与前两种算法相比, 除了在Rosenbrock函数上, 寻优精度略逊于鱼群算法, 在其他标准函数上寻优精度和收敛速度均有所提升, 尤其是在Sphere, Griewank和Rastringin函数上相对明显。笔者算法通过采用分组鱼群的执行策略与带有高斯学习粒子群算法的结合, 通过图2曲线可看出, 在算法前期适应度值下降速度明显优于其他3种算法, 说明分组鱼群算法部分能较快的寻找到全局最优值所在的大致区域, 在算法后期由于高斯学习的引入, 减少了停滞的迭代次数的同时提高了寻优精度, 对于算法计算的稳定性, 通过表3对比可见, 其提升也较为明显, 尤其是在Griewank和Sphere函数上较为显著。

3.3 均匀初始化和分组策略及精英高斯学习的影响分析

为体现均匀初始化, 分组策略和改进精英高斯学习对改进算法的影响程度, 在与3.2节相同的实验条件下, 分别在无均匀初始化, 无分组策略和无高斯学习的条件下, 以典型的复杂多峰函数Griewank测试其在不同维度下的影响程度。表4列出了在不同维度下根据上述3种条件, 分别独立运行30次的寻优结果平均值, 图2为其平均寻优结果(适应度值)的迭代曲线对比图, 横坐标表示迭代次数, 纵坐标取寻优结果平均值以10为底的对数值。

图2 不同维度下适应度值对数迭代曲线对比Fig.2 The fitness value log iteration curve of the fitness value in different dimensions

维数完整笔者算法无均匀初始化无分组策略无精英高斯学习37.40×10-39.80×10-39.72×10-39.96×10-3152.71×10-53.20×10-42.91×10-31.03×10-2304.01×10-67.43×10-61.64×10-52.22×10-2

由表4和图2可见, 均匀初始化在3维时, 对算法前期的收敛速度影响较为明显, 而在15维和30维时, 其对前期的收敛速度和最终的寻优精度影响有限。分组策略部分, 不论是低维还是高维, 对算法前期的收敛速度影响最大, 且维度越高影响越明显, 同时由于执行鱼群算法迭代部分的次数是固定值, 前期收敛速度慢, 搜索盲目性大使混合算法中鱼群算法部分的寻优精度不足, 导致其向粒子群算法部分提供的优秀初始种群的质量下降, 影响到最终的寻优精度。精英高斯学习部分对最优值的影响最大, 其主要帮助最优个体跳出迭代过程中的停滞, 避免其陷入早熟, 同时加快算法后期的收敛速度和最终的收敛精度。

综上所述, 笔者对算法的改进是可行有效的, 均匀初始化在高维时影响较小, 但在低维时配合分组策略可提高前期的收敛速度和精度, 而分组策略和精英高斯学习的结合, 在任何维度对算法的整体运行效率和最终寻优精度提升显著。

4 结 语

笔者针对基本人工鱼群算法和粒子群算法对高维问题的寻优能力进行了研究, 在混合算法的组合思想基础上, 提出一种改进鱼群粒子群混合算法。算法前期, 针对鱼群算法部分存在初始种群个体分布不均, 搜索盲目性大效率低的问题, 通过均匀初始化进行种群初始化, 优化种群分布, 然后采用仿照蛙跳算法的分组方式对种群进行分组, 同时对组内优秀个体和一般个体使用不同的位置更新公式, 以及视野和步长的动态调整策略, 解决了全局搜索的方向性差和运行效率低的问题；算法后期, 针对粒子群算法迭代最优值停滞, 收敛精度低的问题, 引入一种改进的精英高斯学习操作, 通过调整调用时机和适用范围, 并利用对尝试性学习的结果排序分析确定学习方向, 提升高斯学习的有效性, 减少了迭代过程中的停滞, 解决了算法收敛慢精度低的问题。最后通过标准测试函数测试与其他3种算法的性能比较以及各改进部分的独立影响分析, 证明笔者的算法是可行的。