Stochastic Universal Sampling GA in python

Question

I have a genetic algorithm that is currently using roulette wheel selection to produce a new population and I would like to change it to stochastic universal sampling.

I have a rough outline of how things are going to work here:

pointerDistance = sumFitness/popSize
start = rand.uniform(0, pointerDistance)
for i in xrange(popSize):
    pointers.append(start + i*pointerDistance)
cumulativeFit = 0
newIndiv = 0
for p in pointers:
    while cumulativeFit <= p:
        cumulativeFit += pop[newIndiv].fitness
        newPop[newIndiv] = copy.deepcopy(pop[newIndiv])
        newIndiv += 1

But i'm struggling with how exactly to implement stochastic universal sampling. Does anyone know of a good source for some pseudo code, or an example?

A brief description of what stochastic universal sampling is with an example (but i'm not sure if it makes sense?):

http://en.wikipedia.org/wiki/Stochastic_universal_sampling

Answer 1

def makeWheel(population):
    wheel = []
    total = sum(fitness(p) for p in population)
    top = 0
    for p in population:
        f = fitness(p)/total
        wheel.append((top, top+f, p))
        top += f
    return wheel

def binSearch(wheel, num):
    mid = len(wheel)//2
    low, high, answer = wheel[mid]
    if low<=num<=high:
        return answer
    elif low > num:
        return binSearch(wheel[mid+1:], num)
    else:
        return binSearch(wheel[:mid], num)

def select(wheel, N):
    stepSize = 1.0/N
    answer = []
    r = random.random()
    answer.append(binSearch(wheel, r))
    while len(answer) < N:
        r += stepSize
        if r>1:
            r %= 1
        answer.append(binSearch(wheel, r))
    return answer