摘要
最大团问题是一种典型的NP完全问题,是图论中一个经典的组合优化问题。研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法。通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷。仿真实验表明,图中的顶点数较多时,也取得了较好的结果。
Maximum clique problem is a typical NP complete problem,and is a classical problem of combinatorial optimization in graph theory.In this paper,to apply ant colony optimization to resolving maximum clique problem is researched,and an algorithm of ant colony optimization for solving maximum dique problem(ACOMCP) is put forward.With the definition of each element in ACOMCP and the improvement on the way the ant searches its solutions,the disadvantage of easily falling into local best the ant colony optimization has is effectively ameliorated. Simulation results showed,when there are more numbers of the vertex,it can also achieve fairly good effect.
出处
《计算机应用与软件》
CSCD
2010年第10期107-109,113,共4页
Computer Applications and Software
基金
安微省自然科学基金项目(KJ2008B021)
关键词
最大团问题
蚁群算法
最大团问题蚁群算法
Maximum clique problem
Ant colony optimization
Ant colony optimization for solving maximum clique problem(ACOM-CP)