Introduction To The Genetic Algorithm
Written by Mike James   
Article Index
Introduction To The Genetic Algorithm
Examples
Evolution Of Walking

Banner

Running the algorithm

Now you simply run the algorithm replacing each pair that you choose to breed by their two offspring and keep monitoring the average and maximum fitness of the population.

If you actually try this out you will find that the population average fitness really does slowly converge to the optimum value of x=64. Of course this isn’t too surprising as with only 64 possible types of unit almost any search method should find the fittest values in a few tries. What is more impressive is that similar problems with much larger search spaces also converge.

The Schema Theorem

There is a theorem, “The Schema Theorem”, which gives some sort of confidence that a genetic algorithm will actually improve the population fitness but there is no proof that it will find the best solution.

In fact there is a great deal of evidence that the genetic algorithm doesn’t produce the best solution in general but the most “robust”. A robust solution is one that isn’t sensitive to small changes in its specification. That is, a robust solution is a practical solution in that you can manufacture it and it will work well even if it isn’t produced exactly to specification.

I suppose the important question is whether or not the genetic algorithm is better than other forms of randomly searching for better units.

This is a difficult question to answer but genetic algorithms do have advantages.

Apart from being simple to implement they also make use of a parallel search of the parameter space. They also have the strange property of increasing “good” bit patterns in the genes at an exponential rate. That is, if particular patterns of bits in the gene are associated with a high level of fitness then the genes in the population very quickly acquire these patterns.

The “crossover” method of breeding is designed to make sure that this happens. In our example of maximizing the square of the value the pattern or “schema” [1****], where the asterisk means a zero or a one, is associated with a high degree of fitness. As the genetic algorithm runs the percentage of units with the schema [1****] increases rapidly. The next best schema is [*1***] and this increases in number rapidly and so on until all of the population has [11111] for their genes!

Going further

After this basic introduction to the genetic algorithm you might well be tempted to go and find out more.

If you do then be prepared to be swamped by biological jargon and countless variations on the basic theme. You will, for example, discover variations on how the genes are combined in reproduction. Many genetic algorithms treat genes as bit patterns that wrap round to make circles and reproduction occurs by selecting two cut points and swapping the smallest part of a pair of “gene rings”.

 

fig2

Circular genes make crossover easier

 

You will also find methods that attempt to make the genetic algorithm more true to the real workings of genetics – recessive genes, diploidy and dominance – in most cases these are reasonable but mostly unnecessary. The fact of the matter is that the basic genetic algorithm works well enough and anything you do to tinker with it makes little difference. What matters is a good coding of the units’ characteristics as genes, the size of population and how many generations you are prepared to let it run to. It is probably worth saying that genetic algorithms have proved useful in fields as widely separated as breeding robots, electronic circuits, optimising routes, breeding investment strategies and so on.

 

fig3

A real genetic algorithm program – WinGA-in action

 

Some Examples Of GA In Action

Breeding A Face

Pareidoloop is a program which uses a GA approach to create a face that satisfies a face recognition algorithm - and all using JavaScript.

If you go through enough generations the solutions should keep getting better as the population evolves towards a better fitness.

pareidoloop

Image:Philip Mccarthy

This is the idea behind Pareidoloop. It uses a face detection program written in JavaScript. This is taken from Liu Liu's  Core Computer Vision library which provides a range of image processing algorithms as well as face detection and is well worth knowing about.

Next code up a way to generate random polygons such that the representation can take part in the GA. This part of the program is based on an earlier experiment with trying to breed the Mona Lisa - see Roger Alsing’s Evolution of Mona Lisa.

All you have to do next is to run the GA and use the output of the face detection program as the measure of fitness of each individual in the population. Keep the generations turning over and eventually you will reach a reasonable arrangement of polygons which activates the face detection algorithm - i.e. it looks like a face.

Why Pareidoloop?

This is the term for the phenomenon of seeing things like faces in random textures. I'm not sure that this is quite Pareidoloop in that the input isn't random as it is being designed for the purpose.

Is there any purpose to this?

Unlikely, but it is a good demonstration of the GA in action and the images it creates are kind of spooky. There might be a call for artistic renderings of the eigenface of face detection, but mostly it's just fun.

You can find out more at: Pareidoloop

Evolving Soft Robots

The genetic algorithm can be used to evolve solutions to all types of problem. In this case it evolves "soft robots" with body parts built from a range of materials. 

 

softrobotIn just 1000 generations the genetic algorithm creates some amazing solutions to the task of getting from A to B as fast as possible.

Building on the work of Karl Sims and his biomorphs, the team of researchers at Cornell allowed the robots to have bodies made of a mixture of soft and rigid materials. The idea is that evolving bodies using the genetic algorithm had hit a ceiling on the level of sophistication achievable because they were all restricted to mainly rigid components. More natural organisms might result from evolution applied to more natural materials. 

The second novel feature of this experiment is the coding used. This is a common difficulty with implementing the genetic algorithm.  You need to find a genetic coding that allows the full range of possible types to be represented in a natural way. The shape and behavior of the robots was determined using a Compositional Pattern Producing Network. This is like a neural network but the nodes can output using any function of the inputs. The network can be driven with the location in the body of the voxel (volume pixel)and it can output properties for that voxel. The network itself can be evolved using genetic algorithm. 

 

CPPN

The CPPN generates the make up of each robot according to the position of each voxel


<ASIN:0471455652>

<ASIN:9810236026>

<ASIN:B000VXKLLO>

<ASIN:0471315311>

<ASIN:1501087703>

<ASIN:0471576794>

<ASIN:1493303570>

<ASIN:354073189X>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.