Roulette-Auswahl in Genetische Algorithmen

Question

Kann jemand einige pseudo-code für ein roulette-Auswahl-Funktion?Wie würde ich dies umsetzen:

Ich weiß wirklich nicht verstehen, wie Lesen Sie diese mathematische notation.Ich habe nie irgendwelche Wahrscheinlichkeit und Statistik.

Answer 1

Es ist schon ein paar Jahre her, seit ich das selbst gemacht habe, aber der folgende Pseudo-Code leicht genug auf Google gefunden wurde.

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

Der Ort, wo diese herkommt können hier , wenn Sie weiter brauchen Details.

Answer 2

Viele richtigen Lösungen bereits, aber ich denke, dieser Code ist klarer.

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

Darüber hinaus, wenn Sie die fs ansammeln, können Sie eine effizientere Lösung herzustellen.

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

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

Dies ist schneller und es ist extrem präziser Code. STL in C ++ hat einen ähnlichen Bisektionsalgorithmus zur Verfügung, wenn das ist die Sprache, die Sie verwenden.

Answer 3

Der Pseudo-Code geschrieben enthielt einige unklare Elemente, und es fügt die Komplexität der Erzeugung Nachkommen anstelle reiner Auswahl durchzuführen. Hier ist eine einfache Python-Implementierung dieses Pseudo-Code:

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

Dies wird als roulette-Rad Auswahl über stochastic Annahme:

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

Die Durchschnittliche Anzahl der versuche, die nötig für eine einzelne Auswahl ist:

τ = f_max / avg(f)

• f_max ist die maximale fitness der Bevölkerung
• avg(f) ist die Durchschnittliche fitness

τ hängt nicht ab, die explizit auf die Anzahl der Individuen in der population (N), aber das Verhältnis ändert sich mit N.

Aber in vielen Anwendung (wo die fitness bleibt begrenzt und die Durchschnittliche fitness, mindert nicht zu 0 für steigende N) τ nicht erhöhen unboundedly mit N und damit eine typische Komplexität dieses Algorithmus ist O(1) (roulette-Rad Auswahl über such-algorithmen ist O(N) oder O(log N) - Komplexität).

Die Wahrscheinlichkeitsverteilung von dieses Verfahren ist zwar die gleiche wie in den klassischen roulette-Rad-Auswahl.

Für weitere details siehe:

• Roulette-Rad Auswahl über stochastic Annahme (Adam Liposki, Dorota Lipowska - 2011)

Answer 5

Hier ist ein Code 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

Aus der obigen Antwort, habe ich die folgende, die ist mir klarer als die Antwort selbst.

Um ein Beispiel zu geben:

Random (Summe) :: Random (12) Iterieren durch die Bevölkerung, überprüfen wir die folgende: random

Lassen Sie uns gewählt haben 7 als Zufallszahl.

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

Durch dieses Beispiel die Passform (Index 3) hat den höchsten Anteil an (33%) gewählt wird; als die Zufallszahl nur innerhalb 6-> 10 landen muss, und es wird gewählt werden.

    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 von der Stanford AI Lab präsentiert auch einen schnellen (er?) Resampling-Code in Python während seiner CS373 von Udacity. Google Suchergebnis führte zu folgendem Link:

http://www.udacity-forums.com/ cs373 / Fragen / 20194 / Fast-Resampling-Algorithmus

Hope, das hilft

Answer 8

Hier ist eine kompakte Java-Implementierung Ich habe vor kurzem für Roulette Auswahl geschrieben, hoffentlich Nutzungs.

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

Roulette-Rad-Auswahl 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

Okay, so gibt es zwei Methoden für Roulette-Rad Auswahl Umsetzung:. Übliche und Stochastic Acceptance ein

Übliche Algorithmus:

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

Stochastic Acceptance Algorithmus:

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

Sie können wählen, entweder werden sie identische Ergebnisse zurückkehren.

---

Nützliche Informationen:

http://natureofcode.com/book/chapter-9 -die-evolution-of-Code - ein anfängerfreundlich und klar Kapitel über genetische Algorithmen. erklärt Roulette-Rad Auswahl als einen Eimer mit Holzbuchstaben (die mehr als Sie setzen in - der groß ist die Chance, einen A der Kommissionierung, Übliche Algorithmus).

https://en.wikipedia.org/wiki/Fitness_proportionate_selection - beschreibt Stochastic Acceptance Algorithmus.

Answer 12

Swift 4 array Erweiterung implementiert gewichteten Zufallsauswahl, a.k.a Roulette Auswahl aus den Elementen:

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

Zum Beispiel angesichts der zwei Elementanordnung:

[0.9, 0.1]

weightedRandomIndex() wird wieder Null 90% der Zeit und ein 10% der Zeit.

Hier ist ein vollständiger Test:

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

Ausgabe:

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

Diese Antwort ist im Grunde das gleiche wie Andrew Maos Antwort hier: https://stackoverflow.com/a/15582983/74975

Answer 13

Ich schrieb eine Version in C # und wirklich suche eine Bestätigung, dass es in der Tat richtig ist:

(roulette_selector ist eine Zufallszahl, die im Bereich von 0,0 bis 1,0 ist)

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;

    }