Previous Next Contents

Chapter 2    Méthodes et problèmes

Introduction

Nous allons dans ce chapitre nous intéresser à un certain nombre de problèmes classiques pouvant être résolus par algorithmes génétiques, et nous allons nous efforcer de comparer les algorithmes génétiques, quand cela est possible, à d'autres méthodes également applicables.

2.1  Optimisation de fonctions à variables réelles

Dans cette section, nous allons étudier le fonctionnement des AG pour l'optimisation de fonctions à variables réelles et les comparer à d'autres méthodes, soit locales (simplex [NM65, JKP72], BFGS [Bro69, Fle70, Gol70, DS83]), soit globales (programmation par intervalles [Han92, RR95], recuit [AK89, Egl92, Ing89]). Certaines de ces fonctions ont été déjà étudiées par Lester Ingber [IR92b], afin de mesurer les efficacités respectives des algorithmes génétiques et du recuit simulé (variante VFSR1 (ou ASA2 )). Ingber avait utilisé un algorithme génétique classique, GAUCSD [SG91], qui travaillait avec les traditionnelles chaînes de bits.

Nous sommes conscients que le grand absent de cette section est le branch and bound stochastique, mais nous ne disposions pas des compétences suffisantes pour tester cette méthode.

Enfin, il faut également remarquer la difficulté qu'il y a à comparer deux méthodes d'optimisation. Nous avons choisi comme indicateur le nombre d'évaluations de la fonction, Il est clair cependant que certains algorithmes peuvent calculer moins de fois la fonction à optimiser, tout en étant plus lents a l'exécution. Notons tout de même qu'en ce qui concerne BFGS, chaque appel à la fonction pour estimer le gradient est considéré comme un appel de fonction à part entière, et comptabilisé comme tel. Cela désavantage BFGS sur les fonctions pour lesquelles le gradient peut être estimé directement.

2.1.1  Fonction de Rosenbrock et Chebyquad

Nous allons nous intéresser à la minimisation de la fonction :
f2(x,y)=100 (x2-y)2+(1-x)2
sur l'intervalle [-2,2].

Cette fonction peut être optimisée par des méthodes classiques. Une étude élémentaire (dérivées partielles) montre qu'il existe un seul minimum, le point (1,1) et que la valeur du minimum en ce point est 0. D'autre part, notre algorithme de simplex donne une solution à 10-6 en un nombre réduit d'évaluations de fonction, en partant d'un point quelconque de l'espace de recherche.

La fonction est assez difficile à optimiser : le premier terme de la fonction définit une quadrique dont les bords sont très abrupts, dont le fond est plat, défini par la parabole y=x2. C'est sur cette courbe qu'il faut ensuite optimiser le second terme, sachant que toute petite perturbation de x entraîne immédiatement une forte variation du premier terme si y ne varie pas simultanément pour que le point (x,y) reste sur la parabole y=x2. La figure 2.1 permet de mieux comprendre le phénomène.


Figure 2.1: Fonction de Rosenbrock
On a représenté sur la figure 2.1 (à droite) l'évolution de la valeur de f2 en fonction du nombre d'évaluations effectuées par l'algorithme génétique avec mutation adaptative et sans mutation adaptative, ainsi que du recuit simulé (VFSR), d'un algorithme de simplex (Nelder-Mead), de la méthode BFGS et d'une arithmétique des intervalles. L'échelle est logarithmique sur les deux axes. On a utilisé un croisement barycentrique et une mutation sous forme de bruit gaussien pour l'algorithme génétique. On constate que l'algorithme génétique utilisant la mutation adaptative obtient des résultats bien supérieurs à ceux de l'algorithme génétique standard. Les paramètres de VFSR ont été ``adaptés'' de façon à donner un résultat aussi bon que possible.

Si l'on utilise la programmation par intervalle, les résultats sont excellents en terme d'itérations. L'algorithme trouve l'optimum à 10-16 près avec 901 itérations pour la fonction f(x) et 1803 itérations pour la fonction F(X). Cependant, il faut nuancer ce résultat. En effet, le calcul d'une itération de la fonction F(X) (qui calcule l'image d'un intervalle) est environ 25 fois plus longue que le calcul d'une itération de f(x). Nous avons donc représenté sur la figure 2.1 le résultat de (25*IterFX+Iterfx) et non la somme du nombre des itérations. Il est clair qu'un meilleure implantation de l'arithmétique des intervalles permettrait d'améliorer considérablement les résultats.

Pour conclure notons que :

2.1.2  Fonction de De Jong

L'optimisation de la fonction f5 de DeJong [DeJ75] est un des exemples les plus classiques de l'optimisation globale. Cette fonction a la forme suivante :
f5(x1,x2)=
1
500+
25
S
j=1
1
j+
2
S
i=1
(xi-aji)6
aj1={-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,
  0,16,32,-32,-16,0,16,32,-32,-16,0,16,32}
