×

A new hybrid genetic algorithm for the robust graph coloring problem. (English) Zbl 1205.68378

Gedeon, Tamás D. (ed.) et al., AI 2003: advances in artificial intelligence. 16th Australian conference on AI, Perth, Australia, December 3–5, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20646-9/pbk). Lecture Notes in Computer Science 2903. Lecture Notes in Artificial Intelligence, 125-136 (2003).
Summary: The RGCP (Robust Graph Coloring problem) is a new variant of the traditional graph coloring problem. It has numerous practical applications in real world like timetabling and crew scheduling. The traditional graph coloring problem focuses on minimizing the number of colors used in the graph. RGCP focuses on the robustness of the coloring so that the coloring is able to handle uncertainty that often occurs in the real world. By that, we mean that given a fixed number of colors we would like to color the graph so that adjacent vertices are assigned different colors with the consideration of the possible appearance of the missing edges. In this paper, we present a new hybrid genetic algorithm (GA), which embeds two kinds of local search algorithms – enumerative search and random search within the GA framework. In addition, we integrate a partition based encoding scheme with a specialized crossover operator into our GA method. We also propose an adaptive scheme that alternates between two local search methods to increase performance. Experimental results show that our new algorithm outperforms the best published results in terms of the quality of solutions and the computing time needed.
For the entire collection see [Zbl 1088.68007].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI