五种智能算法解决最大割问题分析与比较  

Solutions to Max-Cut Problem Using Five Different Intelligent Algorithms

作　　者：陈宁[1] 黎子芬[2] 陈金柱[3] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]海军航空工程学院研究生管理大队,山东烟台 264001 [3]海军装备研究院,北京100073

出　　处：《海军航空工程学院学报》2009年第4期447-452,共6页Journal of Naval Aeronautical and Astronautical University

基　　金：国家“973”重点基础研究发展规划项目(2007CB311003)

摘　　要：最大割问题（Max—eulProblem）是一个典型的NP难组合优化问题。文章采用遗传算法、分布估计算法、Hopfield网络方法、蚁群算法、粒子群算法等5种算法对最大割问题进行求解，并用标准的多个不同规模最大割测试数据进行测试，研究各参数对算法的影响，并比较各种算法的时间复杂度和空间复杂度。测试结果表明该五种算法虽然在执行效率上有差异，但都能较好的解决最大割问题。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.

关 键 词：最大割问题 遗传算法 分布估计算法:Hoofield网络:蚁群算法:粒子群算法 

分 类 号：O157.6[理学—数学] TP391[理学—基础数学]