Example Genetic Algorithm

For this example, I created a program that starts with a bunch of random strings and tries to evolve them to create a string that reads "Management Information Systems".

The program creates a population of 100 strings. These are strings of random characters at first. Then the program creates generation after generation using the following rules:

  1. The fitness of each string is evaluated. Fitness is a measure of how closely the string matches the target string. A perfect match has a fitness score of 0. The higher the number, the worse the match.
  2. A select few (10) of the best performing members of the population are kept alive for the next generation. The rest of the population is replaced by children of the current population.
  3. The children are created by breeding. Two parents are selected from the original population and the child gets some of its characters from one parent, and the rest of its characters from the other parent. Strings with very good (low) fitness scores are more likely to breed than strings with poor (high) fitness scores.
  4. After breeding, all of the new childen are subject to random mutations. There is a small chance that any one of their characters may change into a different character.

This process continues until the program hits 1000 generations or one of the members of the population achieves a perfect fitness score (which is 0). The printout below shows one sample run of the program. To save space, the program only displays information for generations where the most fit member of the population has changed.

The printout shows the generation number, the average fitness score for the population as a whole, the fitness score for the most fit member of that generation, and the string of the most fit member of that generation.

Notice how poorly the initial random choices perform and how quickly the fitness scores improve. Almost every generation at the beginning shows amazing improvement. By generation 300, the overall fitness of the population has stagnated, but a better top performer is being produced once in a while. Finally, the 568th generation produces a perfect match.

