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.