A hybrid parallel genetic algorithm approach for graph coloring

Article type: Research Article

Authors: Sivanandam, S.N.^{; *} | Sumathi, S. | Hamsapriya, T.

Affiliations: P.S.G College of Technology Coimbatore, Tamilnadu, India, 641004

Correspondence: [*] Corresponding author. E-mail: prish_67@yahoo.co.in

Abstract: Graph-Coloring problem (GCP) deals with assigning labels (colors) to the vertices of a graph such that adjacent vertices do not get the same color. Coloring a graph with minimum number of colors is a well-known NP-hard problem. In this paper a new permutation based representation of graph coloring problem is solved using a parallel genetic algorithm (PGA). Migration model of parallelism is used with Message passing interface (MPI) for implementation of parallel genetic algorithm. Three-crossover operators namely greedy partition crossover (GPX), Uniform independent set crossover (UISX), and Permutation-based crossover (PX) are used. The performance of the three crossover operators is investigated in terms of convergence and execution time for standard benchmark graphs. The results show that GPX performs well in terms of convergence and PX in terms of execution time. The three crossover operators in parallel genetic algorithm outperform the serial genetic algorithm approximately by a factor of three. The paper is also validated with the static wavelength assignment problem in optical networks.

Keywords: Graph coloring problem, parallel genetic algorithm, migration model, message passing interface (MPI), static wavelength assignment

DOI: 10.3233/KES-2005-9309

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 9, no. 3, pp. 249-259, 2005