计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (24): 81-84.

• 学术探讨 • 上一篇    下一篇

禁忌遗传算法求解最小支配集

廖飞雄,马 良   

  1. 上海理工大学 管理学院,上海 200093
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-08-21 发布日期:2007-08-21
  • 通讯作者: 廖飞雄

TSGA for solving minimum dominating set

LIAO Fei-xiong,MA Liang   

  1. College of Management,University of Shanghai for Science and Technology,Shanghai 200093,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-08-21 Published:2007-08-21
  • Contact: LIAO Fei-xiong

摘要: 如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法(TSGA)用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。

关键词: 最小支配集, 启发式算法, 禁忌搜索, 遗传算法

Abstract: 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.

Key words: minimum dominating set, heuristic algorithm, Tabu Search(TS), Genetic Algorithm(GA)