混合驱动的粒子群算法

doi:10.3778/j.issn.1002-8331.2307-0368

摘要/Abstract

摘要： 粒子群优化（particle swarm optimization，PSO）算法是一种在机器人运动规划、信号处理等领域有广泛应用的优化算法。然而该算法易陷入局部最优解，从而导致早熟问题。出现早熟问题的原因之一是粒子群仅依靠适应度值选择学习范例。为了克服上述问题，提出了一种基于适应度值、改进率和新颖性混合驱动的PSO算法（particle swarm optimization algorithm based on hybrid driven by fitness values，improvement rate，and novelty，FINPSO）。在该算法中，引入的新指标和遗传算法会平衡种群的探索与开发，降低粒子群早熟的可能性。适应度值、改进率和新颖性会作为粒子的评价指标。各指标独立地选择学习范例并保存到不同的档案中。粒子每一次速度更新都要确定各个指标的权重，并从每个档案中选择一个范例学习。该算法采用了遗传算法进行粒子间的信息交流。遗传算法中的交叉互换和突变会给种群带来更多的随机性，提升种群的全局搜索能力。以八个PSO算法变体作为对比算法，两个CEC测试套件作为基准函数进行实验。实验结果表明，FINPSO算法优于已有的PSO算法变体达到最先进水平。

关键词: 粒子群优化, 遗传算法, 混合驱动, 全局优化算法, 进化算法

Abstract: The particle swarm optimization(PSO) algorithm is a widely applied optimization algorithm in fields such as robot motion planning and signal processing. However, this algorithm is prone to getting stuck in local optima, resulting in premature convergence problem. One reason for this premature convergence problem is that the particle swarm relies solely on fitness values to select learning examples. To overcome this problem, a particle swarm optimization algorithm called FINPSO(particle swarm optimization algorithm based on a hybrid approach driven by fitness values, improvement rate, and novelty) is proposed. The algorithm introduces new metrics and utilizes a genetic algorithm to balance the exploration and exploitation of the population, reducing the likelihood of premature convergence in the particle swarm. Firstly, fitness values, improvement rate, and novelty are used as evaluation metrics for the particles. Each metric is independently employed to select learning examples, which are then stored in separate archives. During each velocity update, particles need to determine the weights of each metric and learn by selecting an example from each archive. Secondly, the algorithm incorporates a genetic algorithm for information exchange among particles. The genetic algorithm introduces cross-swapping and mutation, bringing more randomness to the population and enhancing its global search capability. Finally, eight variants of the PSO algorithm are used as comparative algorithms, and two CEC test suites are employed as benchmark functions in the experiments. The experimental results demonstrate that the FINPSO algorithm outperforms the existing PSO algorithm variants, reaching a state-of-the-art level.

Key words: particle swarm optimization, genetic algorithm, hybrid drive, global optimization algorithm, evolutionary algorithm

陈峰, 丁泉, 吴乐, 刘爱萍, 陈勋, 张云飞. 混合驱动的粒子群算法[J]. 计算机工程与应用, 2024, 60(8): 78-89.

CHEN Feng, DING Quan, WU Le, LIU Aiping, CHEN Xun, ZHANG Yunfei. Hybrid Driven Particle Swarm Algorithm[J]. Computer Engineering and Applications, 2024, 60(8): 78-89.

参考文献

[1] 朱佳莹, 高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
ZHU J Y, GAO M T. AUV path planning based on particle swarm optimization and improved ant colony optimization[J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
[2] 何元烈, 徐扣. 欠驱动平面机器人逆运动学求解研究——粒子群优化神经网络算法求解[J]. 计算机工程与应用, 2016, 52(17): 54-58.
HE Y L, XU K. Particle swarm neural network solution to inverse kinematics of underactuated planar robot[J]. Computer Engineering and Applications, 2016, 52(17): 54-58.
[3] 王晓艳, 曹德欣. 基于进化能力的多策略粒子群优化算法[J]. 计算机工程与应用, 2023, 59(5): 78-86.
WANG X Y, CAO D X. Multi-strategy particle swarm optimization algorithm based on evolution ability[J]. Computer Engineering and Applications, 2023, 59(5): 78-86.
[4] 梁田, 曹德欣. 基于莱维飞行的改进简化粒子群算法[J]. 计算机工程与应用, 2021, 57(20): 188-196.
LIANG T, CAO D X. Improved and simplified particle swarm optimization algorithm based on Levy flight[J]. Computer Engineering and Applications, 2021, 57(20): 188-196.
[5] 陈博文, 邹海. 总结性自适应变异的粒子群算法[J]. 计算机工程与应用, 2022, 58(8): 67-75.
CHEN B W, ZOU H. Self-conclusion and self-adaptive variation particle swarm optimization[J]. Computer Engineering and Applications, 2022, 58(8): 67-75.
[6] XIA X, GUI L, YU F, et al. Triple archives particle swarm optimization[J]. IEEE Transactions on Cybernetics, 2019, 50(12): 4862-4875.
[7] YU F, TONG L, XIA X. Adjustable driving force based particle swarm optimization algorithm[J]. Information Sciences, 2022, 609: 60-78.
[8] GONG Y J, LI J J, ZHOU Y, et al. Genetic learning particle swarm optimization[J]. IEEE Transactions on Cybernetics, 2015, 46(10): 2277-2290.
[9] LIU W, WANG Z, YUAN Y, et al. A novel sigmoid-function-based adaptive weighted particle swarm optimizer[J]. IEEE Transactions on Cybernetics, 2019, 51(2): 1085-1093.
[10] TIAN M, LIU Q, LU Y, et al. A diversity-feedback-regulated particle swarm optimization for coverage enhancing problem in directional sensor network[C]//Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery，2021: 1416-1424.
[11] VAN DEN BERGH F, ENGELBRECHT A P. A cooperative approach to particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 225-239.
[12] XIA X, GUI L, HE G, et al. An expanded particle swarm optimization based on multi-exemplar and forgetting ability [J]. Information Sciences, 2020, 508: 105-120.
[13] WEI B, XIA X, YU F, et al. Multiple adaptive strategies based particle swarm optimization algorithm[J]. Swarm and Evolutionary Computation, 2020, 57: 100731.
[14] LIU Q, LI J, REN H, et al. All particles driving particle swarm optimization: Superior particles pulling plus inferior particles pushing[J]. Knowledge-Based Systems, 2022, 249: 108849.
[15] LYNN N, SUGANTHAN P N. Ensemble particle swarm optimizer[J]. Applied Soft Computing, 2017, 55: 533-548.
[16] LIU J, HUANG J, SUN R, et al. Data fusion for multi-source sensors using GA-PSO-BP neural network[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22(10): 6583-6598.
[17] GUO E, GAO Y, HU C, et al. A hybrid PSO-DE intelligent algorithm for solving constrained optimization problems based on feasibility rules[J]. Mathematics, 2023, 11(3): 522.
[18] LIANG J J, QU B, SUGANTHAN P N, et al. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization[R]. Zhengzhou：Zhengzhou University. Computational Intelligence Laboratory & Singapore: Nanyang Technological University, 2013.
[19] WU G, MALLIPEDDI R, SUGANTHAN P N. Problem definitions and evaluation criteria for the CEC 2017 competition on constrained real?parameter optimization[R]. Changsha: National University of Defense Technology & Daegu: Kyungpook National University & Singapore: Nanyang Technological University, 2017.
[20] LIANG J J, QIN A K, SUGANTHAN P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295.
[21] CHENG R, JIN Y. A social learning particle swarm optimization algorithm for scalable optimization[J]. Information Sciences, 2015, 291: 43-60.