Genetic Algorithms And Evolutionary Learning .*;

Simple Function Example 1

This example uses a fairly limited genetic algorithm to generate a combination five numbers and four operators that results in a target number.

These are the constraints of this example:

  1. The population remains the same size from one generation to the next; the chromosomes that aren't selected for reproduction are overwritten by the offspring of those that are selected.  Only enough offspring are created to make the population a specified size, so even though several chromosomes are selected for reproduction, not all get to reproduce.
  2. Selection is accomplished using a general random method.
  3. The usual operator precedence rules of algebra are not used, the expressions are simply evaluated from left to right.
  4. Mutation is not implemented in this example.  This is a significant omission, but it helps to illustrate the usefulness of random mutations.

You can adjust:

  • Target - the target number the algorithm should try to achieve.
  • MaxInputs - the number of chromosomes in the population.
  • MaxEpochs - number of generations to attempt before giving up.

Remember, the larger you set MaxInputs and/or MaxEpochs, the longer your computer may take to finish running it.  When I wrote this, I wanted to see all the data, which of course means storing it in a TempString variable which really slows thing down.

NOTE: The way I've designed the GetFitness function in this example, the computer will sometimes hang or throw an "NaN" error message.

NaN means "not a number". This will often show up when a "divide-by-zero"-like error occurs while using type Double variables (as opposed to integers). The way I've implemented this genetic algorithm, it will sometimes weed out all but the one chromosome closest to the target, which leaves nothing but a whole population of the exact same chromosome. And when there's no diversity, the algorithm will only be able to generate "NaN" for fitness scores.

In Example 2, I've added a little code to avoid this.

 

Example Results

Since this example has so many limits, the algorithm doesn't often achieve the target (i.e.: 100).  It'll go through 30 epochs, sometimes arriving at only a population of clones (none of which is the target).

After randomly constructing the initial population, the algorithm sees "112" as the closest to the target, and "2520" as the furthest way.  It's not unusual at all to see a wild variation in the beginning.

010011110110111100101101011111000110 = -13	95.8056478405316%
011011000100110110001100100011110100 = -4	96.1794019933555%
000110100011111110001010011111110001 = 8	96.6777408637874%
001110110011101000101011011010110010 = 16	97.0099667774086%
011011010100101100011100010111010110 = -8	96.0132890365448%
001111101000111000101011100011010100 = 52	98.5049833887043%
011011000010111001011100000010100000 = 20	97.1760797342193%
010010110001111010001010000111000111 = 34	97.7574750830565%
100111000101101000001111011011000100 = -3	96.2209302325581%
010111000001111101001100011111000001 = -7	96.0548172757475%
100010110111111001101110011010111000 = 548	81.8936877076412%
100111001001101010011101000111001000 = 0	96.3455149501661%
011010110011111001001100011111100000 = 0	96.3455149501661%
000111000000110001111110100110110100 = -50	94.2691029900332%
001010100010110100101101010111100011 = -9	95.9717607973422%
000111000101110000001100000111111000 = -1	96.3039867109635%
000011010110101110001110011011011000 = 4	96.5116279069767%
010011010101101101101101010010101001 = 10	96.7607973421927%
010111100011110101011110100011000011 = 77	99.5431893687708%
010110110001110110011110010111101000 = -120	91.3621262458472%
010011010100111000011110001110110111 = 7	96.6362126245847%
010110110111111000111100001111101000 = 264	93.687707641196%
100011010011110010001101100111000100 = -16	95.6810631229236%
011011110100111000101101000111100101 = 10	96.7607973421927%
010111110100110101111100001011000101 = -13	95.8056478405316%
001111000110111001111100000110110100 = -18	95.5980066445183%
011110100110110001111100000111100010 = 10	96.7607973421927%
000110110100101000011110010011100000 = 0	96.3455149501661%
000111010101111100001110001111000010 = -14	95.7641196013289%
011011000110111100111101100110100010 = -7	96.0548172757475%
010111100100110100001101000111100001 = 19	97.1345514950166%
000011100001110101011101001011011000 = -15	95.7225913621263%
010111011000111110011110011111100111 = -16	95.6810631229236%
011011100100101100111111010011010101 = 2	96.4285714285714%
011011100011110101001111010011010000 = 4	96.5116279069767%
100111000111110001111100001111010001 = -9	95.9717607973422%
100011010111101101001100010011001000 = -7	96.0548172757475%
100010110111111000111110011111101000 = 2520	0%
100010110111111101001101000111001001 = -6	96.0963455149502%
001010101000101010011010100111100100 = 112	100%
000010111000101000011011011011000101 = 10	96.7607973421927%
100010110011110000101110011011000111 = 47	98.297342192691%
011010110111110001111101100110100001 = -2	96.2624584717608%
010110110101110110001010000011110011 = 1	96.3870431893688%
011111000001110100101110001011011000 = 0	96.3455149501661%
100010110101111010001011100111000000 = 113	99.9584717607973%
011111000100110100101111010011000111 = -7	96.0548172757475%
000111110100101100011110000111100011 = 4	96.5116279069767%
001010101000111000111111010011000001 = 6	96.5946843853821%
000111101000110101101011010010100010 = 8	96.6777408637874%

 

However, after 30 epochs, the algorithm produces a population that are all very similar and closer to the target.  Now the best is "101" and worst is only "113".

 

010011100011111010001010000110110100 = 101	100%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000110110100 = 101	100%
011010110111111010001010000111000000 = 105	66.6666666666667%
010010110111111010001010100110110100 = 101	100%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000110100001 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000111000000 = 97	83.3333333333333%
100010110101111010001010000111000111 = 98	91.6666666666667%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000111000000 = 97	83.3333333333333%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000111000000 = 97	83.3333333333333%
011010110111111010001010000111000111 = 98	91.6666666666667%
011010110111111010001010000111000111 = 98	91.6666666666667%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010100111000000 = 105	66.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000111000000 = 97	83.3333333333333%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000111000000 = 97	83.3333333333333%
100010110101111010001010000111000111 = 98	91.6666666666667%
011010110111111010001010000111000000 = 105	66.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000110110100 = 101	100%
011010110111111010001010000111000000 = 105	66.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000110110100 = 101	100%
100010110101111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
011010110111111010001010000111000111 = 98	91.6666666666667%
011010110111111010001010000111000000 = 105	66.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010100110110100 = 109	33.3333333333333%
011010110111111010001010100111000000 = 113	0%
010011100011111010001010000111000000 = 97	83.3333333333333%
011010110111111010001010000110110100 = 109	33.3333333333333%
010011100011111010001010000111000111 = 90	25%
100010110101111010001010000110110100 = 109	33.3333333333333%
011010110111111010001010000111000111 = 98	91.6666666666667%
010011100011111010001010000110110100 = 101	100%
010011100011111010001010000111000000 = 97	83.3333333333333%
010011100011111010001010000111000111 = 90	25%

Done.
Completed 30 epochs.

 

Alas, despite the ability of the algorithm, this example rarely achieves the target, unless it happens upon it randomly early on.  This is where mutation and other factors come in.

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}