摘要
最大团问题是组合优化中经典的NP完全问题,该问题的枚举算法只适用于求解中小规模的图。提出了基于遗传算法的最大团问题求解算法,引入概率模型指导变异产生新的个体,并结合启发式局部算法搜索最大团。经算例测试,获得了较好的效果。
Maximum Clique Problem (MCP) is a classic NP Complete problem in combinatorial optimization. Its enumeration algorithm is only suitable for graphs with small scale. A new method based on genetic algorithm for MCP was proposed. Probability model was introduced to guide mutation when generating offspring,. and heuristic local search was combined to find clique. The experimental results show that its performance is satisfying.
出处
《计算机应用》
CSCD
北大核心
2008年第12期3072-3073,共2页
journal of Computer Applications
关键词
最大团问题
优化
遗传算法
Max Clique Problem (MCP)
optimization
genetic algorithm