TY - GEN
T1 - Physarum-based ant colony optimization for graph coloring problem
AU - Lv, Lingyan
AU - Gao, Chao
AU - Chen, Jianjun
AU - Luo, Liang
AU - Zhang, Zili
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Ant colony algorithm
KW - Graph coloring problem
KW - Physarum mathematical model
KW - Physarum-based ant colony optimization
UR - https://www.scopus.com/pages/publications/85073914662
U2 - 10.1007/978-3-030-26369-0_20
DO - 10.1007/978-3-030-26369-0_20
M3 - 会议稿件
AN - SCOPUS:85073914662
SN - 9783030263683
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 210
EP - 219
BT - Advances in Swarm Intelligence - 10th International Conference, ICSI 2019, Proceedings
A2 - Tan, Ying
A2 - Shi, Yuhui
A2 - Niu, Ben
PB - Springer Verlag
T2 - 10th International Conference on Swarm Intelligence, ICSI 2019
Y2 - 26 July 2019 through 30 July 2019
ER -