Selezione della roulette negli algoritmi genetici

Question

Qualcuno può fornire uno pseudo codice per una funzione di selezione della roulette?Come lo implementerei:

Non capisco davvero come leggere questa notazione matematica.Non ho mai preso in considerazione alcuna probabilità o statistica.

Answer 1

Sono passati alcuni anni da quando l'ho fatto da solo, tuttavia il seguente pseudo codice è stato trovato abbastanza facilmente su 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

Il sito da cui proviene è reperibile qui se hai bisogno di ulteriori informazioni i dettagli.

Answer 2

Molte soluzioni giuste già, ma penso che questo codice sia più chiaro.

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

Inoltre, se si accumula la fs, è possibile produrre una soluzione più efficiente.

cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]

def select(cfs):
    return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))

Questo è sia più veloce sia un codice estremamente conciso. STL in C ++ ha un algoritmo di bisection simile disponibile se è la lingua che stai usando.

Answer 3

Lo pseudocodice pubblicato conteneva alcuni elementi poco chiari e aggiunge la complessità di generare prole invece di eseguire la selezione pura. Ecco una semplice implementazione python di quello pseudocodice:

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

Questo si chiama selezione della ruota della roulette tramite accettazione stocastica:

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

Il numero medio di tentativi necessari per una singola selezione è:

&

# 964; = f _max / avg (f)

• f _max è la forma fisica massima della popolazione
• avg (f) è l'idoneità media

&

# 964; non dipende esplicitamente dal numero di individui nella popolazione (N), ma il rapporto può cambiare con N.

Tuttavia, in molte applicazioni (in cui la forma fisica rimane limitata e la forma fisica media non diminuisce a 0 per aumentare N) & # 964; non aumenta in modo illimitato con N e quindi una complessità tipica di questo algoritmo è O (1) (la selezione della ruota della roulette usando algoritmi di ricerca ha complessità O (N) o O (log N)).

La distribuzione di probabilità di questa procedura è effettivamente la stessa della classica selezione della ruota della roulette.

Per ulteriori dettagli consultare:

• Selezione della ruota della roulette tramite accettazione stocastica (Adam Liposki, Dorota Lipowska - 2011)

Answer 5

Ecco un po 'di codice in 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

Dalla risposta di cui sopra, ho ottenuto quanto segue, che era più chiaro per me della risposta stessa.

Per fare un esempio:

Casuale (somma) :: Casuale (12) Scorrendo la popolazione, controlliamo quanto segue: random & Lt; sum

Cerchiamo di scegliere 7 come numero casuale.

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

Attraverso questo esempio, il più adatto (Indice 3) ha la più alta percentuale di essere scelto (33%); poiché il numero casuale deve atterrare entro 6 - > 10 e verrà scelto.

    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 di Stanford AI lab ha anche presentato un veloce (er?) Codice di ricampionamento in pitone durante il suo CS373 di Udacity. Il risultato della ricerca di Google ha portato al seguente link:

http://www.udacity-forums.com/ cs373 / domande / 20194 / fast-ricampionamento-algoritmo

Spero che questo aiuti

Answer 8

Ecco un'implementazione java compatta che ho scritto di recente per la selezione della roulette, si spera sia utile.

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

Selezione della ruota della roulette in 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

Ok, quindi ci sono 2 metodi per selezione della ruota della roulette implementazione: Solito E Accettazione stocastica uno.

Solito algoritmo:

# 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!

Accettazione stocastica algoritmo:

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

Puoi scegliere uno dei due, restituiranno risultati identici.

---

Risorse utili:

http://natureofcode.com/book/chapter-9-the-evolution-of-code - un capitolo chiaro e adatto ai principianti sugli algoritmi genetici.spiega selezione della ruota della roulette come un secchio di lettere di legno (più ne metti, maggiore è la possibilità di scegliere una A, Solito algoritmo).

https://en.wikipedia.org/wiki/Fitness_proportionate_selection - descrive Accettazione stocastica algoritmo.

Answer 12

Questa estensione Swift 4 implementa la selezione casuale ponderata, a.k.a selezione della roulette dai suoi elementi:

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

Ad esempio, dato l'array a due elementi:

[0.9, 0.1]

weightedRandomIndex() restituirà zero il 90% delle volte e un 10% delle volte.

Ecco un test più completo:

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

uscita:

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

Questa risposta è sostanzialmente la stessa della risposta di Andrew Mao qui: https://stackoverflow.com/a/15582983/74975

Answer 13

Ho scritto una versione in C # e sto davvero cercando conferma che sia davvero corretta:

(roulette_selector è un numero casuale che sarà compreso tra 0,0 e 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;

    }