融合局部搜索策略求解DCMST的改进稳态遗传算法  

Improved steady-state genetic algorithm for DCMST with local search strategies

作　　者：鞠成安 王妮娅[1] HANZALA 张书凡 毛剑琳[1] JU Cheng’an;WANG Niya;HANZALA;ZHANG Shufan;MAO Jianlin(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,P.R.China)

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500

出　　处：《重庆邮电大学学报（自然科学版）》2023年第5期935-942,共8页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：云南省重点研发计划项目(202002AC080001)。

摘　　要：针对目前遗传算法求解度约束最小生成树存在的求解质量不稳定、局部搜索不完全的问题,提出一种融合局部搜索策略求解度约束最小生成树(DCMST)的改进稳态遗传算法。提出服从边隶属度值的度约束初始生成树算法,用来提高初始种群的质量;在局部搜索时引入禁忌搜索,防止相似解大量重复搜索;融合自适应变量和点替换的局部搜索方法,提升算法的局部搜索能力。仿真结果表明,提出的算法提高了初始解的质量,加快了算法的收敛速度,加强局部搜索从而提高了算法的求解质量,可获得较好的有效性与稳定性。In order to solve the problem of unstable solution quality and incomplete local search of the current genetic algorithm for solving DCMST(degree-constrained minimum spanning trees),this paper proposes an improved steady-state genetic algorithm combining with local search.First,a degree-constrained initial spanning tree algorithm that obeys the edge membership value is proposed to improve the quality of the initial population.Secondly,tabu search is introduced in the local search to prevent the algorithm from performing a large number of repeated searches for similar solutions.Finally,a local search method that integrates adaptive variables and point replacement is used to improve the local search capability of the algorithm.The running results on Euclidean and non-Euclidean instances show that the improved steady-state genetic algorithm improves the quality of the initial solution,speeds up the convergence of the algorithm,and strengthens the local search to improve the algorithm.The quality of the solution proves the effectiveness and stability of the algorithm.

关 键 词：度约束最小生成树 遗传算法 初始种群 禁忌搜索 局部搜索 

分 类 号：TP306.1[自动化与计算机技术—计算机系统结构]