Frage

Ich bin versucht, einen genetischen Algorithmus zu schreiben, basierend auf Techniken hatte ich aus dem Buch „AI-Techniken für Game-Programmierer“ aufgenommen, die eine binäre Codierung und Fitness verhältnismäßig Auswahl verwendet (auch als Roulette-Rad Auswahl bekannt) auf die Gene der Population, die innerhalb des Programms in einem zweidimensionalen Array zufällig erzeugt werden.

Ich habe kürzlich ein Stück Pseudo-Code und haben versucht, es zu implementieren , haben aber auf einige Probleme mit den Besonderheiten kommen, was ich zu tun brauchen. Ich habe eine Reihe von Büchern und einig Open-Source-Code überprüft und bin immer noch kämpfen, um die Fortschritte. Ich verstehe, dass ich die Summe der gesamten Fitness der Bevölkerung bekommen haben, eine Zufallszahl zwischen der Summe wählen, und Null ist, dann, wenn die Zahl größer ist als die Eltern sie überschreiben, aber ich mit der Umsetzung dieser Ideen habe Schwierigkeiten .

Jede Hilfe bei der Umsetzung dieser Ideen sehr viel wie mein Java würde geschätzt ist verrostet.

War es hilfreich?

Lösung

Im Folgenden ist eine komplette Übersicht über die GA. Ich stellte sicher, sehr detailliert sein, so kann es leicht zu C / Java / Python /..

/* 1. Init population */
POP_SIZE = number of individuals in the population
pop = newPop = []
for i=1 to POP_SIZE {
    pop.add( getRandomIndividual() )
}

/* 2. evaluate current population */
totalFitness = 0
for i=1 to POP_SIZE {
    fitness = pop[i].evaluate()
    totalFitness += fitness
}

while not end_condition (best fitness, #iterations, no improvement...)
{
    // build new population
    // optional: Elitism: copy best K from current pop to newPop
    while newPop.size()<POP_SIZE
    {
        /* 3. roulette wheel selection */
        // select 1st individual
        rnd = getRandomDouble([0,1]) * totalFitness
        for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
            rnd -= pop[idx].fitness
        }
        indiv1 = pop[idx-1]
        // select 2nd individual
        rnd = getRandomDouble([0,1]) * totalFitness
        for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
            rnd -= pop[idx].fitness
        }
        indiv2 = pop[idx-1]

        /* 4. crossover */
        indiv1, indiv2 = crossover(indiv1, indiv2)

        /* 5. mutation */
        indiv1.mutate()
        indiv2.mutate()

        // add to new population
        newPop.add(indiv1)
        newPop.add(indiv2)
    }
    pop = newPop
    newPop = []

    /* re-evaluate current population */
    totalFitness = 0
    for i=1 to POP_SIZE {
        fitness = pop[i].evaluate()
        totalFitness += fitness
    }
}

// return best genome
bestIndividual = pop.bestIndiv()     // max/min fitness indiv

Beachten Sie, dass zur Zeit sind Sie eine Fitness-Funktion fehlt (auf der Domäne abhängt). Der Crossover würde ein einfaches Punkt-Crossover (da Sie eine binäre Darstellung verwenden). Mutation könnte ein einfaches Umlegen eines Bit zufällig sein.

Bearbeiten : Ich habe den oben Pseudo-Code in Java unter Berücksichtigung Ihrer aktuelle Codestruktur und Notationen implementiert (beachten Sie, ich bin eher ein C / C ++ Typ als Java). Hinweis: Dies ist in keiner Weise die effizienteste oder vollständige Implementierung, ich gebe zu ich es geschrieben habe ziemlich schnell:

Individual.java 

import java.util.Random;

public class Individual
{
    public static final int SIZE = 500;
    private int[] genes = new int[SIZE];
    private int fitnessValue;

    public Individual() {}

    public int getFitnessValue() {
        return fitnessValue;
    }

    public void setFitnessValue(int fitnessValue) {
        this.fitnessValue = fitnessValue;
    }

