Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
A Memetic Algorithm with Two Distinct Solution Representations for the Partition Graph Coloring Problem
verfasst von : Petrica C. Pop, Bin Hu, Günther R. Raidl
Erschienen in: Computer Aided Systems Theory - EUROCAST 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we propose a memetic algorithm (MA) for the partition graph coloring problem. Given a clustered graph
G
= (
V
,
E
), the goal is to find a subset
V
*
⊂
V
that contains exactly one node for each cluster and a coloring for
V
*
so that in the graph induced by
V
*
, two adjacent nodes have different colors and the total number of used colors is minimal. In our MA we use two distinct solution representations, one for the genetic operators and one for the local search procedure, which are tailored for the corresponding situations, respectively. The algorithm is evaluated on a common benchmark instances set and the computational results show that compared to a state-of-the-art branch and cut algorithm, our MA achieves solid results in very short run-times.