I am currently writing a keyboard optimization algorithm in C (yes, another one :P) and I want to implement a fitness-proportionate selection as described here (http://www.public.iastate.edu/~crb002/ie574final.pdf):
With roulette selection you select members of the population
based on a roullete wheel model. Make a pie chart, where the
area of a member’s slice to the whole circle is the ratio of
the members fitness to the total population. As you can see if
a point on the circumfrence of the circle is picked at random
those population members with higher fitness will have a higher
probability of being picked. This ensures natural selection takes
place.
The problem is, I don't see how to implement it efficiently. I've thought of two methods: one is unreliable, and the other is slow.
First, the slow one:
For a keyboard pool of length N, create an array of length N where each element of the array actually contains two elements, a minimum and a maximum value. Each keyboard has a corresponding minimum and maximum value, and the range is based on the fitness of the keyboard. For example, if keyboard zero has a fitness of 10, keyboard one has a fitness of 20, and keyboard two has a fitness of 25, it would look like this:
array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;(Remember that a lower fitness is better, since it means less effort is required.)
Then generate a random number. For whichever range that number falls into, the corresponding keyboard is "killed" and replaced with the offspring of a different keyboard. Repeat this as many times as desired.
The problem with this is that it is very slow. It takes O(N^2) operations to finish.
Next the fast one:
First figure out what the lowest and highest fitnesses for the keyboards are. Then generate a random number between (lowest fitness) and (highest fitness) and kill all keyboards with a fitness higher than the generated number. This is efficient, but it's not guaranteed to only kill half the keyboards. It also has somewhat different mechanics from a "roulette wheel" selection, so it may not even be applicable.
So the question is, what is an efficient implementation?
EDIT: There is a somewhat efficient algorithm on page 36 of this book (http://books.google.com/books?id=XY4rQJ … on&f=false), but the problem is, it's only efficient if you do the roulette selection only one or a few times. Is there any efficient way to do many roulette selections in parallel?
My typing speed record: http://hi-games.net/typing-test/watch?u=493