Physarum-based ant colony optimization for graph coloring problem

Lingyan Lv, Chao Gao, Jianjun Chen, Liang Luo, Zili Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Graph coloring problem (GCP) is a classical combinatorial optimization problem and has many applications in the industry. Many algorithms have been proposed for solving GCP. However, insufficient efficiency and unreliable stability still limit their performance. Aiming to overcome these shortcomings, a physarum-based ant colony optimization for solving GCP is proposed in this paper. The proposed algorithm takes advantage of the positive feedback mechanism of the physarum mathematical model to optimize the pheromone matrix updating in the ant colony optimization. Some experiments are implemented to estimate the efficiency and stability of the proposed algorithm compared with typical ant colony optimization and some state-of-art algorithms. According to these results, in terms of the efficiency, stability and computational cost, we can daringly infer that the improved ant colony optimization with the physarum model performs better than the aforementioned for graph coloring. In particular, it is recommended that the model is of rationality and the proposed algorithm is of validity, which will foster a science of color number and computational cost in GCP.

Original languageEnglish
Title of host publicationAdvances in Swarm Intelligence - 10th International Conference, ICSI 2019, Proceedings
EditorsYing Tan, Yuhui Shi, Ben Niu
PublisherSpringer Verlag
Pages210-219
Number of pages10
ISBN (Print)9783030263683
DOIs
StatePublished - 2019
Externally publishedYes
Event10th International Conference on Swarm Intelligence, ICSI 2019 - Chiang Mai, Thailand
Duration: 26 Jul 201930 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11655 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Swarm Intelligence, ICSI 2019
Country/TerritoryThailand
CityChiang Mai
Period26/07/1930/07/19

Keywords

  • Ant colony algorithm
  • Graph coloring problem
  • Physarum mathematical model
  • Physarum-based ant colony optimization

Fingerprint

Dive into the research topics of 'Physarum-based ant colony optimization for graph coloring problem'. Together they form a unique fingerprint.

Cite this