Population Flow on Fitness Landscapes
Unpublished thesis, 1994.
The last two or three decades, there has been an increasing interest in using an evolutionary approach to problem solving. At the same time, biologists are beginning to consider evolution more and more as a combinatorial optimization problem, that is, a problem with a large but finite number of solutions. But although much progress is made with these new developments, evolution itself is still not fully understood.
A successful evolutionary paradigm is the concept of a fitness landscape, i.e. the distribution of fitness values over the space of possible solutions. The evolution of a population of individuals (whether real organisms or solutions for a problem) is envisioned as a population of genotypes (the genetic coding of an individual) adapting on a fitness landscape, in search for the highest peaks. But until now, little is known about how populations adapt, or evolve, on different kinds of fitness landscapes.
This thesis tries to gain more insight into the population flow on fitness landscapes. First, a complete statistical procedure to determine and express the global structure (in terms of correlation structure) of a fitness landscape is introduced. Next, different search strategies, among others hill climbing and a genetic algorithm, are applied to NK-landscapes with different values of K relative to N, to gain more insight into population flow in general. Finally, the usefulness of recombination is examined more thoroughly, by comparing two crossover operators (one-point and uniform) on different NK-landscapes.