Volume 6 Number 6 (Jun. 2011)
Home > Archive > 2011 > Volume 6 Number 6 (Jun. 2011) >
JCP 2011 Vol.6(6): 1175-1182 ISSN: 1796-203X
doi: 10.4304/jcp.6.6.1175-1182

Hybrid Discrete Particle Swarm Algorithm for Graph Coloring Problem

Jin Qin1, 2, Yi-xin Yin1, Xiao-juan Ban1
1College of Information Engineering, University of Science & Technology Beijing, Beijing, China
2College of Computer Science & Information, Guizhou University, Guiyang, China


Abstract—Graph coloring problem (GCP) is one of the most studied combinatorial optimization problems. It is important in theory and practice. There have been many algorithms for graph coloring problem, including exact algorithms and (meta-)heuristic algorithms. In this paper, we attempt another meta-heuristic method⎯particle swarm optimization to graph coloring problem. Particle swarm optimization (PSO) was originally developed for continuous problem. To apply PSO to discrete problem, the standard arithmetic operators of PSO are required to be redefined over discrete space. A conception of distance over discrete solution space is introduced. Under this notion of distance, the PSO operators are redefined. After reinterpreting the composition of velocity of a particle, a general discrete PSO algorithm is proposed. In order to solve graph coloring problem by the discrete PSO algorithm, an algorithm to implement the crucial PSO operator⎯difference of two positions (solutions) is designed. Then, a hybrid discrete PSO algorithm for graph coloring problem is proposed by combining a local search. Empirical study of the proposed hybrid algorithm is also carried out based on the second DIMACS challenge benchmarks. The experimental results are competitive with that of other well-known algorithms.

Index Terms—Graph coloring problem, DIMACS benchmarks, discrete particle swarm optimization, distance, redefinition of operators

[PDF]

Cite: Jin Qin, Yi-xin Yin, Xiao-juan Ban , "Hybrid Discrete Particle Swarm Algorithm for Graph Coloring Problem," Journal of Computers vol. 6, no. 6, pp. 1175-1182, 2011.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>