Modifled 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 modifled particle swarm optimization (PSO) algorithm in which a disturbance factor is added to a particle swarm optimizer for improv- ing 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 modifled particle swarm optimization algorithm. Numerical simulation results show that the per- formance of the modified PSO is superior to that of the classical PSO.