File(s) under permanent embargo
Physarum-based ant colony optimization for graph coloring problem
conference contribution
posted on 2019-01-01, 00:00 authored by L Lv, C Gao, J Chen, L Luo, Zili ZhangZili Zhang© Springer Nature Switzerland AG 2019. 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.
History
Event
Swarm Intelligence. Conference (2019 : 10th : Chiang Mai, Thailand)Series
Lecture Notes in Computer Science; 11655Pagination
210 - 219Publisher
SpringerLocation
Chiang Mai, ThailandPlace of publication
Cham, SwitzerlandPublisher DOI
Start date
2019-07-26End date
2019-07-30ISSN
0302-9743eISSN
1611-3349ISBN-13
9783030263683Language
engPublication classification
E1.1 Full written paper - refereedEditor/Contributor(s)
Y Tan, Y Shi, B NiuTitle of proceedings
ICSI 2019 : Advances in Swarm Intelligence 10th International Conference, ICSI 2019, Chiang Mai, Thailand, July 26–30, 2019, ProceedingsUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC