摘要
最小点覆盖问题是组合优化中经典的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.
作者
吴佩雯
陈京荣
姬璐烨
WU Pei-wen;CHEN Jing-rong;JI Lu-ye(School of Mathematics and Physics,Lanzhou Jiaotong University,Lanzhou 730030,China)
出处
《兰州交通大学学报》
CAS
2020年第2期114-117,共4页
Journal of Lanzhou Jiaotong University
基金
国家自然科学基金(61463026,61463027)
甘肃省自然科学基金(1610RJZA038)。
关键词
最小点覆盖问题
最大最小蚁群算法
信息素浓度
minimum vertex covering problem
max-min ant colony algorism
pheromone concentration
