Python中的健身比例选择（轮盘赌选择）

Question

我有一个对象列表（染色体），它具有属性适应性（chromosome.fitness介于0和1之间）

给定一个这样的对象列表，我如何实现一个返回单个染色体的函数，其被选中的机会与其适应度成正比？也就是说，具有适应度0.8的染色体被选择为具有适合度0.4的染色体的可能性的两倍。

我发现了一些Python和伪代码实现，但它们对于这个要求来说太复杂了：函数只需要一个染色体列表。染色体将自身的适应性存储为内部变量。

我已经写过的实现是在我决定允许染色体存储它们自己的适应性之前，因此更复杂并涉及压缩列表和事物。

- - - - - - - - - - - - - - 编辑 - - - - - - - - - - - -------

谢谢Lattyware。以下功能似乎有效。

def selectOne(self, population):
        max     = sum([c.fitness for c in population])
        pick    = random.uniform(0, max)
        current = 0
        for chromosome in population:
            current += chromosome.fitness
            if current > pick:
                return chromosome

Answer 1

有一种从字典中选择加权随机选择的简单方法：

def weighted_random_choice(choices):
    max = sum(choices.values())
    pick = random.uniform(0, max)
    current = 0
    for key, value in choices.items():
        current += value
        if current > pick:
            return key

如果您手边没有字典，可以修改它以适合您的课程（因为您没有提供更多详细信息，或者生成字典：

choices = {chromosome: chromosome.fitness for chromosome in chromosomes}

假设健身是一种属性。

以下是修改为采用可迭代染色体的函数的示例，再次进行相同的假设。

def weighted_random_choice(chromosomes):
    max = sum(chromosome.fitness for chromosome in chromosomes)
    pick = random.uniform(0, max)
    current = 0
    for chromosome in chromosomes:
        current += chromosome.fitness
        if current > pick:
            return chromosome

Answer 2

使用numpy.random.choice。

import numpy.random as npr
def selectOne(self, population):
    max = sum([c.fitness for c in population])
    selection_probs = [c.fitness/max for c in population]
    return population[npr.choice(len(population), p=selection_probs)]

Answer 3

from __future__ import division
import numpy as np
import random,pdb
import operator

def roulette_selection(weights):
        '''performs weighted selection or roulette wheel selection on a list
        and returns the index selected from the list'''

        # sort the weights in ascending order
        sorted_indexed_weights = sorted(enumerate(weights), key=operator.itemgetter(1));
        indices, sorted_weights = zip(*sorted_indexed_weights);
        # calculate the cumulative probability
        tot_sum=sum(sorted_weights)
        prob = [x/tot_sum for x in sorted_weights]
        cum_prob=np.cumsum(prob)
        # select a random a number in the range [0,1]
        random_num=random.random()

        for index_value, cum_prob_value in zip(indices,cum_prob):
            if random_num < cum_prob_value:
                return index_value


if __name__ == "__main__":
    weights=[1,2,6,4,3,7,20]
    print (roulette_selection(weights))
    weights=[1,2,2,2,2,2,2]
    print (roulette_selection(weights))

Answer 4

我更喜欢线条：

import itertools

def choose(population):
    bounds = list(itertools.accumulate(chromosome.fitness for chromosome in population))
    pick = random.random() * bounds[-1]
    return next(chromosome for chromosome, bound in zip(population, bounds) if pick < bound)

Answer 5

import random

def weighted_choice(items):
    total_weight = sum(item.weight for item in items)
    weight_to_target = random.uniform(0, total_weight)
    for item in items:
        weight_to_target -= item.weight
        if weight_to_target <= 0:
            return item