PROGRAMMATION D´ALGORITHMES GÉNÉTIQUES SIMPLES

Principe
Codage
Structures de données
Organisation du programme
Reproduction
Croisement
Mutation

Principe

         La programmation des algorithmes génétiques simples est aisée à mettre en oeuvre, elle ne nécessite en effet qu´un traitement élémentaire de chaînes de caractères. Le seul véritable problème étant celui du codage (il est important de se rappeler qu´un algorithme génétique travaille sur un codage des paramètres et non pas sur les paramètres eux-mêmes). Nous détaillerons successivement:
         Le codage.
         Les tructures de données.
         La reproduction.
         Le croisement.
         Et la mutation.

Codage

Il s´agit de convertir en chaînes de longueur fixe, prises dans un alphabet fini, les paramètres d´un problème d´optimisation.

         Premier exemple
         Deuxième exemple
         Autres codages
         Principes de base

Premier exemple

         Soit une boîte noire munie de 4 interrupteurs délivrant un signal de sortie f(s) pour chaque configuration binaire de ces interrupteurs. Ainsi s=(0,0,1,0) signifie que l´interrupteur numéro 3 est ouvert et que les autres sont fermés. Le problème est de trouver la configuration maximisant la fonction f.
         Bien entendu, dans ce cas simple, la solution est une méthode énumérative, mais nous montrons comment un algorithme génétique peut résoudre ce problème alors même que l´ensemble de définition de f serait inexploitable (par sa taille) ou que la fonction f ne serait pas exactement définie (imprécisions, valeurs fluctuantes ou aléatoires).
         Un codage simple consiste:
         À prendre l´alphabet binaire {0,1}
         À coder chaque configuration des 4 interrupteurs en une chaîne binaire de longueur 4 (0 signifie fermé et 1 signifie ouvert).

Figure 4-1: Boite noire

         La suite se déroule alors comme il a été expliqué au chapitre 2:
         1) Choix d´une population initiale aléatoire.
         2) Reproduction par tirage aléatoire d´individus avec une probabilité proportionnelle à leur évaluation par la fonction f.
         3) Croisement de paires de tels individus.
         4) Mutations éventuelles.
         5) Recommencer (c´est à dire retourner en 2) tant qu´une amélioration est constatée.

Deuxième exemple

Dans l´exemple décrit en 2-2, optimisation de la fonction f(x) = x² définie sur l´ensemble [0,31], on a vu qu´un codage simple consistait à construire des chaînes binaires de longueur 5 (puisque 5 bits suffisent à représenter les entiers de 0 a 31). Une méthode indirecte ou une méthode énumerative sont les plus simples, mais nous appliquons un algorithme génétique dans un but purement didactique.

