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

Solutions to Max-Cut Problem Using Five Different Intelligent Algorithms

摘要:

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

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 (Hopfield 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.