一种求解GSTP问题的新型黏菌优化算法  

Novel slime mould algorithm for solving GSTP problems

作　　者：王军霞 王晓峰[1,2] 华盈盈 何飞 唐傲 刘建平 WANG Junxia;WANG Xiaofeng;HUA Yingying;HE Fei;TANG Ao;LIU Jianping(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021

出　　处：《现代电子技术》2025年第5期162-168,共7页Modern Electronics Technique

基　　金：国家自然科学基金资助项目(62062001);宁夏青年拔尖人才项目(2021);北方民族大学重点科研项目(2023ZRLG12)。

摘　　要：针对图的Steiner树问题(GSTP)的NP难特性,提出一种融合多策略改进的黏菌优化算法。首先,定义种群初始化方法,由于STP是二进制解空间中的优化问题,而标准的黏菌优化算法迭代更新后每个维度的值是连续的。因此,为搜索个体确定最佳的S型传递函数,对连续的个体位置进行离散化处理。其次,为避免种群陷入局部最优,对二进制的黏菌优化算法引入新的位置更新策略。最后,将改进后的黏菌优化算法在OR-Library标准测试集上的计算结果与其他经典启发式算法、近似算法以及深度强化学习算法进行实验对比分析。结果表明,改进后的黏菌优化算法能够有效避免陷入局部最优,收敛精度更高,在求解GSTP时有一定优越性。In view of the NP-hard property of the Steiner tree problem in Graphs(GSTP),a slime mould algorithm(SMA)incorporating multi-strategy improvement is proposed.Firstly,the population initialization method is defined.Since the STP is an optimization problem in binary solution space,the value of each dimension is continuous after the iteration update of the standard SMA.Therefore,the optimal S-type transfer function is determined for individuals under search,and the continuous individual positions are discretized.Secondly,a new position update strategy is introduced to the binary SMA in order to avoid the population from falling into the local optimum.Finally,the computational results of the improved SMA on the OR-Library standard test set are compared with the classical heuristic algorithms,approximation algorithms,and deep reinforcement learning algorithms,and the comparative results are analyzed.The results show that the improved SMA can avoid falling into the local optimum effectively,with higher convergence accuracy,so it has a certain advantages in solving GSTP.

关 键 词：Steiner树问题 黏菌优化算法 传递函数 位置更新 离散化处理 种群初始化 

分 类 号：TN919-34[电子电信—通信与信息系统] TP301.6[电子电信—信息与通信工程]