static Random random = new Random();
static void Main(string[] args)
{
// Seed three random genes.
// Make sure we don't make the numbers too large, or the Gene - Target could bork.
// Or possible the ABS. Anyway, happened once, should have read the error longer.
List<Int32> genes = new List<Int32>(3);
for (int t = 0; t < 3; ++t)
genes.Add(random.Next() / 2);
Int32 best = 0; // The best result.
Int32 second = 0; // The second best result.
// Need to measure the best distance to get those.
Int32 currentDistance = Int32.MaxValue;
Int32 middle = 0; // The one in the middle of the list.
Int32 one; // Slots for mixing genes.
Int32 two;
Int32 three;
// Whicever one is the farthest from the result is removed.
Int32 worstDistance = 0;
Int32 worst1 = 0;
Int32 target = 12550; // The target number.
do
{
worstDistance = 0;
currentDistance = Int32.MaxValue;
// Find the best, second best and worst genes.
foreach (Int32 gene in genes)
{
if (Math.Abs(gene - target) < currentDistance)
{
currentDistance = Math.Abs(gene - target);
second = best;
best = gene;
}
if (Math.Abs(gene - target) > worstDistance)
{
worstDistance = Math.Abs(gene - target);
worst1 = gene;
}
// Console.Write(gene + ", ");
}
// Remove the worst genes.
genes.Remove(worst1);
// A quick tracker. Also, will tells us if we get the result.
Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]);
// Get the middle.
middle = genes[genes.Count / 2];
// OR, NOR and AND the Best and Middle bits, then flip a random bit.
one = (best | middle) ^ (1 << random.Next(30));
two = (best ^ middle) ^ (1 << random.Next(30));
three = (best & middle) ^ (1 << random.Next(30));
// Add the new genes to the integer population.
if (!genes.Contains(one))
genes.Add(one);
if (!genes.Contains(two))
genes.Add(two);
if (!genes.Contains(three))
genes.Add(three);
// OR, NOR and AND the Best and Second bits, then flip a random bit.
one = (best | second) ^ (1 << random.Next(30));
two = (best ^ second) ^ (1 << random.Next(30));
three = (best & second) ^ (1 << random.Next(30));
// Add the new genes to the integer population.
if (!genes.Contains(one))
genes.Add(one);
if (!genes.Contains(two))
genes.Add(two);
if (!genes.Contains(three))
genes.Add(three);
genes.Add(best ^ (1 << random.Next(30)));
genes.Add(second ^ (1 << random.Next(30)));
// Keep doing this until we've hit our target.
} while (best != target);
// The sole purpose of this is for a rough measurement of average time.
// Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]);
Console.ReadKey(true); // Gives us time to examine the data.
}
Critique my simple Genetic Algorithm
March 15, 2010 02:13 AM
This is a genetic algorithm that tests for fitness by how close the genes are to a target number - The genes and target number being integers (Bit fields). Basically, I seed three random integers and mix-and-match, with a bit of random (No pun intended) and remove the worst, until the target number is found.
My question is, what sorts of things can I do to optimize this? I am reading AI Game Programming Gems, which is where I got the idea to do this.
Thanks.
Edit: Code's been updated - Now flipping a random bit on the Best and Second and adding them. Also, shifting by up to 32 was resulting in negative numbers, which could result in Two's Complement - Which C# doesn't like. It seems to find the answer much faster on average, now. OTOH, putting in 12532 still stumps it.
[Edited by - Narf the Mouse on March 15, 2010 2:32:50 AM]
Now open: MouseProduced Games
400
March 15, 2010 02:30 AM
You're breeding with bit-wise operators, but your fitness is based on the distance from the number itself. This means that the least significant bits will tend to all flip on when the number is too low and off when the number is too high rather than switching to the desired bit values. It will still probably work, but it'll take more iterations because it won't really attempt to fix those bits until the other bits are fixed. A better fitness function might be how many bits are in common with the target number. Also, I don't know how good and, or, and xor are as breeding functions. It would probably be more effective to randomly select bits from each parent(either in sections or one at a time). A simple method is to select 2 random points and put one parent's bits in that range and the other parents bits in the rest of the number. Another useful technique I've read about is roulette selection. Rather than just breeding the best 2, select parents at random where the probability of being selected is relative to fitness. This leads to more diversity in your population which is a good thing particularly at the beginning when none of your genes are very good. That idea comes from the book "AI Techniques for game programming".
March 15, 2010 03:06 AM
Ok, I've tried counting the common bits, but the end result is worse - Much slower and doesn't really converge.
I've also tried counting the bits not in common; no-go.
Source:
I've also tried counting the bits not in common; no-go.
Source:
static Random random = new Random(); static void Main(string[] args) { // Seed three random genes. // Make sure we don't make the numbers too large, or the Gene - Target could bork. // Or possible the ABS. Anyway, happened once, should have read the error longer. List<Int32> genes = new List<Int32>(3); for (int t = 0; t < 3; ++t) genes.Add(random.Next() / 2); Int32 best = 0; // The best result. Int32 second = 0; // The second best result. // Need to measure the best distance to get those. Int32 currentDistance = Int32.MaxValue; // Need something to hold the distance, so it's only calculated once. Int32 distance; Int32 middle = 0; // The one in the middle of the list. Int32 one; // Slots for mixing genes. Int32 two; Int32 three; // Whicever one is the farthest from the result is removed. Int32 worstDistance = 0; Int32 worst1 = 0; Int32 target = 12550; // The target number. do { worstDistance = 0; currentDistance = Int32.MaxValue; // Find the best, second best and worst genes. foreach (Int32 gene in genes) { // distance = Math.Abs(gene - target); distance = BitsNotInCommon(gene, target); if (distance < currentDistance) { currentDistance = distance; second = best; best = gene; } if (distance > worstDistance) { worstDistance = distance; worst1 = gene; } // Console.Write(gene + ", "); } // Remove the worst genes. genes.Remove(worst1); // A quick tracker. Also, will tells us if we get the result. Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); // Get the middle. middle = genes[genes.Count / 2]; // OR, NOR and AND the Best and Middle bits, then flip a random bit. one = (best | middle) ^ (1 << random.Next(30)); two = (best ^ middle) ^ (1 << random.Next(30)); three = (best & middle) ^ (1 << random.Next(30)); // Add the new genes to the integer population. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // OR, NOR and AND the Best and Second bits, then flip a random bit. one = (best | second) ^ (1 << random.Next(30)); two = (best ^ second) ^ (1 << random.Next(30)); three = (best & second) ^ (1 << random.Next(30)); // Add the new genes to the integer population. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); genes.Add(best ^ (1 << random.Next(30))); genes.Add(second ^ (1 << random.Next(30))); // Keep doing this until we've hit our target. } while (best != target); // The sole purpose of this is for a rough measurement of average time. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); Console.ReadKey(true); // Gives us time to examine the data. } public static Int32 BitsInCommon(Int32 a, Int32 b) { Int32 c = a & b; Int32 d = 0; while (c != 0) { c /= 2; ++d; } return d; } public static Int32 BitsNotInCommon(Int32 a, Int32 b) { Int32 c = a & b; Int32 d = 0; while (c != 0) { c /= 2; ++d; } return (32 - d); }
Now open: MouseProduced Games
March 15, 2010 03:32 AM
The current state. Appears to converge faster, with much less of a chance of getting hung up for long periods. Also, 12532 no longer stumps it for long.
Changes: Changed to a Double "fitness" value out of 1. Also, mutation now only occurs 50% of the time per gene combination.
Changes: Changed to a Double "fitness" value out of 1. Also, mutation now only occurs 50% of the time per gene combination.
static Random random = new Random(); static void Main(string[] args) { // Seed three random genes. // Make sure we don't make the numbers too large, or the Gene - Target could bork. // Or possible the ABS. Anyway, happened once, should have read the error longer. List<Int32> genes = new List<Int32>(3); for (int t = 0; t < 3; ++t) genes.Add(random.Next() / 2); SortedGene best = new SortedGene(0, 0); // The best result. SortedGene second = new SortedGene(0, 0); // The second best result. // Need to measure the best distance to get those. // Int32 currentDistance = Int32.MaxValue; // Need something to hold the distance, so it's only calculated once. Double distance; Int32 middle = 0; // The one in the middle of the list. Double mutationChance = 0.5; // The chance of a mutation when combining. Int32 one; // Slots for mixing genes. Int32 two; Int32 three; // Whicever one is the farthest from the result is removed. SortedGene worst = new SortedGene(0, 1); Int32 target = 12532; // The target number. do { worst.Fitness = 1; best.Fitness = 0; // Find the best, second best and worst genes. foreach (Int32 gene in genes) { // distance = Math.Abs(gene - target); distance = target / (gene * 1.0); if (distance > 1) distance = 1 / distance; // distance = BitsNotInCommon(gene, target); if (distance > best.Fitness) { best.Fitness = distance; second = best; best.Gene = gene; } if (distance > worst.Fitness) { worst.Fitness = distance; worst.Gene = gene; } // Console.Write(gene + ", "); } // Remove the worst genes. genes.Remove(worst.Gene); // A quick tracker. Also, will tells us if we get the result. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); Console.WriteLine("Best: " + best); Console.WriteLine("Second: " + second); Console.WriteLine("Middle: " + middle); // Get the middle. middle = genes[genes.Count / 2]; // OR, NOR and AND the Best and Middle bits, then flip a random bit. one = (best.Gene | middle); two = (best.Gene ^ middle); three = (best.Gene & middle); // Maybe add a mutation. if (random.NextDouble() <= mutationChance) one ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) two ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) three ^= (1 << random.Next(30)); // Add the new genes to the integer population. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // OR, NOR and AND the Best and Second bits, then flip a random bit. one = (best.Gene | second.Gene); two = (best.Gene ^ second.Gene); three = (best.Gene & second.Gene); // Maybe add a mutation. if (random.NextDouble() <= mutationChance) one ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) two ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) three ^= (1 << random.Next(30)); // Add the new genes to the integer population. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // Add a mutation of the best and second-best. genes.Add(best.Gene ^ (1 << random.Next(30))); genes.Add(second.Gene ^ (1 << random.Next(30))); // Keep doing this until we've hit our target. } while (best.Gene != target); // The sole purpose of this is for a rough measurement of average time. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); Console.ReadKey(true); // Gives us time to examine the data. }
Now open: MouseProduced Games
March 15, 2010 09:58 AM
The following, somewhat odd change has resulted in most solutions coming in not very many pages of data, with three lines per calculation.
Changes: Mostly, it now uses BitsInCommon + BitsNotInCommon to determine fitness. Including using it to calculate the target number. I've got a vague thought on why, but, well, it's 8:18 in the morning...And I've yet to sleep.
Edit: Whoop, source code. The new features aren't commented yet, but should be pretty easy to understand.
Changes: Mostly, it now uses BitsInCommon + BitsNotInCommon to determine fitness. Including using it to calculate the target number. I've got a vague thought on why, but, well, it's 8:18 in the morning...And I've yet to sleep.
Edit: Whoop, source code. The new features aren't commented yet, but should be pretty easy to understand.
static Random random = new Random(); static void Main(string[] args) { // Seed three random genes. // Make sure we don't make the numbers too large, or the Gene - Target could bork. // Or possible the ABS. Anyway, happened once, should have read the error longer. List<Int32> genes = new List<Int32>(3); for (int t = 0; t < 3; ++t) genes.Add(random.Next() / 2); // genes.Add(12544); SortedGene best = new SortedGene(0, 0); // The best result. SortedGene second = new SortedGene(0, 0); // The second best result. // Need to measure the best distance to get those. // Int32 currentDistance = Int32.MaxValue; // Need something to hold the distance, so it's only calculated once. Double fitness; Int32 middle = 0; // The one in the middle of the list. Double mutationChance = 0.5; // The chance of a mutation when combining. Int32 one; // Slots for mixing genes. Int32 two; Int32 three; // Whicever one is the farthest from the result is removed. SortedGene worst = new SortedGene(0, 1); Int32 target = 12532; // The target number. do { worst.Fitness = 1; best.Fitness = 0; // Find the best, second best and worst genes. foreach (Int32 gene in genes) { // distance = Math.Abs(gene - target); // fitness = target / (gene * 1.0); // fitness = BitsInCommon(gene, target) / (BitsInCommon(target, target) * 1.0); fitness = FitnessCalculator(gene, target); if (fitness > 1) fitness = 1 / fitness; // distance = BitsNotInCommon(gene, target); if (fitness > best.Fitness) { best.Fitness = fitness; second = best; best.Gene = gene; } if (fitness > worst.Fitness) { worst.Fitness = fitness; worst.Gene = gene; } // Console.Write(gene + ", "); } // Remove the worst genes. genes.Remove(worst.Gene); // A quick tracker. Also, will tells us if we get the result. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); Console.WriteLine("Best: " + best); Console.WriteLine("Second: " + second); Console.WriteLine("Middle: " + middle); // Get the middle. middle = genes[genes.Count / 2]; // OR, NOR and AND the Best and Middle bits, then flip a random bit. one = (best.Gene | middle); two = (best.Gene ^ middle); three = (best.Gene & middle); // Maybe add a mutation. if (random.NextDouble() <= mutationChance) one ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) two ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) three ^= (1 << random.Next(30)); // Add the new genes to the integer population. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // OR, NOR and AND the Best and Second bits, then flip a random bit. one = (best.Gene | second.Gene); two = (best.Gene ^ second.Gene); three = (best.Gene & second.Gene); // Maybe add a mutation. if (random.NextDouble() <= mutationChance) one ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) two ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) three ^= (1 << random.Next(30)); // Add the new genes to the integer population. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // Add a mutation of the best and second-best. genes.Add(best.Gene ^ (1 << random.Next(30))); genes.Add(second.Gene ^ (1 << random.Next(30))); // Keep doing this until we've hit our target. } while (best.Gene != target); // The sole purpose of this is for a rough measurement of average time. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); Console.ReadKey(true); // Gives us time to examine the data. } struct SortedGene { public SortedGene(Int32 gene, Double fitness) { this.Gene = gene; this.Fitness = fitness; } public Double Fitness; public Int32 Gene; public override string ToString() { return "Gene: " + this.Gene + " Fitness: " + Math.Round(this.Fitness, 5); } } public static Double FitnessCalculator(Int32 gene, Int32 target) { return (BitsInCommon(gene, target) + BitsNotInCommon(gene, target)) / ((BitsInCommon(target, target) + BitsNotInCommon(target, target)) * 1.0); } public static Int32 Bits(Int32 a) { Int32 d = 0; while (a != 0) { a /= 2; ++d; } return d; } public static Int32 BitsInCommon(Int32 a, Int32 b) { return Bits(a & b); } public static Int32 BitsNotInCommon(Int32 a, Int32 b) { return 32 - Bits(a ^ b); }
Now open: MouseProduced Games
March 15, 2010 05:37 PM
This finalizes the code for now. I'm using SortedGene for all the genes; genes calculate and can recalculate their own fitness and an arbitrary number of "worst genes" can be removed.
I've yet to have a problem with it calculating any gene, save for the "Two's Complement" problem.
I've yet to have a problem with it calculating any gene, save for the "Two's Complement" problem.
static Random random = new Random(); static void Main(string[] args) { Int32 target = Int32.MaxValue / 4; // The target number. // A fitness calculator. Func<Int32, Double> fitnessCalculator = new Func<Int32, Double>( gene => { return (BitsInCommon(gene, target) + BitsNotInCommon(gene, target)) / ((BitsInCommon(target, target) + BitsNotInCommon(target, target)) * 1.0); } ); // Seed three random genes. // Make sure we don't make the numbers too large, or we get Two's Complement. List<SortedGene<Int32>> genes = new List<SortedGene<Int32>>(3); for (int t = 0; t < 3; ++t) genes.Add(new SortedGene<Int32>(random.Next() / 2, fitnessCalculator)); // genes.Add(12544); // The best result. SortedGene<Int32> best = new SortedGene<Int32>(target ^ target, fitnessCalculator); // The second best result. SortedGene<Int32> second = new SortedGene<Int32>(target ^ target, fitnessCalculator); // Need something to hold the distance. Double fitness; // The one in the middle of the list. SortedGene<Int32> middle = new SortedGene<int>(0, fitnessCalculator); // The chance of a mutation when combining. Double mutationChance = 0.5; // Slots for mixing genes. SortedGene<Int32> one = new SortedGene<int>(0, fitnessCalculator); SortedGene<Int32> two = new SortedGene<int>(0, fitnessCalculator); SortedGene<Int32> three = new SortedGene<int>(0, fitnessCalculator); // The number of genes to remove each generation. Int32 cullNumber = 3; // A list of the worst genes. List<SortedGene<Int32>> worst = new List<SortedGene<Int32>>(); do { // Find the best, second best and worst genes. worst.Clear(); foreach (SortedGene<Int32> gene in genes) { fitness = gene.Fitness; if (fitness > 1) fitness = 1 / fitness; if (fitness > best.Fitness) { second = best; best = gene; } if (worst.Count < cullNumber) worst.Add(gene); else if (fitness < worst[0].Fitness) { for (Int32 n = worst.Count - 1; n >= 1; --n) worst[n] = worst[n - 1]; worst[0] = gene; } // Console.Write(gene + ", "); } // A quick tracker. Also, will tells us if we get the result. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); Console.WriteLine("Best: " + best); Console.WriteLine("Second: " + second); Console.WriteLine("Middle: " + middle); // Get the middle. middle = genes[genes.Count / 2]; // Remove the worst genes. for (Int32 n = 0; n < cullNumber; ++n) genes.Remove(worst[n]); // OR, NOR and AND the Best and Middle bits. one.Gene = (best.Gene | middle.Gene); two.Gene = (best.Gene ^ middle.Gene); three.Gene = (best.Gene & middle.Gene); // Maybe add a mutation. if (random.NextDouble() <= mutationChance) one.Gene ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) two.Gene ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) three.Gene ^= (1 << random.Next(30)); // Add the new genes to the integer population, if they don't exist already. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // OR, NOR and AND the Best and Second bits. one.Gene = (best.Gene | second.Gene); two.Gene = (best.Gene ^ second.Gene); three.Gene = (best.Gene & second.Gene); // Maybe add a mutation. if (random.NextDouble() <= mutationChance) one.Gene ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) two.Gene ^= (1 << random.Next(30)); if (random.NextDouble() <= mutationChance) three.Gene ^= (1 << random.Next(30)); // Add the new genes to the integer population, if they don't exist already. if (!genes.Contains(one)) genes.Add(one); if (!genes.Contains(two)) genes.Add(two); if (!genes.Contains(three)) genes.Add(three); // Add a mutation of the best and second-best. genes.Add(new SortedGene<Int32>(best.Gene ^ (1 << random.Next(30)), fitnessCalculator)); genes.Add(new SortedGene<Int32>(second.Gene ^ (1 << random.Next(30)), fitnessCalculator)); // Keep doing this until we've hit our target. } while (best.Gene != target); // The sole purpose of this is for a rough measurement of average time. // Console.WriteLine("#1: " + best + " #2: " + second + " Middle: " + genes[genes.Count / 2]); // So we know how efficient our algorithm is. Console.WriteLine("Total genes: " + genes.Count); Console.ReadKey(true); // Gives us time to examine the data. } // Stores a gene of type T. struct SortedGene<T> { /// <summary> /// Creates a new SortedGene. /// </summary> /// <param name="gene">The gene to store.</param> /// <param name="fitnessCalculator">A fitness calculator function.</param> public SortedGene(T gene, Func<T, Double> fitnessCalculator) { this.Gene = gene; this.FitnessCalculator = new SortedGene<T>.FitnessCalculatorDel(fitnessCalculator); this.Fitness = FitnessCalculator(this.Gene); } private delegate Double FitnessCalculatorDel(T gene); private FitnessCalculatorDel FitnessCalculator; /// <summary> /// Drop a "true" into this to recalculate the fitness. /// </summary> public bool RecalcFitness { set { this.Fitness = FitnessCalculator(this.Gene); } } /// <summary> /// The fitness of the gene. /// </summary> public Double Fitness; /// <summary> /// The gene. /// </summary> public T Gene; /// <summary> /// Converts the gene to a string. /// </summary> /// <returns></returns> public override string ToString() { return "Gene: " + this.Gene + " Fitness: " + Math.Round(this.Fitness, 5); } } /// <summary> /// Computes the bits in an integer. /// </summary> /// <param name="a">The integer.</param> /// <returns>Returns the number of bits.</returns> public static Int32 Bits(Int32 a) { Int32 d = 0; while (a != 0) { a /= 2; ++d; } return d; } /// <summary> /// Returns the number of bits in common between two integers. /// </summary> /// <param name="a">The first integer.</param> /// <param name="b">The second integer.</param> /// <returns>Returns the number of bits in common.</returns> public static Int32 BitsInCommon(Int32 a, Int32 b) { return Bits(a & b); } /// <summary> /// Returns the number of bits not in common between two integers. /// </summary> /// <param name="a">The first integer.</param> /// <param name="b">The second integer.</param> /// <returns>Returns the number of bits not in common.</returns> public static Int32 BitsNotInCommon(Int32 a, Int32 b) { return 32 - Bits(a ^ b); } /// <summary> /// Returns the number of bits in total between two integers. /// </summary> /// <param name="a">The first integer.</param> /// <param name="b">The second integer.</param> /// <returns>Returns the number of bits in total.</returns> public static Int32 BitsInTotal(Int32 a, Int32 b) { return Bits(a | b); }
Now open: MouseProduced Games
March 17, 2010 09:25 AM
I'm intrigued as to why you're deviating from the normal terminology and methods for this.
Normally you would have far more than 3 genes (eg. 20, 50, 100?), so that there's enough diversity in the values. Without the diversity there's little point to the algorithm.
For each iteration you'd generate a new collection of genes based on the old collection, by using crossover and mutation. Your mutation looks ok but you don't have a proper crossover algorithm, instead using OR, NOR and AND (even though the NOR actually looks like XOR to me), which don't serve the same purpose at all. These will slow convergence. Also, you normally perform the crossover on a wide selection of the genes, tending to pick some genes over others according to their fitness (eg. Via fitness proportionate selection, rank selection, tournament selection, etc.) This is so that better solutions are more likely to propagate their properties to the next generation.
There is often a mechanism called 'elitism' where - instead of replacing the whole previous generation of genese with new ones - you keep the top few genes that are the best, to ensure that your current best solution never gets worse. This is sort of the same thing as you removing the worst ones each time, but it's worth noting that usually you only keep a small proportion of the whole population - the rest is meant to be changing dynamically to explore the search space.
Oh, and you appear to have copied and pasted part of the code twice... is that intentional?
The fact that your algorithm works is not proof that it is doing the right thing, unfortunately. You might find that it is hardly converging at all and eventually stumbling across the right answer just by mutation alone (which makes it more of a stochastic hill climbing algorithm that generates random changes and keeps the better ones).
I suggest re-reading the literature and getting a grasp of the basic genetic algorithm procedure and coding yours up in a more generic way rather than hard-coding these crossover and selection routines.
Normally you would have far more than 3 genes (eg. 20, 50, 100?), so that there's enough diversity in the values. Without the diversity there's little point to the algorithm.
For each iteration you'd generate a new collection of genes based on the old collection, by using crossover and mutation. Your mutation looks ok but you don't have a proper crossover algorithm, instead using OR, NOR and AND (even though the NOR actually looks like XOR to me), which don't serve the same purpose at all. These will slow convergence. Also, you normally perform the crossover on a wide selection of the genes, tending to pick some genes over others according to their fitness (eg. Via fitness proportionate selection, rank selection, tournament selection, etc.) This is so that better solutions are more likely to propagate their properties to the next generation.
There is often a mechanism called 'elitism' where - instead of replacing the whole previous generation of genese with new ones - you keep the top few genes that are the best, to ensure that your current best solution never gets worse. This is sort of the same thing as you removing the worst ones each time, but it's worth noting that usually you only keep a small proportion of the whole population - the rest is meant to be changing dynamically to explore the search space.
Oh, and you appear to have copied and pasted part of the code twice... is that intentional?
The fact that your algorithm works is not proof that it is doing the right thing, unfortunately. You might find that it is hardly converging at all and eventually stumbling across the right answer just by mutation alone (which makes it more of a stochastic hill climbing algorithm that generates random changes and keeps the better ones).
I suggest re-reading the literature and getting a grasp of the basic genetic algorithm procedure and coding yours up in a more generic way rather than hard-coding these crossover and selection routines.
March 17, 2010 02:56 PM
I looked the code in the last post over and didn't see a repost.
The answer to all the rest is, it is my first, raw attempt. My second one, taken from the AI Game Programming Gems book, does take advantage of those techniques. I've been debating updating this algorithm (And thanks for the suggestions), but now I think I will.
The answer to all the rest is, it is my first, raw attempt. My second one, taken from the AI Game Programming Gems book, does take advantage of those techniques. I've been debating updating this algorithm (And thanks for the suggestions), but now I think I will.
Now open: MouseProduced Games
March 17, 2010 03:53 PM
I've implemented both your suggestions and what's suggested in the book; the result is something that takes no more than a second or ~20 generations. It's also a lot closer to being capable of generic genetic operations.
Source:
Source:
static Random random = new Random(); static void Main(string[] args) { Int32 target = random.Next(Int32.MaxValue / 2); // The target number. // A fitness calculator. Func<Int32, Double> fitnessCalculator = new Func<Int32, Double>( gene => { return (MathExt.BitsCombined(gene, target, Combinations.InCommon) + MathExt.BitsCombined(gene, target, Combinations.NotInCommon)) / ((MathExt.BitsCombined(target, target, Combinations.InCommon) + MathExt.BitsCombined(target, target, Combinations.NotInCommon)) * 1.0); } ); // Crosses over two genes. Func<Int32, Int32, Int32> crossover = new Func<Int32, Int32, Int32>( (geneOne, geneTwo) => { Int32 temp = 0; Int32 t; for (t = 1; t <= 32; ++t) { if (random.Next(2) == 0) temp |= geneOne & (1 << t); else temp |= geneTwo & (1 << t); } return temp; } ); // Mutates one gene. Func<Int32, Int32> mutate = new Func<Int32, Int32>( gene => { for (Int32 t = 1; t <= 32; ++t) { if (random.NextDouble() <= 0.01) gene ^= (1 << t); } return gene; } ); // The number of genes in the pool. Int32 geneCount = 150; // Seed three random genes. // Make sure we don't make the numbers too large, or we get Two's Complement. List<SortedGene<Int32>> genes = new List<SortedGene<Int32>>(3); for (int t = 0; t < geneCount; ++t) genes.Add(new SortedGene<Int32>(random.Next() / 2, fitnessCalculator, crossover, mutate)); // A counter for the number of generations. Int32 generations = 0; // The fraction of genes which will survive into the next generation. Double surviveFraction = 0.2; // The fraction of genes which will contribute to the next generation. Double crossoverFraction = (1.0 / 3.0); // The fraction of genes they will contribute to the next generation. Double crossoverProductionFraction = 0.7; // The fraction of completely new genes. Double createNewFraction = 0.1; // The actual execution loop. do { // Sorts the genes, from best to worst. genes.Sort( (geneOne, geneTwo) => { if (geneOne.Fitness > geneTwo.Fitness) return -1; else if (geneOne.Fitness < geneTwo.Fitness) return 1; else return 0; } ); // Clears the console and displays the top twenty genes. Console.Clear(); for (Int32 t = 0; t < 20; ++t) { Console.WriteLine(genes[t]); } // If we haven't hit our target, time for a new generation. if (genes[0].Fitness < 1.0) { // Some genes survive to the next generation. Int32 surviveCount = (Int32)((geneCount * surviveFraction) + 0.5); List<SortedGene<Int32>> newGenes = new List<SortedGene<int>>(genes.Take(surviveCount)); // Some genes contribute to the next generation. Int32 crossoverCount = (Int32)((geneCount * crossoverFraction) + 0.5); Int32 newCrossovers = (Int32)((geneCount * crossoverProductionFraction) + 0.5); Int32 one, two, three; for (Int32 t = 0; t < newCrossovers; ++t) { one = random.Next(crossoverCount); two = random.Next(crossoverCount); three = genes[one].Crossover(genes[one].Gene, genes[two].Gene); three = genes[one].Mutate(three); newGenes.Add(new SortedGene<Int32>(three, fitnessCalculator, crossover, mutate)); } // Some genes are completely new. Int32 newGenesCount = (Int32)((geneCount * createNewFraction) + 0.5); for (Int32 t = 0; t < newGenesCount; ++t) { newGenes.Add(new SortedGene<Int32>(random.Next() / 2, fitnessCalculator, crossover, mutate)); } // And the next generation begins. genes = newGenes; ++generations; } // Keep doing this until we've hit our target. } while (genes[0].Fitness < 1.0); // So we know how efficient our algorithm is. Console.WriteLine("Total genes: " + genes.Count + ", Best Gene: " + genes[0].Gene + ", Target: " + target + ", Generations: " + generations); Console.ReadKey(true); // Gives us time to examine the data. }
Now open: MouseProduced Games
March 17, 2010 11:01 PM
It should now be fully capable of generic options. 100 loop tests show an average 14 ms runtime - Much better than the initial seconds of the hill-climbing algorithm.
The genetic algorithm Run function body:
The genetic algorithm Run function body:
#region Setup // Create genes, if needed. if (genes == null) genes = new List<SortedGene<T>>(geneCount); for (int t = genes.Count; t < geneCount; ++t) genes.Add(newGene()); List<SortedGene<T>> newGenes = new List<SortedGene<T>>(geneCount); // A temporary gene; SortedGene<T> temp; Double startTime = GeneralData.Stopwatch.Elapsed.TotalMilliseconds; #endregion { #region Execution loop. do { #region Loop beginning stuff if (testbed != null) testbed(genes); // Sorts the genes, from best to worst. genes.Sort(sort); genes.Reverse(); // Clears the console and displays the top twenty genes. /* Console.Clear(); for (Int32 t = 0; t < 20; ++t) { Console.WriteLine(genes[t]); } */ #endregion // If we haven't hit our target, time for a new generation. if (genes[0].Fitness < minimumFitness && GeneralData.Stopwatch.Elapsed.TotalMilliseconds - startTime < maxRunTimeMS) { #region Creates a new generation #region Elitism // Some genes survive to the next generation. Int32 surviveCount = (Int32)((geneCount * surviveFraction) + 0.5); newGenes.Clear(); newGenes.AddRange(new List<SortedGene<T>>(genes.Take(surviveCount))); #endregion #region Crossover // Some genes contribute to the next generation. Int32 crossoverCount = (Int32)((geneCount * crossoverFraction) + 0.5); Int32 newCrossovers = (Int32)((geneCount * crossoverProductionFraction) + 0.5); Int32 one, two; for (Int32 t = 0; t < newCrossovers; ++t) { one = GeneralData.Random.Next(crossoverCount); two = GeneralData.Random.Next(crossoverCount); temp = genes[one].Crossover(genes[one], genes[two]); temp = genes[one].Mutate(temp); newGenes.Add(temp); } #endregion #region New gene creation // Some genes are completely new. Int32 newGenesCount = (Int32)((geneCount * createNewFraction) + 0.5); for (Int32 t = 0; t < newGenesCount; ++t) { newGenes.Add(newGene()); } #endregion #endregion #region Begins a new generation // And the next generation begins. genes.Clear(); genes.AddRange(newGenes); geneCount = genes.Count; ++generations; #endregion } // Keep doing this until we've hit our target. } while (genes[0].Fitness < minimumFitness && GeneralData.Stopwatch.Elapsed.TotalMilliseconds - startTime < maxRunTimeMS); #endregion // So we know how efficient our algorithm is. Console.WriteLine("Total genes: " + genes.Count + ", Best Gene: " + genes[0] + ", Generations: " + generations); }
Now open: MouseProduced Games
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
