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

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:293

Article

Fidanova, Stefka¹  Pop, Petrica² 

[1] Bulgarian Acad Sci, Inst Informat & Commun Technol, BU-1113 Sofia, Bulgaria

[2] Tech Univ Cluj Napoca, North Univ Ctr Baia Mare, Dept Math & Comp Sci, Cluj Napoca, Romania

关键词: Partition graph coloring problem;    Metaheuristics;    Ant Colony Optimization;    Local search;   

DOI  :  10.1016/j.cam.2015.04.030

来源: Elsevier

【 摘 要 】

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. (C) 2015 Elsevier B.V. All rights reserved.

【 授权许可】

Free