Genetic Algorithm Code

[James_McN]

Functional Description

This code demonstrates how a genetic algorithm can be developed in LabVIEW.  This is the example from my blog post at.  For more general details on genetic algorithms the theory is explained there.

The scenario for this algorithm is:

Max is a robot for cleaning rooms. Each of the rooms consists of 100 spaces (10x10) and Max can see in his space and the four adjacent spaces (North, South, East, West).  Each space that he can see is either empty (0), full of rubbish (1) or be a wall if it is at the edge (2).  In each space Max can choose to move to an adjacent space, pick up rubbish, do nothing or do something random.  Each room has 50 spaces occupied by rubbish and Max gets 10 points for every piece he picks up but loses 1 point for trying to pick up rubbish which is not there and 5 points for hitting a wall.

We can see the required elements are in this problem.

• Scenarios - Each space can be in 3 states and Max can see 5 at any time so there are 3^5 = 243 different scenarios to account for.
• Actions - Max has a choice of 7 actions that could be completed in any scenario.
• Scoring - There is a system of measuring his success.

For this algorithm we are going to use 200 genes and run each one through task 100 times and use the average to score them.  We run up to 1000 generations to ensure the best possible result.  To do this we begin by generation a 200x243 array of random numbers from 0-6.  Each row of 243 elements is a gene and each element is an action for a given scenario.  The scenarios are coded as a base 3 number to then get a decimal to choose the action.  Each gene is then run through a simulator to obtain a score and ranked by the score of 100 runs.  These are then crossed over and mutated as described above to improve them and the process repeated.

The program is attached to have a look and hopefully help to explain what is happening. As an example of the success we use the optimum probability of mutation which in this case is 0.006.  Using this the genetic algorithm can achieve an average score of 472.  That is extremely close to the maximum of 500 per run!  For a comparison when building a gene based on my personal logic (possibly flawed!) I could only achieve an average of 430.

Screenshots

Additional Information

This code is written in LabVIEW 2009 but only uses basic math and array functions so could theoretically work in all versions of LabVIEW.

[EngrStudent]

I can't immediately tell.  Is there a chance that the same "gene" is re-tested a number of times, or is it tested one time only and the score is stored?