2. 轻工过程先进控制教育部重点实验室(江南大学), 江苏 无锡 214122
2. Ministry of Education Key Laboratory of Advanced Process Control for Light Industry (Jiangnan University), Wuxi Jiangsu 214122, China
随着社会发展,解决现实世界中的优化问题越来越要求快速而高效。传统的优化方法已经不能满足现状,自然启发式算法应运而生。群体智能算法便是其中一种,它是受自然界生物群体行为启发而提出,例如模拟蜂群采蜜行为的人工蜂群优化(Artificial Bee Colony,ABC)算法[1],根据萤火虫成虫发光相互吸引的生物学特性而发展起来的萤火虫算法(Firefly Algorithm,FA)[2]。同样地,受鸟群觅食行为启发,1995年,Kennedy等[3]提出粒子群优化(Particle Swarm Optimization,PSO)算法。在PSO算法中,群体中的每个粒子代表一个潜在的解决方案,即搜索空间中的一个点,全局最好的位置即食物源的位置。在解空间中,根据自身和种群搜索经验,每个粒子不断调节飞行方向逼近食物源。PSO算法由于其结构简单、参数设置较少并易于实现等特点,越来越多地被用来解决现实中的优化问题[4]。但是在解决复杂多峰值函数问题时,PSO显现出容易陷入局部最小值,并且收敛速度过于缓慢、精度不高等缺陷[5]。
近年来,许多PSO的改进算法被陆续提出以克服原始PSO存在的缺陷,这些算法用不同的方式来提高PSO的性能。例如Liang等[5]提出了综合学习粒子群(Comprehensive Learning PSO,CLPSO)算法,该算法通过每个粒子学习其他粒子在不同维度上的行为,以此避免陷入局部最优。为了克服粒子群算法因参数设置造成对优化问题的影响,Beheshti等[6]根据局部和全局拓扑结构,使用双二次插值,提出了无参数粒子群优化(Non-Parametric PSO,NP-PSO)算法。通过设定随机值使局部最优值和全局最优值适应正确的惯性权重,Chan等[7]提出了条件随机的粒子群优化(PSO with a Conditional Random,CRPSO)算法。Hakli等[8]将Levy飞行引入到粒子群中,提出了Levy飞行粒子群优化(Levy Flight PSO,LFPSO)算法。Zhang等[9]引入贝叶斯技术,提出基于贝叶斯技术的自适应惯性权重粒子群优化(PSO with Bayesian techniques,BPSO)算法。虽然这些算法在解决很多优化问题上得到了令人满意的结果,但是还是存在不足之处:例如环形结构粒子群(Local topological structure PSO,LPSO)算法[10]在处理单峰问题上收敛速度慢[11];CLPSO也不适合处理单峰问题[5];另外,许多算法很难做到提高收敛速度和避免过早收敛两者兼顾,特别是在处理高维复杂多峰值函数时,收敛速度慢、寻优能力差的缺陷较为明显。 为了提高PSO局部开发和全局探索能力,避免其陷入局部最小值,提高搜索精度,全面优化PSO算法性能,本文提出引入萤火虫行为和Levy飞行的粒子群优化(PSO with Firefly Behavior and Levy Flight,FBLFPSO)算法。因为萤火虫搜索策略在处理复杂的优化函数时寻优能力强于PSO[12],基于萤火虫依靠荧光强度相互吸引而移动的生物学特性,本文提出一种自适应步长的萤火虫搜索策略,并将其引入到PSO中改善局部搜索能力;在局部最优值持续不发生改变时,引入Levy飞行,扩大搜索范围,跳出局部最优,提高全局搜索能力和搜索精度,避免发生过早收敛。
1 Levy飞行粒子群算法LFPSO 1.1 粒子群算法PSOPSO是基于种群的元启发式智能优化算法,算法首先初始化一个粒子数量为N的种群,对于粒子i=1,2,…,N,在D维搜索空间中,都有一个位置向量xi,速度向量vi和自己的历史最好位置pbesti。整个种群有一个全局最好位置gbest。在每一次迭代过程中,使用式(1) 和(2) 对粒子速度和位置进行更新:
$\begin{align} &v_{i}^{d}(t+1)=w\times v_{i}^{d}(t)+{{c}_{1}}\times {{r}_{1}}\times (pbest_{i}^{d}(t)-x_{i}^{d}(t)) \\ &+{{c}_{2}}\times {{r}_{2}}\times (gbes{{t}^{d}}(t)-x_{i}^{d}(t)) \\ \end{align}$ | (1) |
$x_{i}^{d}(t+1)=x_{i}^{d}(t)+v_{i}^{d}(t+1)$ | (2) |
其中:c1、c2是学习因子;r1、r2是[0,1]内的随机数;w是惯性权重。
1.2 LFPSO算法Levy飞行是一种非高斯随机化过程,其随机步长来自Levy稳定分布[13],它的简化形式为:
$L(s)\sim {{\left| s \right|}^{-1-\beta }}\begin{matrix} ,&0<\beta <2 \\ \end{matrix}$ | (3) |
其中s是随机步长。引入Levy飞行的粒子位置更新公式为:
$x\left( t+1 \right)=x\left( t \right)+random\left( size\left( D \right) \right)\oplus Levy\left( \beta \right)$ | (4) |
其中⊕代表内积运算,随机步长为:
$\begin{align} & s=random(size(D))\oplus Levy(\beta )\tilde{\ } \\ & 0.01\frac{\mu }{{{\left| \nu \right|}^{1/\beta }}}({{x}_{i}}(t)-gbest(t)) \\ \end{align}$ | (5) |
其中,μ和ν来自正态分布:
$\mu \sim N(0,\sigma _{\mu }^{2}),\nu \sim N(0,\sigma _{\nu }^{2})$ | (6) |
式中的σμ和σν定义为:
${{\sigma }_{\mu }}={{\left\{ \frac{\Gamma (1+\beta )\sin (\frac{\pi \beta }{2})}{\Gamma \left[ \left( \frac{1+\beta }{2} \right) \right]\beta {{2}^{\left( \beta -1 \right)/2}}} \right\}}^{1/\beta }},{{\sigma }_{v}}=1$ | (7) |
其中Γ是标准Gamma函数。
2 FBLFPSO算法为了提高粒子群算法的全局搜索能力和局部开发能力以及搜索精度,本文通过引入改进的萤火虫搜索策略和Levy飞行策略,分别针对局部和全局搜索各自独立利用,综合提高PSO算法性能。
2.1 改进的萤火虫搜索策略萤火虫算法(FA)是一种新型群体智能算法,由Yang[2]在2008年根据自然界中萤火虫成虫因荧光亮度相互吸引而移动的生物学特性提出,吸引度β和亮度I是算法中两个最基本的要素,亮度决定萤火虫的移动方向,吸引度决定移动距离。萤火虫的亮度和吸引度定义:
$I={{I}_{0}}\times {{e}^{-\gamma {{r}_{ij}}}}$ | (8) |
$\beta ={{\beta }_{0}}\times {{e}^{-\gamma {{r}_{ij}}^{2}}}$ | (9) |
其中:γ是荧光系数,rij是萤火虫i、j的欧氏距离:
${{r}_{ij}}=\left\| {{x}_{i}}-{{x}_{j}} \right\|=\sqrt{\sum\limits_{k=1}^{D}{(x_{i}^{k}-x_{j}^{k}}{{)}^{2}}}$ | (10) |
设I(j)>I(i),萤火虫i被萤火虫j吸引并向其移动:
${{z}_{i}}={{x}_{i}}+\beta ({{z}_{j}}-{{z}_{i}})+\alpha \varepsilon $ | (11) |
其中:α是步长因子,ε是随机参数。式(11) 中,步长因子α是一个[0,1]均匀分布的随机数,这种随机步长仅仅依赖于最大迭代次数,不能适用于不同的个体,并且随着迭代次数的不断增加,每个粒子的步长差别将越来越小。基于这个问题,考虑到迭代次数以及粒子的历史最优位置和种群最优位置,本文提出自调节步长的萤火虫搜索策略。自调节步长公式为:
$A(t)=a(t)\cdot {{e}^{-{{({{f}_{gbest}}-{{f}_{pbest}})}^{2}}maxIter-t/maxIter}}$ | (12) |
$\alpha (t+1)=\max ({{a}_{min}},\min (A(t),{{a}_{max}}))$ | (13) |
其中:t是当前迭代; fgbest代表当前迭代中全局最优解的适应值; fpbest代表当前粒子最优解的适应值;maxIter代表最大迭代次数;αmax、αmin表示步长上限。因此,步长将随着迭代次数依据自身位置和全局位置而变化。将提出的新的搜索策略引入到粒子群中来加强其局部搜索能力,构造出粒子的局部搜索公式描述如下:
$z(t+1)=z(t)+\beta ({{z}_{j}}(t)-{{z}_{i}}(t))+a(t)\varepsilon $ | (14) |
引入自调节步长的萤火虫搜索策略,使得粒子在局部搜索能力上有了较大提高,通过自调节步长参照种群和个体经验,能够保持较好的搜索方向,避免过早收敛,使算法具有更加稳定的局部搜索能力。
2.2 FBLFPSO算法的提出受萤火虫的生物学特性和Levy飞行特征启发,本文引入萤火虫行为和Levy飞行,提出基于两种搜索机制的FBLFPSO算法,实现算法在局部开发和全局探索上的综合提高。
在原始的萤火虫搜索策略中,粒子的步长随着迭代次数增多将趋于相同,这对粒子的局部搜索能力有较大影响。因此,本文在2.1节提出一种自调节步长的萤火虫搜索策略,在每次迭代过程中让粒子根据整个种群和自身的经验调节搜索步长,将其作为局部搜索策略引入到PSO算法中,保证粒子在局部空间进行更细微的搜索,局部搜索能力得到显著提高,有效地避免了早熟现象。但是,单一的局部搜索机制不能保证粒子始终保持着向最优解方向飞行,这时再引入Levy飞行策略,扩大粒子的搜索范围,增强种群丰富度和均匀度,保证粒子有较好的飞行方向,进一步优化算法的全局搜索性能。
因此,分别针对局部开发和全局探索,将两种不同的搜索机制引入到PSO算法中,不仅可以利用两种不同搜索策略的优点,根据两种策略表现出的互补性又能够有效避免单独使用一种策略带来的缺陷,显著提高粒子群算法的整体性能。
2.3 FBLFPSO算法的流程图及主要步骤FBLFPSO算法的流程图如图 1所示。图中flag参数表示寻优停滞次数,当停滞次数达到limit的值时表示算法陷入局部最优;荧光亮度I取值为当前粒子的适应值。
步骤1 初始化种群(种群规模N,维度D,初始速度v和位置x,初始全局最优gbest和个体最优pbest),初始化参数(最大迭代次数maxIter,荧光亮度I0,吸引度β0,荧光系数γ,步长上限αm,限定值limit,标识flag等)。
步骤2 首先用式(1) 更新粒子的速度,然后分别计算出当前粒子i和剩余粒子j的荧光亮度I,若I(j)>I(i),利用式(12) 和(13) 计算步长,并用式(14) 进行局部搜索。 步骤3 判断是否flag<limit,如果是,则使用式(2) 更新当前粒子的位置,转向步骤5;否,转向步骤4。
步骤4 利用Levy飞行方法进行全局搜索,增加种群多样性,避免算法陷入局部最优。首先设置flag=0,使用式(4) 更新粒子位置。
步骤5 进行边界判断,并计算当前粒子的适应度;如果当前适应值优于上一次迭代的适应度,则更新局部最优值,并设置标识flag=0;否则flag=flag+1。
步骤6 判断当前粒子的位置是否优于全局最优位置,若是,则更新全局最优位置;若否,则转向步骤2,直至达到程序终止条件。
对于FBLFPSO算法,在整个过程中,步骤2~4是算法的主要部分,整个算法总共嵌套三个循环,根据基本运算maxIter×N×(N+D);分析算法的时间复杂度为O(maxIter×N×(N+D))。
3 实验结果与分析为了更好地评估FBLFPSO算法的可行性和性能,进行了多组对比实验。首先将FBLFPSO算法与LFPSO算法作对比,其次再与其他相关算法综合对比,并分析实验结果。
3.1 测试函数与参数设定应用于本次实验的测试函数共有21个,包括7个单峰值函数(F1~F4,F15~F17) 、10个复杂多峰值函数(F5~F10,F18~F21) 以及4个旋转多峰值函数(F11~F14) ,因数量过多无法全部列出,具体细节详见文献[8]中表 2。
实验设定惯性权重w根据迭代次数线性递减的方式进行,最大值设为0.9,最小值设为0;另外设定种群规模N为30,学习因子设为2;维度为30维时设定迭代次数为200000,维度50时设定迭代次数为250000,算法在每个测试函数上独立运行30次。实验在Windows7系统上使用Matlab 2012a进行。
3.2 仿真实验结果与分析表 1为FBLFPSO算法与LFPSO算法在21个测试函数上独立运行30次得到的平均结果。表中分别给出算法在30维和50维问题上的寻优能力和稳定性,即适应度平均值Mean和标准方差Std.Dev。其中Opt.表示函数的最优解。
从表 1中可以看出,不论问题维度是30维还是50维,FBLFPSO算法的性能几乎在所有测试函数上都优于LFPSO算法。只有在复杂多峰值旋转测试函数F11上,FBLFPSO算法的寻优能力虽然强于LFPSO算法,但算法的稳定性要略差一些。另外,随着问题维度的增加,FBLFPSO算法的寻优能力和稳定性也逐步增强。分析表中数据,本文提出的FBLFPSO算法采用两种不同策略,使得全局最优解的精度明显提高。
3.3 收敛性能曲线图 2和图 3是FBLFPSO算法和LFPSO算法分别在30维和50维问题上的部分收敛性能曲线,实验中得到的其他收敛图与给出部分类似,因篇幅问题不再给出。
从图 2~3中可以看出,LFPSO算法在初期收敛速度明显很快,但寻优结果达到一定精度后始终不再继续优化,此时算法便陷入局部最小值,最终找到的最优解也不能让人满意;而FBLFPSO算法在整体上收敛速度明显快于LFPSO算法,并显著地改善了LFPSO算法过早收敛的缺陷,因其在局部开发和全局探索上表现良好,所以在提高最优解精度的同时也具有最佳的收敛速度。另外,比较30维和50维的收敛图可以看出,50维时的收敛曲线更平滑,说明FBLFPSO算法在处理50维问题时稳定性更高。分析图 2和图 3,本文采用的两种搜索策略在局部和全局搜索上表现出良好的互补性,因此FBLFPSO算法的收敛速度和性能才得以显著提高。
3.4 FBLFPSO算法与其他相关算法的对比实验结果为了更好地评估FBLFPSO算法的有效性和性能,将FBLFPSO和CLPSO、全信息粒子群(Fully Informed PSO,FIPSO)[14]算法、标准粒子群(Standard PSO,SPSO)算法[15]、LPSO、动态多群粒子群算法(Dynamic Multi-Swarm PSO,DMS-PSO)算法[16]作比较.表 2给出在30维问题上,算法在10个测试函数上独立运行30次得到的结果,其中CLPSO、FIPSO、SPSO、LPSO、DMS-PSO的数据来自文献[8]。实验参数设定详见3.1节。
从表 2可以看出FBLFPSO算法在F3、F5、F6、F8、F11、F12、F14上性能更好,其中F3是单峰值函数,F5、F6、F8是多峰值函数,F11、F12、F14是复杂旋转测试函数。FBLFPSO算法虽然不能在所有测试函数上都表现最好,但是在解决复杂多峰值和旋转测试函数上的性能优于其他算法,这表明FBLFPSO算法在处理低耦合性问题上更加有效,这是由于两种不同搜索策略分别提高了算法的局部和全局搜索能力,使得算法整体性能得到改善,能更精准地得到最优解。通过对比实验数据表明,FBLFPSO算法的性能更优,尤其在复杂的多峰值和旋转函数上具有优异的寻优能力和稳定性。
为了研究FBLFPSO算法与其他智能算法性能的差异,将FBLFPSO算法与FA、蚁群算法(Ant Colony Optimization,ACO)[17]、遗传算法(Genetic Algorithm,GA)[18]在6个测试函数上作了对比,其中F1、F3、F4为单峰值函数,F6、F8、F9为多峰值函数。表 3给出在30维问题上的实验结果。从表中可以看出,FBLFPSO算法在5个测试函数上具有较为明显的优势,只有在F4上性能表现得不是很好,在F3上和FA性能相差不大;但就整体来看,FBLFPSO算法的性能远远优于其他算法,特别是在多峰值问题上,这说明本文采用的两种不同机制综合提高了PSO算法的性能,使得算法更具有竞争力。
为了克服标准粒子群算法容易陷入局部最小值和全局搜索能力差的缺点,针对其他改进算法采用单一搜索策略不能在整体上全面优化PSO的问题,提出引入萤火虫行为和Levy飞行的粒子群优化算法FBLFPSO,综合提高算法性能。本文首先提出自调节步长的萤火虫搜索策略,并将其引入到粒子群优化算法中,提高算法在局部空间上的搜索能力;当局部最优解连续不更新时再引入Levy飞行避免粒子陷入局部最优,增强算法的全局搜索能力,提高搜索精度,特别是在复杂多峰值优化问题上表现性能更好。仿真实验结果表明,使用两种不同搜索策略的FBLFPSO算法在避免粒子陷入局部最优、提高全局搜索能力和搜索精度上表现出优异的性能,两种策略的互补性使得算法不论是在单峰值函数还是多峰值函数上都具有较强的寻优能力和稳定性。
[1] | KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization:Artificial Bee Colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39 (3) : 459-471. doi: 10.1007/s10898-007-9149-x |
[2] | YANG X S. Nature-inspired metaheuristic algorithms[M].[S.l.]:Luniver Press, 2008:83-96. http://cn.bing.com/academic/profile?id=1596914020&encoded=0&v=paper_preview&mkt=zh-cn |
[3] | KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proceedings of the 1995 IEEE International Conference on Neural Networks. Washington, DC:IEEE Computer Society, 1995:1942-1948. http://link.springer.com/article/10.1007%2Fs11721-007-0002-0 |
[4] | CALVINI M, CARPITA M, FORMENTINI A, et al. PSO-based self-commissioning of electrical motor drives[J]. IEEE Transactions on Industrial Electronics, 2015, 62 (2) : 768-776. doi: 10.1109/TIE.2014.2349478 |
[5] | LIANG J J, QIN A K, BASKAR S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10 (3) : 281-295. doi: 10.1109/TEVC.2005.857610 |
[6] | BEHESHTI Z, SHAMSUDDIN S M. Non-parametric particle swarm optimization for global optimization[J]. Applied Soft Computing, 2015, 28 (1) : 345-359. |
[7] | CHAN C L, CHEN C L. A cautious PSO with conditional random[J]. Expert Systems with Applications, 2015, 42 (8) : 4120-4125. doi: 10.1016/j.eswa.2014.12.046 |
[8] | HAKLI H, UĜUZ H. A novel particle swarm optimization algorithm with Levy flight[J]. Applied Soft Computing, 2014, 23 (5) : 333-345. |
[9] | ZHANG L, TANG Y, HUA C, et al. A new particle swarm optimization algorithm with adaptive inertia weight based on Bayesian techniques[J]. Applied Soft Computing, 2015, 28 (C) : 138-149. |
[10] | KENNEDY J, MENDES R. Population structure and particle swarm performance[C]//CEC'02:Proceedings of the Evolutionary Computation on 2002. Washington, DC:IEEE Computer Society, 2002:1671-1676. http://cn.bing.com/academic/profile?id=2162012556&encoded=0&v=paper_preview&mkt=zh-cn |
[11] | BEHESHTI Z, SHAMSUDDIN S M H. CAPSO:centripetal accelerated particle swarm optimization[J]. Information Sciences, 2014, 258 (3) : 54-79. |
[12] | APOSTOLOPOULOS T, VLACHOS A. Application of the firefly algorithm for solving the economic emissions load dispatch problem[J]. International Journal of Combinatorics, 2011, 2011 . |
[13] | FIORITI V, FRATICHINI F, CHIESA S, et al. Levy foraging in a dynamic environment-extending the Levy search[J/OL]. International Journal of Advanced Robotic Systems, 2015, 12.[2016-03-06]. http://arx.sagepub.com/content/12/7/98.full.pdf. |
[14] | MENDES R, KENNEDY J, NEVES J. The fully informed particle swarm:simpler, maybe better[J]. IEEE Transactions on Evolutionary Computation, 2014, 8 (3) : 204-210. |
[15] | OMRAN M. SPSO2007 Matlab[EB/OL].[2016-03-06]. http://www.particleswarm.info/Programs.html. |
[16] | LIANG J J, SUGANTHAN P N. Dynamic multi-swarm particle swarm optimizer[C]//Proceedings of the 2005 IEEE Swarm Intelligence Symposium. Piscataway, NJ:IEEE, 2005:124-129. http://www.oalib.com/references/18217681 |
[17] | DORIGO M. Optimization, learning and natural algorithms[D]. Milano:Politecnico di Milano, 1992:26-33. |
[18] | HOLLAND J H. Adaptation in natural and artificial systems[M]. Cambridge, CA: MIT Press, 2015 : 39 -48. |