In this paper the Bandwidth Multicoloring Problem (BMCP) and the Bandwidth Coloring Problem (BCP) are considered. The problems are solved by two genetic algorithms (GAs) which use the integer encoding and standard genetic operators adapted to the problems. In both proposed implementations, all individuals are feasible by default, so search is directed into the promising regions. The first proposed method named GA1 is a constructive metaheuristic that construct solution, while the second named GA2 is an improving metaheuristic used to improve an existing solution. | Yugoslav Journal of Operations Research 22 (2012), Number 2, 225-246 DOI: TWO GENETIC ALGORITHMS FOR THE BANDWIDTH MULTICOLORING PROBLEM Jasmina FIJULJANIN Faculty of Matematics University of Belgrade, Belgrade, Serbia fjasmina@ Received: September 2010 / Accepted: August 2012 Abstract: In this paper the Bandwidth Multicoloring Problem (BMCP) and the Bandwidth Coloring Problem (BCP) are considered. The problems are solved by two genetic algorithms (GAs) which use the integer encoding and standard genetic operators adapted to the problems. In both proposed implementations, all individuals are feasible by default, so search is directed into the promising regions. The first proposed method named GA1 is a constructive metaheuristic that construct solution, while the second named GA2 is an improving metaheuristic used to improve an existing solution. Genetic algorithms are tested on the publicly-available GEOM instances from the literature. Proposed GA1 has achieved a much better solution than the calculated upper bound for a given problem, and GA2 has significantly improved the solutions obtained by GA1. The obtained results are also compared with the results of the existing methods for solving BCP and BMCP. Keywords: Evolutionary computation, graph coloring problem, combinatorial optimization. MSC: 90C59, 68T20. 1. INTRODUCTION . Problem definitions The vertex coloring problem on graphs (VCP) is a well-known NP-complete problem that has been studied extensively. The first coloring algorithms date back to the 1960s [10, 39] and since then, important progress has been made. Nowadays literature contains a great number of heuristic algorithms that belong to three main solution 226 Jasmina Fijuljanin / GA for the BMCP approaches: sequential construction (very fast methods but not particularly efficient), metaheuristics (tabu search [3, 12, 15, 17], simulated annealing [6, 20], iterated local search [7, 9], variable neighborhood .
