| 基于离散粒子群算法的近似最大连通分量抽取 |
| |
| 引用本文： | 王楠楠,石丽.基于离散粒子群算法的近似最大连通分量抽取[J].大连民族学院学报,2005,7(1):13-16. |
| |
| 作者姓名： | 王楠楠 石丽 |
| |
| 作者单位： | 沈阳理工大学,信息分院,辽宁,沈阳,110004;大连民族学院,非线性信息技术研究所,辽宁,大连,116600;沈阳理工大学,信息分院,辽宁,沈阳,110004 |
| |
| 摘 要： | 无向图中的最大连通分量抽取(Maximum Clique Problem，MCP)是一种具有重要应用价值的组合优化问题，已被证明属于NP问题．传统的深度优先、分枝限定等算法可以处理规模较小的MCP问题，所以提出处理大规模MCP问题的算法是非常必要的．粒子群优化算法是一种基于群智能的演化计算技术，离散粒子群算法(DiscretePSO)是其中解决离散编码的算法．提出了一种基于离散粒子群算法的近似连通图的抽取算法，通过定义连通图编码、合法随机初始化过程，编码校正算法使得DPSO能够解决最大连通图的抽取问题．为验证其效果及效率，将该算法与RAClique进行了比较．实验结果表明，该算法在解决此类问题时，执行的速度受节点规模变化不大，效率略优于RAClique其他算法．
|
| 关 键 词： | 粒子群算法 最大连通分量 群智能 |
| 文章编号： | 1009-315X(2005)01-0013-04 |
| 修稿时间： | 2004年10月20 |
A Discrete Particle Swarm Optimizer for Finding a Maximum Clique |
| |
| WANG Nan-nan,SHI Li.A Discrete Particle Swarm Optimizer for Finding a Maximum Clique[J].Journal of Dalian Nationalities University,2005,7(1):13-16. |
| |
| Authors: | WANG Nan-nan SHI Li |
| |
| Institution: | WANG Nan-nan1,2,SHI Li1 |
| |
| Abstract: | A solution to the maximum clique problem using a discrete particle swarm algorithm is presented. This method provides an encoding method to initialize each individual in one group to find a maximum clique using discrete PSO. The proposed algorithm is tested on some types of random graphs from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). The simulation results indicate that the algorithm can find better solutions in reasonable computation time than RAClique. |
| |
| Keywords: | particle swarm optimization maximum clique swarm intelligence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
