GQPSO算法在动态环境优化问题中的应用

王梦梅

摘要：动态环境优化问题求解是近年来优化领域的研究热点。为了解决动态环境优化问题中种群的早熟收敛现象，寻找3种学习策略更新种群中的吸引子，提出一种基于高斯分布的量子行为粒子群优化算法（GQPSO）。在改进算法中，种群中粒子的吸引子由高斯公式产生。通过对比3种吸引子对算法的影响，确定了产生吸引子的最佳更新公式。此外，GQPSO算法中粒子的位置由概率密度函数以一定概率分散在搜索空间内，处于束缚状态，因此可以增加种群多样性以达到全局搜索，从而提高GQPSO算法在求解动态环境优化问题上的收敛能力。

关键词：高斯分布；粒子群算法；动态环境；优化问题

DOIDOI：10.11907/rjdk.173334

中图分类号：TP311

文献标识码：A 文章编号：1672-7800（2018）008-0035-05

英文摘要Abstract：Solving dynamic optimization problems （DOPs） has become a hot research area in recent years.In order to solve the precocious convergence of population in dynamic environment optimization problem，a Gaussian particle swarm optimization algorithm （GQPSO） based on Gaussian distribution is proposed.In GQPSO，the attractors of particles in the population are produced by gauss formulas，and updated by three learning strategies.By comparing the effects of three kinds of attractors on the algorithm，the optimal formula for generating the attractor is determined.In addition，the particle's position in GQPSO algorithm is scattered by the probability density function at a certain probability in the search space，and the particle is in the bound state，so it can increase the diversity of population to achieve global searching optimization to improve the ability of convergence of GQPSO algorithm in dynamic environment.

英文关键词Key Words：Gaussian distribution； particle swarm optimization； dynamic environment； optimization problem

0 引言

近年来，动态环境优化问题[1]（dynamic optimization problems，DOPs）已经成为一个新的研究热点。不同于静态优化问题[2]，DOPs的最优解随着目标函数、环境参数以及约束条件的变化而改变，在当前时刻得到的最优解不一定是下一时刻的最优解。因此，优化算法不仅要在一个特定环境中找到最优解，而且需要对最优解变化轨迹具有追踪能力。

为了提高量子行为粒子群优化算法[3]解决动态环境优化问题中收敛速度与跟踪定位的能力，提出一种改进的量子行为粒子群优化算法。通过分析量子行为粒子群优化算法中单个粒子的运动行为，构造3种吸引子公式，并给出最佳吸引子的产生条件。然后根据吸引子的产生公式，提出一种全局搜索策略，分析粒子群的搜索轨迹及算法的性能评价标准。通过对标准测试函数的实验仿真，验证了改进算法对复杂动态环境优化问题的快速收敛能力及高效跟踪定位能力。

1 量子行为粒子群算法

Sun等[4]从量子力学的角度出发，基于提高PSO算法的收敛能力，提出了一种新的PSO模型——量子行为粒子群优化（Quantum-behaved particle swarm optimization，QPSO）算法。QPSO算法一直受到众多学者的广泛关注，许多基于QPSO算法的改进算法及应用相继被提出。2005年Sun等[5]基于高斯概率分布产生随机数替代算法参数的方法，提出了一种保持种群多样性的参数选择方法，改进粒子的早熟问题；2007年孙俊等[6]提出QPSO算法中已压缩膨胀系数值小于1.78时才能保证算法收敛，并提出两种选择控制参数的方法：线性递减和非线性递减。QPSO算法的应用已经渗透到计算科学的各个领域，包括组合优化、动态优化、图像图形、神经网络、机器学习等。

QPSO算法中的粒子不需要粒子的速度信息，与PSO算法相比，具有控制参数少、收敛速度快、运算简单等特点，是一种通用的优化技术。实践证明QPSO算法是一种快速全局收敛算法，能够应用于各种复杂的优化问题。若PSO系统是一个量子系统，在量子空间中粒子的速度和位置不能同时确定，每个粒子的运行状态都由波函数ψ确定，ψ2是粒子位置的概率密度函数。通過代数和数学分析方法，Clerc等[7]研究了PSO系统中粒子运行轨迹，假定在第t次迭代，粒子i在D维空间运动，该粒子在第d维的势阱为pid（t），那么在第t+1次迭代可以得到粒子i的波函数如式（1）。

（5）比较当前迭代全局最好位置与前一次迭代的全局最好位置，如果当前全局最好位置较好，则群体的全局最好位置更新为它的值。

（6）计算得到一个随机点的位置。

重复（2）至（6），直至满足一定的结束条件。

2 量子行为粒子群优化算法的动态优化

