Question GA écrit en Java


J'essaie d'écrire un algorithme génétique basé sur des techniques que j'ai prises dans le livre "AI Techniques for Game Programmers", qui utilise un codage binaire et une sélection proportionnelle (aussi appelée roulette) sur les gènes de la population. générés aléatoirement dans le programme dans un tableau à deux dimensions.

Je suis récemment tombé sur un morceau de pseudocode et ont essayé de le mettre en œuvre, mais ont rencontré des problèmes avec les détails de ce que je dois faire. J'ai vérifié un certain nombre de livres et de code open source et j'ai toujours du mal à progresser. Je comprends que je dois obtenir la somme de l'aptitude totale de la population, choisir un nombre aléatoire entre la somme et zéro, alors si le nombre est supérieur aux parents pour l'écraser, mais j'ai du mal à mettre en œuvre ces idées .

Toute aide dans la mise en œuvre de ces idées serait très appréciée car mon Java est rouillé.


14
2017-10-15 21:04


origine


Réponses:


Ce qui suit est un aperçu complet de l'AG. Je me suis assuré d'être très détaillé pour pouvoir facilement le coder en 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

Notez que vous manquez actuellement une fonction de remise en forme (dépend du domaine). Le crossover serait un simple crossover à un point (puisque vous utilisez une représentation binaire). La mutation pourrait être un simple retour au hasard.


MODIFIER: J'ai implémenté le pseudocode ci-dessus en Java en tenant compte de votre structure de code et de vos notations actuelles (gardez à l'esprit que je suis plutôt un gars c / c ++ que Java). Notez que ce n'est en aucun cas l'implémentation la plus efficace ou la plus complète, j'avoue que je l'ai écrite assez rapidement:

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

49
2017-10-16 01:14



Pourquoi ne pas utiliser un framework open-source comme JGAP: http://jgap.sf.net


4
2018-02-16 15:00



J'ai implémenté cet algorithme en créant un "tableau de fitness cumulatif" et recherche binaire, Ainsi réduire le besoin d'itérer à travers chaque élément dans le tableau lors de la sélection:

  1. Pour la taille de la population N, créez une matrice de fitness cumulative: arr [N].
  2. Set arr [0]: = computeFitness (individual [0]).
  3. Ensuite, pour chaque élément suivant: X, arr [X] = arr [X-1] + computeFitness (individu [X]).
  4. Générer un nombre aléatoire compris entre 0 et arr [N] (c.-à-d. L'aptitude totale).
  5. Utilisez une recherche binaire (par exemple, Collections.binarySearch) pour localiser l'index approprié dans la matrice de fitness cumulative et utilisez cet index pour sélectionner l'individu.

Notez qu'il vous suffit de créer la matrice de remise en forme au début de la phase de reproduction, puis de la réutiliser plusieurs fois pour effectuer des sélections dans O (log N) temps.

En passant, notez que la sélection de tournois est beaucoup plus facile à mettre en œuvre!


3
2017-10-15 21:43



Le concept que vous recherchez s'appelle "la sélection de la roulette". Vous n'avez pas encore de fonction de conditionnement physique établie (vous pouvez sous-entendre que la forme physique de chaque individu est la valeur intégrale de son chromosome), mais lorsque vous effectuez un plan général, vous devez:

  1. Somme la condition physique de toute la population.
  2.  Obtenez un nombre aléatoire (appelez-le x) entre 0 et la condition physique totale.
  3.  Itérer à travers la population. Pour chaque membre:
    1.  Soustraire la condition physique du membre de x.
    2.  Si x est maintenant inférieur ou égal à zéro, sélectionnez le membre actuel.

Il existe d'autres implémentations équivalentes, mais l'idée générale est de sélectionner des membres avec une probabilité proportionnelle à leur forme physique.

Modifier: Quelques notes sur les fonctions de fitness. La représentation d'un chromosome (dans votre cas sous la forme d'un entier sur 32 bits) est indépendante de la fonction de remise en forme utilisée pour l'évaluer. Par exemple, les codages binaires traitent typiquement le chromosome comme un ensemble de champs de bits empaquetés dans une valeur intégrale de taille appropriée. Le croisement et la mutation peuvent alors être réalisés par les opérations de masquage de bits appropriées. Si vous êtes intéressé, je peux poster du code GA simple que j'ai autour de vous (en C et Python) qui utilise des opérations binaires pour implémenter ces fonctions. Je ne sais pas si vous êtes à l'aise avec ces langues.


1
2017-10-15 21:14



J'ai réalisé une implémentation extensible en Java, dans laquelle les opérateurs et la structure individuelle sont bien définis par des interfaces qui fonctionnent ensemble. Github repo ici https://github.com/juanmf/ga 

Il a une implémentation standard pour chaque opérateur et un exemple de mise en œuvre de problème avec une structure individuelle / de population particulière et un compteur de fitness. L'exemple de problème d'implémentation consiste à trouver une bonne équipe de football avec des joueurs parmi 20 équipes et une restriction budgétaire.

Pour l'adapter à votre problème actuel, vous devez fournir des implémentations de ces interfaces:

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;

Dans pkg juanmf.grandt Vous disposez des exemples de classes d'implémentation de problèmes et de leur publication, comme illustré dans l'extrait de code ci-dessous.

Pour publier vos implémentations, il vous suffit de renvoyer les classes appropriées depuis ce fichier Spring Beans:

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

L'opérateur de crosser a deux implémentations pour la même technique, l'une séquentielle et l'autre concurrente qui surpasse de loin la séquence.

La condition d'arrêt peut être spécifiée. Si aucune n'est donnée, il y a une condition d'arrêt par défaut qui s'arrête après 100 générations sans amélioration (vous devez faire attention avec l'élitiste, ne pas perdre le meilleur de chaque génération pour déclencher efficacement cette condition d'arrêt).

Donc, si quelqu'un est prêt à essayer, je serais heureux de vous aider. N'importe qui est invité à proposer des suggestions, mais encore mieux à mettre en œuvre l'opérateur: D ou toute demande de tirage améliorée.


1
2017-09-28 14:06



Ces autres questions sur la sélection de la roulette devraient vous aider:

Dans le premier, J'ai essayé d'expliquer comment fonctionne la roulette. Dans la seconde, Jarod Elliott a fourni un pseudo-code. Combiné avec La description d'Adamski d'une implémentation efficace, cela devrait suffire à faire fonctionner quelque chose.


0
2017-10-16 00:17



Juste un point qui mérite d'être mentionné. La sélection de la roulette (comme indiqué dans le pseudo-code) ne fonctionnera pas pour les problèmes de minimisation - elle est cependant valable pour les problèmes de maximisation.

En raison de la manière dont l'individu le plus adapté est sélectionné, le cas de minimisation ne sera pas maintenu. Les détails sont fournis dans: Intelligence informatique: 2e édition


0
2018-02-13 06:44