A hybrid Multi-Objective Genetic Algorithm for Bandwidth Multi-Coloring Problem

Standard Genetic Algorithm (GA) yields poor performance on the Graph Coloring Problem (GCP) and its variants. This paper presents a Multi-Objective Genetic Algorithm (MOGA) for Bandwidth Multi-Coloring Problem (BMCP). The problem is a generalization of GCP. In the proposed method, genetic operations are replaced with new ones which suit better to the structure of the problem. Performance of this MOGA framework is further boosted by hybridizing it with a Local Search (LS) algorithm. The aim of this hybrid approach is to increase the variety within the population through the genetic operations and to improve those individuals further by using LS. Several tests were conducted on a collection of benchmarks from GEOM series and promising results are obtained.