Domanda

Sto tentando di scrivere un algoritmo genetico basato su tecniche che avevo raccolto dal libro "Tecniche di intelligenza artificiale per il gioco programmatori" che utilizza una codifica binaria e fitness selezione proporzionale (noto anche come selezione roulette) sui geni della popolazione che vengono generate in modo casuale all'interno del programma in una matrice bidimensionale.

Recentemente ho trovato un pezzo di pseudocodice e ho cercato di attuarlo , ma hanno incontrato alcuni problemi con le specifiche di quello che devo fare. Ho controllato un certo numero di libri e un po 'di codice open-source e sto ancora lottando per il progresso. Capisco che devo ottenere la somma del benessere totale della popolazione, scegliere un numero casuale compreso tra la somma e pari a zero, quindi se il numero è maggiore di genitori per sovrascrivere, ma io sto lottando con l'attuazione di queste idee .

Qualsiasi aiuto nella realizzazione di queste idee sarebbe molto apprezzato come il mio Java è arrugginito.

È stato utile?

Soluzione

Di seguito è un quadro completo della GA. Ho fatto in modo di essere molto dettagliato in modo che possa essere facilmente codificato per 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

Si noti che attualmente vi state perdendo una funzione di fitness (dipende dal dominio). Il crossover sarebbe un semplice punto di crossover (dal momento che si sta utilizzando una rappresentazione binaria). La mutazione potrebbe essere un semplice lancio di un po 'a caso.

Modifica : Ho implementato il pseudocodice sopra in Java prendendo in considerazione la struttura del codice attuale e notazioni (tenere a mente io sono più di un c / c ++ ragazzo di Java). Nota: questo non è in alcun modo l'implementazione più efficiente o completa, lo ammetto ho scritto piuttosto rapidamente:

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

Altri suggerimenti

Perché non usare un framework open-source come JGAP: http://jgap.sf.net

Ho implementato questo algoritmo per la creazione di una "matrice di fitness cumulativo" e ricerca binaria , quindi riducendo la necessità di scorrere ogni elemento nella matrice durante la selezione:

  1. Per dimensione della popolazione N creare array di forma fisica cumulativa:. Arr [N]
  2. Imposta arr [0]:. = ComputeFitness (individuale [0])
  3. Quindi, per ogni elemento successivo:. X, arr [X] = arr [X-1] + computeFitness (individuale [X])
  4. generare un numero casuale compreso tra 0 e arr [N] (vale a dire l'idoneità totale).
  5. Utilizza una ricerca binaria (ad esempio Collections.binarySearch) per individuare l'indice appropriato nella matrice di fitness cumulativo, e utilizzare questo indice per selezionare l'individuo.

Si noti che è necessario solo per creare l'array fitness presso l'inizio della fase di riproduzione, e può quindi ri-utilizzarlo più volte per effettuare le selezioni in O (log N) di tempo.

Per inciso, si noti che la selezione del torneo è molto più facile da implementare!

Il concetto che stai cercando si chiama "selezione ruota della roulette." Non si dispone di una funzione di fitness stabilita ancora (si può essere che implica che l'idoneità di ogni individuo è il valore integrale del suo cromosoma), ma quando si fa un piano generale è:

     
  1. sommare il benessere di tutta la popolazione.
    2.  
  2. Ottenere un numero casuale (lo chiamano x) tra 0 e l'idoneità totale.
    3.  
  3. Scorrere la popolazione. Per ogni membro:
    1. Sottrarre idoneità del membro da x.
    2. Se x è ora minore o uguale a zero, selezionare il membro corrente.

Ci sono altre implementazioni equivalenti, ma l'idea generale è quella di selezionare i membri con una probabilità proporzionale alla loro idoneità.

Modifica: Alcune note sulle funzioni di fitness. La rappresentazione di un cromosoma (nel tuo caso come un intero a 32 bit) è indipendente dalla funzione di idoneità utilizzato per valutarla. Ad esempio, le codifiche binarie tipicamente trattano il cromosoma come insieme di campi di bit imballato in un valore integrale di dimensioni adeguate. Crossover e la mutazione possono essere realizzati dagli appositi operazioni bit-mascheramento. Se siete interessati, posso inviare qualche semplice codice GA ho sparso in giro (in C e Python), che utilizza operazioni bit per bit per implementare queste funzioni. Non sono sicuro di come si sta comodi con queste lingue.

feci un'implementazione estensibile in Java, in cui gli operatori e struttura individuale è ben definito da interfacce che lavorano insieme. Github repo qui https://github.com/juanmf/ga

Si dispone di un'implementazione standard per ciascun operatore, e un'implementazione problema esempio con una particolare struttura individuale / popolazione e un misuratore di fitness. L'esempio di implementazione problema è quello di trovare la buona squadra di calcio con giocatori tra 20 squadre e una restrizione di bilancio.

Per adattarlo al vostro problema attuale è necessario fornire implementazioni di queste interfacce: 

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 voi hanno le classi di implementazione ad esempio problema, e come a pubblicarle, come illustrato nel frammento di codice seguente.

Per pubblicare si implementazioni non resta che tornare alle classi appropriate da questo bean Spring: 

/**
 * 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();
    }
}

operatore Crosser ha due implementazioni per la stessa tecnica, una sequenziale e una concorrente che supera di gran lunga sequenziale.

condizione di Stop può essere specificato. Se nessuno è dato, ha una condizione di arresto di default che si ferma dopo 100 generazioni senza miglioramenti (qui bisogna stare attenti con elitario, per non perdere il meglio di ogni generazione, in modo da innescare efficacemente questa condizione di arresto).

Quindi, se qualcuno è disposto a fare un tentativo, sarei felice di aiutare. Chiunque è il benvenuto a offrire suggerimenti, e meglio ancora implementazioni operatore:. D o qualsiasi richiesta di pull migliorare

Queste altre domande sulla selezione roulette dovrebbero aiutare:

Nella prima, ho provato a spiegare come il ruota della roulette funziona. Nel secondo, Jarod Elliott ha fornito alcune pseudocodice . Combinato con descrizione di Adamski di un'implementazione efficace , questi dovrebbero essere sufficienti per ottenere qualcosa di lavoro.

Solo un punto degno di nota. La selezione roulette (come indicato in pseudo-codice) non funziona per problemi di minimizzazione -. È, tuttavia, valido per problemi di massimizzazione

A causa del modo in cui viene selezionata la persona più adatta, il caso minimizzazione non mantiene. I dettagli sono forniti in: Computational Intelligence: 2a edizione

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top