PROGRAMMATION GÉNÉTIQUE


Principe
Populations de programmes

















































Principe


         Algorithmes génétiques et programmation génétique

         S_expressions et arbres

Algorithmes génétiques et programmation génétique

         Les algorithmes génétiques sont une méthode d´optimisation de type évolutionniste consistant à coder des solutions potentielles d´un problème en chaînes de longueur fixe. Une population de telles chaînes est évaluée par une fonction d´adaptation mesurant la plus ou moins grande capacité de ces solutions à résoudre le problème. À chaque génération des individus sont sélectionnés aléatoirement avec une probabilité proportionnelle à leur valeur d´adaptation, cette opération de reproduction favorise les individus les mieux adaptés. De nouvelles chaînes sont créées par croisement de paires d´individus sélectionnés ce qui a pour effet d´enrichir leur patrimoine génétique. Des mutations aléatoires introduisent des erreurs autorisant de nouvelles potentialités.
         Cette méthode s´est montrée étonamment efficace dans la recherche de l´extremum global de certains problèmes d´optimisation, en particulier ceux qui sont hautement non linéaires ou ceux qui présentent des interactions couplées compliquées de paramètres.
         Cependant la complexité d´une solution optimale à un problème donné n´est pas connue à l´avance. En ne fixant pas à priori la longueur des chaînes, cette complexité peut évoluer au cours de la reproduction.
         Plus précisément, la programmation génétique opère sur des chaînes de longueurs variables représentant des programmes plutôt qu´un codage par caractères. La population initiale est un ensemble de programmes censés résoudre le problème posé, et la fonction d´adaptation mesure la plus ou moins grande capacité de ces programmes à trouver de bonnes solutions.
         Le langage LISP a la particularité de représenter, aussi bien le code que les structures de données, sous formes d´arbres. La programmation génétique consiste à faire évoluer des populations de tels arbres, elle est donc facilement implémentable en LISP. Cependant rien n´empêche d´utiliser un autre langage (C ou C++ par exemple).

S_expressions et arbres

         Les objets de base manipulés par le LISP sont les atomes et les listes. Les atomes peuvent être soit des symboles, soit des nombres, une liste est une suite ordonnée d´objets encadrés par des parenthèses, par exemple:
         (ceci est une liste)
         Une forme est une liste particulière dont le premier terme est le nom d´une fonction et les termes suivants sont les paramètres d´appel de cette fonction. Par exemple:
         (+ 3 5) retourne la valeur de la fonction PLUS appliquée aux deux nombres 3 et 5, c´est à dire 8.
         Un programme LISP n´est rien d´autre qu´une forme.
         Une forme, ou S-expression se représente par un arbre, exemples:


Figure 5-1: S-expressions et arbres associés.


         Dans un tel arbre on distingue deux types de noeuds:
         1) Les feuilles, ou noeuds terminaux qui sont soit des constantes, soit des variables, soit encore des fonctions sans arguments.
         2) Les autres noeuds sont toujours des fonctions ayant au moins un argument.
        

Populations de programmes


         Population initiale

         Mesure d´adaptation

         Reproduction

         Croisement

         Permutation

         Encapsulation

         Contraction

         Mutation

Population initiale

         Une population initiale de programmes est générée aléatoirement sous la forme d´arbres construits de la façon suivante:
         On suppose donnés:
                  1) Un ensemble de fonctions {fi(arg1,arg2,...,argni)}0 <= i <= n
                  2) Un ensemble d´éléments terminaux {t1,t2,...,tm)}0 <= i <= m
         On définit une construction récursive de l´arbre à partir de la racine en choisissant d´abord aléatoirement une fonction, si celle-ci prend n arguments, il y aura n branches partant de la racine.
         Pour chaque branche recommencer récursivement l´opération.
         La construction cesse dès qu´est tirée une feuille, ou dès que la profondeur de récursion atteint une limite donnée, auquel cas le choix est restreint à une feuille.
