搜索引导网络辅助的动态粒子群优化算法

doi:10.3778/j.issn.1673-9418.2312030

摘要/Abstract

摘要： 在动态优化问题（DOP）中环境的变化可描述为不同类型的动态，动态优化算法（DOA）对环境的适应性十分重要。此外，DOA的局部和全局多样性损失是导致其开发和勘探能力下降的主因之一。在动态环境中保持局部和全局多样性可有效避免多样性损失。为此，提出一种基于搜索引导网络的粒子群优化算法（SGN-PSO），每个输入粒子基于SGN隐藏层选择学习目标，在输出层调整其加速系数，从而引导粒子的搜索。SGN属于单隐层径向基神经网络，每个隐藏节点由其中心和半径组成。设置多个相互远离的隐藏节点中心，即子群中心，从而获得多个子群。每个粒子从其所属子群不同个体历史最优位置中选择局部学习目标，从相互远离的多个子群中心中选取全局学习目标，有助于种群的局部和全局多样性保持。SGN以强化学习方式来获得输入粒子的期望输出，并通过极限学习来预训练网络。设计节点的重要性和拥挤度指标，以获取紧凑网络结构，并增量学习保证网络拟合能力。无论环境如何变化，所提方法都能够通过学习来适应不同的环境，以引导粒子的搜索，从而有效处理不同动态的DOP。在MPB和DRPBG标准测试组件上和五种主流DOA开展对比实验，结果表明，SGN-PSO在求解多种动态的DOP上取得了显著的表现提升。

关键词: 动态优化, 增量极限学习机, 前馈神经网络, 粒子群优化

Abstract: In dynamic optimization problems (DOPs), environmental changes can be characterized as different dynamics, and adaption of dynamic optimization algorithms (DOAs) in different dynamic environments is vital. In addition, the local and global diversity loss is one of the main reasons behind the degradation of the exploitation and exploration capabilities of DOAs. Maintaining local and global diversity in dynamic environments can effectively avoid diversity loss. To this end, a search guidance network-based particle swarm optimization (SGN-PSO) is proposed. The learning target of each input particle is selected based on the hidden layer of SGN, and its acceleration coefficient is adjusted in the output layer to guide the search of particles. Specifically, SGN is a single-hidden layer radial basis function neural network, and each of its hidden layer nodes consists of a center and radius. By setting multiple hidden nodes whose centers, i.e. the subpopulation centers, are far from each other, multiple subpopulations can be obtained. Each particle selects the local learning target from the personal best historical positions that belong to its subpopulation, and selects the global learning target from the subpopulation centers that are far from each other, contributing to maintaining local and global diversity of the population. Reinforcement learning is employed to obtain the desired output of the input particles and extreme learning machine is utilized to pre-train the network. Furthermore, the significance and crowding degree metrics of hidden nodes are designed to obtain a compact network structure, and incremental learning is used to ensure the network approximation ability. No matter which dynamic occurs, SGN-PSO can adapt to different environments through learning for guiding the search of particles, and can effectively address DOPs of different dynamics. Compared with five mainstream DOAs on MPB and DRPBG benchmark test suites, the results demonstrate that SGN-PSO achieves significant performance improvement in solving DOPs.

Key words: dynamic optimization, incremental extreme learning machine, feedforward neural network, particle swarm optimization

刘志, 宋威. 搜索引导网络辅助的动态粒子群优化算法[J]. 计算机科学与探索, 2024, 18(12): 3189-3202.

LIU Zhi, SONG Wei. Search Guidance Network Assisted Dynamic Particle Swarm Optimization Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(12): 3189-3202.

参考文献

