| 基于遗传算法的近似最大连通分量的抽取算法 |
| |
| 引用本文： | 石丽,王楠楠.基于遗传算法的近似最大连通分量的抽取算法[J].沈阳理工大学学报,2005,24(3):31-34. |
| |
| 作者姓名： | 石丽 王楠楠 |
| |
| 作者单位： | 沈阳理工大学,国有资产管理处,辽宁,沈阳,110168 |
| |
| 摘 要： | 提出了一种基于遗传算法的近似连通图的抽取算法，通过定义编码、种群初始化方法和交叉变异修正使得遗传算法可以解决最大连通分量的抽取问题．为验证该算法，将该算法与RACLIQUE进行了比较．实验结果表明本文提出的算法在解MCP问题时，执行的速度受节点规模变化小，效率优于RACLIQUE算法．
|
| 关 键 词： | 最大连通分量 遗传算法 连通图 |
| 文章编号： | 1003-1251(2005)03-0031-04 |
| 收稿时间： | 2004-10-21 |
| 修稿时间： | 2004年10月21 |
An Extraction Algorithm for Finding a Near-Maximum Clique Based on the Genetic Algorithm |
| |
| SHI Li,WANG Nan-nan.An Extraction Algorithm for Finding a Near-Maximum Clique Based on the Genetic Algorithm[J].Transactions of Shenyang Ligong University,2005,24(3):31-34. |
| |
| Authors: | SHI Li WANG Nan-nan |
| |
| Affiliation: | Shenyang Ligong University, Shenyang 110168, China |
| |
| Abstract: | In this article, a solution to the near-maximum clique problem using a genetic algorithm is presented. This method provides a code and method to initializing each individual in group to finding a near-maximum clique using genetic algorithm. The proposed algorithm is tested on some types of random graphs and some benchmark graphs. The simulation results show that the algorithm can find good solutions in reasonable computation time. |
| |
| Keywords: | genetic algorithm maximum clique connect graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
