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


Abstract:

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 over-all 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.

Año de publicación:

2003

Keywords:

  • drift
  • Epistasis
  • Genetic Algorithms
  • mutation
  • NK-landscapes
  • Nonlinear fitness functions
  • Recombination
  • Selection

Fuente:

scopusscopus

Tipo de documento:

Other

Estado:

Acceso restringido

Áreas de conocimiento:

  • Evolución
  • Evolución
  • Algoritmo

Áreas temáticas de Dewey:

  • Métodos informáticos especiales
  • Probabilidades y matemática aplicada
  • Genética y evolución
Procesado con IAProcesado con IA

Objetivos de Desarrollo Sostenible:

  • ODS 15: Vida de ecosistemas terrestres
  • ODS 11: Ciudades y comunidades sostenibles
  • ODS 12: Producción y consumo responsables
Procesado con IAProcesado con IA