2.1 分层聚类策略

传统的聚类方法一般以大量可用数据为基础进行信息挖掘和实践验证。但在求解动态多峰优化问题中，算法对于规避早熟以及在收敛速度与精度上仍然存在不足。目前经常采用随机选取粒子的方法对种群进行预先处理，或者检测到环境变化后对种群进行随机选取。该随机选取策略具有一定盲目性和不确定性，优化结果往往依赖于初始化种群的位置。本文采用分层聚类策略解决动态环境优化问题，是一种产生多种群的有效方法[9]。在移动峰问题中，最优解的适应值随着峰的位置变化而改变[10]。分层聚类能够产生多种群从而检测峰的变化，并跟踪最优值的变化轨迹。首先，将初始种群中每个粒子都当作一个子类，然后根据子种群之间的距离，合并两个子类为一个新的子种群，直到找到最优解的位置。

由高斯公式产生GQPSO中的吸引子，能够充分利用种群中粒子的个体最优位置信息，保持粒子多样性，从而提高算法解决动态环境优化问题的能力。

根据以上讨论分析，本文所提算法GQPSO的伪代码见表1。

3 实验结果及分析

3.1 算法性能测试

为了测试本文算法的性能，实验设置了9种粒子群群体规模M（10，30，50，70，100，120，150，200）和8种初始聚类子群中粒子数max_subsize（2，3，4，5，6，7，10，12，15）。

从图2的实验结果对比可知，离线性能指标越小，说明算法性能越好。当山峰数为一个特定的值时，离线性能指标随着粒子群粒子数的增长而增加。这是因为搜索区域内的粒子数目增多，聚类的子群就会增加，随着算法迭代进行，种群能搜索的峰的数目也会增加收敛的种群增加，从而导致离线性能指标有所增长。此外，当移动峰数一定时，每当粒子群不同，最优算法也是不同的。比如：当max_subsizeN=3、M=100时，算法性能最佳，而当max_subsizeN=7、M=200时离线性能最小，说明算法最佳。因此，由图3-图5可知，GQPSO算法能够适应多种移动峰问题的求解。

3.2 参数设置影响

实验主要测试算法中压缩膨胀系数[13]对算法性能的影响，黑体数据则表示在不同峰值下，最佳压缩膨胀系数得到的离线性能指标。由表2可知，对比所有数据，当算法中压缩膨胀系数值设置为静态值0.4时，得到离线性能指标最小，说明压缩膨胀系数对算法求解动态优化问题的全局搜索能力有一定影响；其值范围越大，即当压缩膨胀系数设置为线性递减策略或者非线性递减策略时，对应的离线性能指标的值比静态参数策略大，也就说明短发的全局搜索能力越弱。当压缩扩张系数的值设置为固定值0.4时，有3个最优值存在（P=5、P=15、P=30），算法的全局搜索能力越强，算法快速找到峰数的能力就越强。

3.3 3种高斯吸引子对比

本组实验旨在比较3种高斯分布吸引子[14]对算法的影响。表3中L1是第一种高斯分布，更新公式为式（16）；L2为第二种高斯分布，更新公式为式（17）；L3是第三种高斯分布，更新公式为式（19）。为对比每种吸引子算法的适应能力，本组实验还给出了6种移动峰问题，从而证明GQPSO算法对复杂动态环境优化问题的有效性。由表3所示，当吸引子确定时，随着山峰数的增加，算法离线性能指标的值反而减小，说明该算法能够适应复杂的移动峰问题，证明了算法的有效性和鲁棒性。

对比3种吸引子的衰减趋势（见图3），第二种高斯分布吸引子L2的离线性能指标最低，说明当吸引子的方差为Cid（t）到pid（t）与pg_nearest，d（t）中点之间的距离时，算法结果最佳。因此，实验结果证明，本文提出的高斯分布量子行为粒子群优化算法在求解动态环境优化问题中具有较好的性能。

3.4 算法比较实验

该组实验考察GQPSO算法处理不同环境变化频率和变化强度的MPB性能。算法参数设置如下：粒子群数为120，环境变化设置为10、50、100、200，峰变化强度设置为0.05、0.5、1.0、2.0。环境变化强度是指峰的顶点位置移动的剧烈程度。表4是GQPSO与其它5种算法（CQPSO、FPSO、mIPSO1、mIPSO2、mIPSO3）的对比。从表4中数据可知，当环境变化强度较大（0.5、1.0）或很大（20）时，算法能够快速对环境变化作出反应，具有较强的收敛性能和适应能力。

从图4和表4中可以看出，首先，在不同的变化剧烈程度下，GQPSO算法的性能远远好于列出的所有算法。

