python - python 中的随机通用采样 GA

Question

我有一个遗传算法，目前正在使用轮盘赌选择来产生新的群体，我想将其更改为随机通用抽样。

我对这里的运作方式有一个粗略的概述:

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

但我正在努力解决如何准确地实现随机通用采样。有谁知道一些伪代码的好来源或示例？

通过示例简要描述什么是随机通用采样(但我不确定它是否有意义？):

<强> 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