角逐和信息素引导的多目标黑寡妇优化算法

doi:10.3778/j.issn.1673-9418.2207004

摘要/Abstract

摘要： 黑寡妇优化算法（BWOA）是一种群体智能优化算法，具有收敛速度快、收敛精度高等优点。但BWOA所采用的更新策略过于简单，容易陷入局部最优解；其次在多维空间中搜索能力欠缺，种群结构单一，算法的收敛性和多样性有待改善。为提高BWOA的综合性能，并使其能够应用于多目标优化问题，提出一种角逐机制和改进信息素机制引导的多目标黑寡妇优化算法（MBWOA）。MBWOA采用动态分配种群的方法，在迭代过程中将种群一分为二，分别使用不同的角逐机制，增强迭代过程中种群的多样性，提升算法的收敛性；同时，使用改进的信息素机制对经过角逐的子代个体进行更新，引导个体向种群间隙方向优化，改善种群的分布，增强算法的收敛能力。MBWOA与四个对比算法在IGD、HV、Spread三个指标上分别进行对比实验，结果表明MBWOA具有更好的收敛精度、收敛速度和多样性。最后，通过在三个指标上对MBWOA所用机制的对比实验，证实了所用机制的有效性。

关键词: 多目标优化, 黑寡妇优化算法（BWOA）, 角逐机制, 改进信息素机制

Abstract: Black widow optimization algorithm (BWOA) is a swarm intelligence optimization algorithm, which has the advantages of fast convergence and high precision. However, the update strategy adopted by BWOA is too simple, and it is easy to fall into the local optimal solution. Moreover, the search ability in multi-dimensional space is lacking, the population structure is single, and the convergence and diversity of the algorithm need to be improved. In order to improve the comprehensive performance of BWOA and make it applicable to multi-objective optimization problems, this paper proposes a multi-objective black widow optimization algorithm (MBWOA) guided by a competition mechanism and an improved pheromone mechanism. MBWOA adopts the method of dynamic allocation of populations, which divides the populations into two in the iterative process and uses different competition mechanisms to enhance the diversity of the populations in the iterative process and improve the convergence of the algorithm. At the same time, it uses the improved pheromone mechanism to guide offspring individuals that have gone through the competition mechanism to optimize in the direction of population gap, improve the distribution of population, and enhance the convergence ability of the algorithm. Using MBWOA and four comparison algorithms to conduct comparative experiments on three indicators of IGD, HV and Spread respectively, the results show that MBWOA has better convergence accuracy, convergence speed and diversity. Finally, the effectiveness of the used mechanism is confirmed by the experiments of MBWOA and the comparison algorithms on three indicators.

Key words: multi-objective optimization, black widow optimization algorithm (BWOA), competition mechanism, improved pheromone mechanism

傅彦铭, 许励强, 祁康恒, 沈煜鸣, 屈迟文. 角逐和信息素引导的多目标黑寡妇优化算法[J]. 计算机科学与探索, 2023, 17(12): 2913-2927.

