Evolutionary vs Revolutionary Algorithms

http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/

This is a nice little post on building a simple evolutionary algorithm.  I have not thought of applying it to string mutation but its a nice little application.

A couple of thoughts occur to me.

The first being that "evolution" is strongly encoded in the mutation algorithm which single-steps one of the characters in the string a single position ( plus or minus). Which produces a slightly random systematic search strategy.  A "revolutionary" approach would be to randomly replace a character in the string with another character. 
If this approach was taken, then it would introduce much greater possible degree of individual mutation.  This is detrimental for a population of one but would be much more valuable if there is a larger population using cross-over and cull based on fitness.  Beneficial mutations would be quickly reinforced.  In a population of one, there is no chance to move toward beneficial or away from detrimental mutations.  You just keep randomly mutating until you exactly hit the target.   

Either way, this is still essentially a search strategy toward a known target. As long as the fitness function and the mutation function can play together to move the solution toward the target, it will eventually get there.

The more interesting application is moving toward an unknown target, which means the fitness function needs to have some method of either encoding the properties of a desirable solution ( beware of assumptions) or have some way to brute force test each possible solution in some fashion and collect some metrics from the test to measure fitness.

The mutation function can then either take an evolutionary or revolutionary approach to seeking new solutions.

The next level of subtlty is to introduce a more complex fitness function that evaluates both the overall fitness and "sections" of fitness.  In the example above, it would be beneficial to evaluate the overall closeness of the string and the closeness of the first and second halves.  This way, its possible to introduce multiple mutations in each generation, rather than a single mutation per step.


What is the benefit of this?  Its the same process just running in parallel.  Parallel evolution anyone?

You could add random cross overs along with culling based on part and whole fitness values. (So a solution with a high fitness in one half would not be culled even though its overall fitness may be low. )

This allows the solution to evolve at different rates in different parts of its DNA. Again evolutionary rather than revolutionary.

The next stage of fun being to randomly add or remove modules from the solution string and do some sort of fitness evaluation on different parts of the solution string, for different parts of the target.  This allows a valuable mutation to may occur in one section to migrate to a different location in the target string, even though it was useless in the position it occurred in initially.

 We will call this a matrix of fitness functions.  More dimensions can be added to the fitness matrix, depending on how bored you are. 

The choice really comes down to the type of mutation function, is it evolutionary (incremental steps) or revolutionary ( random jumps).  The first can get trapped on plateaus while the second wanders much more wildly.  We need a mix of both.  The question is the influence of either in the mutation algorithm.   Next trick would be to vary that based on the fitness value.  Need to figure out a continuum effect for the mutation algorithm while still keeping it blind to the eventual target state.

Endless fun...