A Study on the Behavior of Genetic Algorithms on NK-Landscapes: Effects of Selection, Drift, Mutation, and Recombination

Hernan AGUIRRE  Kiyoshi TANAKA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.9   pp.2270-2279
Publication Date: 2003/09/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Nonlinear Theory and its Applications)
Category: Neuro, Fuzzy, GA
Keyword: 
genetic algorithms,  NK-Landscapes,  epistasis,  nonlinear fitness functions,  selection,  drift,  mutation,  recombination,  

Full Text: PDF(633.5KB)
>>Buy this Article


Summary: 
NK-Landscapes are stochastically generated fitness functions on bit strings, parameterized with N bits and K epistatic interactions between bits. The term epistasis describes nonlinearities in fitness functions due to changes in the values of interacting bits. Empirical studies have shown that the overall performance of random bit climbers on NK-Landscapes is superior to the performance of some simple and enhanced genetic algorithms (GAs). Analytical studies have also lead to suggest that NK-Landscapes may not be appropriate for testing the performance of GAs. In this work we study the effect of selection, drift, mutation, and recombination on NK-Landscapes for N = 96. We take a model of generational parallel varying mutation GA (GA-SRM) and switch on and off its major components to emphasize each of the four processes mentioned above. We observe that using an appropriate selection pressure and postponing drift make GAs quite robust on NK-Landscapes; different to previous studies, even simple GAs with these two features perform better than a random bit climber (RBC+) for a broad range of classes of problems (K 4). We also observe that the interaction of parallel varying mutation with crossover improves further the reliability of the GA, especially for 12 < K < 32. Contrary to intuition, we find that for small K a mutation only evolutionary algorithm (EA) is very effective and crossover may be omitted; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone (K > 12). This work indicates that NK-Landscapes are useful for testing each one of the major processes involved in a GA and for assessing the overall behavior of a GA on complex non-linear problems. This study also gives valuable guidance to practitioners applying GAs to real world problems of how to configure the GA to achieve better results as the non-linearity and complexity of the problem increases.