其次，环境变化强度对算法GQPSO的影响与其它算法是相似的。环境变化强度增加反而导致算法性能降低，这是因为环境变化强度越大，函数适应值曲面变化越大，相应地，变化后峰与原来峰的距离也就越远。因此，算法很难重新定位和跟踪到变化的峰。然而，环境变化强度对算法GQPSO性能的影响并不是很大，说明算法具有很好的鲁棒性，能够适应不同程度峰位置移动的变化。

图4给出了实验设置下GQPSO解决不同变化剧烈程度和变化周期的MPB离线性能指标与其它算法比较结果。环境变化周期是指每隔一定的评价次数，环境就会发生变化，成为环境变化频率。由图4可知，对于相同峰数的MPB，当环境变化周期逐渐增加时，粒子群能在一个变化周期内收敛，粒子的数量会减少，子群的数目也会随之下降，意味着算法有充足的时间进行重新定位和追踪最优解的位置，说明粒子群的收敛性很好，动态环境中参数的变化会影响算法的性能。环境变化得越慢，算法的性能越好；環境强度变化越大，算法求解动态环境优化问题的能力越差。显然当环境频率变化较小时，算法需要更长时间获取更好的解；当环境频率变化较大时，问题的适应度函数值便会很大，算法则需要花费更长时间寻找改变后的最优解。

4 结语

本文首先从原理上分析了量子行为粒子群优化算法，其具有全局搜索能力能够解决动态环境优化问题。其次对当前粒子群优化算法在动态环境优化问题中存在的缺陷进行分析，在此基础上，采用分层聚类策略产生多种群，扩大了种群粒子搜索区域范围，增强了算法的局部搜索能力。针对复杂多变的动态环境采用一种有效的环境监测办法监测环境的变化，提高了算法对变化强度较高和变化频率较快的应变能力，通过与其它文献算法的横向对比，实验表明算法解决动态环境优化问题具有较强的适用性和鲁棒性。

为增强全局搜索能力和局部搜索能力，对量子行为粒子算法进行了改进。首先，对算法中吸引子进行分析，提出3种吸引子公式，并通过对单个粒子的运动进行分析，证明了最佳吸引子公式的可靠性。然后根据吸引子的产生公式，提出一种全局搜索策略，分析了粒子群体的搜索轨迹与算法的性能评价标准。通过对动态环境优化问题测试函数仿真，验证了改进算法可对复杂动态环境优化问题快速跟踪，具有较强的动态适应性和较好的优化性能。

参考文献：

[1] FU H，LEWIS P R， SENDHOFF B，et al.What are dynamic optimization problems[C].2014 IEEE Congress on Evolutionary Computation，2014：1550-1557.

[2] 陈莉.动态优化问题的粒子群算法研究[D].武汉：武汉大学，2012.

[3] 孙俊.量子行为粒子群优化算法研究[D].无锡：江南大学，2009.

[4] SUN J，XU W，FENG B.A global search strategy of quantum-behaved particle swarm optimization[C].Cybernetics and Intelligent Systems，2004：111-116.

[5] XU W，SUN J.Adaptive parameter selection of quantum-behaved particle swarm optimization on global level[J].International Conference on Advances in Intelligent Computing，2005，3612（23）：420-428.

[6] SUN J，XU W，LIU J.Parameter selection of quantum-behaved particle swarm optimization[J].Dynamics of Continuous Discrete & Impulsive Systems，2007，14（4）：603-607.

[7] CLERC M，KENNEDY J.The particle swarm：explosion，stability and convergence in a multi-dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6（1）：58-73.

[8] 杨玉良.高分子科学中的Monte Carlo方法[M].上海：复旦大学出版社，1993.

[9] YANG S.Evolutionary computation for dynamic optimization problems[C].Companion Publication of the 2015 Conference on Genetic and Evolutionary Computation，2015：629-649.

[10] KENNEDY J.Stereotyping：improving particle swarm performance with cluster analysis[J].Congress on Evolutionary Computation，2000，2：1507-1512.

[11] 王洪峰，汪定偉，黄敏.求解动态优化问题的分叉PSO算法[J].系统仿真学报，2010，22（12）：2895-2899.

[12] TING T O，MAN K L，GUAN S U，et al.Weightless Swarm Algorithm （WSA） for dynamic optimization problems[J].Springer Berlin Heidelberg，2012，7513：508-515.

[13] FANG W，SUN J，WU X J，et al.Study on the compression-expansion coefficient in drift particle swarm optimization[C].WCCI 2012 IEEE World Congress on Computational Intelligence，2014：1-6.

（责任编辑：何 丽）