Solving Graph Coloring Problem Using Divide and Conquer-Based Turbulent Particle Swarm Optimization

The graph coloring problem, an NP-hard combinatorial optimization problem, is required in some engineering applications. This research focuses on the requirement of designing a new particle swarm optimization model to minimize the search space and generations. This stochastic method is developed using divide and conquer with improved strategies to offset the problems in the well-known existing ways. The divide and conquer strategy splits the vertex set of graph G into two subsets, and then, the subsets are solved to reduce the search space. The advanced neighborhood search operator is applied to a particle for a fixed number of iterations to improve its position to obtain the best neighborhood. The modified turbulent strategy is designed to overcome the problem of getting a divergent solution. The iterative fitness assessment and walking one strategy are applied to identify the maximum conflicting vertices and assign a set of valid colors. The behavioral analysis of this stochastic search model reveals that premature convergence is primarily caused by the decrease in the velocity of particles in the search space that leads to a total implosion and, ultimately, fitness stagnation of the swarm. The lazy particles are driven out for exploring new search spaces to avoid premature convergence. The experimental results of this method have revealed that a better near-optimal solution is obtained for some of the critical benchmark graphs compared with the state-of-the-art techniques.