Teaching - 2i013

Enseignants


2i013 - Groupe 5 : Course de voiture

Algorithmes Génétiques

Pour utiliser les algorithmes génétiques, voici la base de code décrite dans le cours:

li260ag2014.zip

A mettre dans le src/li260 de votre projet. Contient:

  • le package li260.optimisation
    • classe d'algorithme génétique
    • spécification des opérateurs
    • implémentation du croisement (générique)
    • implémentation de la mutation (pour les doubles uniquement)
  • li260.tools.Pair (classe nécessaire pour faire fonctionner les AG)

Nous prenons ensuite l'exemple de l'optimisation d'un vecteur de paramètres (Double)

Etape 1: StrategyGenome

Construire une classe StrategyGenome capable de jouer une course lorsqu'un génome est fourni.

Toute la gestion de la course dépend d'un tableau de double, ici param, qui code:

  • dist secu (pour avoir des murs devant la voiture)
  • acc secu (que faire quand un mur arrive devant la voiture)
  • fact angle secu (à partir de quelle besoin de rotation je commence à freiner)
  • acc virage (je fais quoi quand je veux tourner)
  • vit limite (au dessous de quelle vitesse j'accélère toujours?)

Dans le cours, j'ai donné l'exemple (partiel) suivant:

    public Commande getCommande() {
        radar.scores();        
        double com =
          radar.thetas()[radar.getBestIndex()]/car.getBraquage();
        double turnAbs =
          Math.min(Math.abs(com), car.getMaxTurn());

        double acc = 1; // accélération par défaut
        if(RadarClassique.distInPixels(0, car, track)<param[0]) // methode static qui regarde devant la voiture
            acc = param[1];  
        else if(RadarClassique.distInPixels(
                radar.thetas()[radar.getBestIndex()], car, track)  // methode static qui regarde là où la voiture désire aller
                     < param[0]*1.5)
            acc = param[1];                    
        else if(param[2]*turnAbs < Math.abs(com)) acc = param[3];

        if(car.getVitesse() < param[4]) acc = 1;

        Commande c = new Commande(acc, turnAbs * Math.signum(com));
        return c;
    }

Etape 2: Générateur de génome

Construire une classe générant des génomes aléatoires (et implémentant l'interface adhoc)

Proposition partielle du cours:

// quatre tableaux:
// valeurs par défaut, sigma (variations), min, max
public Genome<Double> build(){
        Genome<Double> gen = new Genome<Double>(); // génome vide
        for(int i=0; i<default.length; i++){
           // parcours d'un tableau de valeurs par défaut

           // génération aléatoire gaussienne
            double d = r.nextGaussian() * defaultparamSig()[i] + defaultparam()[i];
            d = Math.min(d, StrategyRadar.paramMax()[i]); // borne
            d = Math.max(d, StrategyRadar.paramMin()[i]);
            gen.add(d);
        }
        return gen;
    }

Etape 3: Fonction d'évaluation

Construire la classe d'évaluation de la fitness (et implémentant l'interface adhoc)

Rappel de cours:

  • ATTENTION: algo de maximisation
  • Stocker le circuit (attention à ne pas relire à chaque fois)
  • Générer une voiture, une stratégie à partir du génome
  • Jouer la course
  • score =
    • si course OK : -nbCoups (ou 1./(double) nbCoups)
    • sinon : -dernierDijk -1e6 (pour être sûr d'être moins bon que les bonnes courses)

Etape 4: Main

Code donné à titre indicatif:

        String filename = "track/3_safe.trk";
        Circuit c = CircuitFactoryFromFile.build(filename);
        GenomeGenerator<Double> strGen =
          new StrategyGeneratorBasicRadarParameter();

        int populationSize = 200;
        double rate  = 0.1; // pour la mutation
        MutationOperator<Double> muteOp = new MutationOperatorImplDouble(rate, defaultparamSig());
        CrossingOperator<Double> crossOp = new CrossingOperatorImpl<Double>();
        FitnessOperator<Double> fitnessOp = new FitnessOperatorImpl(c);

        GeneticAlgorithm<Double> ga =
          new GeneticAlgorithm<Double>(populationSize, strGen,
                               muteOp, crossOp, fitnessOp);
        Genome<Double> res = ga.optimize(10);

        System.out.println("Best : "+res.getFitness());
        for(int i=0; i<res.size(); i++) System.out.print(res.get(i)+", ");
        System.out.println();