摘要
如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法(TSGA)用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。
How to find a minimum dominating set for a network is a NP-hard problem.This paper gives a backward sequential heuristic algorithm and a tabu search algorithm,to solve this minimum dominating set problem.And furthermore,these two algorithms are combined into a more effective hybrid algorithm-TSGA in order to overcome their disadvantages of getting into local optimum and accelerate the speed of convergence.Series of experiments on random networks and logistics network location problems are tested that show the effectiveness of the TSGA for solving the minimum dominating set problem.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第24期81-84,共4页
Computer Engineering and Applications
基金
上海市重点学科建设项目资助(No.T0502)
上海市教委科技发展基金资助项目(No.05EZ31)
关键词
最小支配集启发式算法禁忌搜索遗传算法
minimum dominating set
heuristic algorithm
Tabu Search（TS ）
Genetic Algorithm （GA）
