Academic Journals Database
Disseminating quality controlled scientific knowledge

Two genetic algorithms for the bandwidth multicoloring problem

ADD TO MY LIST
 
Author(s): Fijuljanin Jasmina

Journal: Yugoslav Journal of Operations Research
ISSN 0354-0243

Volume: 22;
Issue: 2;
Start page: 225;
Date: 2012;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: evolutionary computation | graph coloring problem | combinatorial optimization

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.
Why do you need a reservation system?      Affiliate Program