Hybrid discrete particle swarm algorithm forgraph coloring problem

作者：Qin Jin^*; Yin Yi Xin; Ban Xiao Juan

来源：Journal of Computers, 2011, 6(6): 1175-1182.

DOI：10.4304/jcp.6.6.1175-1182

• DIMACS benchmarks
• Discrete particle swarm optimization
• Distance
• Graph coloring problem
• Redefinition of operators

Graph coloring problem (GCP) is one of the moststudied combinatorial optimization problems. It isimportant in theory and practice. There have been manyalgorithms for graph coloring problem, including exactalgorithms and (meta-)heuristic algorithms. In this paper,we attempt another meta-heuristic method-particle swarmoptimization to graph coloring problem. Particle swarmoptimization (PSO) was originally developed for continuousproblem. To apply PSO to discrete problem, the standardarithmetic operators of PSO are required to be redefinedover discrete space. A conception of distance over discretesolution space is introduced. Under this notion of distance,the PSO operators are redefined. After reinterpreting thecomposition of velocity of a particle, a general discrete PSOalgorithm is proposed. In order to solve graph coloringproblem by the discrete PSO algorithm, an algorithm toimplement the crucial PSO operator-difference of twopositions (solutions) is designed. Then, a hybrid discretePSO algorithm for graph coloring problem is proposed bycombining a local search. Empirical study of the proposedhybrid algorithm is also carried out based on the secondDIMACS challenge benchmarks. The experimental resultsare competitive with that of other well-known algorithms.

• 出版日期2011
• 单位北京科技大学