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: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Jul 19, 2019 News!

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

  • Jun 21, 2019 News!

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

  • Apr 28, 2019 News!

    Vol 14, No 5 has been published with online version 7 papers are published in this issue after peer review   [Click]

  • Mar 20, 2019 News!

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

  • Feb 22, 2019 News!

    Vol 14, No 2 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Read more>>