کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4638369 | 1631998 | 2016 | 7 صفحه PDF | دانلود رایگان |
In this paper we propose a hybrid Ant Colony Optimization (ACO) algorithm for the Partition Graph Coloring Problem (PGCP). Given an undirected graph G=(V,E)G=(V,E), whose nodes are partitioned into a given number of the sets, the goal of the PGCP is to find a subset V∗⊂VV∗⊂V that contains exactly one node from each cluster and a coloring for V∗V∗ so that in the graph induced by V∗V∗, two adjacent nodes have different colors and the total number of used colors is minimal. Our hybrid algorithm is obtained by executing a local search procedure after every ACO iteration. The performance of our algorithm is evaluated on a set of instances commonly used as benchmark and the computational results show that compared to state-of-the-art algorithms, our improved hybrid ACO algorithm achieves solid results in very short run-times.
Journal: Journal of Computational and Applied Mathematics - Volume 293, February 2016, Pages 55–61