    public int getGene(int index) {
        return genes[index];
    }

    public void setGene(int index, int gene) {
        this.genes[index] = gene;
    }

    public void randGenes() {
        Random rand = new Random();
        for(int i=0; i<SIZE; ++i) {
            this.setGene(i, rand.nextInt(2));
        }
    }

    public void mutate() {
        Random rand = new Random();
        int index = rand.nextInt(SIZE);
        this.setGene(index, 1-this.getGene(index));    // flip
    }

    public int evaluate() {
        int fitness = 0;
        for(int i=0; i<SIZE; ++i) {
            fitness += this.getGene(i);
        }
        this.setFitnessValue(fitness);

        return fitness;
    }
}

Population.java 

import java.util.Random;

public class Population
{
    final static int ELITISM_K = 5;
    final static int POP_SIZE = 200 + ELITISM_K;  // population size
    final static int MAX_ITER = 2000;             // max number of iterations
    final static double MUTATION_RATE = 0.05;     // probability of mutation
    final static double CROSSOVER_RATE = 0.7;     // probability of crossover

    private static Random m_rand = new Random();  // random-number generator
    private Individual[] m_population;
    private double totalFitness;

    public Population() {
        m_population = new Individual[POP_SIZE];

        // init population
        for (int i = 0; i < POP_SIZE; i++) {
            m_population[i] = new Individual();
            m_population[i].randGenes();
        }

        // evaluate current population
        this.evaluate();
    }

    public void setPopulation(Individual[] newPop) {
        // this.m_population = newPop;
        System.arraycopy(newPop, 0, this.m_population, 0, POP_SIZE);
    }

    public Individual[] getPopulation() {
        return this.m_population;
    }

    public double evaluate() {
        this.totalFitness = 0.0;
        for (int i = 0; i < POP_SIZE; i++) {
            this.totalFitness += m_population[i].evaluate();
        }
        return this.totalFitness;
    }

    public Individual rouletteWheelSelection() {
        double randNum = m_rand.nextDouble() * this.totalFitness;
        int idx;
        for (idx=0; idx<POP_SIZE && randNum>0; ++idx) {
            randNum -= m_population[idx].getFitnessValue();
        }
        return m_population[idx-1];
    }

    public Individual findBestIndividual() {
        int idxMax = 0, idxMin = 0;
        double currentMax = 0.0;
        double currentMin = 1.0;
        double currentVal;

        for (int idx=0; idx<POP_SIZE; ++idx) {
            currentVal = m_population[idx].getFitnessValue();
            if (currentMax < currentMin) {
                currentMax = currentMin = currentVal;
                idxMax = idxMin = idx;
            }
            if (currentVal > currentMax) {
                currentMax = currentVal;
                idxMax = idx;
            }
            if (currentVal < currentMin) {
                currentMin = currentVal;
                idxMin = idx;
            }
        }

        //return m_population[idxMin];      // minimization
        return m_population[idxMax];        // maximization
    }

    public static Individual[] crossover(Individual indiv1,Individual indiv2) {
        Individual[] newIndiv = new Individual[2];
        newIndiv[0] = new Individual();
        newIndiv[1] = new Individual();

        int randPoint = m_rand.nextInt(Individual.SIZE);
        int i;
        for (i=0; i<randPoint; ++i) {
            newIndiv[0].setGene(i, indiv1.getGene(i));
            newIndiv[1].setGene(i, indiv2.getGene(i));
        }
        for (; i<Individual.SIZE; ++i) {
            newIndiv[0].setGene(i, indiv2.getGene(i));
            newIndiv[1].setGene(i, indiv1.getGene(i));
        }

        return newIndiv;
    }


