• Contribute
• What's New
• Submit News

Genetic Algorithms

In nature 'building information' for plants and creatures is stored in genes. These genes are passed over from one generation to the next. During that 'pass over' process, or reproduction, genes from the male and female parent are mixed together to form the genes of the child. This mixture of genes will determine the future succes of the child. Succes in this case is called 'fitnes', meaning fitness to survive in the given environment. The phrase 'survival of the fittest' is based on this mechanism. Normally only the children who are best adapted to their environment (who are 'the fittest' will survive long enough to be able to reproduce themselves. So only the genes that lead to a succesful creature get passed on. I'm trying to summerise in a few lines a subject that one can study for years, so I hope you'll forgive me for neglecting a lot of 'details'.

This is nature's way of breeding a succesfull creature. It appears logical that this could also be a computer's way to breed a succesful robot. And in fact it is, and it's called 'genetic algoritms'.

Perhaps an example would make things a lot clearer:

Let's assume we would like to find a number below 255 called x, which has the highest value if it is raised to the second power. So find a maximum for x2 where x is in the range 0 - 255. You don't need a degree in mathematics to know the answer to this question (255), but let's see if a genetic algorithm could find it too.

First we'll need a way to make the numbers look like a string of genes (this is usually the most difficult step in working with genetic algorithms). Being computer nerds the thought of representing the numbers in binary surely comes to mind, and 255 means we'll have to use 8 bit numbers (you would almost think that this is no coincidence).

Now assume that we start with two parents, 200 and 86. In binary: 11001000 and 01010110. To cross these genes we'll pick a random point (the cross over point) in the strings, cut both strings and then paste them together crossed over, like this:

In decimal the children are 72 and 214. Now we have 4 creatures so the fitness can be calculated. Since the aim was to find the highest x2 the fitness is simple: also x2.

Creature    genes       fitness

Parent1     11001000    200^2= 40000
Parent2     01010110    86^2=   7396
Child1      01001000    72^2=   5184
Child2      11010110    214^2= 45796

From our total population of 4 the best performers (parent1 and child2) are selected to cross over again. This process will repeat untill the fitness no longer rises, and that will be the answer to the question. Or rather, it will be OUR answer to the question, because there is no guarantee that the actual answer is found. The only guarantee is that an optimum will be found of some sort, but it may be a local optimum. This technique is therefor only used when the real answer cannot be determined in another way.

The reason for the risk of finding a local maximum is based on the size of the population, and the randomness. In this example there can never be more '1's that originally present in the parents. So it can be predicted that the most likely outcome will be 11011110 (222) with a fitness of 222^2= 49284, while the mathematically correct answer would be 11111111 (255) with afitness of 255^2= 65025. This is called 'inbreeding' and a reason why for humans incest is illegal (amoungst other moral objections).

The way to overcome this issue is two fold:

1. Use a much larger population (10,000 is a normal population size)
   
2. Use mutation
   

Mutation is a random modification of a gene. Just as in real life a reproduction error, nuclear radiation etc can cause a random change in the genes. Usually this is not very advantageous, but every once in a while a mutation will make a creature more adapt to it's environment. In genetic algorithms it is used to 'jump' out of a local optimum. If instead of the fitness in our example the fitness would be a curve like this:

If the population is too smal (meaning they're not spread across the total range of options) it is most likely that the genetic algorithm will get stuck in one of the two peaks. Offhand I'd say 50% chance that the wrong peak is found (as in the picture). A random mutation can help to get unstuck and proceed in the other peak. The number of random mutations is typically very low (in the order of 1%). I have posted an example program of a genetic algorithm in search of the maximum value which can be made with a 8 bit number (which is ofcourse 255). The program is in QuickBasic, and in Dutch, but I'm sure you'll be able to appreciate the beauty of GA's when you watch it at work. Here's a screenshot compilation:

Genetic algorithm

In short: if we want to write a genetic algorithm in order to breed a succesfull robot the following steps will need to be taken:

1. Determine how to turn robot behaviour into a string of genes
2. Generate a sufficiently large population
3. Perform cross over
4. Perform (occasionally) a mutation
5. Select the fittest creature
6. Put them into the new population
7. See if the fitness is high enough to be satisfied (if no, loop to item 3)

If you look at step 1 you'll realise why the page on modelling behaviour was written (read it if you haven't done so yet). At step 5 fitness can be tested by downloading a program into your Lego pBrick and simply testing wether it does what you want it to do (for example find a bright light). If you think about this for a while a small problem becomes apparent: you don't own 20,000 Mindstorms, Cybermasters or Scouts to put them through a fitness test. And testing them one by one would be rather time consuming. So unless you manage to find a wealthy sponsor fitness testing will have to be simulated.

Modelling behaviour

Mobile robots seem to have an unlimited range of possibilities for movement, and this seems to confined only by objects in their path. But upon closer observation all movements are based on a combination of a limited set of very basic movements, 'movement building blocks' if you like. Lego engineers know this ofcourse, so they've built a complete set of movement building blocks into the Scout, which they call ROM subroutines. Using these building blocks you can design your robot's behaviour.

When designing these building blocks Lego had ease of programming in mind, and not so much behavioural modelling, but these blocks are usefull anyway. Let's take a simple example. The building blocks that we'll use are:

B1: Seek (the location of a bright light)

B2: Drive straight (in the current direction)

For easier reading we'll call the Seek building block B1 and the Drive straight building block B2. If we want to model the behaviour 'search a bright light and then drives towards it' this will look like this:

These behaviours are time limited. The robot will not search for a bright light forever, eventually it will time-out. The same applies for the straight line driving, that will only happen for a predefined time period. If that doesn't bring the robot close enough one could write

meaning after finding the proper direction drive straight forward for 6 times the predefined period of time. It is also possible that the robot isn't able to maintain the propper direction (due to rough terrain for example) so realignment is needed at regular intevals, so the behaviour could be:

meaning seek the light, drive 3 times the predefined time in that direction then seek the light again and drive 3 times in that direction again. In this example the robot might 'over shoot' so to make a complete model one additional building block is required, block B3:

B3: Stop when the light is bright enough.

And the model could look like:

Assuming you have designed the right building blocks any behaviour can be modelled. This is all very interesting (or maybe not) but is there a point to all this? Well, ofcourse. It is rather difficult to let an artificial brain control the behaviour of a robot, especially if it has to have some complexity, if it has to design all actions 'manually'. But combining building blocks is much simpeler.

To give you a silly example here's a program (QuickBasic source) that generates a random behaviour for the Scout. It will generate a Lego Assembler file ready for download into the Scout. Note that the building blocks are real this time and thus have a different number.

screenshot and part of automatically generated Scout source code

If you look at the program you'll see that it's amazingly simple. If you try to do the same thing without the building blocks you'll find that much more complicated.

These are the basic building blocks that are used in the program:

B01 Straight line
B02 Zig zag
B03 Turn right
B04 Turn left
B05 Turn right and back
B06 Turn left back and forth
B07 Drive and turn back and forth
B08 Random turns
B09 Random zig zag
B10 Seek bright light

With the actual driving pattern looking like this:

These building block drawings were made with a Scout which had a Whiteboard marker attatched to it. A picture of the Scout is at the top of this page, and details are below. Using a Whiteboard marker teaches you two things: the actual shape of the building block, and the fact that you can't wipe it off the floor....

gearing pen

Genetic algorithm robot breeding

The goal of this genetic algorithm is to breed a robot which is capable of finding a light source, and then stay in that light source for as long as possible. If you don't know what a genetic algorithm is I suggest you read the page AI/GeneticAlgorithms first, otherwise it'll be hard to understand what's going on.

The genetic algorithms uses behavioural blocks as described on the page AI/ModelBehaviour. The blocks are a bit different though:

B01 Straight line
B02 Circle
B03 Turn right
B04 Turn left
B05 Search light spot
B06 Search dark spot
B07 Bug dance

Using these blocks different behaviours are generated randomly. These behaviours are then put through a genetic algorithm to breed a solution. Rather than downloading each behaviour (string) into a Scout and testing it the behaviours are tested in a simulated environment. Depending on how wel this particular behaviour matches the goal (find a bright light and stay in it) the behaviour is awarded a fitness. The simulated environment contains a black field with one light source. Since the color code of black is zero, and the codes for yellow and white are 14 and 15 calculating fitness can be as easy as adding the colorcodes of each pixel the robot passes together. There is one problem with this method: if the robot circles it will cross it's own path (color code 10). To make my life easy I've decided to ignore color code 10. That does mean that circling in the bright spot does not count towards an increased fitness. As it turns out this is not a problem.

This genetic algorithm program used on this page introduces a few mechanisms that weren't discussed on the GA page:

1. 1. Generation gap cross-over In normal cross-over unused parents are discared after cross-over, and only the children are put in the next generation. This means succesfull parents may be lost if they're not selected for crossover. The generation gap cross-over mechanism (suggested by De Jong) put's these parents also in the next generation. This means that parents and children co-exist in one generation, hence the name of the mechanism.
   
   
2. 2. Elite Since not all parents are selected it is possible that the best of the population is not selected and thus lost. The elite mechanism makes sure that the best performer is copied into the next generation.
   
   
3. 3. Scaling In the beginning of a run fitness values may differ widely. This means that strings with a very low value tend to become 'extinct' rather quickly, thus reducing the diversity of the population prematurely. Towards the end of the run fitnesses show only tiny variation, thus preventing further optimalisation. Scaling means that fitnesses of a run are 're-scaled' to a fixed maximum difference between max and min fitness. The selection mechanism is therefor more even throughout the entire run.
   
   

This is the simulated environment with the black field and the light source with an example of a simulation run. In reality the black part fills the entire screen. This robot (who's path is indicated by the green line) is obviously moving in the wrong direction and isn't even getting close to the light source:

simulated robot way off target

This robot is doing much better. It's behaviour string seems to contain more than one B05 (search light) module so it has no difficulty finding the lightsource and staying close to it (this is an example from the end of a ga run):

simulated robot on track

At the end of each run the results so far are show in a graph. This is a good example of such a graph. The red line show the maximum fitness obtained in each run, the green line the average fitness and the blue line the minimum fitness. Each yellow dot is an actual run.

results of 16 runs

In this (real) graph it only takes a few runs before a reasonable string is found. The average fitness of all strings is steadily increasing which means the mechanism is performing well. After about 10 runs the average has reached a value where the diversity of the population has diminished and no further optimization is to be expected. And the result behaviour B05B07B06B01 seems reasonable as well.

This however is an example of a run gone wrong.

over adapted run

The graph looks allright, a normal pattern even though there's virtually no increase in the maximum value. What's wrong however is the result behaviour B07B01B04B03. The behaviour does not contain B05, the search light module. That means that this string just happens to move the robot in the right direction, but if the light were somewhere else this behaviour would fail. The fact is that the genetic algorithm worked perfectly (it found a string which matches the current environment best) but that the environment (this the fitness calculation) is not suitable (enough) to breed a flexible behaviour. In genetic terms the string has been 'over adapted' to the environment, and only minor changes (such as moving the light) will render it useless. Stuff like this kills dinosaurs, so in order to breed better strings the environment has to change occaisonally.

In the final version of the program this is done by moving the light spot across the screen, in three different positions. The light is moved in between populations. The full source (in Quick Basic) can be downloaded here. Now the result looks even more interesting.

perfect example

The sawtooth pattern shows the effect right from the start: for each location of the light spot a different string performs best, and a different maximum is obtained. After about 12 runs the diversity of the population is seriously reduced without seeminly getting closer to a good end result. After some 26 runs however a basic mechanism appears to have been found which performs well in all situations, and after run 29 this mechanism resulted in a 'universal' string. The end result of this run is B05B07B04B03B06B04, and it contains the expected B05 module.

At the end of the run the results are diplayed and a Scout source (in Lego Assembler) is automatically generated. An example:

// Automatically generated program for the Lego Scout pBrick
// by a Genetic Algorithm search: B03B06B03B04
// Copyright Bert van Dam - December 13, 1999

#include "c:\lego\scout\scouttools\ScoutDef.h"

#define Arg1 10
#define Arg2 11


task 0

  // Play system sound at start of program
  plays 3

  // Turn left (B03)
  setv Arg1,2,4
  setv Arg2,2,200
  calls 4

  // Seek bright light (B05)
  setv Arg1,2,1
  setv Arg2,2,200
  calls 9

  // Turn left (B03)
  setv Arg1,2,4
  setv Arg2,2,200
  calls 4

  // Turn right (B04)
  setv Arg1,2,3
  setv Arg2,2,200
  calls 4

endt

Will this program allways yield this result? No, just like nature doesn't yield the same results at 'each run'. Feel free to try the program and tinker with the variables, but beware that it takes quite some time to run. The largest run took 7 hrs on a 486DX4...

Basic variables to play with:

Number of strings This is the number of elements in one generation. If you keep it too small the diversity will be too low, thus possibly preventing a good end result. If you make it too high you're basically randomizing the entire search. Besides even simulation takes quite some time. I use values between 50 and 100.

String Length This is the number of behavioural blocks in a string. If you keep it too low the objective may be unattainable, if you make it too high you'll introduce unused blocks in the string. That isn't really a problem, however processing longer strings (in the simulation) also takes more time. I use values between 4 and 7.

Chance of cross-over Not all succesfull parents perform cross-over. This number indicates how many of the selected parents actually produce offspring. If you keep it too low nothing will happen, if you make it too high you'll loose diversity quite fast. I use values between 0.5 and 0.85.

Chance of mutation This indicates the chance of a mutation taking place in a run. If you keep it too low you run the risk of getting stuck in a local optimum. I keep this at 1.0 (1 mutation in every generation), perhaps that might even be higher, but then the program needs to be changed a bit.

The environment This is ofcourse the most interesting variable to play around with. If you change the environment, and the fitness calculation you breed entitely different robot behaviour. You can breed a robot which seraches for food, a robot which sleeps during the night and moves during the day. In fact anything that you can program, you can breed. Only your imagination is the limit (where have we heard that one before...)