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

Area of Science:

• Combinatorial Optimization
• Computational Intelligence
• Algorithm Design

Background:

• The max-cut problem is an NP-hard problem with significant real-world applications.
• Existing Particle Swarm Optimization (PSO) and Estimation of Distribution Algorithm (EDA) methods have limitations.

Purpose of the Study:

• To propose an integrated PSO-EDA method for solving the max-cut problem.
• To overcome the individual shortcomings of PSO and EDA.
• To enhance the performance of max-cut algorithms.

Main Methods:

• Developed an integrated Particle Swarm Optimization and Estimation of Distribution Algorithm (PSO-EDA).
• Incorporated a fast local search procedure to improve performance.
• Implemented a path relinking procedure for search intensification.

Main Results:

• Extensive experiments conducted on benchmark instances (800-20,000 vertices).
• PSO-EDA demonstrated significant performance improvement over existing PSO-based and EDA-based algorithms.
• Achieved highly competitive results compared to other state-of-the-art algorithms.

Conclusions:

• The proposed PSO-EDA is an effective method for solving the max-cut problem.
• The integration of local search and path relinking enhances solution quality.
• PSO-EDA offers a superior approach for complex combinatorial optimization challenges.