求解高维复杂连续优化问题的粒子群算法研究

潘允敬

（厦门海合达电子信息股份有限公司，福建 厦门361009）

0 引 言

随着时代发展，计算理论愈发复杂化，待优化问题逐渐多样化.传统的优化方法不能满足现代工业科学等领域的需求，遇到的问题也不只是单纯的凸优化问题.研究者为寻求更好的优化技术而着眼于群智能优化方法的研究.群智能算法是一种模仿自然生命演化方式，从而进行抽象为数学模型的一种方法，例如模仿蚂蚁觅食的蚁群算法[1]和模拟鸟类觅食的粒子群优化算法[2]，借鉴神经遗传方面进化知识抽象的遗传算法[3]，简化变异方式提出的差分进化算法[4]，以及近年来提出的比较经典的萤火虫算法以及果蝇优化算法[5-6].这类算法具有强大的并行运算与独特的自组织信息交流方式，在一些非线性、多峰值问题上，具有良好的分布优化性能.

粒子群算法自提出以来得到广泛关注，研究者从多种角度，以不同的方式对其进行改进以使其可以应对更多问题.王碧等[7]以增加粒子群迭代更新中的探索能力为主，提出一种返巢策略，在更改原始粒子群学习因子的背景下，新的更新策略有效缓解了粒子群后期开发能力不足的劣势.群智能算法中利用混沌系统进行算法位置初始化操作比较常见，目的是为了保证初始化种群随机分布不会过于单一.文献[8]中引入混沌系统操作对粒子群进行更改，不同于传统的初始化操作，该改进算法是在算法进化过程中以一种交替转换的方式进行状态的牵引，整体种群在一种动态序列中不断进行更新变化的.算法进化后期粒子间差异逐渐降低，针对这种缺陷，文献[9]中判断进化后期最优解不再更新时，利用莱维飞行的操作进行局部空间之外的搜索，发现这种方式可以有效避免局部最优现象.生物进化过程中个体的变异有可能变得更好也有可能变得更坏，在粒子群中如何以变异的方法控制算法向好的方向进化？文献[10]中分析粒子群收敛点，以迭代过程中最佳位置为基准进行高斯扰动，文献[11-12]分别给定不同的变异概率进行变异控制.文献[12-14]都用到了变异的方式，不过采用的变异方式都不同.除变异之外，利用设计的精英学习方法或者自定义搜索的空间划分模式结合改进算法，都取得不错的效果.

文章在前人的研究基础之上，研究粒子群进化过程中，如何进行种群变异，才可更好地在进化后期分化种群聚集性.利用分组变异的方式，在粒子群进化过程中尽可能进行解空间搜索.在算法后期，种群多样性丧失难以避免，利用反向认知与学习的方式可有效跳出循环.

1 粒子群算法

现在采用的一般粒子群进化公式如公式（1）、公式（2）所示，其中v表示第i个个体的速度，w为第 t代的学习权重，c1、c2表示学习因子，r1、r2都是分布在（0,1）之间的随机数.pbest与gbest分别记录第t代粒子群算法搜索得到的个体最优位置与全局最优位置.根据公式求出的速度，每个粒子个体利用公式进行位置迁移.

从进化公式可以看出每个粒子都具有自己的进化轨迹，通过相互协作的方式在解空间中迭代进行搜索.高度的自组织并行搜索方式是粒子群独特优势.

2 分组变异与反向进化的粒子群算法

2.1 基本思想描述

根据粒子群算法的进化公式可知，种群之间的粒子群通过信息共享，各个个体利用自身保留的最佳位置与当代全局最佳位置学习，从而达到全局最优解或者全局近似最优解.在有限空间的计算方式下，在复杂问题上往往没有一个完美的方法可以保证最终得到的解是全局最优解.因此需要在相同的实验环境中得到精度相对较高的近似解.

