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

摘要：

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

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

所属期刊栏目：43

分类号：TP18(自动化基础理论)

资助基金：上海市重点学科建设项目T0502;上海市教委资助项目05EZ31

在线出版日期：2007-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：81-84