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:
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.
qeffb FV = 1 (e)
ltryu FV = 2 (l and r)
aawey FV = 1 (y)
leggn FV = 2 (l and e)
abeoe FV = 1 (e)
ggn from the first string,
wey from the second string and swapped, resulting in the following two strings:
Notice that the fitness values have changed because
lewey FV = 3 (l, e, y)
aaggn FV = 0
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
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.