OK, so I know I don't post enough code... blah blah blah... so on this lonelySaturday evening, I'm going to make you all proud.
Tonight I present to you: Roulette Wheel Selection (sample simulation in C#)
So what is roulette wheel selection and what does it have to do with anything? I'm sureyou're all familiar with a roulettewheel... So we have that much so far, randomness applied to number selection thatrepeats itself.
This particular implementation and application is in the context of GeneticAlgorithms. (read: cool evolution simulation) Basically, to simulate the breeding ofindividuals (genes) within a population, there has to be some method of parent selection.Using whatever theory suites your need, you can do anything from random parent selectionto a roulette wheel selection where the individuals who are more fit for the environmentare more likely to be chosen as parents. Think of it in terms of pie (read: dutch apple pie). If the piewere cut into non-equal pieces, you are going to want to pick the biggest slice. Samehere, in survival of the fittest, you want the most fit individuals (genes) breeding.Roulette wheel selection can help while at the same time, provide little quirks ofrandomness.
There are many implementations out there, but for an earlier project that I did as anundergraduate... and in my current implementation (the soon to be releasedDevelopStuff.EvolveStuff), I chose this simulation of roulette wheel selection.
/// <summary>/// Selects a single parent (<see cref="AbstractIndividual"/>) using a roulette wheel./// </summary>/// <param name="environment"></param>/// <returns></returns>public AbstractIndividual SelectParent(AbstractEnvironment environment){decimal totalFitness = 0;
foreach(AbstractIndividual individual in environment.Population.Individuals){totalFitness += individual.Fitness;}
Random random = new Random(System.DateTime.Now.Millisecond);decimal goal = random.Next(0,(int)totalFitness);decimal sumSoFar = 0;AbstractIndividual selectedParent = null;
foreach(AbstractIndividual individual in environment.Population.Individuals){sumSoFar += individual.Fitness;
selectedParent = individual;
if(sumSoFar > goal){break;}}
return selectedParent;}Basically, you figure out the sum of the “fitness†of the entirepopulation, then select a random value (goal) from 0 to the total sum of thefitness... Go through your list of individuals again (thus spinning the roulette wheel)and tally up the total accumulated fitness again... once your total accumulatedfitness has reached that random value (goal), that individual should be the parent. Thisfavors more fit individuals as their fitness is more likely to push the accumulatedfitness over the goal, thus ensuring their lineage. Though with drastic values, thissimulation can tend to favor the larger of the fitness too often. If this starts tooccur, you can always randomly manipulate the order of the individuals to check (sortingby fitness or random sorting) to ensure that you still have that taste of randomness.
This is an actual snippet of the code from my framework (DevelopStuff.EvolveStuff) ...When it's released, a .Net developer (read: C#, VB.Net or any other .Net compatible language) can easilyevolve whatever they would like. Whether is evolving code itself (read: GeneticProgramming) or a simple checkers player (which my team did back in 810:162), the framework should allowfor quick implementations.
* I wish I could remember the exact source in which we got the original idea, as ithas been done many times (roulette wheel selection), but to whom ever it was...thanks!