为了提升求解问题最终解的质量，采用分组变异的方式，这种方式不同于传统的变异方式，不是单纯的在种群进化得到的解不更新时，对种群中的某一个个体或者一部分个体进行随机扰动，也不是针对gbest所在位置进行扰动.单纯的对最优位置进行变异操作，其原理是牵引种群向当前停滞时的全局最优解的某一个邻域进行迁移，重新进行搜索，一定程度上是可以扩大搜索范围，但是在本质上没有进行整体空间的遍历.种群搜索停滞，说明其整体陷入局部环境，在多峰问题中种群停滞很容易出现，进行几次迭代之后没有新解的出现，可以认为停滞现象出现，利用有效的方式进行改善这种现象，可以增大探索到更优解的可能.

采用反向进化的方式，在算法更新多次没有新解出现，则向最优位置的反方位置进化，可增大寻找全局优化解的概率.

2.2 分组变异

将种群分为N个组，每个小组采用不同的变异算子进行变异，其变异概率p采取递减方式，如公式（3）所示，随着迭代次数的增加，变异概率线性递减.公式（4）中δ为高斯变异算子.算法执行初，为保证尽可能的在解空间内遍历采用较大的变异概率，随着迭代的进行最终要趋于收敛，因此变异概率幅度逐渐趋于0.

根据分组的不同变异算子的取值是不同的，初始随机生成的高斯变异数会随着种群更新而发生变化，具体变化按公式进行.

分组变异执行流程如下：

step1.输入适应度值，种群分组数以及变异概率的最大最小值；

step2.将输入的种群按适应度fitness排序；

step3.将排好序的个体划分为N个小组；

step4.产生N组高斯随机数；

step5.根据公式更新变异算子；

step6.对于每一个小组内的个体按照公式进行变异操作；

step7.将变异后的个体适应值与原适应值比较，若优于则选择变异后的个体，否则淘汰.

step8.返回变异后生成的种群位置.

2.3 反向进化

由于算法进化过程时一个整体趋向极值点的过程，在进化的过程中采用反向进化策略影响收敛速度，甚至导致在有限范围内求解精度更低.因此反向进化不会伴随整个算法的进程，只在判断种群进化停滞时采用反向进化方式寻找突破局部限制的位置.

反向进化策略具体执行公式（6），其中low与up分别是预求解问题的空间下界与上界.执行过程中越界的粒子群一般采用上下限赋值的方法，这种方法易出现多个个体聚拢于边界的问题，新算法处理越界粒子采用空间映射的方式.

假设粒子越界执行公式（7）.这种方式在一定程度上也保持了搜索过程中种群的灵活性.对于反向学习执行选择是：当算法连续达到总迭代次数的1/20次没有更新最优解，则认定算法陷入局部最优解范围，采用反向学习，一直搜索到更新新解或者算法执行终止为止.

综上所述，新算法的伪代码如下：

1）初始化种群规模：Maxsize、维度Dim、迭代次数T;

2）求出初始各个个体的适应度；

3） While t＜T

4） For i＜Maxsize

5） For d＜Dim

6） 执行公式（1）（2）;

7） End

8）End

9）根据变异概率，进行分组变异；

10）记录全局最优解gbest的值;

11） If gbest（t+1）=gbest（t）

12） Record++;

13） End

14） If Record＞=T/20

15） 利用反向进化中公式生成反向解；搜索的新解更优则进行位置替换；

16） End

17）End

18） Return min（f（x））;

3 实验分析

3.1 实验设计

设置新改进的算法与原算法分别在4组测试函数上进行性能比较，具体测试函数信息如表1所示，分别在30维与50维的条件下进行算法对比.算法参数设定为：最大迭代次数：1000、种群规模：20.

表1 测试函数表

3.2 实验结果

通过在30维与50维的条件下，对粒子群算法与改进后的分组变异与反向进化的粒子群算法进行横向比较，算法的迭代过程见图1（其中为方便观察进化曲线，对数据用LOG10进行处理）.由图1可以看出新的改进算法在4种测试函数上都具有更好的寻优精度.50维度的时候算法的搜索精度明显更低，这是因为随着维度上升，局部陷阱越来越多.进化曲线变化说明，在算法迭代后期新算法可以一定程度保证算法跳离局部最优值点，开辟新的搜索空间.