[1] 罗逸轩, 刘建华, 胡任远, 等. 融合经验共享Q学习的粒子群优化算法[J]. 计算机科学与探索, 2022, 16(9): 2151-2162.
LUO Y X, LIU J H, HU R Y, et al. Particle swarm optimization combined with Q-learning of experience sharing strategy[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2151-2162.
[2] 罗仕杭, 何庆. 混沌精英池协同教与学改进的ChOA及其应用[J]. 计算机工程与应用, 2023, 59(6): 299-309.
LUO S H, HE Q. Chimp optimization algorithm improved by chaos elite pool collaborative teaching-learning and its mechanical application[J]. Computer Engineering and Applications, 2023, 59(6): 299-309.
[3] 黄志锋, 刘媛华, 任志豪, 等. 融合改进哈里斯鹰和改进动态窗口的机器人动态路径规划[J]. 计算机应用研究, 2024, 41(2): 450-458.
HUANG Z F, LIU Y H, REN Z H, et al. Research on mobile robot dynamic path planning based on improved Harris hawk algorithm and improved dynamic window algorithm [J]. Application Research of Computers, 2024, 41(2): 450-458.
[4] WANG Y, ZHOU J, LU Y, et al. Chaotic self-adaptive particle swarm optimization algorithm for dynamic economic dispatch problem with valve-point effects[J]. Expert Systems with Applications, 2011, 38(11): 14231-14237.
[5] 杜利珍, 王宇豪, 宣自风, 等. 基于改进模拟退火算法的针织生产线调度研究[J]. 计算机工程与应用, 2023, 59(9): 304-312.
DU L Z, WANG Y H, XUAN Z F, et al. Research on knitted production line scheduling based on improved simulated annealing algorithm[J]. Computer Engineering and Applications, 2023, 59(9): 304-312.
[6] YAZDANI D, CHENG R, YAZDANI D, et al. A survey of evolutionary continuous dynamic optimization over two decades—part A[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(4): 609-629.
[7] KARIMI J, NOBAHARI H, POURTAKDOUST S H. A new hybrid approach for dynamic continuous optimization problems[J]. Applied Soft Computing, 2012, 12(3): 1158-1167.
[8] ZHANG T, WANG H D, YUAN B, et al. Surrogate-assisted evolutionary Q-learning for black-box dynamic time-linkage optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2022, 27(5): 1162-1176.
[9] BOSE D, BISWAS S, KUNDU S, et al. A strategy pool adaptive artificial bee colony algorithm for dynamic environment through multi-population approach[C]//Proceedings of the 3rd International Conference on Swarm, Evolutionary, and Memetic Computing, Bhubaneswar, Dec 20-22, 2012. Berlin, Heidelberg: Springer, 2012: 611-619.
[10] 李飞, 乐强, 潘紫微, 等. 基于自动快速密度峰值聚类的粒子群动态优化算法[J]. 计算机应用, 2023, 43(S1): 154.
LI F, YUE Q, PAN Z W, et al. Dynamic particle swarm optimization algorithm based on automatic fast density peak clustering[J]. Journal of Computer Applications, 2023, 43(S1): 154.
[11] LUO W, LIN X, ZHU T, et al. A clonal selection algorithm for dynamic multimodal function optimization[J]. Swarm and Evolutionary Computation, 2019, 50: 100459.
[12] KAZEMI K J, MEYBODI M R, RAHMANI A M. A note on the exclusion operator in multi-swarm PSO algorithms for dynamic environments[J]. Connection Science, 2020, 32(3): 239-263.
[13] CAO L, XU L, GOODMAN E D. A neighbor-based learning particle swarm optimizer with short-term and long-term memory for dynamic optimization problems[J]. Information Sciences, 2018, 453: 463-485.
[14] LIU X F, ZHOU Y R, YU X, et al. Dual-archive-based particle swarm optimization for dynamic optimization[J]. Applied Soft Computing, 2019, 85: 105876.
[15] BLACKWELL T, BRANKE J. Multi-swarm optimization in dynamic environments[C]//Workshops on Applications of Evolutionary Computation. Berlin, Heidelberg: Springer, 2004: 489-500.
[16] SHARIFI A, NOROOZI V, BASHIRI M, et al. Two phased cellular PSO: a new collaborative cellular algorithm for optimization in dynamic environments[C]//Proceedings of the 2012 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2012: 1-8.
[17] MUKHERJEE R, PATRA G R, KUNDU R, et al. Cluster-based differential evolution with crowding archive for niching in dynamic environments[J]. Information Sciences, 2014, 267: 58-82.
[18] YAZDANI D, CHENG R, HE C, et al. Adaptive control of subpopulations in evolutionary dynamic optimization[J]. IEEE Transactions on Cybernetics, 2022, 52(7): 6476-6489.
[19] EMARY E, ZAWBAA H M, GROSAN C. Experienced gray wolf optimization through reinforcement learning and neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 29(3): 681-694.
[20] MAVROVOUNIOTIS M, YANG S. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors[J]. Applied Soft Computing, 2013, 13(10): 4023-4037.
[21] DEBENER S, ULLSPERGER M, SIEGEL M, et al. Trial-by-trial coupling of concurrent electroencephalogram and functional magnetic resonance imaging identifies the dynamics of performance monitoring[J]. Journal of Neuroscience, 2005, 25(50): 11730-11737.
[22] CAO J, ZHANG K, YONG H, et al. Extreme learning machine with affine transformation inputs in an activation function[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(7): 2093-2107.
[23] HUANG G B, ZHU Q Y, SIEW C K. Extreme learning machine: theory and applications[J]. Neurocomputing, 2006, 70: 489-501.
[24] HUANG G B, CHEN L, SIEW C K. Universal approximation using incremental constructive feedforward networks with random hidden nodes[J]. IEEE Transactions on Neural Networks, 2006, 17(4): 879-892.
[25] CHENG J, CHEN X, YANG H, et al. An enhanced k-means algorithm using agglomerative hierarchical clustering strategy[C]//Proceedings of the 2012 IEEE International Conference on Automatic Control and Artificial Intelligence, Xiamen, Mar 3-5, 2012. Piscataway: IEEE, 2012: 407-410.
[26] MICHE Y, SORJAMAA A, BAS P, et al. OP-ELM: optimally pruned extreme learning machine[J]. IEEE Transactions on Neural Networks, 2009, 21(1): 158-162.
[27] 梁靓, 魏亚星, 李义鑫, 等. 基于非线性跨代差分进化的花授粉优化算法及其应用研究[J]. 电子学报, 2023, 51(9): 2445-2456.
LIANG L, WEI Y X, LI Y X, et al. A flower pollination algorithm based on nonlinear cross-generation differential evolution and its application study[J]. Acta Electronica Sinica, 2023, 51(9): 2445-2456.
[28] BONYADI M R, MICHALEWICZ Z. Analysis of stability, local convergence, and transformation sensitivity of a variant of the particle swarm optimization algorithm[J]. IEEE Transactions on Evolutionary Computation, 2015, 20(3): 370-385.
[29] FANG W, SUN J, CHEN H, et al. A decentralized quantum-inspired particle swarm optimization algorithm with cellular structured population[J]. Information Sciences, 2016, 330: 19-48.
[30] YAZDANI D, CHENG R, YAZDANI D, et al. A survey of evolutionary continuous dynamic optimization over two decades—part B[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(4): 630-650.
[31] BRANKE J, SCHMECK H. Designing evolutionary algorithms for dynamic optimization problems[M]//Advances in Evolutionary Computing: Theory and Applications. Berlin, Heidelberg: Springer, 2003: 239-262.
[32] TROJANOWSKI K, MICHALEWICZ Z. Searching for optima in non-stationary environments[C]//Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway: IEEE, 1999: 1843-1850.
[33] YAZDANI D, OMIDVAR M N, CHENG R, et al. Benchmarking continuous dynamic optimization: survey and generalized test suite[J]. IEEE Transactions on Cybernetics, 2022, 52(5): 3380-3393.
[34] VAFASHOAR R, MEYBODI M R. A multi-population differential evolution algorithm based on cellular learning automata and evolutionary context information for optimization in dynamic environments[J]. Applied Soft Computing, 2020, 88: 106009.
[35] FENG G, HUANG G B, LIN Q, et al. Error minimized extreme learning machine with growth of hidden nodes and incremental learning[J]. IEEE Transactions on Neural Networks, 2009, 20(8): 1352-1357.
[36] MENG M, ZHANG T, YANG W, et al. Diverse complementary part mining for weakly supervised object localization[J]. IEEE Transactions on Image Processing, 2022, 31: 1774-1788.
[37] LI C, NGUYEN T T, YANG M, et al. An adaptive multipopulation framework for locating and tracking multiple optima[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(4): 590-605.
[38] DAS S, MANDAL A, MUKHERJEE R. An adaptive differential evolution algorithm for global optimization in dynamic environments[J]. IEEE Transactions on Cybernetics, 2014, 44(6): 966-978.
[39] LIU X F, ZHAN Z H, GU T L, et al. Neural network-based information transfer for dynamic optimization[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(5): 1557-1570.
[40] LU X, TANG K, MENZEL S, et al. Dynamic optimization in fast-changing environments via offline evolutionary search[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(3): 431-445.