FU Yanming, XU Liqiang, QI Kangheng, SHEN Yuming, QU Chiwen. Multi-objective Black Widow Algorithm Guided by Competitive Mechanism and Pheromone Mechanism[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(12): 2913-2927.

参考文献

[1] LI B D, LI J L, TANG K, et al. Many-objective evolution-ary algorithms: a survey[J]. ACM Computing Surveys, 2015, 48(1): 13.
[2] LIEFOOGHE A, DAOLIO F, VEREL S, et al. Landscape-aware performance prediction for evolutionary multiobjec-tive optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(6): 1063-1077.
[3] 高岳林, 杨钦文, 王晓峰, 等. 新型群体智能优化算法综述[J]. 郑州大学学报(工学版), 2022, 43(3): 21-30.
GAO Y L, YANG Q W, WANG X F, et al. Overview of new swarm intelligent optimization algorithms[J]. Journal of Zhengzhou University (Engineering Edition), 2022, 43(3): 21-30.
[4] KENNEDY J, EBERHART R. Swarm intelligence[C]//Pro-ceedings of the 1995 International Conference on Neural Networks, Perth, Nov 27-Dec 1, 1995. Piscataway: IEEE, 1995: 1942-1948.
[5] 杨洋, 陈家俊. 基于群智能算法优化BP神经网络的应用研究综述[J]. 电脑知识与技术, 2020, 16(35): 7-10.
YANG Y, CHEN J J. Review on application of intelligent algorithm to optimize BP neural network[J]. Computer Knowledge and Technology, 2020, 16(35): 7-10.
[6] 史春天, 曾艳阳, 侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
SHI C T, ZENG Y Y, HOU S M. Summary of application of swarm intelligence algorithms in image segmentation[J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[7] 李琼琼, 布升强, 杨家富. 生物群体智能算法在移动机器人路径规划中的应用研究综述[J]. 世界科技研究与发展, 2021, 43(5): 535-546.
LI Q Q, BU S Q, YANG J F. Research review on biological swarm intelligence algorithm in mobile robot path planning[J]. World Science and Technology Research and Develop-ment, 2021, 43(5): 535-546.
[8] 刘双双, 黄宜庆. 多策略蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2022, 58(6): 278-286.
LIU S S, HUANG Y Q. Application of multi-strategy ant colony algorithm in robot path planning[J]. Computer Eng-ineering and Applications, 2022, 58(6): 278-286.
[9] 徐宁, 樊郁徽. 群体智能优化算法在入侵检测中的应用综述[J]. 信息与电脑(理论版), 2019(11): 41-43.
XU N, FAN Y H. A review of the application of swarm intelligence optimization algorithms in intrusion detection[J]. Information and Computer (Theoretical Edition), 2019(11): 41-43.
[10] 安家乐, 刘晓楠, 何明, 等. 量子群智能优化算法综述[J]. 计算机工程与应用, 2022, 58(7): 31-42.
AN J L, LIU X N, HE M, et al. Survey of quantum swarm intelligence optimization algorithm[J]. Computer Enginee-ring and Applications, 2022, 58(7): 31-42.
[11] 蔡雨希, 何英杰, 陈涛, 等. 基于粒子群的三电平并网逆变器LCL滤波参数的高效精确设计方法[J]. 中国电机工程学报, 2020, 40(20): 6663-6674.
CAI Y X, HE Y J, CHEN T, et al. Efficient and accurate design method of LCL filter for three-level grid-connected inverter based on particle swarm optimization[J]. Chinese Journal of Electrical Engineering, 2020, 40(20): 6663-6674.
[12] 李晓岩, 苏娜. 基于蚁群算法和神经网络的船舶图像压缩方法[J]. 舰船科学技术, 2022, 44(8): 165-168.
LI X Y, SU N. Ship image compression method based on ant colony algorithm and neural network[J]. Ship Science and Technology, 2022, 44(8): 165-168.
[13] PENA-DELGADO A F, PERAZA-VáZQUEZ H, ALMAZáN-COVARRUBIAS J H, et al. A novel bio-inspired algorithm applied to selective harmonic elimination in a three-phase eleven-level inverter[J]. Mathematical Problems in Enginee-ring, 2020: 1-10.
[14] MUKILAN P, SEMUNIGUS W. Human object detection: an enhanced black widow optimization algorithm with deep convolution neural network[J]. Neural Computing and App-lications, 2021, 33(22): 15831-15842.
[15] WILSON A J, RADHAMANI A S. Real time flood disaster monitoring based on energy efficient ensemble clustering mechanism in wireless sensor network[J]. Software Prac-tice and Experience, 2022, 52(1): 254-276.
[16] PREMKUMAR K, VISHNUPRIY A M, SUDHAKAR BABU T, et al. Black widow optimization-based optimal PI-controlled wind turbine emulator[J]. Sustainability, 2020, 12(24): 10357.
[17] LIU H W, SONG G J. A multiuser detection based on quan-tum PSO with Pareto optimality for STBC-MC-CDMA sys-tem[C]//Proceedings of the 2009 IEEE International Con-ference on Communications Technology and Applications, Beijing, Oct 16-18, 2009. Piscataway: IEEE, 2009: 652-655.
[18] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Tran-sactions on Evolutionary Computation, 2002, 6(2): 182-197.
[19] DENG L B, SONG L, SUN G J. A competitive particle swarm algorithm based on vector angles for multi-objective optimization[J]. IEEE Access, 2021, 9: 89741-89756.
[20] SOLIS F J, WETS R J B. Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6(1): 19-30.
[21] FELZENSZWALB P F, HUTTENLOCHER D P. Efficient belief propagation for early vision[J]. International Journal of Computer Vision, 2006, 70(1): 41-54.
[22] COELLO C A C, CORTES N C. Solving multiobjective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines, 2005, 6(2): 163-190.
[23] ZITZLER E, THIELE L. Multiobjective evolutionary algo-rithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computa-tion, 1999, 3(4): 257-271.
[24] WANG Y N, WU L H, YUAN X F. Multi-objective self-adaptive differential evolution with elitist archive and crow-ding entropy-based diversity measure[J]. Soft Computing, 2010, 14(3): 193-209.
[25] NEBRO A J, DURILLO J J, GARCIA-NIETO J, et al. SMPSO: a new PSO-based metaheuristic for multi-objective optimization[C]//Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making, Nashville, Mar 30-Apr 2, 2009. Piscataway:IEEE, 2009: 66-73.
[26] YUAN Y, XU H, WANG B, et al. Balancing convergence and diversity in decomposition-based many-objective opti-mizers[J]. IEEE Transactions on Evolutionary Computa-tion, 2016, 20(2): 180-198.
[27] TIAN Y, CHENG R, ZHANG X, et al. A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization[J]. IEEE Trans-actions on Evolutionary Computation, 2019, 23(2): 331-345.
[28] TIAN Y, ZHENG X, ZHANG X, et al. Efficient largescale multi-objective optimization based on a competitive swarm optimizer[J]. IEEE Transactions on Cybernetics, 2019, 50(8): 3696-3708.
[29] TIAN Y, CHENG R, ZHANG X Y, et al. PlatEMO: a MATLAB platform for evolutionary multi-objective optimi-zation[J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
[30] ZHANG Q F, ZHOU A M, JIN Y C. RM-MEDA: a regu-larity model-based multiobjective estimation of distribution algorithm[J]. IEEE Transactions on Evolutionary Computa-tion, 2008, 12(1): 41-63.
[31] ZITZLER E, DEB K, THIELE L. Comparison of multi-objective evolutionary algorithms: empirical results[J]. Evolu-tionary Computation, 2000, 8(2): 173-195.