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


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”.



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.



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.



Image:Philip Mccarthy




Why Pareidoloop?


Is there any purpose to this?


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. 

















RSS feed of all content
I Programmer - full contents
Copyright © 2016 All Rights Reserved.