GRAPH-COLORING WITH ADAPTIVE EVOLUTIONARY ALGORITHMS

This paper presents the results of an experimental investigation on so lving graph coloring problems with Evolutionary Algorithms (EAs). Afte r testing different algorithm variants we conclude that the best optio n is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the ev olution. This adaptive EA is general, using no domain specific knowled ge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique D Satur and the Grouping Genetic Algorithm (GGA) on a wide range of prob lem instances with different size, topology and edge density. The resu lts show that the adaptive EA is superior to the Grouping (GA) and out performs DSatur on the hardest problem instances. Furthermore, it scal es up better with the problem size than the other two algorithms and i ndicates a linear computational complexity.