|
|||||
|
|
| 五种智能算法解决最大割问题分析与比较 | |
| 引用本文： | 陈宁,黎子芬,陈金柱.五种智能算法解决最大割问题分析与比较[J].海军航空工程学院学报,2009,24(4):447-452. |
| 作者姓名： | 陈宁 黎子芬 陈金柱 |
| 作者单位： | 1. 清华大学计算机科学与技术系,北京,100084 2. 海军航空工程学院研究生管理大队,山东,烟台,264001 3. 海军装备研究院,北京,100073 |
| 基金项目： | 国家"973"重点基础研究发展规划项目 |
| 摘 要： | 最大割问题（Max—eulProblem）是一个典型的NP难组合优化问题。文章采用遗传算法、分布估计算法、Hopfield网络方法、蚁群算法、粒子群算法等5种算法对最大割问题进行求解，并用标准的多个不同规模最大割测试数据进行测试，研究各参数对算法的影响，并比较各种算法的时间复杂度和空间复杂度。测试结果表明该五种算法虽然在执行效率上有差异，但都能较好的解决最大割问题。 |
| 关 键 词： | 最大割问题 遗传算法 分布估计算法：Hoofield网络：蚁群算法：粒子群算法 |
Solutions to Max-Cut Problem Using Five Different Intelligent Algorithms |
|
| CHEN Ning,LI Zi-fen and CHEN Jin-zhu.Solutions to Max-Cut Problem Using Five Different Intelligent Algorithms[J].Journal of Naval Aeronautical Engineering Institute,2009,24(4):447-452. | |
| Authors: | CHEN Ning LI Zi-fen and CHEN Jin-zhu |
| Institution: | 1. Department of Computer Science and Technology, 2. Graduate Students＇ Brigade of NAAU, 3. Naval Academy of Armament, TsinghuaUniversity, Beijing 100084, China： Yantai Shandong 264001, China; Beijing 100073, China) |
| Abstract: | The Max-cut Problem is a typical and NP complete Combinatorial Optimization Problem, which has been widely researched for many years. In this paper, five different intelligent algorithms, including GA （Genetic Algorithm）, EDA （Estimation of Distribution Algorithm）, HNN （Hopfieid Neural Network）, ACO （Ant Colony Optimization） and PSO （Particle Swarm Optimization） were applied on the topic. Based on large amount of comparable analysis, a conclusion was drawn that all the proposed algorithms could work the problem out successfully, although there existed differences both in temporal and spatial efficiencies. |
| Keywords: | max-cut problem genetic algorithm estimation of distribution algorithm Hopfield neural network ant colony optimization particle swarm optimization |
| 本文献已被 维普 万方数据 等数据库收录！ | |
| 点击此处可从《海军航空工程学院学报》浏览原始摘要信息 | |
| 点击此处可从《海军航空工程学院学报》下载免费的PDF全文 | |