An improved hybrid ant-local search algorithm for the partition graph coloring problem

作者：Fidanova Stefka^*; Pop Petrica

来源：Journal of Computational and Applied Mathematics, 2016, 293: 55-61.

DOI：10.1016/j.cam.2015.04.030

• Partition graph coloring problem
• Metaheuristics
• Ant Colony Optimization
• Local search

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* subset of 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.

• 出版日期2016-2