Figure 4-2: Optimisation de f(x) = x² sur [0,32[

Autres codages

         Tous les problèmes ne se ramènent pas aussi aisément à une description binaire, en particulier les paramètres peuvent être des nombres réels. Il peut être tantant de représenter chacun d´eux par un gène, sans se soucier du nombre d´allèles nécessaires au codage. Ainsi, un individu pourrait être constitué d´une chaîne de 100 paramètres réels, les opérateurs de croisement et de mutation travaillant alors sur ces nombres, ce qui exige un alphabet de grande taille. Bien qu´il soit possible de coder un float sur 32 bits, et donc un paramètre sur une chaîne de longueur 32, le fait de maintenir une signification attachée à un gène nuit au bon fonctionnement de l´algorithme génétique. En effet, un des atouts de ces algorithmes, est qu´ils sont aveugles (c´est à dire qu´ils ne font aucune hypothèse de départ), et qu´ils codent le problème de façon abstraite et arbitraire. Il n´y a donc aucune raison pour conserver, dans le codage, la séparation des paramètres du problème.
         Il est toujours possible de projeter l´ensemble de variation d´un paramètre [p1,p2] sur un intervalle [0,2^l] dont chaque élément se code sur l bits: Si p appartient à l´intervalle [p1,p2] alors (2^l-1)*(p-p1)/(p2-p1) appartient à l´intervalle [0,2^l]. La précision du codage est: (p2-p1)/(2^l-1). Pour coder plusieurs paramètres on peut tout simplement concaténer les codages de chacun d´entre eux, avec des longueurs différentes. Cette méthode est le codage multiparamètre à bornes fixes [GOLDBERG 1991] qui est en fait une discrétisation des paramètres réels.
         Certains problèmes, outre la fonction à optimiser, exigent que soient satisfaites un certain nombre de contraintes. On fait appel, pour les résoudre, à la méthode de pénalisation: Il s´agit d´associer un coût aux dépassements des contraintes, puis d´inclure ce coût dans la fonction d´évaluation. Par exemple dans une population d´animats censés apprendre à se déplacer, si on les contraint à garder une direction constante d = (dx,dy,dz), on peut ajouter à la fonction d´évaluation (qui est par exemple la distance parcourue) une pénalité proportionnelle à l´angle de la vitesse v de l´individu avec cette direction:
         f = (distance parcourue) + k * angle(v,d), avec k < 0

Principes de base

Goldberg conseille l´observation des principes suivants:

Le codage doit satisfaire le théorème fondamental des algorithmes génétiques, c´est à dire que les schèmes courts et d´ordres petits soient pertinents pour le problème et le plus indépendants possible des schèmes complémentaires (aux autres positions instanciées).

Dans la pratique il peut être difficile de déterminer de tels schèmes, mais on peut toujours calculer les longueurs et les ordres des schèmes et revoir le codage de façon à les minimiser.

Un alphabet de taille minimale est toujours préférable.

En effet, un alphabet de grande taille réduit considérablement l´effet du parallélisme implicite.
Bien que cela ne soit pas absolument nécessaire, il sera toujours possible de ramener un codage à des chaînes binaires.

Structures de données

         Soit une population de N individus et f la fonction à optimiser.
         Chaque individu est défini par:
                  Son indice permettant de le repérer dans la population.
                  Son génotype sous la forme d´une chaîne de L bits choisis dans un alphabet Alpha de Na éléments. Nous supposerons que les codes ASCII des éléments de Alpha sont consécutifs et croissants depuis Alpha[0] jusqu´à Alpha[Na-1].
                  Son phénotype (paramètre décodé): phen.
                  Sa valeur d´adaptation: adapt = f(phen).
                  En langage C il est commode de définir un type Ind et deux tableaux Pop1 et Pop2 de N individus au maximum:


typedef struct {

        
    long ind;

        
    char gen[L];

        
    long phen;

        
    long adapt;

        
    } Ind;

Ind Pop1[N], Pop2[N];
Le premier tableau contient la population initiale (ou première génération) et le deuxième tableau contient la deuxième génération, puis le premier tableau est utilisé pour calculer la troisième génération et le deuxième tableau pour calculer la quatrième génération, et ainsi de suite.

Organisation du programme

         Déclarations et initialisations
         Générations successives
         Utilitaires

Déclarations et initialisations

Saisie du nombre d´individus d´une population, de l´alphabet Alpha et de la longueur des génotypes. Réservation des tableuax Pop1 et Pop2.
Initialisation aléatoire des génotypes des individus de la population initiale Pop1:


for(i=0;i < N; i++)

        
    {

        
    pc = (Pop1 + i)->gen;

        
    for (j = 0; j < L; j++)

        
        
        pc[j] = rnd(Alpha[0], Alpha[Na-1] + 1);

        
    }

Où rnd(v1,v2) retourne un entier de l´intervalle [v1,v2[ (voir 4-4-3).

Générations successives

         Les deux tableaux Pop1 et Pop2 sont utilisés alternativement pour générer la population à l´instant t+1 en fonction de celle à l´instant t. À chaque génération les individus sont évalués et si leurs adaptations sont satisfaisantes le processus est stoppé.
         Sinon les individus sont sélectionnés aléatoirement au moyen d´une roue de loterie biaisée, c´est à dire avec une probabilite proportionnelle à leur adaptation (fonction reproduction()).
         Les individus sélectionnés sont alors appariés et croisés. Pour cela un point de croisement est choisi aléatoirement entre 0 et L-1 permettant la construction de deux autres génotypes par mélange des matériels génétiques (fonction croisement()).

Figure 4-3: Croisement

Des mutations de faible probabilité (de l´ordre de 1/1000) sont appliquées lors du croisement (fonction mutation()).
Un compteur permet de sortir de la boucle de génération au cas où l´optimum ne pourrait pas être atteint.

Utilitaires

Fonction de base retournant un aléatoire de l´intervalle [0.0,1.0[:
double drand48();
Fonction retournant un booleen vrai avec une probabilité p (utilisée pour décider de croiser ou non deux individus):


long flip(float p)


{


return((drand48() <= p) ? 1 : 0);


}

Fonction retournant un entier de l´intervalle v1, v2 (utilisée pour choisir un point de coupure lors d´un croisement):


long rnd(long v1, long v2)


{


return((long) (drand48() * (v2 - v1) + v1));


}

Fonction retournant la somme des adaptations de tous les individus de la population pop (utilisée pour sélectionner des individus par une probabilité biaisée par son adaptation: voir la fonction reproduction()):


long Somme(Ind *pop)


{


long S = 0, i;



for (i = 0; i < N; i++)
    S += (pop + i)->adapt;


return(S);


}

Reproduction

La fonction reproduction() retourne l´indice d´un individu de la population pop en fonction de son adaptation et de la somme S des adaptations de la population:


reproduction(Ind *pop)


{


static long inc = 0;


long i, v;



v = S * drand48();
for (i = 0; i < N; i++)

        
    {

        
    if ((++inc >= N) inc = 0;

        
    if ((pop + inc)->adapt > v) return(inc);

        
    }


return(N - 1);


}

Croisement

La fonction croisement(i1, i2, i3, i4, pop) calcule les génotypes de deux individus d´indices i3 et i4 obtenus par croisement de deux individus d´indices i1 et i2 dans la population pop:


void croisement(long i1, long i2, long i3, long i4, Ind *pop)


{


char *pc1, *pc2, *pc3, *pc4;


long coup, i;



pc1 = (pop + i1)->chaine; pc2 = (pop + i2)->chaine;


pc3 = (pop + i3)->chaine; pc4 = (pop + i24->chaine;


coup = rnd(0, 4);


for (i = 0; i < coup; i++)

        
    {pc3[i] = pc1[i];pc4[i] = pc2[i];}


for (i = coup; i < L; i++)

        
    {pc3[i] = pc2[i];pc4[i] = pc1[i];}


}

Remarquons q´une coupure plus complexe peut être effectuée en choisissant plusieurs points:

Figure 4-4: Croisement à plusieurs points de coupures.

Mutation

La fonction mutation(ind) mute un élément du génotype de l´individu d´indice ind de la population pop avec la probabilité 1/1000.


void mutation(long ind, Ind *pop)


{

      
	char *pc;



      
	if(flip(0.001))

       
	{

              
		pc = (pop + ind)->chaine + rnd(0, 4);

              
		*pc = rnd(Alpha[0], Alpha[Na-1]);

       
	}


}