Modified PSO algorithm for solving planar graph coloring problem

详细信息    查看全文

• 作者：Guangzhao Cui ; Limin Qin ; Sha Liu ; Yanfeng Wang ; Xuncai Zhang ; Xianghong Cao
• 关键词：Planar graph coloring problem ; PSO ; Optimization algorithm
• 刊名：Progress in Natural Science
• 出版年：2008
• 出版时间：10 March 2008
• 年：2008
• 卷：18
• 期：3
• 页码：353-357
• 全文大小：347 K

文摘

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.