Improved and Simplified Particle Swarm Optimization Algorithm Based on Levy Flight

doi:10.3778/j.issn.1002-8331.2006-0254

Abstract

Abstract:

Based on the deficiency that elementary particle swarm optimization is easy to fall into local optimum, an improved simplified particle swarm optimization algorithm based on levy flight（LISPSO） is proposed. The Simplified Particle Swarm Optimization（SPSO） discards the velocity in the updated formula and its evolution direction is only controlled by the position. Firstly, on the basis of simplified particle swarm optimization, the position of each particle is dynamically updated by using the nonlinear decreasing inertia weight with randomness. Secondly, the algorithm integrates Levy flight based on similarity and aggregation analysis. The higher the similarity between particles and the optimal particles, or the higher the concentration of particles, the greater the probability that the particle update the position with Levy flight, which can effectively help paticles to jump out of the local optimum. The 11 test function are simulated by matlab. The results show that the improved algorithm has significant improvement in solving accuracy and convergence speed. In addition, LISPSO is applied to solve min-max-min problem, and the experimental results show that the improved algorithm is obviously superior to other comparison algorithms in solving effect.

Key words: Levy flight, simplified particle swarm, similarity analysis, aggregation, min-max-min

摘要：

基于基本粒子群算法易陷入局部最优的不足，提出一种基于莱维飞行的改进简化粒子群算法LISPSO（An Improved and Simplified Particle Swarm Optimization algorithm based on Levy flight）。简化粒子群算法舍去更新公式中的速度项，仅由位置项控制其进化方向。在简化粒子群算法SPSO（Simplified Particle Swarm Optimization）的基础上，采用带有随机性的非线性递减惯性权重动态地更新每个粒子的位置。算法又融合了基于相似度及聚集度分析的莱维飞行。粒子与最优粒子间的相似度越高，或者粒子间的聚集度越高，则粒子利用莱维飞行来重新更新位置的概率也就越大，有效地帮助粒子逃离局部最优。利用matlab语言对11个测试函数进行算法仿真，结果表明，改进的算法在求解精度和收敛速度上有显著的改善。另外，将LISPSO算法应用于求解min-max-min问题，实验结果显示，改进算法在求解效果上明显优于其他对比算法。

关键词: 莱维飞行, 简化粒子群, 相似度分析, 聚集度, min-max-min

LIANG Tian, CAO Dexin. Improved and Simplified Particle Swarm Optimization Algorithm Based on Levy Flight[J]. Computer Engineering and Applications, 2021, 57(20): 188-196.

梁田，曹德欣. 基于莱维飞行的改进简化粒子群算法[J]. 计算机工程与应用, 2021, 57(20): 188-196.

References

[1] KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks，Perth，1995：1942-1948.
[2] SHI Y，EBERHART R C.A modified particle swarm optimizer[C]//Proceedings of the IEEE Congress on Evolutionary Computation，Piscataway，NJ，1998：69-73.
[3] MENDES R，KENNEDY J.The full informed particle swarm：simpler，maybe better[J].IEEE Transactions on Evolutionary Computation，2004，8（3）：204-210.
[4] 高立群，吴沛锋，邹德旋.基于变异策略的粒子群算法[J].东北大学学报（自然科学版），2010，31（11）：1530-1533.
GAO Liqun，WU Peifeng，ZOU Dexuan.Particle swarm optimization based on mutation strategy[J].Journal of Northeastern University（Natural Science），2010，31（11）：1530-1533.
[5] 胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报，2007，18（4）：861-868.
HU Wang，LI Zhishu.A simpler and more effective particle swarm optimization algorithm[J].Journal of Software，2007，18（4）：861-868.
[6] 刘长平，叶春明.一种新颖的仿生群智能优化算法：萤火虫算法[J].计算机应用研究，2011，28（9）：3295-3297.
LIU Changping，YE Chunming.Novel bioinspired swarm intelligence optimization algorithm：firefly algorithm[J].Application Research of Computers，2011，28（9）：3295-3297.
[7] 王庆喜，郭晓波，基于莱维飞行的粒子群算法[J].计算机应用研究，2010（4）：330-343.
WANG Qingxi，GUO Xiaobo.Particle swarm optimization algorithm based on Levy flight[J].Application Research of Computers，2011，28（9）：3295-3297.
[8] 刘晓龙，宁芋，赵成萍，等，基于莱维飞行的鸟群优化算法[J].计算机测量与控制，2016，24（12）：194-197.
LIU Xiaolong，NING Yu，ZHAO Chengping，et al.Bird swarm algorithm based on Levy flight[J].Computer Measurement and Control，2016，24（12）：194-197.
[9] 张志宇，白云霞.非线性递减惯性权重的简化粒子群算法[J].咸阳师范学院学报，2017，32（2）：57-61.
ZHANG Zhiyu，BAI Yunxia.Simplified particle swarm optimized algorithm based on nonlinear diminishing inertia weight[J].Journal of Xianyang Normal University，2017，32（2）：57-61.
[10] RATNAWEERA A，HALGAMUGE S K，WATSON H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Trans on Evolutionary Computation，2004，8（3）：240-255.
[11] XIE X F，ZHANG W J，YANG Z L.A dissipative particle swarm optimization[C]//Proc of the IEEE Int Conf on Evolutionary Computation.Honolulu：IEEE Inc，2002：1666-1670.
[12] 刘建华，樊晓平，瞿志华.一种基于相似度的新型粒子群算法[J].控制与决策，2007，22（10）：1155-1159.
LIU Jianhua，FAN Xiaoping，QU Zhihua.A new particle swarm optimization algorithm based on similarity[J].Control and Decision，2007，22（10）：1155-1159.
[13] 袁小平，蒋硕.基于分层自主学习的改进粒子群优化算法[J].计算机应用，2019，39（1）：148-153.
YUAN Xiaoping，JIANG Shuo.Particle swarm optimization based on hierar chical autonomous learning[J].Journal of Computer Applications，2019，39（1）：148-153.
[14] 韦鹏，曹德欣.混合三群粒子群优化算法求解min-max-min问题[J].计算机工程与应用，2010，46（35）：219-222.
WEI Peng，CAO Dexin.Hybrid three sub-swarms particle swarm optimizer for min-max-min problem[J].Computer Engineering and Applications，2010，46（35）：219-222.
[15] 陈美蓉，蒋娟，曹德欣.一类min-max-min问题的区间算法[J].应用数学与计算数学学报，2006，20（2）：255-263.
CHEN Meirong，JIANG Juan，CAO Dexin.Interval algorithm for a class of min-max-min problems[J].Communication on Applied Mathematics and Computation，2006，20（2）：255-263.
[16] CAO Dexin，CHEN Meirong，WANG Haijun，et al.Interval method for global solutions of a class of min-max-min problems[J].Applied Mathematics and Computation，2008，196：594-602.