Solving the Graph Coloring Problem Using Adaptive Artificial Bee Colony

• Kui Chen

  Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba, Japan

• Kanoh Hitoshi

  Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba, Japan

抄録

Recently, some discrete swarm intelligence algorithms such as particle swarm optimization with hamming distance (HDPSO), similarity artificial bee colony (S-ABC), and discrete firefly algorithm (DFA) have been proposed to solve graph 3-coloring problems (3-GCP) and obtain good results. However, these algorithms use static parameter settings that limit their performance on graphs with various sizes and topology. In this paper, we propose a discrete adaptive artificial bee colony (A-ABC) algorithm that can adjust the parameter automatically during the evolution according to the graph size and the fitness of candidates. For the convenience of comparison, we also propose a fixed ABC (F-ABC), which is identical to A-ABC but using fixed parameter setting during the evolution. A-ABC is simple and high performance. Experiments on 3-GCP show that A-ABC dramatically outperforms its competitors F-ABC, HDPSO, S-ABC, and DFA. We also study the scout bee phase and report that the scout bee phase is not required in solving 3-GCP

収録刊行物

• 進化計算学会論文誌

  進化計算学会論文誌 9 (3), 103-114, 2019

  進化計算学会

キーワード

• swarm intelligence
• artificial bee colony
• graph coloring problem

詳細情報

• CRID: 1390001288122228224
• NII論文ID: 130007596741
• DOI: 10.11394/tjpnsec.9.103
• ISSN: 21857385
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可