Memetic search for the equitable coloring problem

摘要

Given an undirected graph G=(V,E) and a positive integer k, an equitable legal k-coloring of G is a partition of the vertex set V into k disjoint independent sets such that the cardinalities of any two independent sets differ by one at most. The equitable coloring problem is to find the smallest k for which an equitable legal k-coloring exists. The problem has a number of applications. However, it is known to be NP-hard and thus computationally challenging. In this work, we present the first population-based memetic algorithm for solving the problem. The proposed algorithm combines a backbone-based crossover operator (to generate promising offspring solutions), a 2-phase tabu search procedure (to seek high-quality local optima) as well as a quality-and-distance based pool updating strategy (to maintain a healthy population). The computational results on 73 benchmark instances demonstrate that the proposed algorithm competes favorably with the state-of-the-art algorithms in the literature. Specifically, our algorithm attains the optimal results for all 41 instances with known optima and discovers improved upper bounds for 9 out of the 32 instances whose optimal solutions are still unknown. We investigate the benefits of the 2-phase tabu search procedure and the crossover operator with the memetic framework.