An improved hybrid ant local search algorithm for the partition graph coloring problem
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 whose nodes are partitioned into a given number of the sets, the goal of the PGCP is to find a subset V V that contains exactly one node from each cluster and a coloring for V so that in the graph induced by 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.
J. Comput. Appl. Math.