    public static void main(String[] args) {
        Population pop = new Population();
        Individual[] newPop = new Individual[POP_SIZE];
        Individual[] indiv = new Individual[2];

        // current population
        System.out.print("Total Fitness = " + pop.totalFitness);
        System.out.println(" ; Best Fitness = " + 
            pop.findBestIndividual().getFitnessValue());

        // main loop
        int count;
        for (int iter = 0; iter < MAX_ITER; iter++) {
            count = 0;

            // Elitism
            for (int i=0; i<ELITISM_K; ++i) {
                newPop[count] = pop.findBestIndividual();
                count++;
            }

            // build new Population
            while (count < POP_SIZE) {
                // Selection
                indiv[0] = pop.rouletteWheelSelection();
                indiv[1] = pop.rouletteWheelSelection();

                // Crossover
                if ( m_rand.nextDouble() < CROSSOVER_RATE ) {
                    indiv = crossover(indiv[0], indiv[1]);
                }

                // Mutation
                if ( m_rand.nextDouble() < MUTATION_RATE ) {
                    indiv[0].mutate();
                }
                if ( m_rand.nextDouble() < MUTATION_RATE ) {
                    indiv[1].mutate();
                }

                // add to new population
                newPop[count] = indiv[0];
                newPop[count+1] = indiv[1];
                count += 2;
            }
            pop.setPopulation(newPop);

            // reevaluate current population
            pop.evaluate();
            System.out.print("Total Fitness = " + pop.totalFitness);
            System.out.println(" ; Best Fitness = " +
                pop.findBestIndividual().getFitnessValue()); 
        }

        // best indiv
        Individual bestIndiv = pop.findBestIndividual();
    }
}

Andere Tipps

Warum nicht eine Open-Source-Framework wie JGAP verwenden: http://jgap.sf.net

Ich habe diesen Algorithmus implementiert, indem einen „kumulativen Fitness-Array“ Erstellen und binäre Suche , so dass die Notwendigkeit, Iterierte durch jedes Element zu reduzieren in der Anordnung bei der Auswahl:

  1. Für Populationsgröße N schaffen kumulativen Fitness-Array: arr. [N]
  2. Set arr [0]:. = ComputeFitness (Einzel [0])
  3. Dann wird für jedes nachfolgende Element. X, Arr [X] = arr [X-1] + computeFitness (Einzel [X])
  4. Erzeugen Sie eine Zufallszahl zwischen 0 und arr [N] (das heißt die Gesamt Fitness).
  5. Verwenden Sie eine binäre Suche (z Collections.binarySearch) den entsprechenden Index in der kumulativen Fitness-Array zu suchen, und verwenden Sie diesen Index, um die Person zu wählen.

Beachten Sie, dass Sie nur die Fitness-Array zu Beginn der Reproduktionsphase erstellen müssen, und kann dann wiederverwendet es mehrere Male Auswahlen in O (log N) Zeit auszuführen.

Als Nebenwirkung zur Kenntnis, dass Turnierauswahl ist viel einfacher zu implementieren!

Das Konzept, nach dem Sie suchen ist „Roulette-Rad-Auswahl“ bezeichnet. Sie haben nicht eine etablierte Fitness-Funktion haben noch (Sie impliziert werden, dass die Fitness jedes einzelnen der Integralwert von seinem Chromosom ist), aber wenn Sie einen allgemeinen Plan zu tun ist:

     
  1. Summe der Fitness der gesamten Bevölkerung.
    2.  
  2. Holen Sie sich eine Zufallszahl (nennen wir es x) zwischen 0 und der Gesamt Fitness.
    3.  
  3. Iterate durch die Bevölkerung. Für jedes Mitglied:
    1. subtrahieren Sie die Fitness-Mitglied von x.
    2. Wenn x nun kleiner oder gleich Null ist, das aktuelle Element aus.

Es gibt andere gleichwertige Implementierungen, aber die allgemeine Idee ist es, Mitglieder mit einer Wahrscheinlichkeit proportional zu ihrer Fitness zu wählen.