aj2={-32,-32,-32,-32,-32,-16,-16,-16,-16,-16,
  0,0,0,0,0,16,16,16,16,16,32,32,32,32,32}

Nous présentons sur la figure 2.2 la forme de cette fonction ainsi que les résultats obtenus par l'algorithme génétique avec et sans (clustering+sharing). Sur la partie gauche de la figure, on représente la convergence vers l'optimum en format log/log, avec en abscisse le logarithme du nombre d'évaluations, et en ordonnée le logarithme de l'écart à l'optimum. Le clustering améliore les performances, car il permet de maintenir une meilleure diversité de population et sort rapidement l'algorithme d'un optimum local.


Figure 2.2: Fonction de DeJong
La convergence est réalisé en moyenne en 1500 évaluations de fonctions avec le clustering. Les résultats sont très proches de ceux obtenus par VFSR [IR92b].

A ce sujet, on peut rapidement rappeler les résultats présentés par David Fogel dans [Fog95]. Les résultats de notre AG sont meilleurs que ceux obtenus par Fogel avec un mécanisme dit d' ``Evolutionary Computation3 ''. Au demeurant, l'ensemble des résultats présentés par Fogel à l'appui de sa thèse (l' ``Evolutionary Computation'' est supérieur aux mécanismes génétiques standard) est plus que discutables. Il nous a été possible en effet d'obtenir sur l'ensemble des fonctions de test qu'il présente de meilleurs résultats que ses algorithmes. En ne prenant en compte que des algorithmes génétiques binaires primitifs, et non des algorithmes à codage réel qu'il semble mal connaître, il commet une erreur qui fausse totalement sa présentation. D'autre part, les fonctions de test qu'ils utilisent ne présentent que peu, ou pas du tout, d'intérêt sur le plan de l'optimisation globale : elles sont bien trop simples (de même d'ailleurs que la fonction de De Jong).

2.1.3  Fonction de Corana

Cette fonction est présentée en détail dans [CMMR87]. Nous en utilisons ici la restriction que présente Ingber. On doit optimiser la fonction sur le compact [-10000,10000]N.
f0(x1,...,xN)=
N
S
i=1
 ì
í
î
0.15   di (0.05  S(zi)+zi)2si |xi-zi|<0.05
di   xi2sinon
zi=0.2   ë |xi/0.2|+0.49999û  S(xi)
S(zi)=
ì
í
î
1si zi>0
0si zi=0
-1si zi<0
d
 
i mod 4
={1.0,1000.0,10.0,100.0}
Cette fonction est intéressante à plus d'un titre. D'une part, elle présente la propriété d'avoir 105N optima locaux. Pour N=4, cela signifie déjà qu'un algorithme utilisant un millième de second pour parcourir chaque minimum mettrait un temps supérieur à l'âge de l'univers pour trouver l'optimum global (tous les points du compact [-0.05,0.05]N sont optimaux). D'autre part cette fonction est, pour L. Ingber, un des meilleurs tests possibles pour un algorithme d'optimisation global. Il nous a donc semblé intéressant de nous mesurer à VFSR sur cet exemple.


Figure 2.3: Fonction de Corana représenté pour N=2 (à gauche). Résultats de convergence pour N=12 (à droite)
La figure 2.3 représente la fonction pour N=2. Il faut noter que pour les deux algorithmes concernés, la convergence ne présente aucune difficulté pour N=4 et N=8. A partir de N=12, le problème devient plus difficile. Les paramètres par défaut de VFSR ne permettent pas de faire converger l'algorithme simplement.

Avec l'aide de L. Ingber, il nous a été possible de trouver un ensemble de paramètres faisant converger VFSR. Il s'agit en fait d'utiliser une technique particulière, le ``Quenching'' qui consiste à accélérer le schéma de recuit, au risque de tomber d'ailleurs dans un optimum local. Sur 10 tests faits avec VFSR, 5 d'entre eux trouvent la solution optimale et 5 restent bloqués dans un optimum local. L'algorithme génétique trouve toujours la meilleure solution avec une population de 400 éléments. En revanche, lorsqu'il converge, l'algorithme de recuit est nettement plus rapide que l'algorithme génétique (voir figure 2.3 un exemple nominal de convergence des deux algorithmes).

Nous avons alors décidé d'augmenter la valeur de N pour observer le comportement de chacun des deux algorithmes lorsque le problème se durcit. Pour l'algorithme génétique, il suffit d'augmenter le nombre d'éléments de population jusqu'à ce que l'algorithme converge. La limite avec l'AG classique se trouve autour de N=24. Nous ne sommes pas parvenus à faire converger VFSR pour N=20.

La fonction de Corana étant complètement séparée, il est intéressant de lui appliquer la méthode d'optimisation pour les fonctions partiellement séparables mise au point par Nicolas Durand présentée dans la section 1.4.1. Pour appliquer l'AG avec les opérateurs adaptés, on définit trivialement la fitness locale comme suit :
G(xi)=
ì
í
î
0.15   di (0.05  S(zi)+zi)2     si |xi-zi|<0.05
di   xi2     sinon

Puisque la fonction est totalement séparée, on pouvait s'attendre à ce que l'opérateur adapté se révèle particulièrement efficace, ce que confirment les tests : avec une population de 400 éléments sur 100 tests, l'AG utilisant le croisement adapté trouve toujours le minimum global avant la génération 100 pour N=1000.

Enfin, nous avons également testé la programmation par intervalle.
 Appels à fAppels à F
N=13163
N=2440881
N=317553511
N=449799959
N=53899477989
N=65251931050387


Table 2.1: Programmation par intervalles appliquée à la fonction de Corana
Les résultats sont présentés sur le tableau 2.1. On remarque que l'on ne peut trouver de solution pour N>6, en raison de l'occupation mémoire. En fait, la fonction de Corana est très mal adaptée à la programmation par intervalles, car elle présente de nombreux plateaux. Ces plateaux peuvent être subdivisés en de nombreux intervalles pour lesquels les bornes de la fonction sont les mêmes. Cela provoque une explosion du nombre d'intervalles que l'estimateur ne parvient pas à ``couper''.

2.1.4  Fonction de Griewank

Cette fonction ressemble à la précédente mais présente une difficulté supplémentaire : elle n'est pas séparable. En revanche, elle ne présente pas de plateaux, ce qui la rend beaucoup plus facile pour la programmation par intervalles.

La fonction de Griewank est définie comme suit :
F(x1,..,xn)=
1
4000
n
S
i=1
xi 2-
n
P
i=1
cos(
xi
((i)(1/2)
)

Nous nous intéresserons ici au cas n=10. Cette fonction n'est pas représentable facilement mais on peut par exemple tracer F(x+y,x+y,...x+y) pour x variant entre -P et P et y variant entre -20 et 20 (voir figure 2.4). On observe alors sur cette coupe que le minimum de la fonction concernée se situe en 0, mais que la fonction a de nombreux minima locaux proches et éloignés de 0.



Figure 2.4: F(x+y,x+y,...x+y) pour x Î [-P,P] et yÎ[-20,20] et valeur moyenne de la meilleure fitness en fonction de la génération courante
Nous allons montrer sur cet exemple combien l'utilisation d'une fitness locale peut être utile, bien que la fonction ne soit pas complètement séparable. On définit la fitness locale comme suit :
G(x1,..,x10)=
1
4000
 xi 2-
10
P
i=1
cos(
xi
((i)(1/2)
)

On effectue alors 4 séries de tests : Dans chaque cas, l'algorithme génétique est testé une centaine de fois avec 600 générations et 100 individus (qui représente environ 36000 évaluations de fonction). On dit que l'algorithme génétique a convergé lorsqu'il a trouvé une solution, qui, par une méthode locale simple, permet d'atteindre l'optimum global. On peut d'ailleurs souligner ici l'importance de l'association AG/méthodes locales qui permet seule de trouver l'optimum de la fonction.

Le tableau 2.2 donne le nombre minimal, maximal et moyen de générations nécessaires pour que l'algorithme génétique converge. Le tableau donne également l'écart-type de ce nombre de générations ainsi que la distance moyenne (en norme infinie) de la solution optimale trouvée à la solution optimale absolue, (0).
type de croisementminmaxmoysdist à 0
classique76294179.44178.470.00
adapté4220492.3391.812.03
classique avec sharing79357248.87247.320.06
adapté avec sharing4218696.5795.950.01


Table 2.2: 600 générations et 100 éléments de population
Les résultats ci-dessus montrent que la convergence de l'algorithme est 2 fois plus rapide avec le croisement adapté qu'avec un croisement classique. On observe également que le sharing ralentit légèrement la convergence de l'algorithme quel que soit le croisement utilisé. Ainsi, l'intérêt de l'opérateur de sharing n'est pas évident dans ce cas. Cependant, les performances de l'algorithme ne sont pas dégradées par l'opérateur de sharing lorsque le croisement adapté est utilisé. On observe même que l'opérateur de sharing permet d'obtenir une solution après convergence proche de 0 alors que sans l'opérateur de sharing, la meilleure solution après convergence reste éloignée de 0.

La figure 2.4 donne les valeurs moyennes des meilleures fitness suivant les 4 tests. Cette figure confirme le bon comportement de l'opérateur adapté avec sharing.

Dans chacune de ces 4 séries de tests, il est possible d'observer l'effet du croisement de la façon suivante : à chaque génération, on effectue 60 croisements, parmi ceux-ci, certains donnent soit un individu optimal (au sens défini précédemment), soit un individu acceptable, soit un individu qui sera immédiatement rejeté. Les courbes , , 2.6 et 2.6 donnent les répartitions de ces catégories pour un test extrait de chacune des 4 séries de tests.



Figure 2.5: Croisement classique et croisement adapté avec sharing
On observe sur les 4 figures que lorsque l'algorithme génère des solutions optimales, il génère également des solution rejetées (tellement mauvaises que l'opérateur de sélection ne les conserve pas). C'est la difficulté de ce problème (les solutions optimales sont proches de solutions très mauvaises). On observe sur la figure que l'opérateur de croisement adapté génère un nombre très important de solutions rejetées. Il est intéressant de constater que l'opérateur de sharing permet d'atténuer cet effet.

Des tests ont été effectués avec VFSR. Nous ne sommes pas parvenus à faire converger le recuit, qui tombe systématiquement dans un minimum local. Il est possible que notre maîtrise de VFSR soit insuffisante pour arriver au résultat. Cependant, du fait que les résultats que nous sommes parvenus à obtenir avec VFSR pour les trois fonctions précédentes sont proches de ceux présentés par Ingber, nous pensons fortement que la fonction de Griewank est difficile à optimiser pour un algorithme de recuit simulé.



Figure 2.6: Convergence d'une méthode par intervalles sur la fonction de Griewank
La programmation par intervalle, en revanche, parvient à résoudre le problème avec une précision de 10-5 en 180026 évaluation de fonction pour f(x) et 360053 évaluations pour F(X). Il faut noter qu'il n'y a là aucun besoin d'appliquer une méthode locale en fin de convergence. Les résultats sont donc réellement intéressants.

Dans le cas présent, une évaluation de F(X) est équivalente (en temps) à 10 évaluations de f(x). On a représenté sur la figure 2.7 l'évolution de la valeur de f en fonction de (10*IterFX+Iterfx), les échelles étant là encore logarithmiques sur les deux axes.

2.2  Problèmes de type combinatoire

On peut appliquer les algorithmes génétiques sur les problèmes purement combinatoires, tels les problèmes SAT ou CSP [DS89, HD94], ainsi qu'au classique problème d'optimisation combinatoire qu'est le voyageur de commerce. C'est cet exemple que nous présentons ici. Notons cependant, avant de présenter cet exemple, que nous avons également testé les algorithmes génétiques sur des problèmes de satisfaction de contraintes purs, comme le classique problème du zèbre. Les résultats [Hue94] montrent que les méthodes ``classiques'' de satisfaction de contraintes restent plus efficaces que les AG.

2.2.1  Codage des données

Le problème du voyageur de commerce peut se coder de diverses façons, tenant compte des positions respectives des villes les unes par rapport aux autres ou non. Avec les méthodes de croisement classiques à un ou plusieurs points l'ordre dans lequel les villes sont codées a une influence sur la convergence. Pour notre algorithme, cet ordre n'a aucune importance. Les données seront donc codées sous forme d'une liste d'entiers représentant l'indice de la ville suivante. Ainsi le code bcdea représente le chemin abcdea. Pour faciliter l'utilisation des divers opérateurs, nous aurons besoin de connaître le prédécesseur de la ville dans laquelle on se trouve. Pour éviter une recherche coûteuse en temps du prédécesseur, nous introduisons dans le codage une redondance : à chaque ville on associe l'indice de son successeur et celui de son prédécesseur. Ainsi le code (be, ca, db, ec, ad) représente le chemin abcdea.

Un tableau de distances est initialisé en début d'algorithme afin de limiter les calculs. Un deuxième tableau est créé dans lequel pour chaque ville, on classe dans l'ordre les villes les plus proches. Ceci permettra lors des opérations de croisement et de mutation de sélectionner rapidement des villes pas trop éloignées.

2.2.2  Opérateur de croisement

Au lieu de définir une seule fitness locale Gi, pour des raisons de symétrie, chaque variable ou ville sera dotée de deux fitness locales fs et fp. Soit nprof un nombre compris entre 1 et la longueur totale du chromosome. Pour chaque ville à l'intérieur d'un chromosome, on détermine la longueur du chemin lorsque l'on parcourt nprof villes dans le sens direct (c'est à dire en prenant la ville suivante à chaque fois). La fitness locale fs représente donc cette valeur. On peut faire de même en parcourant les villes dans le sens opposé (c'est à dire en considérant chaque fois la ville précédente). On affectera à fp cette valeur. Ainsi, notre codage s'enrichit. Il comporte désormais quatre listes au lieu de deux. Les deux premières listes permettent de définir l'ordre des villes dans le cycle, les deux dernières sont composées des fitness locales de chaque ville.

Le principe de notre croisement est le suivant : on choisit une ville au hasard qui constitue le point de départ de notre croisement. Le processus suivant est répété n fois où n est le nombre total de villes : pour choisir la ville suivante (voir figure 2.8), on va comparer les valeurs fp et fs des deux parents, représentant quatre chemins possibles. Parmi ces quatre chemins, certains parcourent des villes déjà utilisées. On pénalise alors les fp, fs des chemins correspondants. Le choix de la ville suivante se fera en considérant le chemin le plus court, à une certaine valeur D près. Si le chemin le plus court est distant de moins de D d'un autre, la ville suivante est choisie au hasard entre ces deux villes. On retrouve bien là le principe de croisement détaillé précédemment. La valeur D a pour but de ne pas rendre l'algorithme trop déterministe. Dans le cas où les quatre villes suivantes possibles ont déjà été utilisées, on choisira de façon heuristique la ville la plus proche disponible.


Figure 2.7: Stratégie de croisement et de mutation
Pour construire le deuxième fils, on effectue la même opération en prenant un point de départ différent.

Pour nos simulations, nous avons choisi D constante et valant la distance moyenne entre les villes. On peut imaginer que D décroisse au fur et à mesure des générations. Par contre, on a intérêt à choisir nprof petit en début de convergence et de le faire croître de façon à prospecter de plus en plus loin dans les chemins possibles. Nous prendrons par exemple nprof proportionnel au nombre de générations effectuées et variant entre 1 et
n
5
.

2.2.3  Opérateur de mutation

L'opérateur de mutation utilisé est très simple. Cependant, son rôle est utile pour parcourir le plus largement possible l'espace de recherche. Observons le tableau donnant pour chaque ville les villes les plus proches dans l'ordre des distances croissantes. Il est clair que si toutes les villes sont reliées à la ville la plus proche, on a un chemin optimal. En général, un certain nombre de villes ne sont pas reliées aux villes les plus proches au profit d'autres. Nous appellerons ville de rang k une ville dont la ville suivante est la kième dans l'ordre croissant des villes les plus proches. Il est évident que passer d'une solution courante à la solution optimale du problème améliore au moins le rang d'une des n villes considérées. L'opérateur de mutation découle de cette observation. Son principe est de relier quelques villes à leurs villes voisines les plus proches et de compléter ensuite le chemin en parcourant l'ancien chemin dans l'ordre d'apparition des villes. La figure 2.8 donne un exemple de mutation sur un problème à 19 villes. L'une d'entre elles est choisie au hasard. La mutation consiste à rechercher cinq fois la ville la plus proche non parcourue, dans l'exemple, on parcourt les villes 0, 3, 2, 1, 9, 11, et l'on complète ensuite le graphe avec les villes dans leur ancien ordre d'apparition.

2.2.4  Opérateurs locaux

Les opérateurs de croisement et de mutation précédemment décrits entraînent la formation de chemins imparfaits que l'on peut corriger trivialement. Nous introduisons ici deux opérateurs de correction que nous appellerons loc1 et loc2 et que nous appliquerons à tous les chromosomes avant chaque évaluation.

L'opérateur Loc1

Cet opérateur consiste, pour chaque ville X (voir figure 2.9), à comparer la somme des coûts des arcs XC + XD - CD avec les coûts XA + XB - AB où A et B sont des villes successives proches de X. Si la deuxième somme est inférieure à la première, on reliera X aux villes A et B.



Figure 2.8: Les opérateurs de correction Loc1 et Loc2.

L'opérateur Loc2

Cet opérateur a pour but de ``déboucler les boucles''. Pour chaque arc AB (voir figure 2.9, on cherche des villes consécutives proches C et D telles que la somme AB + CD soit supérieure à AC + BD. On déboucle alors la boucle.

Il est à noter que ces deux opérateurs ne nécessitent pas que la distance entre les villes respecte l'inégalité triangulaire. Il n'est par ailleurs pas question de faire une recherche exhaustive de tous les arcs pouvant être concernés mais seulement de regarder les villes proches de chaque ville ou arc concerné. Le coût de ces deux opérateurs est donc simplement proportionnel au nombre de villes considérées dans le problème.

2.2.5  Résultats numériques



Pour tous les résultats évoqués ci-dessous, les populations initiales sont construites de façon aléatoire. L'algorithme a été testé sur un certain nombre de problèmes classiques dont on connaît les solutions optimales. Pour chacun de ces problèmes, les paramètres des simulations sont les suivants :
Probabilité de croisement : 0.6
Probabilité de mutation : 0.15

Pour chacun de ces problèmes, nous avons fait tourner l'algorithme une cinquantaine de fois. Les simulations ont été réalisées sur HP720 sans méthode de sharing pour limiter le temps de calcul. L'algorithme a toujours trouvé la solution optimale. Les résultats sont présentés dans le tableau 2.3. La première ligne donne la référence du problème  [Rei91]. La deuxième ligne donne sa taille. On donne ensuite la taille de la population utilisée pour résoudre le problème, la valeur numérique de l'optimum, le nombre minimum, moyen et maximum de générations pour résoudre le problème. Le temps minimum, moyen et maximum pour atteindre l'optimum.
Pb considérélin105kroa100kroa200
Taille du problème105100200
Taille de la pop5050100
Valeur du minimum143792128229368
Nb min de gens2240
Nb moy de gens146110
Nb max de gens3043268
Temps min (en sec)12130
Temps moy (en sec)63441
Temps max (en sec)12171418


Table 2.3: Résultats numériques sans sharing du problème du voyageur de commerce.
Les résultats sont très bons pour des problèmes de l'ordre de 100 villes et tout à fait encourageants pour 200 villes. Ils montrent l'intérêt de cette approche locale utilisée pour le croisement. Cependant, l'algorithme génétique reste loin des méthodes les plus efficaces connues actuellement dans ce domaine.

2.3  Parallélisme et apprentissage

Nous allons présenter dans cette section une application des algorithmes génétiques à l'apprentissage d'une fonction d'évaluation pour un programme d'Othello. Il faut noter que des techniques d'apprentissage bayesiennes sont utilisées avec succès pour Othello depuis BILL [LM90], jusqu'aux programmes les plus modernes comme LOGISTELLO [Bur94]. Cependant, ces méthodes nécessitent de très grandes bases de données contenant des milliers de parties, et elle ne sont réellement efficaces que sur le jeu d'Othello, car la partie se termine toujours en un nombre fixe de coups. L'apprentissage bayésien ne s'étend pas à des jeux comme les échecs. Nous allons décrire ici une technique basée sur les AG qui peut s'étendre à tous les programmes de jeux reposant sur des algorithmes de type a-b.

Des tentatives ont été faites d'appliquer des techniques telles que la co-évolution [SG94], des réseaux de neurones appris par AG [MM94], ou des stratégies évolutives [MM93] à Othello. Mais ces tentatives, pour intéressantes qu'elles soient, n'ont pas donné de résultats particulièrement concluants. Le niveau de jeu de [SG94] était relativement faible, [MM94] ne parvenait pas à améliorer le niveau de jeu s'il utilisait des fonctions d'évaluation de bonne qualité comme fonctions test, et [MM93] ne parvint pas à améliorer la stratégie classique à Othello (un terme positionnel plus un terme de mobilité).

Nous allons, en ce qui nous concerne, partir d'un programme d'Othello et utiliser les AG pour améliorer la fonction d'évaluation (ces résultats sont également présentés dans [All95]).

2.3.1  Introduction

Le point de départ de ce travail est un programme d'Othello développé par l'auteur il y a quelques années. Il faut noter que ce programme a été testé contre de bons joueurs français (en particulier contre le numéro 10 français), et a obtenu des résultats fort honorables4 .

Ce programme a une structure extrêmement simple. Il utilise un algorithme a-b, avec une recherche en profondeur itérative et des fenêtres de coupure. Le programme déclenche une recherche exhaustive 11 à 14 demi-coups avant la fin de la partie, en fonction du temps restant et de la puissance de la machine. La fonction d'évaluation est composée de trois termes, que nous allons détailler.

Le premier terme de la fonction d'évaluation est purement statique ; on utilise la table 2.4 comme référence.
500-15030101030-150500
-150-2500000-250-150
3001221030
100216162010
100216162010
3001221030
-150-2500000-250-150
500-15030101030-150500


Table 2.4: Valeur statique des cases
Pour chaque disque sur le tableau de jeu, on additionne la valeur de la case correspondante si le disque est de la couleur du programme, ou on retranche cette valeur si le disque appartient à l'adversaire. Cette table, en raison des symétries, comporte 10 paramètres.

Le second terme a pur but de raffiner cette évaluation grossière. En effet, quand un coin du bord est déjà pris, les trois cases immédiatement adjacentes peuvent être occupées sans aucun risque, et leur valeur est donc ramenée à 0. Enfin, toujours lorsqu'un coin est occupé, tous les disques du bord de la même couleur et connectés à ce coin reçoivent un bonus. Par exemple, sur la figure 2.10, on voit que trois disques reçoivent un bonus. La valeur de ce bonus est un autre paramètre de la fonction d'évaluation.


Figure 2.9: Evaluation des libertés et des bords
Enfin, le troisième partie de la fonction d'évaluation est le facteur de mobilité ; on calcule pour chaque disque le nombre de libertés : il s'agit du nombre de cases libres autour de ce disque. On additionne ensuite les libertés de chaque disque pour un joueur donné (par exemple, sur la figure 2.10, le joueur noir a 8 libertés). Le score de mobilité est la différence des libertés des deux joueurs. Ce score est multiplié par un coefficient avant d'être ajouté à la valeur de la fonction d'évaluation.

La fonction d'évaluation comporte donc 12 (10+1+1) paramètres. Les valeurs initialement prises par ces paramètres étaient [500, -150, -250, 30, 0, 1, 10, 0, 2, 16] pour les valeurs des cases, +30 pour le bonus de connexion, et 8 pour la pénalité de mobilité5 . Ces valeurs ont été choisies de façon arbitraire. Elles ``semblent'' raisonnables, mais rien ne permet de penser qu'elles sont ``optimales''.

Nous allons maintenant décrire comment un AG peut-être utilisé pour améliorer les valeurs de ces coefficients.

2.3.2  Principes généraux

L'espace de recherche de l'algorithme génétique est l'ensemble des coefficients de la fonction d'évaluation. Cependant, comme la fonction d'évaluation est linéaire, on peut arbitrairement fixer la valeur d'un des coefficients. On ne garde alors que 11 paramètres au lieu de douze (dans le cas présent, nous avons fixé la valeur d'un angle à 500, car nous sommes sûrs qu'un angle doit avoir une pondération positive).

Le croisement utilisé est de type barycentrique. Un nombre a est tiré aléatoirement dans l'intervalle [-0.5,1.5] and un nombre i dans l'intervalle [1,11]. On croise alors le ith élément de chaque chromosome. Le nouveau ième composant de chaque chromosome vaut :
c1i'= a c1i+ (1-a) c2i
c2i'= (1-a) c1i+ a c2i

Le programme utilise également du sharing. La distance utilisée est la distance euclidienne sur l'espace des coefficients.

2.3.3  Calcul de la fitness

La première idée pour évaluer la fitness consiste à faire jouer chaque programme contre un programme de référence et à noter les résultats. Cependant, du fait que les résultats sont purement probabilistes, il faudrait à chaque génération que chaque programme joue un très grand nombre de parties à des profondeurs d'évaluation différentes pour que le résultat soit fiable. Le temps d'évaluation devient alors complètement prohibitif. Nous avons donc décidé d'utiliser une technique mixte. Tout d'abord, un programme qui n'est pas modifié d'une génération à l'autre conserve la mémoire des matchs déjà joués. De cette façon, la valeur de l'intervalle de confiance sur la valeur de la fitness s'améliore au fil des parties.

La méthodologie choisie est donc la suivante pour chaque élément de la population : On peut alors choisir comme fitness :
f=
Nvictoires+Nnuls/2+D/1000
Nparties
où D représente les différences cumulées des pions en fin de partie.

Pourtant, cette technique n'est pas satisfaisante. On voit intuitivement qu'il est plus intéressant d'avoir un programme qui a gagné 95 parties sur 96 qu'un programme qui a gagné 12 parties sur 12. La confiance que nous avons sur le premier est forte, alors qu'elle est beaucoup plus faible pour le second. Nous avons alors défini l'estimateur suivant :

Si la probabilité de gagner une partie sur une jouée est notée p alors celle de gagner m parties sur n jouées est donnée par la loi binomiale :
p(m,n)=Cnm pm (1-p)n-m
Ensuite, si n parties sont jouées, il y a n+1 résultats possibles6 et dans l'espace des probabilités ils sont tous équiprobables, on en déduit :
ó
õ
1
 
0
 p(m,n)dp=
1
n+1


Figure 2.10: Courbe h(p,m,n)
Cette valeur f sera utilisée pour calculer l'adaptation de l'élément concerné ; mathématiquement, l'adaptation sera donc telle que :
ó
õ
1
 
f
(n+1)(
Cnm pm (1-p)n-m)
dp=0.95

Construisons alors la fonction h(p,m,n)=(n+1)p(m,n), elle va servir à établir un intervalle de confiance que nous fixerons à 95% : on désire trouver la valeur f à partir de laquelle il y a 95% de chance pour que la fitness soit supérieure à f. On cherche donc la valeur telle que 95% de la surface se situant sous la courbe (représentée figure 2.11) se trouve après f.

Les valeurs de la fitness sont assez profondément modifiées. Ainsi, par exemple, f(12,12)=0.79, f(23,24)=0.83, f(44,48)=0.82 et f(65,72)=0.83. Cette technique, qui peut se généraliser à d'autres problèmes où les calculs de fitness sont statistiques, a donné d'excellents résultats.

2.3.4  Résultats expérimentaux

Pour traiter ce problème, la mise en oeuvre du parallélisme a été indispensable. En effet, le temps d'évaluation d'un élément à chaque génération est de l'ordre de 15 secondes. Sachant que la fitness est évolutive, et que l'on utilise le recuit, il faudrait compter environ 18 minutes par génération pour une population de 40 éléments si l'on n'utilise pas le parallélisme. Les deux formes de parallélisme (simple et par îlots) ont été essayées7 . Le parallélisme par îlot a donné les meilleurs résultats, sans doute parce qu'il provoque un clustering forcé.

On a tout d'abord développé un programme dit de niveau 1, qui a appris à jouer contre le programme de référence (niveau 0). Ce programme a ensuite été testé extensivement (sur 400 matchs) à toutes les profondeurs de 0 à 5, et sur 100 matchs à la profondeur 6. A partir de ce programme de niveau 1, on a développé un programme de niveau 2 qui était testé contre les programmes de niveau 1 et de niveau 0. Les résultats des différents tests sont présentés dans la table 2.5.
ProfGPNGPNGPN
028298201881941827410719
12521014728582332668241
22787844303554224312037
3281754429850522926147
4280754532046343204641
528668463294031   
672208      


Table 2.5: Résultats des programmes développés par AG
Il est remarquable de constater que, bien que l'apprentissage ne soit fait qu'aux profondeurs 0, 1 et 2, les ``nouveaux'' programmes battent les anciens de façon impressionnante jusqu'à la profondeur 6.

2.3.5  Conclusion

Les travaux décrits ci-dessus ont été poursuivis par l'auteur de ces lignes durant ses moments libres (hélas trop peu nombreux). Une nouvelle version du programme a vu le jour. Cette version utilise une fonction d'évaluation totalement différente : elle est bâtie sur une technique de ``reinforcement learning'' qui est appliquée à la reconnaissance de formes spécifiques sur les bords et dans les coins. Les coefficients de la fonction sont toujours appris par AG.

Ce programme a été engagé sur le serveur international d'Othello (IOS), sous le nom d'otage. Il occupe actuellement la 4ème place en Blitz et la 9ème place en partie classique sur un ensemble d'environ 500 joueurs classés. Ses résultats contre certains des bons programmes mondiaux (Bugs, Yapp, Hannibal) indiquent que ce classement de 9ème doit approximativement correspondre à sa valeur réelle.

Il serait intéressant de poursuivre le travail sur otage, en particulier en raffinant l'algorithme de recherche, en introduisant des tables de hash, en lui faisant utiliser le temps de l'adversaire, en utilisant une bibliothèque d'ouvertures, en améliorant la qualité de la reconnaissance de patterns, etc. Le potentiel de progression du programme est, à mon avis, encore important.

2.4  Conclusion

Il est toujours délicat de conclure une étude de ce type. En effet, pour bien juger de la supériorité d'une méthode sur une autre méthode, il nous faudrait parfaitement connaître les deux. Il est en effet trop facile pour un spécialiste de la méthode A de démontrer la supériorité de ses algorithmes, simplement parce qu'il sait parfaitement utilisé son outil, alors qu'il ne maîtrise pas la méthode B à laquelle il se compare. Il faut donc être excessivement prudent lors de comparaison de plusieurs méthodes différentes sur un même problème. D'autre part, les problèmes traités sont fort différents les uns des autres, et l'on ne peut être que nuancé dans ses conclusions.

 Méthodes localesRecuitAGProg. Inter.
Optimum trouvéouinonnonoui
ParallélismedifficiledifficileIntrinsèqueFacile
Optima multiplenonnonouioui
Optimisation globalenonouiouioui
Nombreuses variablesefficaceefficaceefficaceinefficace


Table 2.6: Comparaison de différentes méthodes d'optimisation
Nous pensons cependant que l'on peut retenir un certain nombre d'enseignements du travail que nous avons effectué au cours des dernières années ; les algorithmes génétiques sont efficaces lorsque : En revanche, ils se révèlent relativement inefficaces dans les cas suivants : Le tableau 2.6 présente un résumé de ces éléments. De façon générale, les algorithmes génétiques ne doivent être employés que lorsque les méthodes plus classiques ne peuvent être utilisées. Il ne s'agit en aucun cas d'une panacée universelle susceptible de couvrir tous les domaines de l'optimisation.

1
Very Fast Simulated Reannealing
2
Adaptive Simulated Annealing
3
Le terme ``Evolutionary Computation'' désigne des algorithmes de type génétique mais qui n'utilisent que la mutation.
4
Les meilleurs programmes d'Othello sont ``presque'' imbattables par un joueur humain.
5
Il faut noter, qu'à Othello, le but est d'avoir le moins de libertés possibles, une liberté étant une case potentielle d'attaque pour l'adversaire.
6
On gagne 0,1,...,n-1 ou n parties soit donc n+1 résultats distincts.
7
Pour une présentation plus détaillée, en particulier sur les speedups obtenus, on peut se reporter à [LeF95].
Previous Next Contents