Modified PSO algorithm for solving planar graph coloring problem

The graph coloring is a classic NP-complete problem. Presently there is no effective method to solve this problem. Here we propose a modified particle swarm optimization (PSO) algorithm in which a disturbance factor is added to a particle swarm optimizer for improving its performance. When the current global best solution cannot be updated in a certain time period that is longer than the disturbance factor, a certain number of particles will be chosen according to probability and their velocities will be reset to force the particle swarm to get rid of local minimizers. It is found that this operation is helpful to improve the performance of particle swarm. Classic planar graph coloring problem is resolved by using modified particle swarm optimization algorithm. Numerical simulation results show that the performance of the modified PSO is superior to that of the classical PSO.