An Integrated Method Based on PSO and EDA for the Max-Cut Problem. (18th February 2016)

• Record Type: Journal Article
• Authors: Lin, Geng; Guan, Jian
• Other Names: Heger Dominic Academic Editor.
• Is Part Of: Computational intelligence and neuroscience. Volume 2016(2016)
• Publication Date: 2016-02-18
• Subjects: Neurosciences -- Data processing -- Periodicals; Computational intelligence -- Periodicals; Computational neuroscience -- Periodicals; 612.80285
• DOI: 10.1155/2016/3420671
• Languages: English
• ISSNs: 1687-5265

Abstract

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 20000 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.