计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (20): 188-196.DOI: 10.3778/j.issn.1002-8331.2006-0254

• 模式识别与人工智能 • 上一篇    下一篇

基于莱维飞行的改进简化粒子群算法

梁田,曹德欣   

  1. 中国矿业大学 数学学院,江苏 徐州 221116
  • 出版日期:2021-10-15 发布日期:2021-10-21

Improved and Simplified Particle Swarm Optimization Algorithm Based on Levy Flight

LIANG Tian, CAO Dexin   

  1. School of Mathematics, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China
  • Online:2021-10-15 Published:2021-10-21

摘要:

基于基本粒子群算法易陷入局部最优的不足,提出一种基于莱维飞行的改进简化粒子群算法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

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