Exemple:
         L´ensemble des fonctions est: {+(arg1,arg2),*(arg1,arg2)}
         L´ensemble des éléments terminaux est {3,x,y}
         Le premier tirage aléatoire d´une fonction donne ´+´ pour la racine, ayant deux arguments.
                  Le choix pour la première branche est la constante 3 qui, n´ayant pas d´argument, termine le développement de cette branche.
                  Le choix pour la deuxième branche est la fonction ´*´ ayant deux arguments.
                           Le choix pour la première branche est la variable x qui, n´ayant pas d´argument, termine le développement de cette branche.
                           Le choix pour la deuxième branche est la variable y qui, n´ayant pas d´argument, termine le développement de cette branche.


Figure 5-2: Construction d´un arbre aléatoire.


         C´est la méthode de croissance [KOZA 1994].
         Dans la méthode dite complète tous les noeuds d´ordre maximum sont terminaux, tous les autres étant des fonctions.
         Une autre méthode intermédiaire consiste à générer le même nombre d´arbres de profondeurs comprises entre 2 et un maximum n, et, pour chaque profondeur, la moitié des arbres sont créés par la méthode de croissance et l´autre moitié par la méthode complète: Cette méthode assure la plus grande variété possible de formes et de tailles des arbres et améliore la convergence de l´algorithme.
         Koza propose aussi d´utiliser, outre les constantes et les variables, un troisième type d´éléments terminaux: Les constantes aléatoires éphémères dont la valeur est tirée aléatoirement.

Mesure d´adaptation

         La fonction d´adaptation, appliquée à un individu de la population, retourne une valeurs appelée adaptation brute fb de cet individu, le problème consiste à minimiser cette fonction. L´adaptation standardisée fs est une mesure d´adaptation telle que plus d´individus bien adaptés ont une plus petite adaptation standardisée que les individus moins bien adaptés. Un individu parfaitement optimal doit avoir une adaptation normalisée nulle. L´adaptation brute est parfois égale à l´adaptation standardisée, mais il peut être nécessaire de définir une transformation de l´adaptation brute en adaptation standardisée afin de satisfaire la définition ci-dessus.
         L´adaptation ajustée fa est définie par rapport à l´adaptation standardisée:
                  fa = 1 / (1 + fs)
         L´adaptation normalisée fn est définie par:
                 



Reproduction

         Des individus sont sélectionnés avec une probabilité proportionnelle à leur adaptation normalisée.
         Dans l´adaptation proportionnelle le meilleur remplace le pire (sélectionné par l´inverse de la fonction d´adaptation).
         Dans la sélection compétitive les programmes sont tirés aléatoirement par paquets (par exemple par groupes de 5), dans chaque paquet le meilleur remplace le pire.
         Les individus sélectionnés sont ensuite appariés puis croisés, permutés, encapsulés, contractés et éventuellement mutés.

Croisement

         Un noeud est tiré aléatoirement sur chacun des arbres d´une paire sélectionnée, puis les sous arbres ayant ce noeud pour racine sont échangés. Exemple:


Figure 5-3: Programmes sélectionnés


Figure 5-4: Programmes croisés


Permutation

         Un noeud de fonction est tiré aléatoirement et l´ordre des arguments de la fonction sont permutés aléatoirement. Par exemple si f(a1,a2,a3) est un tel noeud, il peut devenir:
         f(a1,a2,a3) ou f(a1,a3,a2) ou f(a2,a1,a3) ou f(a2,a3,a1) ou f(a3,a1,a2) ou f(a3,a2,a1).

Encapsulation

         Un noeud est tiré aléatoirement et le sous arbre ayant ce noeud pour racine est remplacé par une fonction sans argument. Lorsque celle-ci est appelée, le sous arbre est évalué. Le but de l´encapsulation est de conserver des sous arbres utiles lors de l´opération de croisement.

Contraction

         Un noeud est tiré aléatoirement et prend la place de son père. Cet opérateur a pour but de réduire la taille des arbres qui peut augmenter considérablement lors de l´évolution de la population.

Mutation

         Un noeud est tiré aléatoirement sur un arbre, le sous arbre ayant ce noeud pour racine est remplacé par un sous arbre généré aléatoirement. Exemple:


Figure 5-5: Mutation d´un programme