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

Abstract EN

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.