Modified PSO algorithm for solving planar graph coloring problem

作者：Cui Guangzhao; Qin Limin^*; Liu Sha; Wang Yanfeng; Zhang Xuncai; Cao Xianghong

来源：Progress in Natural Science, 2008, 18(3): 353-357.

DOI：10.1016/j.pnsc.2007.11.009

• planar graph coloring problem
• PSO
• optimization algorithm

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.

• 出版日期2008-3-10
• 单位华中科技大学; 郑州轻工业大学