Selección de ruleta en algoritmos genéticos

Question

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

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

Answer 1

Han pasado algunos años desde que lo hice yo mismo, sin embargo, el siguiente pseudocódigo se encontró fácilmente en Google.

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
    do this twice
        number = Random between 0 and 1
        for all members of population
            if number > probability but less than next probability 
                then you have been selected
        end for
    end
    create offspring
end loop

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

Answer 2

Muchas soluciones correctas ya, 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 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 lenguaje que está utilizando.

Answer 3

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 en Python de ese pseudocódigo:

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <http://stackoverflow.com/questions/177271/roulette
        -selection-in-genetic-algorithms/177278#177278>
    """
    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

Answer 4

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 intentos necesarios para una sola selección es:

& # 964; = f _max / avg (f)

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

& # 964; 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 el estado físico permanece limitado y el estado físico promedio no disminuye a 0 para aumentar N) & # 964; no aumenta ilimitadamente con N y, por lo tanto, una complejidad típica de este algoritmo es O (1) (la selección de la rueda de la ruleta que usa algoritmos de búsqueda tiene una 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 clásica de la ruleta.

Para más detalles ver:

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

Answer 5

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

Answer 6

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

Para dar un ejemplo:

Aleatorio (suma) :: Aleatorio (12) Iterando a través de la población, verificamos lo siguiente: random & Lt; suma

Vamos a elegir 7 como 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%); ya que el número aleatorio solo tiene que aterrizar dentro de 6 - > 10, y será elegido.

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }

Answer 7

Prof. Thrun of Stanford AI lab también presentó un código de muestreo rápido (¿er?) En python durante su CS373 de Udacity. El resultado de la búsqueda de Google condujo al siguiente enlace:

http://www.udacity-forums.com/ cs373 / preguntas / 20194 / algoritmo de remuestreo rápido

Espero que esto ayude

Answer 8

Aquí hay una implementación compacta de Java 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;
}

Answer 9

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) && CumProb(j+1)>=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

Answer 10

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;
        }

Answer 11

Bien, entonces hay 2 métodos para la implementación de selección de rueda de ruleta : Usual y Aceptación estocástica uno.

Algoritmo habitual :

# 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 amigable para principiantes sobre algoritmos genéticos. explica la selección de la rueda de la ruleta como un cubo de letras de madera (cuanto más lo pones, mayor es la posibilidad de elegir un algoritmo A, Usual ).

https://en.wikipedia.org/wiki/Fitness_proportionate_selection - describe Algoritmo de aceptación estocástica .

Answer 12

Esta extensión de matriz Swift 4 implementa una selección aleatoria ponderada, también conocida como una selección de ruleta de sus elementos:

public extension Array where Element == Double {

    /// Consider the elements as weight values and return a weighted random selection by index.
    /// a.k.a Roulette wheel selection.
    func weightedRandomIndex() -> Int {
        var selected: Int = 0
        var total: Double = self[0]

        for i in 1..<self.count { // start at 1
            total += self[i]
            if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
        }

        return selected
    }
}

Por ejemplo, dada la matriz de dos elementos:

[0.9, 0.1]

weightedRandomIndex() devolverá cero el 90% del tiempo y un 10% del tiempo.

Aquí hay una prueba más completa:

let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
    let index = weights.weightedRandomIndex()
    results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
    print(weights[key], Double(val)/Double(n))
}

salida:

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

Esta respuesta es básicamente la misma que la respuesta de Andrew Mao aquí: https://stackoverflow.com/a/15582983/74975

Answer 13

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;

    }