表2 实验结果对比

表2中是新算法与粒子群算法在30维的条件下，进行优化4个函数的是实验结果，给出独立运行100次的平均数据.表2中的各项评定指标Min、Max、Mean、Std、Time 分别表示独立运行算法100次后取得的最小值、最大值、均值和标准差以及算法平均运行1次花费的时间.算法对比的指标分别用：迭代范围内的最小值、最大值、均值以及判断算法稳定程度的标准差，后面列出平均运行时间.

从表2中得出，新算法在平均运行时间上比原来的粒子群算法都要高，这是因为，新算法中增加的变异机制与反向生成解方法，在进行判断运行时需要花费运行时间，虽然运行时间有所增加，但都在一个数量级上，是可以接受的.

针对单峰函数F1，保证较快的收敛速度的同时，新算法平均精度高于粒子群8个量度点.F2虽然是一种单峰函数，但该函数求解精度一直不高，文中提出算法虽没有以倍数级提升求解精度，但在最终的解质量上还是优于原算法.F3与F4都是多峰问题，新算法在求解精度上分别提高5、6个精度点.这可以很好论证新改进的算法在解空间内具有好的搜索性能，可以一定程度上避免局部最优.

4 结 论

文章研究了粒子群算法在求解较高维优化问题时出现的早熟现象，引入分组变异的方式，使粒子群进化过程中可以在保持种群多样性的同时有针对性的遍历解空间.进化后期种群共享信息不足时，采用反向进化的操作进行跳出局部环境操作.经过对4个高维函数的测试，证明新提出的算法在收敛速度与优化精度上都具有更高的性能.是利用最优解连续多次不更新的方法来判断种群停滞，然后再进行反向进化的.这种方式的灵活性较低，具体要判断多少次最优解不更新才合适？这里无法给出严格的数据，这也是文章不足之处.以后的研究重点是寻找更为精确的方法判定何时利用反向进化策略来深度优化.

[1]Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on evolutionary computation,1997,1(1):53-66.

[2]Kennedy J,Eberhart R.Particle swarm optimization[C]//IEEE International Conference on Neural Networks,1995.Proceedings.IEEE,2002:1942-1948.

[3]苗振华，孙旭东，邵诚.一种并行变异自适应遗传算法及其性能分析[J].信息与控制，2016，45(2):142-150.

[4]李牧东，赵辉，翁兴伟，等.基于最优高斯随机游走和个体筛选策略的差分进化算法[J].控制与决策，2016，31(8):1379-1386.

[5]陆克中，孙俊.萤火虫算法收敛分析[J].计算机科学与探索，2016，10(2):293-300.

[6]张水平，陈阳，丁小军.动态搜索协同进化的果蝇优化算法[J].小型微型计算机系统，2018(1):48-52.

[7]王碧，罗潇，张水平.一种返巢模式下的粒子群优化策略[J].江西理工大学学报，2015，36(3):95-100.

[8]胥小波，郑康锋，李丹，等.新的混沌粒子群优化算法[J].通信学报，2012，33(1):24-30.

[9]王庆喜，郭晓波.基于莱维飞行的粒子群优化算法[J].计算机应用研究，2016，33(9):2588-2591.

[10]刘志刚，曾嘉俊，韩志伟.基于个体最优位置的自适应变异扰动粒子群算法[J].西南交通大学学报，2012，47(5):761-768.

[11]周利军，彭卫，邹芳，等.自适应变异粒子群算法[J].计算机工程与应用，2016，52(7):50-55.

[12]黄松，田娜，纪志成.基于自适应变异概率粒子群优化算法的研究[J].系统仿真学报，2016，28(4):874-879.

[13]韩敏，何泳.基于高斯混沌变异和精英学习的自适应多目标粒子群算法[J].控制与决策，2016，31(8):1372-1378.

[14]陈侃松，阮玉龙，戴磊，等.区域分割的自适应变异粒子群算法[J].电子学报，2017，45(8):1849-1855.