This program is a coded version of an algorithm that John Holland came up with.
It is used to demonstrate evolution via the principle of "survival of the fittest."
The program initially creates a number of genotypes (strings) which can be thought of as DNA.
Each strings sole goal in "life" is to become a replica of the master string (which the program asks for).
In this case, each string (including the master) is composed of a number of random letters from a to z totaling the same number
as in the master.
Also of importance is the "fitness value" (FV) of each string relative to that of the master. The fitness value is number of letters the string shares
in common with the master (keeping in mind that the position has to be the same).
So, initially, the master may look like leroy
, and the five other strings may look like this:
qeffb
FV = 1 (e)
ltryu
FV = 2 (l and r)
aawey
FV = 1 (y)
leggn
FV = 2 (l and e)
abeoe
FV = 1 (e)
After all of the strings have been created and fitness values calculated, the program then picks two strings and mutates them.
It does this by picking two "random" strings. This is not actually random because the strings with the higher fitness values are
more likely to be picked. By biasing the selection, strings with already high fitness values exhibit traits that will allow growth of the
species. So, for example, let's say the program picks
The program that picks a random point to "break" the strings, say position 2. Remember that in computers, we start counting at 0.
So the program takes what is in positions 2, 3, and 4, and swaps them between the strings. ggn
from the first string,
and wey
from the second string and swapped, resulting in the following two strings:
lewey
FV = 3 (l, e, y)
aaggn
FV = 0
Notice that the fitness values have changed because lewey
now matches leroy
in three places.
Now the next time thru the process, lewey
will stand an even greater chance of being selected, whereas aaggn
stands a very small one. It is not guaranteed that either will be picked, but that is the beauty of biasing. The process can
be carried out for an arbitrary number of generations. One generation consists of selected two strings, mutating them, and recalculating
their fitness values.
This version of the program works with strings of length up to 50 (although this can be changed in the source). First you enter the
master string (letter combination you want evolution to achieve), then the number of strings to create for the selection pool, and finally
the maximum number of generations to run for.
Warning: This version of the program contains no comments. Here is the source code.
Back to the main page.