aptitud selección proporcional (ruleta rueda de selección) en Python

Question

que tiene una lista de objetos (cromosoma) que tienen un atributo de fitness (chromosome.fitness está entre 0 y 1)

Dada una lista de este tipo de objetos, ¿cómo puede Implemento una función que devuelve un solo cromosoma cuya posibilidad de ser seleccionado es proporcional a su estado físico. Es decir, un cromosoma con aptitud 0.8 tiene el doble de probabilidades de ser seleccionado que uno con una aptitud de 0.4.

He encontrado algunas implementaciones de Python y pseudocódigo, pero son demasiado complejas para este requisito: la función solo necesita una lista de cromosomas. Los cromosomas almacenan su propia condición física como una variable interna.

La implementación que ya escribí fue antes de que decidiera permitir que los cromosomas almacenaran su propio estado físico, por lo que era mucho más complicado e implicaba relampagar listas y cosas.

---------------------------- EDIT ---------------- ------------

Gracias Lattyware. La siguiente función parece funcionar.

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

Hay una forma muy sencilla de seleccionar una elección aleatoria ponderada de un diccionario:

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 

Si usted no tiene un diccionario a la mano, se podría modificar esto para adaptarse a su clase (ya que no se han dado más detalles de la misma, o generar un diccionario:

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

Suponiendo que la condición física es un atributo

.

Aquí hay un ejemplo de la función modificada para tomar un iterable de cromosomas, nuevamente, haciendo la misma presunción.

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

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 

Answer 3

preferiría menos líneas:

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 4

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