An Integrated Method Based on PSO and EDA for the Max-Cut Problem.

Journal: Computational intelligence and neuroscience
Published Date: Feb 18, 2016

Abstract

The max-cut problem is NP-hard combinatorial optimization problem with many real world applications. In this paper, we propose an integrated method based on particle swarm optimization and estimation of distribution algorithm (PSO-EDA) for solving the max-cut problem. The integrated algorithm overcomes the shortcomings of particle swarm optimization and estimation of distribution algorithm. To enhance the performance of the PSO-EDA, a fast local search procedure is applied. In addition, a path relinking procedure is developed to intensify the search. To evaluate the performance of PSO-EDA, extensive experiments were carried out on two sets of benchmark instances with 800 to 20,000 vertices from the literature. Computational results and comparisons show that PSO-EDA significantly outperforms the existing PSO-based and EDA-based algorithms for the max-cut problem. Compared with other best performing algorithms, PSO-EDA is able to find very competitive results in terms of solution quality.

Authors

  • Geng Lin
    Department of Mathematics, Minjiang University, Fuzhou 350108, China.
  • Jian Guan
    State Key Laboratory of Multiphase Complex Systems, Institute of Process Engineering, Chinese Academy of Sciences, Beijing 100190, China; College of Chemical Engineering, University of Chinese Academy of Sciences, Beijing 100049, China; Key Laboratory of Science and Technology on Particle Materials, Institute of Process Engineering, Chinese Academy of Sciences, Beijing 361021, China.

Keywords

External Resources

Popular Topics
Recent Journals