Edit: Ein paar Anmerkungen zu Fitness-Funktionen. Die Darstellung eines Chromosoms (in Ihrem Fall als 32-Bit-Integer) ist unabhängig von der Fitness-Funktion verwendet, um sie zu bewerten. Zum Beispiel behandeln binäre Codierungen typischerweise das Chromosom als einen Satz von Bitfeldern in einen Integralwert von geeigneter Größe gefüllt. Crossover und Mutation können dann durch die entsprechenden Bit-Maskierungsoperationen durchgeführt werden. Wenn Sie interessiert sind, kann ich einige einfache GA Code schreiben Ich habe rumliegen (in C und Python), die bitweise Operationen verwendet diese Funktionen zu implementieren. Ich bin mir nicht sicher, wie gut Sie mit diesen Sprachen sind.

Ich habe eine erweiterbare Implementierung in Java, in denen die Betreiber und individuelle Struktur auch durch Schnittstellen definiert, die zusammenarbeiten. Github Repo hier https://github.com/juanmf/ga

Es hat eine Standard-Implementierung für jeden Betreiber, und ein Beispiel Problem Implementierung mit einer bestimmten Person / Bevölkerungsstruktur und einem Fitness Meter. Das Beispiel Problem Implementierung ist die eine gute Fußballmannschaft mit Spielern unter 20 Teams und eine Budgetrestriktion zu finden.

Um es zu Ihrem aktuellen Problem anzupassen, müssen Sie Implementierungen dieser Schnittstellen bieten: 

juanmf.ga.structure.Gen;
juanmf.ga.structure.Individual;
juanmf.ga.structure.IndividualFactory; 
juanmf.ga.structure.Population;  // Has a basic implementation already
juanmf.ga.structure.PopulationFactory;

In pkg juanmf.grandt haben Sie die Beispiel Probleme Implementierungsklassen, und wie sie zu veröffentlichen, wie weiter unten im Codeausschnitt gezeigt.

So veröffentlichen Sie Implementierungen Sie einfach die richtigen Klassen von diesem Frühling Bohnen zurück: 

/**
 * Make sure @ComponentScan("pkg") in juanmf.ga.App.java includes this class' pkg 
 * so that these beans get registered.
 */
@Configuration
public class Config {

    @Bean(name="individualFactory")
    public IndividualFactory getIndividualFactory() {
        return new Team.TeamFactory();
    }

    @Bean(name="populationFactory")
    public PopulationFactory getPopulationFactory() {
        return new Team.TeamPopulationFactory();
    }

    @Bean(name="fitnessMeter")
    public FitnessMeter getFitnessMeter() {
        return new TeamAptitudeMeter();
    }
}

Crosser Operator hat zwei Implementierungen für die gleiche Technik, eine sequentielle und eine gleichzeitige, die mit Abstand aufeinanderfolgende trifft.

Stop-Bedingung angegeben werden. Wenn nicht angegeben wird, ist es eine Standard-Stoppbedingung hat, die ohne Verbesserungen nach 100 Generationen hält (hier müssen Sie mit elitären vorsichtig sein, nicht das Beste aus jeder Generation zu verlieren, um diese Stoppbedingung wirksam auszulösen).

Also, wenn jemand bereit ist, es zu versuchen, würde ich Ihnen gerne behilflich. Jeder ist willkommen, bieten Anregungen, und besser noch Operator-Implementierungen. D oder eine Verbesserung der Pull-Anforderung

sollten diese anderen Fragen über Roulette-Rad Auswahl helfen:

In der ersten, Ich habe versucht, zu erklären, wie die Roulette-Rad funktioniert. In der zweiten hat Jarod Elliott einige Pseudo-Code zur Verfügung gestellt. In Kombination mit Adamskis Beschreibung einer effizienten Umsetzung , sollten diese ausreichend sein, um bekommen etwas arbeiten.

Nur ein Punkt erwähnenswert. Die Roulette-Rad-Auswahl (wie in dem Pseudo-Code angegeben) wird nicht Arbeit für Minimierungsprobleme -. Es ist jedoch gültig für die Maximierung Probleme

Durch die Art und Weise, in der die meisten passen einzelne ausgewählt ist, wird die Minimierung Fall nicht halten. Details werden zur Verfügung gestellt in: Computational Intelligence: 2. Auflage

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top