基于最大最小蚁群算法求解最小点覆盖问题  

Research of Minimum Vertex Covering Problem Based on Maximum and Minimum Ant Colony Algorithms

作　　者：吴佩雯 陈京荣[1] 姬璐烨 WU Pei-wen;CHEN Jing-rong;JI Lu-ye(School of Mathematics and Physics,Lanzhou Jiaotong University,Lanzhou 730030,China)

机构地区：[1]兰州交通大学数理学院,兰州730070

出　　处：《兰州交通大学学报》2020年第2期114-117,共4页Journal of Lanzhou Jiaotong University

基　　金：国家自然科学基金(61463026,61463027);甘肃省自然科学基金(1610RJZA038)。

摘　　要：最小点覆盖问题是组合优化中经典的NP完全问题.最大最小蚁群算法通过对信息素浓度的限定使其不会在好的顶点上变得更强,也不会使过弱的点被忽略从而避免了局部最优现象的出现.针对最小点覆盖问题使用最大最小蚁群算法进行求解,避免了蚁群算法求解最小点覆盖问题时出现的早期停滞现象,通过实验表明算法对最小点覆盖问题的可行性.The minimum vertex covering problem is a classical NP complete problem in combinatorial optimization.The maximum and minimum ant colony algorithm can limit the pheromone concentration so that it will not become stronger at the good vertex or ignore the weak point so as to avoid the occurrence of local optimality.The maximum and minimum ant colony algorithm is used to solve the minimum vertex covering problem,which avoids the early stagnation phenomenon when the ant colony algorithm is used to solve the minimum point covering problem.Experiments show that the algorithm is feasible and effective for the problem of minimum point coverage.

关 键 词：最小点覆盖问题 最大最小蚁群算法 信息素浓度 

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