Selección de Ruleta en Algoritmos Genéticos

¿Alguien puede proporcionar algún pseudo código para una función de selección de ruleta? ¿Cómo implementaría esto?

texto alternativo

Realmente no entiendo cómo leer esta notación matemática. Nunca tomé ninguna probabilidad o estadística.

    Han pasado unos años desde que hice esto yo mismo, sin embargo, el siguiente pseudo código se encontró con bastante facilidad en Google.

     para todos los miembros de la población
         sum + = aptitud de este individuo
     final para
    
     para todos los miembros de la población
         probabilidad = sum de probabilidades + (aptitud / sum)
         sum de probabilidades + = probabilidad
     final para
    
     bucle hasta que la nueva población esté llena
         haz esto dos veces
             number = Aleatorio entre 0 y 1
             para todos los miembros de la población
                 if número> probabilidad pero menor que la probabilidad siguiente 
                     entonces has sido seleccionado
             final para
         fin
         crear descendencia
     ciclo final
    

    El sitio de donde vino esto se puede encontrar aquí si necesita más detalles.

    Ya hay muchas soluciones correctas, pero creo que este código es más claro.

     def select(fs): p = random.uniform(0, sum(fs)) for i, f in enumerate(fs): if p < = 0: break p -= f return i 

    Además, si acumula el fs, puede producir una solución más eficiente.

     cfs = [sum(fs[:i+1]) for i in xrange(len(fs))] def select(cfs): return bisect.bisect_left(cfs, random.uniform(0, cfs[-1])) 

    Esto es más rápido y es un código extremadamente conciso. STL en C ++ tiene un algoritmo de bisección similar disponible si ese es el idioma que está usando.

    El pseudocódigo publicado contenía algunos elementos poco claros, y agrega la complejidad de generar descendencia en lugar de realizar una selección pura. Aquí hay una implementación simple de Python de ese pseudocódigo:

     def roulette_select(population, fitnesses, num): """ Roulette selection, implemented according to:  """ total_fitness = float(sum(fitnesses)) rel_fitness = [f/total_fitness for f in fitnesses] # Generate probability intervals for each individual probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))] # Draw new population new_population = [] for n in xrange(num): r = rand() for (i, individual) in enumerate(population): if r < = probs[i]: new_population.append(individual) break return new_population 

    Esto se llama selección de ruleta mediante aceptación estocástica:

     /// \param[in] f_max maximum fitness of the population /// /// \return index of the selected individual /// /// \note Assuming positive fitness. Greater is better. unsigned rw_selection(double f_max) { for (;;) { // Select randomly one of the individuals unsigned i(random_individual()); // The selection is accepted with probability fitness(i) / f_max if (uniform_random_01() < fitness(i) / f_max) return i; } } 

    El número promedio de bashs necesarios para una única selección es:

    τ = f max / avg (f)

    • f max es la aptitud máxima de la población
    • avg (f) es la aptitud promedio

    τ no depende explícitamente del número de individuos en la población (N), pero la relación puede cambiar con N.

    Sin embargo, en muchas aplicaciones (donde la aptitud permanece limitada y la aptitud promedio no disminuye a 0 para boost N), τ no aumenta sin límites con N y, por lo tanto, una complejidad típica de este algoritmo es O (1) (selección de ruleta usando los algoritmos de búsqueda tienen complejidad O (N) u O (log N).

    La distribución de probabilidad de este procedimiento es de hecho la misma que en la selección de rueda de ruleta clásica.

    Para más detalles ver:

    • Selección de rueda de la ruleta mediante aceptación estocástica (Adam Liposki, Dorota Lipowska - 2011)

    Aquí hay un código en C:

     // Find the sum of fitnesses. The function fitness(i) should //return the fitness value for member i** float sumFitness = 0.0f; for (int i=0; i < nmembers; i++) sumFitness += fitness(i); // Get a floating point number in the interval 0.0 ... sumFitness** float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness; // Translate this number to the corresponding member** int memberID=0; float partialSum=0.0f; while (randomNumber > partialSum) { partialSum += fitness(memberID); memberID++; } **// We have just found the member of the population using the roulette algorithm** **// It is stored in the "memberID" variable** **// Repeat this procedure as many times to find random members of the population** 

    De la respuesta anterior, obtuve lo siguiente, que fue más claro para mí que la respuesta en sí.

    Para dar un ejemplo:

    Aleatorio (sum) :: Aleatorio (12) Iterando a través de la población, verificamos lo siguiente: al azar

    Permítanos elegir 7 como el número aleatorio.

     Index | Fitness | Sum | 7 < Sum 0 | 2 | 2 | false 1 | 3 | 5 | false 2 | 1 | 6 | false 3 | 4 | 10 | true 4 | 2 | 12 | ... 

    A través de este ejemplo, el más apto (Índice 3) tiene el porcentaje más alto de ser elegido (33%); como el número aleatorio solo tiene que aterrizar dentro de 6-> 10, y será elegido.

      for (unsigned int i=0;i 

    El Prof. Thrun, del laboratorio de IA de Stanford, también presentó un rápido (¿?) Código de re-muestreo en Python durante su CS373 de Udacity. El resultado de búsqueda de Google llevó al siguiente enlace:

    http://www.udacity-forums.com/cs373/questions/20194/fast-resampling-algorithm

    Espero que esto ayude

    Aquí hay una implementación java compacta que escribí recientemente para la selección de ruleta, con suerte de uso.

     public static gene rouletteSelection() { float totalScore = 0; float runningScore = 0; for (gene g : genes) { totalScore += g.score; } float rnd = (float) (Math.random() * totalScore); for (gene g : genes) { if ( rnd>=runningScore && rnd< =runningScore+g.score) { return g; } runningScore+=g.score; } return null; } 

    Selección de rueda de ruleta en MatLab:

     TotalFitness=sum(Fitness); ProbSelection=zeros(PopLength,1); CumProb=zeros(PopLength,1); for i=1:PopLength ProbSelection(i)=Fitness(i)/TotalFitness; if i==1 CumProb(i)=ProbSelection(i); else CumProb(i)=CumProb(i-1)+ProbSelection(i); end end SelectInd=rand(PopLength,1); for i=1:PopLength flag=0; for j=1:PopLength if(CumProb(j)=SelectInd(i)) SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength); flag=1; break; end end if(flag==0) SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength); end end 
     Based on my research ,Here is another implementation in C# if there is a need for it: //those with higher fitness get selected wit a large probability //return-->individuals with highest fitness private int RouletteSelection() { double randomFitness = m_random.NextDouble() * m_totalFitness; int idx = -1; int mid; int first = 0; int last = m_populationSize -1; mid = (last - first)/2; // ArrayList's BinarySearch is for exact values only // so do this by hand. while (idx == -1 && first < = last) { if (randomFitness < (double)m_fitnessTable[mid]) { last = mid; } else if (randomFitness > (double)m_fitnessTable[mid]) { first = mid; } mid = (first + last)/2; // lies between i and i+1 if ((last - first) == 1) idx = last; } return idx; } 

    De acuerdo, entonces hay 2 métodos para la implementación de la selección de ruleta : Aceptación usual y estocástica .

    Algoritmo usual :

     # there will be some amount of repeating organisms here. mating_pool = [] all_organisms_in_population.each do |organism| organism.fitness.times { mating_pool.push(organism) } end # [very_fit_organism, very_fit_organism, very_fit_organism, not_so_fit_organism] return mating_pool.sample #=> random, likely fit, parent! 

    Algoritmo de aceptación estocástica :

     max_fitness_in_population = all_organisms_in_population.sort_by(:fitness)[0] loop do random_parent = all_organisms_in_population.sample probability = random_parent.fitness/max_fitness_in_population * 100 # if random_parent's fitness is 90%, # it's very likely that rand(100) is smaller than it. if rand(100) < probability return random_parent #=> random, likely fit, parent! else next #=> or let's keep on searching for one. end end 

    Puede elegir cualquiera de ellos, devolverán resultados idénticos.


    Recursos útiles:

    http://natureofcode.com/book/chapter-9-the-evolution-of-code : un capítulo claro y sencillo para principiantes sobre algoritmos genéticos. explica la selección de la rueda de ruleta como un cubo de letras de madera (mientras más lo pones, más grande es la posibilidad de elegir un algoritmo A, usual ).

    https://en.wikipedia.org/wiki/Fitness_proportionate_selection – describe el algoritmo de aceptación estocástica .

    Escribí una versión en C # y realmente estoy buscando confirmación de que sea correcta:

    (roulette_selector es un número aleatorio que estará en el rango de 0.0 a 1.0)

     private Individual Select_Roulette(double sum_fitness) { Individual ret = new Individual(); bool loop = true; while (loop) { //this will give us a double within the range 0.0 to total fitness double slice = roulette_selector.NextDouble() * sum_fitness; double curFitness = 0.0; foreach (Individual ind in _generation) { curFitness += ind.Fitness; if (curFitness >= slice) { loop = false; ret = ind; break; } } } return ret; }