Gen Average Best  Most fit phrase
--- ------- ----  ------------------------------
  0 1001.49  684  7hiW_VZ9`t8g2diXm_hc`BC|Y7YH~+
  1  915.18  650  m[Zlp$f`p&!9bxuHu2QalMY}cPnapb
  2  841.21  546  m[Zlp$f`p&!9bxuHu2QalM7Lfvnapb
  3  782.42  542  m[Zlp$f`p&!9bxua"_hcXs7LfPnapb
  4  709.86  525  m[Zlp$fVp&!9bxuHuyQaXs7Lfvnapb
  5  659.82  462  7[ZlpH|{`t89bdiXm_hcXs7LfvjH~+
  6  619.99  409  7hiW_VZ9`t8g~OiXm_haXs7Lfvj]pb
  7  581.38  391  7hiW_VZ9`t8g~OiXm_haXs%Lfvj]pb
  8  536.06  367  SeZl\`=Mxh?5rdiXm_hxXs7Lfvnapn
 10  493.14  350  SeZl\`=Mxh?5rdiXm_haXs%Lfvj]pn
 11  476.08  342  SeZl\`=9`t!9bxiXm_hcXs%Lfvnapn
 12  458.27  311  7aiW_Vf`xh?5rdiXm_hcXg7Lfvj]pn
 13  444.88  283  7aiW_Vf`xh?5rdiXm_hcXs%Lfvnapn
 14  430.37  273  7aiW_Vf``t!5rdiXm_hcXg7Lfvj]pn
 15  412.22  237  SaiW_Vf``t!5rdiXm_hcXs%Lfvj]pn
 18  358.98  216  SaiW_Vf``t!5rdiXm_hcms%Lfvj]pn
 20  339.06  208  SaiW_Vf``t!5rdiXm_hcms%Lfvnapn
 21  332.26  196  SaiW_Vf``t!IrdiXm_hcms%Lfvj]pn
 23  313.55  188  SaiW_Vf``t!9rdiXm_hcms%Lvvnapn
 24  307.56  184  SaiW_uf``t!IrdiXm_hhms%Lfvnapn
 25  301.77  178  SaqWm`f``t!IrdiXm_hcms%Lfvn]pn
 26  295.15  168  SaqWmVf``t!IrdiXm_hcms%Lvvnapn
 27  289.30  161  SarW_`f``t!IrdiXm_hcms%Lvvnapn
 29  283.80  157  SaiW_`f``t!IrdiXm_hhms%Lvvnapn
 30  276.49  152  SarW_`f``t!Irdiam_hcms%Lvvnapn
 31  275.08  142  SeqWY`k``t!Irdimm_hcms%Lvtnapn
 32  273.03  134  SaqW_`f``t!Irdimm_hhms%Lvvnapn
 33  263.96  128  SaqW_`l``t!Irdimm_hhms%Lvvnapn
 35  253.86  126  SaqW_`l``t!Irdimm_hhms%Lvtnapn
 36  251.44  122  SaqW_`l``t!Indimm_hhms%Lvtnapn
 37  246.30  117  SaqW_`l``t!Irdimm_whms%Lvtnapn
 40  235.80  113  SaqW_`l``t!Indimm_whms%Lvtnapn
 41  234.47  112  SaqW_`l`ft!Irdimm_whms%Lvtnain
 42  231.56  111  SaqW_`l`ft!Irdimm_whms%Lvtnapn
 44  227.01  107  SaqW_`l``t!Indimm_whms%Tvtnapn
 46  226.01  105  SaqW_`l`ft!Irdimm_whms%Tvtnapn
 47  224.75  101  SaqW_`l`ft!Indimm_whms%Tvtnapn
 50  222.49   99  Saq]_`l`ft!Irdimm_whms%Tvtnapn
 52  218.67   95  Saq]_`l`ft!Indimm_whms%Tvtnapn
 54  219.61   92  Saq]_`l`ft!Indimm_whms%Tvtnamn
 56  216.36   90  Saq]_`l`ft!Indimm_whmn%Tvtnapn
 58  211.78   87  Saq]_`l`ft!Indimm_whmn%Tvtnamn
 60  207.20   85  Saq]_`l`kt!Indimm_whmn%Tvtnapn
 61  206.11   83  Saq]_`l`kt!Indimm^whmn%Tvtnamn
 62  205.27   82  Saq]_`l`kt!Indimm_whmn%Tvtnamn
 63  203.16   78  Saq]_`l`kt!Indimm_whmn%Tvtnamr
 65  201.20   75  Saq]_`lgkt!Indimm_whmn%Tvtnamr
 67  197.65   73  Saq]_`lgkt!Indipm_whmn%Tvtwamn
 68  197.61   69  Jaq]_`lgkt!Indimm_whmn%Tvtwamr
 70  196.71   66  Jaq]_`lgkt!Indipm_whmn%Tvtwamr
 71  191.75   64  Jaq]_`lgkt!Indimm_whmn Tvtwamr
 75  188.69   61  Jaq]_`lgkt!Indipm_whmn Tvtwamr
 82  182.14   60  Jaq]_`lgkt!Indipm_whmn T{twamr
 85  183.66   59  Jaq]_`lgkt!Indism_whmn T{twamr
 88  181.08   58  Jao]_`lgkt!Indipm_whmn T{twamr
 90  179.68   57  Jao]_`lgkt!Indism_whmn T{twamr
 91  179.49   56  Jao]_`lgpt!Indism_whmn T{twamr
 95  177.10   53  Jao]_glgpt!Indism_whmn T{twamr
101  178.55   52  Jao]_glgpt!Indism_whmn T{twbmr
110  171.98   51  Jao]_glgpt!Indism_whnn T{twbmr
112  175.62   49  Jao]_glgpt!Indism_thmn T{twbmr
115  176.80   46  Jao]dglgpt!Indism_whnn T{twbmr
117  170.39   43  Jao]dglgpt!Indism_thnn T{twbmr
120  169.32   40  Jaobdglgpt!Indism_thnn T{twbmr
121  173.88   39  Jaobdgldpt!Indism_thnn T{twbmr
124  164.23   38  Jaobdglgpt!Indssm_thnn T{twbmr
126  166.61   37  Jaobdgldpt!Indssm_thnn T{twbmr
130  162.20   36  Jaobdgldpt!Indssmbthnn T{twbmr
133  161.89   33  Jaobdgldpt!Indnsmbthnn T{twbmr
137  161.49   32  Jaobddldpt!Indnsmbthnn T{twbmr
138  159.19   31  Jaobdeldpt!Indnsmbthnn T{twbmr
146  157.38   29  Jaobdeldpt!Indnsmbthnn T{twdmr
157  156.15   28  Jaobdeldpt!Indnsmbthon T{twdmr
160  155.04   27  Janbdeldpt!Indnsmbthon T{twdmr
162  152.47   26  Jaobdeldpt!Indnsmbthon T{tudmr
163  152.50   25  Janbdeldpt!Indnsmbthon T{tudmr
169  152.22   23  Janbdeldnt!Indnsmbthon T{tudmr
175  148.55   22  Janbieldnt!Indnsmbthon T{tudmr
178  147.35   21  Janbieldnt!Indnsmathon T{tudmr
182  144.84   20  Janaieldnt!Indnsmathon T{tudmr
187  144.97   19  Janaieldnt!Indnsmathon T{ttdmr
190  144.21   18  Nanaieldnt!Indnsmathon T{tudmr
192  146.93   17  Nanaieldnt!Indnsmathon T{ttdmr
201  144.45   16  Nanaieldnt!Indnsmathon Tzttdmr
209  142.89   15  Nanaieldnt!Indnsmathon Tzttemr
229  141.94   14  Nanaieldnt Indnsmathon Tzttemr
232  144.33   13  Nanageldnt!Indnsmathon Tzttemr
233  144.76   12  Nanageldnt Indnsmathon Tzttemr
239  140.19   10  Nanageldnt Infnsmathon Tzttemr
272  134.55    9  Nanagelent Infnsmathon Tzttemr
278  137.49    8  Nanagelent Infnsmathon Tyttemr
287  134.83    7  Nanagement Infnsmathon Tyttemr
295  133.02    6  Nanagement Infnsmathon Syttemr
305  132.54    5  Nanagement Infnsmathon Systemr
319  130.34    4  Nanagement Infnsmathon Systems
493  134.53    3  Nanagement Infosmathon Systems
499  133.41    2  Nanagement Infosmation Systems
505  128.91    1  Management Infosmation Systems
568  131.64    0  Management Information Systems

The code

If anyone understands Java and is interested, the source code for this example is available at ExampleGA.java.txt. Remove the ".txt" extension to compile the code.