title: An Integrated Method Based on PSO and EDA for the Max-Cut Problem.
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.affiliation: Department of Mathematics, Minjiang University, Fuzhou 350108, China.
authors.forename: Geng
authors.initials: G
authors.lastname: Lin
authors.affiliation: Modern Educational Technology Center, Minjiang University, Fuzhou 350108, China.
authors.forename: Jian
authors.initials: J
authors.lastname: Guan
mesh_terms: D000465:Algorithms; D000818:Animals; D001185:Artificial Intelligence; D001522:Behavior, Animal; D019985:Benchmarking / Q000706:statistics & numerical data; D001717:Birds; D003198:Computer Simulation; D006801:Humans; D015233:Models, Statistical