I have written a C# version of the WEASEL application, first demonstrated in the '80s by Richard Dawkins.
It took no more than 45 minutes, and can easily be done by anyone with basic (or mad) programming skills.
For more information, check the Weasles on Parade thread at Panda's Thumb.
Author: Sander van Driel
Date: March 20, 2009
Update 16:23 GMT+1: Spent 5 minutes making the mutation mechanism equal to the original program (e.g. with a mutation rate per character).
Update 23:39 GMT+1: Added a plot visualizing the fitness over generations.
For an offspring count of 30 and a mutation rate of 4%, the program gives the output listed below. It takes just 186 generations to obtain the target string.
As you can see, there are mutations that reverse prior good mutations (the fitness is defined as the number of matching characters).
No 'locking' occurs; just check out the first character M.
=== WEASEL Mutation and Selection Test ===
Written in 45 minutes by Sander van Driel, 2009
Distribute at will.
Target string: "METHINKS IT IS LIKE A WEASEL"
Offspring count: 30
Mutation rate: 4.00%
Generation 1 - Fitness 3.6% - LZMOXBIFZXCCGNOTZZIPAFBGSRP
Generation 2 - Fitness 7.1% - LZMOXBCFZXCCGNOTZZIPAWBGSRP
Generation 3 - Fitness 10.7% - LZMOXBCFZTCCGNOTZZIPAWBGSRP
Generation 4 - Fitness 14.3% - QZMOXBCFZTCCGNOTKZIPAWBGSRP
Generation 8 - Fitness 17.9% - MQZMOXBCFZTCCBNOTKZGPAWBGS P
Generation 10 - Fitness 21.4% - MQZHOXBCFZTCCBNOTKZGPAWBGSAP
Generation 12 - Fitness 25.0% - MQZHOXHCFZTCCMNOTKZGPAWBGSAL
Generation 17 - Fitness 28.6% - MQTHYLHEAZTCCMTFTKYGPAWBGSAL
Generation 18 - Fitness 32.1% - MQTHYLHEABTCCMTFIKYGPAWBGSAL
Generation 20 - Fitness 35.7% - MQTHYLHEABTCCMTFIKY UAWBGSAL
Generation 21 - Fitness 39.3% - MQTHYNHEAKTCCMTFIKK UAWBGSAL
Generation 25 - Fitness 42.9% - MQTHYNHEFKTTIDXFIKK UAWAGSAL
Generation 27 - Fitness 46.4% - MQTHINHEFKTLIDXFIKK UAWAGSAL
Generation 30 - Fitness 50.0% - MQTHINHEFKTLIDXFIKK U WAGSAL
Generation 43 - Fitness 53.6% - MQTHINHEKYTQIQGGIKE U WA SAL
Generation 45 - Fitness 57.1% - MQTHINHEKYT IQGGIKE U WA SAL
Generation 46 - Fitness 60.7% - MQTHINKEKYT IQGGIKE I WA SAL
Generation 49 - Fitness 64.3% - MQTHINKEKIT IQGGIKE I WA SAL
Generation 53 - Fitness 67.9% - MQTHINKE IT IQGGIKE I WA SAL
Generation 57 - Fitness 71.4% - MQTHINKE IT IQ JIKE T WP SAL
Generation 73 - Fitness 75.0% - MCTHINKS IT IQ VIKE Q WPQSLL
Generation 79 - Fitness 78.6% - MCTHINKS IT IQ IIKE A WPQSCL
Generation 80 - Fitness 82.1% - METHINKS IT IQ YIKE A WPQSCL
Generation 103 - Fitness 85.7% - METHINKS IT IC YIKE A WEQSCL
Generation 123 - Fitness 89.3% - DEDHINKS IT IC LIKE A WEASEL
Generation 146 - Fitness 92.9% - PETHINKS IT IQ LIKE A WEASEL
Generation 150 - Fitness 96.4% - PETHINKS IT IS LIKE A WEASEL
Generation 186 - Fitness 100.0% - METHINKS IT IS LIKE A WEASEL
I've graphed a single test run in order to verify the logarithmic convergence of the algorithm.
Please note that the x-axis (generation) is in logarithmic scale.
With the exception of the aberrations at the start and the end, you can clearly identify a linear trend.
Listed below is the C# source code for the Weasel application. It is a simple console application that has its parameters (target string and offspring count) hardcoded.
The code may be distributed freely; just mention my name somewhere in your code.
1: using System;
2:
3: namespace Weasel
4: {
5: class WeaselApp
6: {
7: private static readonly Random m_random = new Random();
8: private static char[] m_charValues;
9:
10: static void Main(string[] args)
11: {
12: // Target string
13: string target = "METHINKS IT IS LIKE A WEASEL";
14:
15: // Offspring count
16: int offspringCount = 30;
17:
18: // Probability that a character is mutated
19: double mutationRate = 0.04;
20:
21: // Initialize array of possible character values
22: InitChars();
23:
24: // Write header and parameters
25: Console.WriteLine("=== WEASEL Mutation and Selection Test ===");
26: Console.WriteLine();
27: Console.WriteLine("Written in 45 minutes by Sander van Driel, 2009");
28: Console.WriteLine("Distribute at will.");
29: Console.WriteLine();
30: Console.WriteLine("Target string: \"{0}\"", target);
31: Console.WriteLine("Offspring count: {0}", offspringCount);
32: Console.WriteLine("Mutation rate: {0:0.00%}", mutationRate);
33: Console.WriteLine();
34:
35: // Start out with random string
36: string current = RandomString(target.Length);
37:
38: // Array to store offspring
39: string[] offspring = new string[offspringCount];
40:
41: int generation = 0;
42: double bestFitness = -1;
43: while (true)
44: {
45: // Create offspring
46: Offspring(current, offspring, mutationRate);
47:
48: // Select fittest
49: current = SelectFittest(offspring, target);
50:
51: // Get difference with target and calculate fitness
52: int diff = StringDiff(current, target);
53: double fitness = 1 - (double)diff / target.Length;
54:
55: // Increment generation counter
56: generation++;
57:
58: // If fitness has improved, print something
59: if (fitness > bestFitness)
60: {
61: Console.WriteLine("Generation {0,8} - Fitness {1,6:0.0%} - {2}", generation, fitness, current);
62: bestFitness = fitness;
63: }
64:
65: // Stop if target has been reached
66: if (diff == 0)
67: break;
68: }
69: }
70:
71: /// <summary>
72: /// Creates 'offspring' for a certain string, each having 1 mutation.
73: /// </summary>
74: /// <param name="input">The string to create 'offspring' for.</param>
75: /// <param name="output">An array about to be teeming with newly bred offspring</param>
76: /// <param name="mutationRate">The probability of a character changing</param>
77: static void Offspring(string input, string[] output, double mutationRate)
78: {
79: for (int i = 0; i < output.Length; i++)
80: output[i] = Mutate(input, mutationRate);
81: }
82:
83: /// <summary>
84: /// Selects the 'fittest' candidate from a series (i.e.
85: /// the candidate with the least difference to the target).
86: /// </summary>
87: /// <param name="candidates">An array of candidate strings, must be non-empty.</param>
88: /// <param name="target">The target string</param>
89: /// <returns>The fittest candidate.</returns>
90: static string SelectFittest(string[] candidates, string target)
91: {
92: int best = Int32.MaxValue;
93: int bestIndex = -1;
94:
95: for (int i = 0; i < candidates.Length; i++)
96: {
97: // Get difference between current candidate and target
98: int diff = StringDiff(candidates[i], target);
99:
100: // If better than the current best, replace it
101: if (diff < best)
102: {
103: best = diff;
104: bestIndex = i;
105: }
106: }
107:
108: return candidates[bestIndex];
109: }
110:
111: /// <summary>
112: /// Mutates a string by randomly replacing characters
113: /// with characters from [A, Z] U {space}.
114: /// </summary>
115: /// <param name="input">
116: /// The string to mutate.
117: /// </param>
118: /// <param name="mutationRate">
119: /// The probability of a letter mutating.
120: /// </param>
121: /// <returns>
122: /// The mutated string
123: /// </returns>
124: static string Mutate(string input, double mutationRate)
125: {
126: char[] chars = new char[input.Length];
127:
128: for (int i = 0; i < chars.Length; i++)
129: {
130: if (m_random.NextDouble() > mutationRate)
131: // No mutation on current character
132: chars[i] = input[i];
133: else
134: // Mutate current character
135: chars[i] = RandomChar();
136: }
137:
138: // Return mutated string
139: return new string(chars);
140: }
141:
142: /// <summary>
143: /// Gets the number of characters that differ between
144: /// two strings of equal length.
145: /// </summary>
146: /// <param name="a">The first string</param>
147: /// <param name="b">The second string</param>
148: /// <returns>The number of different characters.</returns>
149: static int StringDiff(string a, string b)
150: {
151: int diff = 0;
152: // Loop over both strings and increment counter
153: // when a different character has been found
154: for (int i = 0; i < a.Length; i++)
155: if (a[i] != b[i])
156: diff++;
157:
158: return diff;
159: }
160:
161: /// <summary>
162: /// Chooses a random character from [A, Z] U {space}.
163: /// </summary>
164: /// <returns>A character from [A, Z]</returns>
165: static char RandomChar()
166: {
167: return m_charValues[m_random.Next(0, m_charValues.Length)];
168: }
169:
170:
171: /// <summary>
172: /// Generates a string of specified length with
173: /// randomly selected characters from [A, Z] U {space}.
174: /// </summary>
175: /// <param name="length">
176: /// The length of the string to be generated.
177: /// </param>
178: /// <returns>
179: /// The randomly generated string.
180: /// </returns>
181: static string RandomString(int length)
182: {
183: char[] chars = new char[length];
184: for (int i = 0; i < length; i++)
185: chars[i] = RandomChar();
186: return new string(chars);
187: }
188:
189: private static void InitChars()
190: {
191: // Initialize array of possible character values
192: m_charValues = new char[27];
193: for (int i = 0; i < 26; i++)
194: m_charValues[i] = (char)('A' + i);
195: m_charValues[26] = ' ';
196: }
197: }
198: }