求解最小支配集问题的禁忌遗传混合算法

吴歆韵 彭瑞 熊才权

［摘要］ 將最小支配集问题转换为一系列判定问题[CD2]k支配集问题，并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来，互补不足。高效的邻域结构保证了算法的运行效率，禁忌策略防止算法过早陷入局部最优陷阱，遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较，禁忌遗传混合算法的结果较其它算法更优。

［关键词］ 最小支配集； NP难问题； 禁忌遗传混合算法； k支配集

［中图分类号］ TP393［文献标识码］ A