首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Hybrid Discrete Particle Swarm Algorithm for Graph Coloring Problem
  • 本地全文:下载
  • 作者:Qin, Jin ; Yin, Yi-xin ; Ban, Xiao-juan
  • 期刊名称:Journal of Computers
  • 印刷版ISSN:1796-203X
  • 出版年度:2011
  • 卷号:6
  • 期号:6
  • 页码:1175-1182
  • DOI:10.4304/jcp.6.6.1175-1182
  • 语种:English
  • 出版社:Academy Publisher
  • 摘要: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.
  • 关键词:graph coloring problem;DIMACS benchmarks;discrete particle swarm optimization;distance;redefinition of operators
国家哲学社会科学文献中心版权所有