Graph Coloring with Adaptive Evolutionary Algorithms (bibtex)

by AE Eiben, van der Hauw, JK and van Hemert, J

Abstract:

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EA). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping GA on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping GA and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.

Reference:

Graph Coloring with Adaptive Evolutionary Algorithms (AE Eiben, van der Hauw, JK and van Hemert, J), In Journal of Heuristics, Kluwer Academic Publishers, volume 4, 1998.

Bibtex Entry:

@article{EHH98,
	_day = {01},
	abstract = {This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EA). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution.  This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping GA on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping GA and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.},
	author = {AE Eiben and van der Hauw, JK and van Hemert, J},
	date-added = {2008-08-18 12:42:43 +0100},
	date-modified = {2009-01-22 19:51:55 +0000},
	journal = {Journal of Heuristics},
	keywords = {constraint satisfaction; graph colouring},
	notedisabled = {\textsc{Cited by 108 (Google Scholar 2009/01/19); ISI impact factor = 0.644 (2007)}},
	number = {1},
	pages = {25--46},
	ps.gz = {http://www.vanhemert.co.uk/publications/heuristics.Graph_Coloring_with_Adaptive_Evolutionary_Algorithms.ps.gz},
	publisher = {Kluwer Academic Publishers},
	title = {Graph Coloring with Adaptive Evolutionary Algorithms},
	volume = {4},
	year = {1998}}