This content was published by Andrew Tomazos and written by several hundred members of the former Internet Knowledge Base project.
Fitness Landscapes and Optimization Techniques
Even though the above description introduces genetic algorithms in a very comprehensive manner, with any type of optimization problem which uses a genetic algorithm there is an even more abstract decision making layer to deal with - ie what optimization technique to use with the genetic algorithm as the foundation.
At ths point it makes sense to introduce the concept of a fitness lanscape. The term fitness landscape speaks for itself, as it is the fitness function evaulated over the whole spectrum of different solutions to the problem. Presumably as every solution has many variables which it is uniquely determined by, the fitness landscape can be a very high dimensional space.
So what do we use this landscape for? By definition the nature of the landscape is completely determined by the problem itself and NOT the technique used to solve it. The nature of the landscape can tell us which type of optimization is going to be the most effective one. It can give us a clue as to what ratio of mutation vs crossover to use. The way we can assess the nature of a fitness landscape is to apply some information theory measures to random walk data across the landscape. Doing this can give information about the ruggedness of the landscape, how many local optima exist, whether or not there exists a global optimum and what step size is best for reaching the optimum.
But how do we accurately implement average step size in our genetic algorithm? First one has to note that in fitness landscape terms a crossover operation (hence operator) is a global search and mutation is a local search operator! This is so because crossover attempts to find a solution "half-way" between two solutions which could be very far apart on the landscape whereas mutation simply makes a small change to an existing solution. One can see that with the amount of mutation applied one can vary the step size of the optimization fairly accurately.
One has to note that the efficiency of all crossover operations is very much dependent on the original starting population - and in fact the spread of the population of the landscape at any generation. Only if this is the case can global searching be performed effectively.
And even with all of the above in place, genetic algorithms will not give you the optimal answers you're after if you do not guide them. Obviously, on average if you keep throwing away the worst solutions you would expect your best solution to improve over time. But it might happen (more often than not) that over time your whole population of solutions might converge to a fairly small area of the landscape and even though your answers are good, you might be missing out on the really good ones some distance apart.
The problem is that with deterministic selection of the fittest solutions will make you get stuck in a local optimum and the nature of the landscape might be such that to get to another (better) optimum you'd have to go through a long patch of bad solutions.
There exist at least two obvious answers to this - either allow for a probablistically small acceptance of solutions worse than the fittest or attempt to maintain diversity within your population.
For the first solution there exist countless variations of the acceptance probability, which is a whole field of study in itself. And the second can be difficult to implement, but in the cake baking example earlier the distance between two recipes would be just the hamming distance between their respective genomes.
Back to Index