Techniques d’optimisation stochastique appliqu´ees

7/30/2019 Techniques doptimisation stochastique appliquees

1/187

Techniques doptimisation stochastique appliqu ees a certainsprobl emes du trac a erien

Jean-Marc Alliot

27 octobre 1998


2/187

2


3/187

Table des mati eres

I R esultats g en eraux 11

1 Les Algorithmes G en etiques 151.1 Principes g eneraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Description d etaill ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2.1 Codage des donn ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2.2 G eneration aleatoire de la population initiale . . . . . . . . . . . . . . . . . 171.2.3 Gestion des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2.4 Operateur de Croisement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.2.5 Operateur de mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.2.6 Principes de s election . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.3 Am eliorations classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.3.2 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.3.3 Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3.4 Sharing clusteris e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.3.5 Algorithmes g enetiques et recuit simul e . . . . . . . . . . . . . . . . . . . . 261.3.6 Recherche multi-objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 281.3.7 Association des AG avec des m ethodes locales . . . . . . . . . . . . . . . . 29

1.4 Autres am eliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301.4.1 Croisement adapt e pour les fonctions partiellement s eparables . . . . . . . . 301.4.2 Mutation adaptative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321.4.3 Clustering adaptatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1.5 Parallelisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331.5.1 Parallelisme par lots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331.5.2 Parallelisation des calculs . . . . . . . . . . . . . . . . . . . . . . . . . . . 341.5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

1.6 R esultats theoriques sur les algorithmes binaires . . . . . . . . . . . . . . . . . . . . 361.6.1 D enitions fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 361.6.2 Effets de la reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371.6.3 Effets des croisements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381.6.4 Effets des mutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381.6.5 Conclusion sur le codage binaire . . . . . . . . . . . . . . . . . . . . . . . . 39

1.7 Modelisation par chane de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . 391.7.1 Description rapide dun algorithme g enetique . . . . . . . . . . . . . . . . . 391.7.2 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411.7.3 Application de la th eorie de Freidlin et Wentzell . . . . . . . . . . . . . . . 45

3


4/187

2 M ethodes et probl emes 532.1 Optimisation de fonctions ` a variables reelles . . . . . . . . . . . . . . . . . . . . . . 53

2.1.1 Fonction de Rosenbrock et Chebyquad . . . . . . . . . . . . . . . . . . . . 532.1.2 Fonction de De Jong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552.1.3 Fonction de Corana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562.1.4 Fonction de Griewank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

2.2 Probl`emes de type combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592.2.1 Codage des donn ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612.2.2 Operateur de croisement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612.2.3 Operateur de mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.2.4 Operateurs locaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.2.5 R esultats numeriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.3 Parallelisme et apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652.3.2 Principes g eneraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662.3.3 Calcul de la tness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662.3.4 R esultats experimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682.3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

II Applications aux probl emes du trac a erien 71

3 Optimisation de la r esolution de conits 753.1 Etude du trac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.1.1 Simulation du trac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.1.2 R esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823.1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.2 Approche math ematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.2.1 Conit entre des avions non contraints en vitesse . . . . . . . . . . . . . . . 883.2.2 Conit entre deux avions contraints en vitesse . . . . . . . . . . . . . . . . . 903.2.3 Complexit e th eorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943.2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3.3 Approximation par point tournant et par offset . . . . . . . . . . . . . . . . . . . . . 963.3.1 Point tournant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963.3.2 Approximation par offset . . . . . . . . . . . . . . . . . . . . . . . . . . . . 983.3.3 Avions en rattrapage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

3.4 Modelisation de lincertitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1043.4.1 N ecessit e de modeliser lincertitude . . . . . . . . . . . . . . . . . . . . . . 1043.4.2 Evaluation de la probabilit e de conit. . . . . . . . . . . . . . . . . . . . . . 1043.4.3 Esperance de cout de r esolution de conit. . . . . . . . . . . . . . . . . . . . 106

3.5 Modelisation pour la r esolution de conits complexes . . . . . . . . . . . . . . . . . 1083.5.1 Mod`ele de cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1093.5.2 D eroulement en temps r eel . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.6 R esolution par algorithmes g enetiques . . . . . . . . . . . . . . . . . . . . . . . . . 1113.6.1 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1123.6.2 G eneration de la population initiale . . . . . . . . . . . . . . . . . . . . . . 112

4


5/187

3.6.3 Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1133.6.4 Operateurs de croisement et de mutation adapt es . . . . . . . . . . . . . . . 1153.6.5 Sharing simpli e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1153.6.6 M ethode locale en n de convergence . . . . . . . . . . . . . . . . . . . . . 1173.6.7 Applications num eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173.6.8 Architecture g enerale du simulateur de trac . . . . . . . . . . . . . . . . . 1233.6.9 R esultats sur une journ ee de trac r eelle . . . . . . . . . . . . . . . . . . . . 1263.6.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

3.7 Programmation lin eaire et AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1273.7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1273.7.2 Codage des donn ees du probl` eme . . . . . . . . . . . . . . . . . . . . . . . 1283.7.3 Croisement et mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1283.7.4 Evaluation de la tness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1283.7.5 R esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1293.7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.8 Techniques de parcours de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . 1313.8.1 Algorithme de type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1313.8.2 M ethode de plus forte pente . . . . . . . . . . . . . . . . . . . . . . . . . . 1323.8.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

3.9 R esolution reactive et autonome . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1333.9.1 M ethodes reactives à mod ele physique . . . . . . . . . . . . . . . . . . . . . 1333.9.2 R esolution par r eseaux de neurones . . . . . . . . . . . . . . . . . . . . . . 136

3.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

4 Sectorisation de lespace et r epartition des ux 1414.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1414.2 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

4.2.1 Routes a eriennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1424.2.2 Charge de contr ole dans un secteur . . . . . . . . . . . . . . . . . . . . . . 143

4.3 Problèmes a r esoudre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1454.3.1 Problème de sectorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1454.3.2 Problème daffectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

4.4 Complexit e associ ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1484.4.1 Problème de sectorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1484.4.2 Problème daffectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

4.5 Sectorisation dun r eseau a ux affectes . . . . . . . . . . . . . . . . . . . . . . . . 1484.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1484.5.2 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1494.5.3 Optimisation du probl` eme par Algorithmes G enetiques . . . . . . . . . . . . 1514.5.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1594.5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

4.6 Affectation des ux sur un r eseau sectoris e . . . . . . . . . . . . . . . . . . . . . . . 1624.6.1 M ethodes classiques daffectation statique . . . . . . . . . . . . . . . . . . . 1624.6.2 Optimisation du probl` eme par AG . . . . . . . . . . . . . . . . . . . . . . . 1634.6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

4.7 Sectorisation et affectation de trac simultan ees . . . . . . . . . . . . . . . . . . . . 1694.8 Regroupement de secteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

5


6/187

4.8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1704.8.2 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1704.8.3 Complexit e du principe de regroupement . . . . . . . . . . . . . . . . . . . 1714.8.4 Optimisation par algorithme g enetique . . . . . . . . . . . . . . . . . . . . . 171

4.9 Limitations du mod` ele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1734.9.1 Modelisation de la charge de contr ole . . . . . . . . . . . . . . . . . . . . . 1734.9.2 Prise en compte de la troisi` eme dimension . . . . . . . . . . . . . . . . . . . 1744.9.3 Limitation de lexploration de lespace d etat . . . . . . . . . . . . . . . . . 1744.9.4 Prise en compte des zones militaires . . . . . . . . . . . . . . . . . . . . . . 1754.9.5 Probl`emes politiques li es a la souverainet e de lespace a erien . . . . . . . . . 1754.9.6 Prise en compte de la propagation des ux . . . . . . . . . . . . . . . . . . . 176

4.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

6


7/187

In a forest a fox bumps into a little rabbit, and says, Hi, junior, what are you up to? Im writing a dissertation on how rabbits eat foxes, said the rabbit.Come now, friend rabbit, you know thats impossible!

Well, follow me and Ill show you. They both go into the rabbits dwelling and after a while the rabbit emerges with a satised expression on his face.

Comes along a wolf. Hello, what are we doing these days? Im writing the second chapter of my thesis, on how rabbits devour wolves.Are you crazy? Where is your academic honesty? Come with me and Ill show you. As before, the rabbit comes out with a satised look on his face and a

diploma in his paw. Finally, the camera pans into the rabbits cave and, as everybody should have guessed bynow, we see a mean-looking, huge lion sitting next to some bloody and furry remnants of the wolf and the fox.

The moral: Its not the contents of your thesis that are important its your PhD advisor that reallycounts.


8/187

8


9/187

Introduction

Ce document pr esente le bilan de quatre ann ees d etudes et de recherches effectu ees par toute uneequipe de thesards et detudiants de DEA dont jai fort modestement assur e, partiellement, la directionet lencadrement. Ils ont implant e, corrige, am elior e, d ecouvert, et sans eux, nombre des id ees que jaipu essayer dexploiter nauraient jamais d epass e le stade de la feuille de papier.

Ce document est donc le r esultat dun travail d equipe. Je le revendique comme tel, et jen suisparticuli erement heureux. Il est vrai que si lon consid` ere lHabilitation ` a Diriger des Recherchescomme un doctorat dEtat d eguis e, cette monographie manque compl` etement son but : on aura peine ` atrouver plus dune vingtaine de pages d ecrivant une recherche purement et exclusivement personnelle.Si, au contraire, on consid` ere aussi lHDR comme la d emonstration dune capacit e a animer uneequipe de recherche, alors les quelques pages qui suivent essaient de remplir cet ofce.

Ce document se compose de deux parties que lon peut lire de facon presque ind ependante.La premi`ere partie presente un certain nombre de r esultats de caract` ere g eneral sur les techniques

genetiques. Cette partie comporte deux chapitres :

le premier chapitre sera consacr ee aux algorithmes g enetiques, avec une pr esentation des r esultats

theoriques existants, puis la description de tous les rafnements (scaling1, sharing, clustering,

parall elisme, etc.) indispensables ` a un fonctionnement efcace.

dans le second chapitre, nous d evelopperons sur quelques exemples classiques lutilisation desalgorithmes g enetiques et nous les comparerons ` a dautres techniques, locales (simplex, BFGS),globales deterministes (programmation par intervalles) ou stochastiques (recuit).

La seconde partie pr esentera lapplication des techniques g enetiques aux probl` emes du tracaerien a travers un certain nombre dexemples :

construction de trajectoires optimales pour la r esolution de conits en route

optimisation de la sectorisation de lespace et de la r epartition de ux

resolution reactive de conits ` a court terme

Bien entendu, ce document est incomplet. Certains travaux r ealis es, comme loptimisation deschanes s ecurit e dans les aerogares (etude pour le Service des Bases A eriennes), loptimisation desredevances a eroportuaires (pour A eroport De Paris), ou la r eexion sur loptimisation des cr eneaux

1Nous emploierons dans tout ce document les termes anglais qui se sont (malheureusement? ) impos es au l des ann ees,dont ceux developpes sp eciquement par notre equipe. On pourrait certes remplacer scaling par mise ` a l echelle,sharing par r epartition forc ee des elements ou clustering par regroupement par paquets. Le texte ny gagnerait pasnecessairement en lisibilit e...Notons egalement que nous employons abusivement le mot al eatoire chaque fois que nousdesignons un processus al eatoire dont le tirage est uniforme. La nature du processus est pr ecis ee chaque fois quil ne sagitpas dun tirage uniforme.

9


10/187

de d ecollage, nont pu y trouver place. Cependant, nous pensons quil re` ete lesprit general du travailque nous effectuons et souhaitons effectuer : appliquer une m ethodologie scientique aux probl` emesdu trac aerien.

10


11/187

Partie I

Resultats g en eraux

11


12/187


13/187

Numerical optimization can be likened to a kangaroo searching for the top of Mt. Everest. Everest is theglobal optimum, but the top of any other really high mountain such as K2 would be nearly as good.

When training a neural network, initial weights are usually chosen randomly, which means that the kanga-

roo may start out anywhere in Asia. If you know something about the scales of the inputs, you may be able toget the kangaroo to start near the Himalayas. However, if you make a really stupid choice of distributions for the random initial weights, or if you have really bad luck, the kangaroo may start in South America.

In standard backprop or stochastic approximation, the kangaroo is blind and has to feel around on theground to make a guess about which way is up. He may be fooled by rough terrain unless you use batchtraining. If the kangaroo ever gets near the peak, he may jump back and forth across the peak without ever landing on the peak. If you use a decaying step size, the kangaroo gets tired and makes smaller and smaller hops, so if he ever gets near the peak he has a better chance of actually landing on it before the Himalayaserode away. In backprop with momentum, the kangaroo has poor traction and cant make sharp turns.

With Newton-type (2nd order) algorithms, the Himalayas are covered with a dense fog, and the kangaroocan only see a little way around his location. Judging from the local terrain, the kangaroo make a guess about where the top of the mountain is, and tries to jump all the way there. In a stabilized Newton algorithm, thekangaroo has an altimeter, and if the jump takes him to a lower point, he backs up to where he was and takesa shorter jump. If the algorithm isnt stabilized, the kangaroo may mistakenly jump to Shanghai and get served for dinner in a Chinese restaurant. (I never claimed this analogy was realistic.) In steepest ascent with linesearch, the fog is very dense, and the kangaroo can only tell which direction leads up. The kangaroo hops inthis direction until the terrain starts going down again, then chooses another direction.

Notice that in all the methods discussed so far, the kangaroo can hope at best to nd the top of a mountainclose to where he starts. Theres no guarantee that this mountain will be Everest, or even a very high mountain.

In simulated annealing, the kangaroo is drunk and hops around randomly for a long time. However, hegradually sobers up and tends to hop up hill.

In genetic algorithms, there are lots of kangaroos that are parachuted into the Himalayas (if the pilot didnt get lost) at random places. These kangaroos do not know that they are supposed to be looking for the top of Mt. Everest. However, every few years, you shoot the kangaroos at low altitudes and hope the ones that are left willbe fruitful and multiply.

From all this we can conclude that the best methods to nd the Mount Everest are (in order):

1. to know where it is

2. to have a map on which you can nd it

3. to know someone who knows where it is or who has a map

4. to send (a) kangaroo(s) to search for it

and even if you have to send a kangaroo, it is useful if you know at least:

1. where the mountain range is in which the Mount Everest may be and

2. how to bring your kangaroo to that mountain range.

Warren Searle


14/187

14


15/187

Chapitre 1

Les Algorithmes G en etiques

1.1 Principes g en erauxLes algorithmes g enetiques sont des algorithmes doptimisation sappuyant sur des techniques d eriveesde la g enetique et de l evolution naturelle 1 : croisements, mutations, s election, etc. Les algorithmesgenetiques ont d eja une histoire relativement ancienne puisque les premiers travaux de John Hol-land sur les syst` emes adaptatifs remontent ` a 1962 [Hol62]. Louvrage de David Goldberg [Gol89c] alargement contribu e a les vulgariser.

Un algorithme g enetique recherche le ou les extrema dune fonction d enie sur un espace dedonn ees. Pour lutiliser, on doit disposer des cinq elements suivants :

1. Un principe de codage de l element de population. Cette etape associe ` a chacun des pointsde lespace d etat une structure de donn ees. Elle se place g eneralement apr` es une phase demod elisation math ematique du probl` eme traite. La qualite du codage des donn ees conditionnele succ es des algorithmes g enetiques. Le codages binaires ont ete tr es utilis es a lorigine. Lescodages reels sont desormais largement utilis es, notamment dans les domaines applicatifs pourloptimisation de probl` emes a variables reelles.

2. Un mecanisme de g eneration de la population initiale. Ce m ecanisme doit etre capable de pro-duire une population dindividus non homog` ene qui servira de base pour les g enerations futures.Le choix de la population initiale est important car il peut rendre plus ou moins rapide la conver-gence vers loptimum global. Dans le cas o` u lon ne connat rien du probl` eme a r esoudre, il estessentiel que la population initiale soit r epartie sur tout le domaine de recherche.

3. Une fonction ` a optimiser. Celle-ci retourne une valeur de appel ee tness ou fonction d evaluationde lindividu.

4. Des operateurs permettant de diversier la population au cours des g enerations et dexplorerlespace detat. Loperateur de croisement recompose les g` enes dindividus existant dans lapopulation, lop erateur de mutation a pour but de garantir lexploration de lespace d etats.

5. Des param` etres de dimensionnement : taille de la population, nombre total de g enerations oucritere darret, probabilites dapplication des op erateurs de croisement et de mutation.

1Il est interessant de trouver dans luvre dun sp ecialiste de zoologie, Richard Dawkins [Daw89], un exemple informa-tique tendant ` a prouver la correction de lhypoth` ese darwinienne de la s election naturelle. La m ethode utilisee est presquesemblable aux techniques g enetiques.

15


16/187

E

REPRODUCTION

CROISEMENT

EVALUATION

Gnration k

POPULATION

Gnration k+1

POPULATION

P1 P2

E1 E2

MUTATION

PPROBABILITE Pm PROBABILITE Pc

Figure 1.1: Principe g eneral des algorithmes g enetiques

Le principe g eneral du fonctionnement dun algorithme g enetique est repr esent e sur la gure 1.1 :on commence par g enerer une population dindividus de facon al eatoire. Pour passer dune g eneration

a la g eneration , les trois op erations suivantes sont r epetees pour tous les elements de lapopulation . Des couples de parents et sont s electionnes en fonction de leurs adaptations.Lop erateur de croisement leur est appliqu e avec une probabilit e (generalement autour de ) etgenere des couples denfants et . Dautres elements sont s electionnes en fonction de leuradaptation. Lop erateur de mutation leur est appliqu e avec la probabilit e ( est g eneralementtres inf erieur a ) et g enere des individus mut es . Le niveau dadaptation des enfants ( , ) etdes individus mut es sont ensuite evalu es avant insertion dans la nouvelle population. Diff erentscriteres darret de lalgorithme peuvent etre choisis :

Le nombre de g enerations que lon souhaite ex ecuter peut etre x e a priori. Cest ce que lonest tent e de faire lorsque lon doit trouver une solution dans un temps limit e.

Lalgorithme peut etre arr ete lorsque la population n evolue plus ou plus sufsamment rapide-ment.

Nous allons maintenant d etailler chacun de ces points.

16


17/187

1.2 Description d etaill ee

1.2.1 Codage des donn ees

Historiquement le codage utilis e par les algorithmes g enetiques etait represent e sous forme de chanesde bits contenant toute linformation n ecessaire `a la description dun point dans lespace d etat. Cetype de codage a pour int eret de permettre de cr eer des operateurs de croisement et de mutationsimples. Cest egalement en utilisant ce type de codage que les premiers r esultats de convergencetheorique ont ete obtenus.

Cependant, ce type de codage nest pas toujours bon comme le montrent les deux exemples sui-vants :

deux elements voisins en terme de distance de Hamming ne codent pas n ecessairement deuxelements proches dans lespace de recherche. Cet inconv enient peut etre evite en utilisant uncodage de Gray.

Pour des probl` emes doptimisation dans des espaces de grande dimension, le codage binairepeut rapidement devenir mauvais. G eneralement, chaque variable est repr esent ee par une partiede la chane de bits et la structure du probl` eme nest pas bien re etee, lordre des variablesayant une importance dans la structure du chromosome alors quil nen a pas forc ement dans lastructure du probl` eme.

Les algorithmes g enetiques utilisant des vecteurs r eels [Gol91, Wri91] evitent ce probl` eme enconservant les variables du probl` eme dans le codage de l element de population sans passer par lecodage binaire interm ediaire. La structure du probl` eme est conserv ee dans le codage.

1.2.2 G en eration al eatoire de la population initialeLe choix de la population initiale dindividus conditionne fortement la rapidit e de lalgorithme. Si laposition de loptimum dans lespace d etat est totalement inconnue, il est naturel de g enerer al eatoirementdes individus en faisant des tirages uniformes dans chacun des domaines associ es aux composantesde lespace d etat en veillant ` a ce que les individus produits respectent les contraintes [MJ91]. Si parcontre, des informations ` a priori sur le probl` eme sont disponibles, il parait bien evidemment naturelde g enerer les individus dans un sous-domaine particulier an dacc elerer la convergence. Dans lhy-poth ese o u la gestion des contraintes ne peut se faire directement, les contraintes sont g eneralementincluses dans le crit` ere a optimiser sous forme de p enalit es. Il est clair quil vaut mieux, lorsque cestpossible ne g enerer que des elements de population respectant les contraintes.

1.2.3 Gestion des contraintes

Un element de population qui viole une contrainte se verra attribuer une mauvaise tness et aura uneprobabilite forte detre elimin e par le processus de s election.

Il peut cependant etre int eressant de conserver, tout en les p enalisant, les elements non admissiblescar ils peuvent permettre de g enerer des elements admissibles de bonne qualit e. Pour de nombreuxprobl emes, loptimum est atteint lorsque lune au moins des contraintes de s eparation est satur ee, cesta dire sur la fronti` ere de lespace admissible.

Gerer les contraintes en p enalisant la fonction tness est difcile, un dosage simpose pour nepas favoriser la recherche de solutions admissibles au d etriment de la recherche de loptimum ouinversement.

17


18/187

CROISEMENT

P 1 P 2

1C C

2

Figure 1.2: Slicing crossover

Disposant dune population dindividus non homog` ene, la diversit e de la population doit etreentretenue au cours des g enerations an de parcourir le plus largement possible lespace d etat. Cestle role des operateurs de croisement et de mutation.

1.2.4 Op erateur de Croisement

Le croisement a pour but denrichir la diversit e de la population en manipulant la structure des chro-mosomes. Classiquement, les croisements sont envisag es avec deux parents et g enerent deux enfants.

Initialement, le croisement associ e au codage par chanes de bits est le croisement ` a d ecoupagede chromosomes (slicing crossover). Pour effectuer ce type de croisement sur des chromosomesconstitu es de genes, on tire al eatoirement une position dans chacun des parents. On echange en-suite les deux sous-chanes terminales de chacun des deux chromosomes, ce qui produit deux enfants

et (voir gure 1.2).On peut etendre ce principe en d ecoupant le chromosome non pas en sous-chanes mais en , ,

etc [BG91]. (voir gure 1.3).Ce type de croisement ` a d ecoupage de chromosomes est tr` es efcace pour les probl` emes discrets.

Pour les probl` emes continus, un croisement barycentrique est souvent utilis e : deux g`enes et

sont s electionnes dans chacun des parents ` a la m eme position . Ils d enissent deux nouveauxgenes et par combinaison lin eaire :

ou est un coefcient de pond eration aleatoire adapte au domaine dextension des g` enes (il nestpas n ecessairement compris entre et , il peut par exemple prendre des valeurs dans lintervalle

ce qui permet de g enerer des points entre, ou ` a lext erieur des deux g` enes consideres).Dans le cas particulier dun chromosome matriciel constitu e par la concat enation de vecteurs, on

peut etendre ce principe de croisement aux vecteurs constituant les g` enes (voir gure 1.4) :

18


19/187

CROISEMENT

P 1 P 2

1C C 2

Figure 1.3: Slicing crossover ` a 2 points

P2

C1

C2P1

Figure 1.4: Croisement barycentrique

19


20/187

gngig1

gngig1

gi gi

chromosome initial

chromosome mut

Figure 1.5: Principe de lop erateur de mutation

On peut imaginer et tester des op erateurs de croisement plus ou moins complexes sur un probl` emedonn e mais lefcacit e de ce dernier est souvent li e intrins equement au probl` eme.

1.2.5 Op erateur de mutationLop erateur de mutation apporte aux algorithmes g enetiques la propri ete dergodicit e de parcours des-pace. Cette propri ete indique que lalgorithme g enetique sera susceptible datteindre tous les pointsde lespace d etat, sans pour autant les parcourir tous dans le processus de r esolution. Ainsi en touterigueur, lalgorithme g enetique peut converger sans croisement, et certaines implantations fonction-nent de cette mani` ere [FOW66]. Les propri etes de convergence des algorithmes g enetiques sont doncfortement dependantes de cet op erateur sur le plan th eorique.

Pour les probl` emes discrets, lop erateur de mutation consiste g eneralement à tirer aleatoirementun g ene dans le chromosome et ` a le remplacer par une valeur al eatoire (voir gure 1.5). Si la notionde distance existe, cette valeur peut etre choisie dans le voisinage de la valeur initiale.

Dans les probl` emes continus, on proc` ede un peu de la m eme manière en tirant al eatoirement ungene dans le chromosome, auquel on ajoute un bruit g eneralement gaussien. L ecart type de ce bruitest difcile à choisir a priori. Nous discutons ce probl` eme de facon plus d etaill ee, en presentant uneamorce de solution, dans la section 1.4.2.

1.2.6 Principes de s election

A linverse dautres techniques doptimisation, les algorithmes g enetiques ne requi` erent pas dhy-poth ese particulière sur la regularit e de la fonction objectif. Lalgorithme g enetique nutilise notam-ment pas ses d eriv ees successives, ce qui rend tr` es vaste son domaine dapplication. Aucune hypoth` esesur la continuit e nest non plus requise. N eanmoins, dans la pratique, les algorithmes g enetiques sontsensibles à la r egularit e des fonctions quils optimisent.

20


21/187

Le peu dhypoth` eses requises permet de traiter des probl` emes tr es complexes. La fonction ` a opti-miser peut ainsi etre le r esultat dune simulation.

Las election permet didentier statistiquement les meilleurs individus dune population et d eliminerles mauvais. On trouve dans la litt erature un nombre important de principes de s election plus ou moinsadapt es aux probl` emes quils traitent. Dans le cadre de notre travail, les deux principes de s electionsuivants ont ete test es et evalu es:

Roulette wheel selection [Gol89c];

Stochastic remainder without replacement selection [Gol89c];

Le principe de Roulette wheel selection 2 consiste à associer à chaque individu un segment dont lalongueur est proportionnelle ` a sa tness. On reproduit ici le principe de tirage al eatoire utilise dansles roulettes de casinos avec une structure lin eaire. Ces segments sont ensuite concat enes sur un axeque lon normalise entre et . On tire alors un nombre al eatoire de distribution uniforme entre et ,

puis on regarde quel est le segment s electionne. Avec ce syst` eme, les grands segments, cest-` a-direles bons individus, seront plus souvent adress es que les petits. Lorsque la dimension de la populationest r eduite, il est difcile dobtenir en pratique lesp erance mathematique de s election en raison dupeu de tirages effectu es. Un biais de s election plus ou moins fort existe suivant la dimension de lapopulation.

La Stochastic remainder without replacement selection evite ce genre de probl` eme et donne debons r esultats pour nos applications. D ecrivons ce principe de s election :

Pour chaque element , on calcule le rapport de sa tness sur la moyenne des tness.

Soit la partie entière de , chaque element est reproduit exactement fois.

La roulette wheel selection precedemment decrite est appliqu ee sur les individus affect es destness .

Compte-tenu du fait que des faibles populations seront utilis ees par la suite, ce principe de s electionsav erera le plus efcace dans les applications pratiques et sera donc utilis e par la suite.

1.3 Am eliorations classiques

1.3.1 Introduction

Les processus de s election present es sont très sensibles aux ecarts de tness et dans certains cas, untres bon individu risque d etre reproduit trop souvent et peut m eme provoquer l elimination compl` etede ses congeneres; on obtient alors une population homog` ene contenant un seul type dindividu.Ainsi, dans lexemple de la gure 1.6 le second mode risque detre le seul repr esentant pourla g eneration suivante et seule la mutation pourra aider ` a atteindre lobjectif global au prix denombreux essais successifs.

Pour eviter ce comportement, il existe dautres modes de s election ( ranking ) ainsi que des prin-cipes ( scaling, sharing ) qui empechent les individus forts d eliminer compl` etement les plus fai-bles. On peut egalement modier le processus de s election en introduisant des tournois entre parentset enfants, bas e sur une technique proche du recuit.

Enn, on peut egalement introduire des recherches multi-objectifs, en utilisant la notion de domi-nance lors de la s election.

2Dans la litterature, ctte m ethode porte parfois le nom de m ethode de Monte-Carlo.

21


22/187

y

M 2

M 1

individus

x

Figure 1.6: Exemple o` u les s elections classiques risquent de ne reproduire quun individu

1.3.2 Scaling

Le scaling ou mise `a l echelle, modie les tness an de r eduire ou damplier articiellement lesecarts entre les individus. Le processus de s election nop` ere plus sur la tness r eelle mais sur sonimage apr`es scaling. Parmi les fonctions de scaling, on peut envisager le scaling lin eaire et le scalingexponentiel. Soit la tness avant scaling et la tness modi ee par le scaling.

Scaling lin eaire

Dans ce cas la fonction de scaling est d enie de la facon suivante [Mic92] :

En r egle g enerale, le coefcient est inf erieur a un, ce qui permet de r eduire les ecarts de tness etdonc de favoriser lexploration de lespace. Ce scaling est statique par rapport au num ero de g enerationet p enalise la n de convergence lorsque lon d esire favoriser les modes dominants.

Scaling exponentiel

Il est d eni de la facon suivante [Mic92] (voir gure 1.7):

ou est la g eneration courante.

Pour proche de zero, on reduit fortement les ecarts de tness ; aucun individu nest vraimentfavoris e et lalgorithme g enetique se comporte comme un algorithme de recherche al eatoire etpermet dexplorer lespace.

22


23/187

s

f r

min

max

avg

f rf s

f

k=1

min maxavg

= k

k1

Figure 1.7: Fonction de scaling exponentielle

Pour proche de : le scaling est inop erant.

Pour les ecarts sont exag eres et seuls les bons individus sont s electionnes ce qui produitlemergence des modes.

Dans la pratique, on fait g eneralement varier des faibles valeurs vers les fortes valeurs au coursdes g enerations. Pour cela on peut utiliser la formule suivante :

etant la generation courante, le nombre total de g enerations prevues, un param`etre a choisir.Le choix de sest av ere pertinent dans les applications. L evolution de en fonction de lageneration est donnee par la gure 1.8.

Ce dernier principe de scaling donne effectivement de meilleurs r esultats sur nos probl` emes quele scaling lineaire et sera donc syst ematiquement utilis e. Dans le cas des fonctions objectifs multi-modes presentant des optimaux quasi- equivalents, cette technique de scaling, en ampliant les ecartsde tness en n de convergence, va effectivement favoriser le mode dominant mais aussi masquer

les modes sous-optimaux qui peuvent tout de m eme pr esenter un int eret. Le scaling permet donc unebonne exploration de lespace d etat mais ne favorise pas la r epartition des individus sur les diff erentsmodes de la fonction objectif.

1.3.3 Sharing

Introduction

Lobjectif du sharing est de r epartir sur chaque sommet de la fonction ` a optimiser un nombre din-dividus proportionnel ` a la tness associ ee a ce sommet. La gure 1.9 pr esente deux exemples derepartitions de populations dans le cas dune fonction ` a cinq sommets : le premier sans sharing, lesecond avec sharing.

23


24/187

k

nN

2

1

Figure 1.8: Allure de l evolution de en fonction des g enerations

AVEC SHARING (sans mutation)SANS SHARING (sans mutation)

Figure 1.9: Objectif du sharing

24


25/187

share

d

= 1

< 1

> 1

1

SH(d)

1

Figure 1.10: Allure de

Principe

De la meme facon que le scaling, le sharing consiste ` a modier la tness utilis ee par le processusde s election. Pour eviter le rassemblement des individus autour dun sommet dominant, le sharingpenalise les tness en fonction du taux dagr egation de la population dans le voisinage dun individu. Ilrequiert lintroduction dune notion de distance. Dans la pratique, il faut d enir une distance indiquantla dissimilarit e entre deux individus. Cette distance est alors utilis ee pour calculer la nouvelle tness

de la facon suivante :

avec

si

si

Le param`etre permet de delimiter le voisinage dun point et d epend du probl` eme traite.

La gure 1.10 donne lallure de pour differentes valeurs de . Suivant la valeur donn ee a lesharing sera plus ou moins efcace. Ainsi pour , on p enalise les groupes tr` es agglomeres.Dans la pratique ce type de sharing donne effectivement de bons r esultats mais au prix de

calculs de distances entre chromosomes ` a chaque generation pour une population de taille . Or lesalgorithmes g enetiques induisent une complexit e en sans sharing et le fait de passer en peutetre p enalisant, notamment pour grand.

Pour r eduire ce nombre, on utilise un sharing clusteris e.

1.3.4 Sharing clusteris e

Pour effectuer ce type de sharing [YG93], on commence par identier les diff erents clusters dindi-vidus dans la population. Ce dernier utilise deux param` etres et respectivement pour fusion-

25


26/187

ner des clusters ou en cr eer de nouveaux. Initialement, chaque individu de la population est consid erecomme le centre dun cluster. On applique alors successivement les deux principes suivants :

si deux centres sont ` a une distance inf erieure a , on fusionne ces derniers dans un clusterunique dont le centre r esultant est le barycentre des deux centres initiaux.

un nouvel individu est agr ege a un cluster si sa distance au centre le plus proche est inf erieurea . Dans ce cas, on recalcule le centre du cluster global. Sinon, on cr ee un nouveau clustercontenant ce seul individu.

Ce principe de fusion-agr egation permet dobtenir un nombre de clusters uctuant avec la r epartitiondes individus dans lespace d etat. On applique ensuite le principe de sharing en modiant les tnessde la facon suivante :

avec

: nombre dindividus contenus dans le cluster auquel appartient lindividu .

: coefcient de sensibilit e.

: distance entre lindividu et le centre du cluster .

On montre que ce type de sharing induit une complexit e en [YG93] pour des r esultatstout a fait comparables ` a ceux fournis par le sharing classique. Dans la pratique, on remarque que lereglage des coefcients et est assez delicat car lefcacit e de ces derniers d epend essen-tiellement de la connaissance a priori des distances inter-modes dans lespace d etat, distance quilest tr es difcile destimer. Nous pr esentons dans la section 1.4.3 une technique permettant de calculerautomatiquement ces quantit es.

1.3.5 Algorithmes g en etiques et recuit simul e

Introduction

Les algorithmes g enetiques et le recuit simul e etant deux techniques doptimisation stochastique tra-vaillant sur les m emes types de probl` emes, il est logique de chercher ` a les associer an de tirer par-tie de leurs avantages respectifs. Apr` es plusieurs evaluations de ces deux techniques sur les m emesprobl emes test, on remarque que le recuit simul e converge g eneralement plus vite vers la solutionoptimale lorsque le probl` eme est de taille raisonnable. Toutefois, il ne donne quune solution dans lecas des probl` emes multi-modes, ceci conrme les r esultats donn es dans [IR92a]. A linverse, les algo-rithmes genetiques fournissent plusieurs solutions quasi-optimales mais au prix dun temps de conver-gence g eneralement plus long. Il semble alors naturel dassocier ces deux techniques an dam eliorerla convergence des algorithmes g enetiques.

Il y a eu de nombreuses tentatives de fusion entre les algorithmes g enetiques et le recuit simul e,les travaux les plus int eressants etant ceux de Mahfoud et de Goldberg [MG92].

26


27/187

P 1 P 2

croisement

C 1 C 2P 1 P 2

C1 C2

POP(n)

TOURNOItirage aleatoire des couples E-P

selection par RS sur chacun des couples

Figure 1.11: Principe du croisement avec recuit simul e

Principe du croisement avec recuit simul e

Pour appliquer ce principe de croisement, on commence par s electionner deux parents et dansla population (voir gure 1.11). On applique ensuite lop erateur de croisement classique qui g eneredeux enfants et . Un tournoi est alors effectu e entre les parents et les enfants pour lequel lesdeux vainqueurs sont s electionnes par le sch ema de recuit suivant. On consid` ere lindividu . On tireensuite aleatoirement un des deux parents, soit ce parent :

si est meilleur que est s electionne.

sinon est s electionne avec la probabilit e :

ou est un coefcient d ecroissant en fonction de la g eneration courante ( ).

On fait de m eme pour avec le parent restant et lon d etermine ainsi deux individus et .L evolution de la variable se fait de la facon suivante. On utilise un sch ema de recuit standard

geometrique a un palier de basculement. Pratiquement, on calcule trois temp eratures dont les valeursdependent de la connaissance des ecarts et des tness de la population initiale.

Temperature initiale

Temperature de basculement

Temperature nale

ou repr esentent les ecarts minimum et maximum des tness de la population ini-tiale. Le schema g eometrique fait evoluer la temp erature courante de la facon suivante :

pourpour

27


28/187

avec .Pour chaque palier, on calcule le nombre dit erations de stabilisation ` a laide des formules :

Ces deux formules, nous permettent de calculer le nombre total de g enerations pour un probl` emedonn e.

Ce m eme principe de recuit simul e a ete essay e sur loperateur de mutation en faisant un sch emade recuit entre lindividu mut e et lindividu dorigine mais il ne produit pas leffet escompt e. Eneffet, on peut supposer que dans ce cas le recuit simul e r eduit le brassage de la population provoqu epar la mutation en limitant lespace explor e aux zones qui am eliorent statistiquement la tness eninterdisant les domaines qui la d egradent. Lexploration de du domaine admissible est fragilis ee. Ceconstat sur les probl` emes que nous avons test es ne permet pas de g eneraliser.

1.3.6 Recherche multi-objectifs

Introduction

Dans le cadre de la recherche multi-objectifs, on cherche ` a optimiser une fonction suivant plusieurscriteres, dont certains peuvent dailleurs etre antagonistes. On d enit alors la classique notion dedominance : on dit que le point domine le point si, , o u les represententles crit eres a maximiser. Lensemble des points qui ne sont domin es par aucun autre point forme lasurface de Pareto. Tout point de la surface de Pareto est optimal, dans la mesure o` u on ne peutameliorer la valeur dun crit` ere pour ce point sans diminuer la valeur dau moins un autre crit` ere.

Les algorithmes g enetiques peuvent permettre de trouver lensemble de la surface de Pareto, caril est possible de r epartir la population de lalgorithme g enetique sur la dite surface.

Technique employ ee

La technique que nous employons d erive directement des travaux de Jeffrey Horn et Nicholas Nafplio-tis ([HN93]). Le principal changement induit concerne le processus de s election : en multi-objectifs,comment va t-on d ecider quun individu est meilleur quun autre 3 ? On introduit alors une variante dela notion de dominance que lon d enit ainsi : on peut par exemple d ecider que l element domine

si le nombre des valeurs contenues dans son vecteur dadaptation qui sont sup erieures aux valeurscorrespondantes dans depasse un certain seuil. A partir de l` a, la technique propos ee pour effectuerla s election est simple : on tire deux individus au hasard ainsi quune sous-population 4 a laquelle ils

nappartiennent pas et qui va servir ` a les comparer.Trois cas se pr esentent alors :

si le premier element domine tous ceux de la sous-population et que ce nest pas le cas pour lesecond alors le premier sera s electionne.

inversement si seul le second domine lensemble de la sous-population alors cest lui qui seraconserv e.

3En ce qui concerne les autres op erateurs de base ` a savoir le croisement et la mutation il ny a aucune modication carceux-ci travaillent dans lespace d etat et non dans lespace r esultat.

4La sous-population tir ee aura une taille proportionnelle ` a celle de la population de d epart. Seule une partie des individusest utilisee, ce qui permet de r eduire le temps de calcul.

28


29/187

restent maintenant deux possibilit es : soit les deux sont domin es, soit les deux dominent. Onne peut se prononcer sans ajouter un autre test, cest pourquoi dans ce cas il est fait usage dunnouveau type de sharing qui op` ere sur lespace objectif.

Le sharing va conduire ` a s electionner celui des deux individus qui a le moins de voisins proches,autrement dit on elimine celui qui se situe dans une zone dagr egation pour conserver celui qui estdans une region moins dense.

Encore une fois, le terme voisin proche na pas de signication pr ecise mais il est possible dedenir un voisinage (aussi appel e niche) correct en se servant de la distance de Holder :

designant la -ieme composante du vecteur adaptation de l element . Le param`etre permet defaire varier la forme et la taille du voisinage. A lint erieur des voisinages ainsi d enis dans lespaceobjectif, il suft de compter le nombre dindividus pour favoriser les zones les moins denses et decette facon maintenir la diversit e de la population. Ainsi la gure 1.12 montre comment les voisinagessont choisis autour des individus de la r egion de Pareto lorsque ceux-ci ne peuvent etre d epartag essans sharing.

Ej

Ei

Voisinages

Rgion de Pareto

Element conserv => Ej

Figure 1.12: Surface de Pareto et voisinages

1.3.7 Association des AG avec des m ethodes locales

La grande force des algorithmes g enetiques est leur capacit e a trouver la zone de lespace des solutionscontenant loptimum de la fonction. En revanche, ils sont inefcaces lorsquil sagit de trouver lavaleur exacte de loptimum dans cette zone. Or, cest pr ecis ement ce que les algorithmes locauxdoptimisation r ealisent le mieux.

Il est donc naturel de penser ` a associer un algorithme local ` a lalgorithme g enetique de facon ` atrouver la valeur exacte de loptimum. On peut ais ement le faire en appliquant ` a la n de lalgorithmegenetique un algorithme local sur le meilleur element trouve. Cette technique est dautant plus ef-cace que lon utilise simultan ement du clustering, et que lalgorithme local est appliqu e a chaquemeilleur element de chaque cluster. En effet, on constate souvent que le meilleur element trouve par

29


30/187

lalgorithme g enetique ne reste pas le meilleur element apr`es am elioration par lalgorithme local detous les meilleurs elements de clusters.

Une autre technique consiste ` a utiliser un algorithme local associ e a lalgorithme g enetique pourcalculer la tness dun element. On peut, par exemple dans un espace fortement combinatoire, re-chercher avec lalgorithme g enetique les zones int eressantes de lespace en g enerant les elements,ladaptation de chaque element etant calculee par un programme doptimisation local (lin eaire parexemple). Un exemple de ce type est donn e dans la section 3.7.

En fait, lassociation AGm ethodes locales est une quasi-n ecessit e. Les deux m ethodes sont compl ementaireset ont des champs dapplication diff erents. Lalgorithme g enetique permet de faire disparaitre lacombinatoire du probl` eme, laissant alors le champ libre aux m ethodes locales dans chacune des zonesconnexes quil pense susceptible de contenir loptimum global.

1.4 Autres am eliorations

Les rafnements d ecrits dans cette section ont ete developp es au sein de notre equipe, et sont donc, enprincipe, originaux. Notons que lalgorithme g enetique que nous avons d evelopp e implante lint egralit edes techniques pr esent ees dans la section pr ecedente, celles pr esent ees dans cette section, ainsi queles diff erents types de parall elismes decrits dans la section 1.5. Nous pensons quil sagit dun desprogrammes les plus efcaces actuellement.

1.4.1 Croisement adapt e pour les fonctions partiellement s eparables

Introduction

Dans beaucoup de probl` emes doptimisation, la fonction ` a optimiser d epend de nombreuses variables,et peut se decomposer comme somme de sous-fonctions prenant en compte une partie des variablesseulement ([GT82]). Les algorithmes g enetiques sav`erent etre de bons outils doptimisation glo-bale en raison de leur capacit e a sortir des minima locaux. N eanmoins, leurs performances sontsouvent penalis ees par le caract` ere tr es al eatoire des op erateurs de croisement et de mutation. Pourremedier a ce ph enom ene, certains evolutionnistes utilisent des heuristiques qui permettent de favo-riser les bons croisements ou les bonnes mutations et d eviter les mauvaises. Nous pr esentonsici un operateur de croisement efcace, utilisable dans des probl` emes o u la fonction ` a optimiser peutse d ecomposer en somme de sous-fonctions positives ne d ependant pas de toutes les variables duprobl eme.

Apr es une presentation formelle du type de probl` emes auxquels sadresse cette m ethode, nouspresenterons lop erateur de croisement. Une illustration de lefcacit e de cette methode sera ensuitepropos ee au travers de plusieurs exemples simples comportant jusqu` a une cinquantaine de variables.Enn, [DAN94] propose une application de cet outil au classique probl` eme du Voyageur de Com-merce, largement etudi e dans la litterature, aussi bien pour son int eret pratique quen raison de sagrande complexit e [Bra90, GL85, GGRG85, HGL93, OSH89, WSF89]. En effet, pour tester la perfor-mance dun algorithme doptimisation globale, le probl` eme du Voyageur de commerce, NP-Complet,permet doffrir de nombreux exemples de tr` es grande taille comportant beaucoup doptima locauxdont on connat les solutions.

30


31/187

Probl emes concern es

Il sagit de probl` emes ou fonctions partiellement s eparables, `a savoir des probl` emes o u la fonction

a optimiser d epend de plusieurs variables , , .., , et peut se d ecomposer en somme de fonctionspositives ne d ependant pas de toutes les variables. On remarquera que bon nombre de fonctions

multiplicatives peuvent se transformer en fonction additives gr ace a des transformations simples. Onsint eresse donc aux fonctions pouvant s ecrire :

Soit lensemble des indices tels que soit une variable de :

Pour d enir notre op erateur de croisement, nous allons introduire pour chaque variable satness locale denie comme suit :

La tness locale associ ee a une variable isole sa contribution. Le but de cette section est de montrercomment utiliser cette tness locale pour d enir un operateur de croisement permettant de r eduire lataille des populations et de converger plus rapidement vers la solution optimale. Ces op erateurs sontparticuli erement efcaces lorsquon les combine avec le sharing.

Lop erateur de croisement

Lop erateur de croisement consiste, ` a partir de deux chromosomes parents, ` a cr eer deux nouveauxchromosomes.

Le codage que nous adopterons pour appliquer notre croisement consiste ` a repr esenter le chro-mosome par la liste brute des variables du probl` eme. Sil sagit de bits, nous aurons une liste de bits,sil sagit de variables r eelles, nous aurons une liste de r eels. On pourra eventuellement avoir un pa-nachage de diff erents types de variables. Lid ee intuitive est la suivante : dans le cas dun probl` emecompl etement separable, optimiser le probl` eme global peut se r eduire a loptimisation de chaquevariable separ ement. Nous essayons dadapter ce raisonnement au cas de fonctions partiellementseparables. La technique que nous proposons consiste donc ` a retenir pour chaque variable, lors dela conception des ls, celle des deux parents qui a la meilleure tness locale, ceci ` a un facteur pres.

Par exemple, dans le cas o` u lon cherche un minimum pour , pour laieme

variable, si :

alors le ls se verra affecter la variable du p ere . Si par contre :

il se verra affecter la variable du p ere . Si enn :

la variable du ls sera choisie al eatoirement.

31


32/187

Lors du croisement, on souhaite cr eer deux ls ` a partir de deux parents. Si lon applique la m emestrat egie pour le ls que celle decrite ci-dessus pour le ls , les deux ls risquent de se ressemblerfortement, surtout si est faible. Ceci nest pas souhaitable. On peut donc pour le deuxi` eme lschoisir une autre valeur de ce qui permet d etre plus ou moins d eterministe, ou alors, comme pourles techniques de croisement classiques choisir le compl ementaire du ls , a savoir affecter au lsla variable des deux p` eres non affect ee au ls .

On peut remarquer quil est facile dintroduire un op erateur de mutation qui sappuie sur le m emeprincipe et modie avec une plus forte probabilit e les variables ayant une mauvaise tness locale.

1.4.2 Mutation adaptative

Un des gros inconv enients de lalgorithme g enetique est sa mauvaise convergence locale. Il est pos-sible de rafner le comportement des AGs en utilisant une technique que nous qualions de mutationadaptative dans tous les probl` emes a variable reelle.

Le principe est le suivant : dans les probl` emes a variable reelle, loperateur de mutation consistegeneralement à ajouter un bruit gaussien ` a lelement de population concern e. Le problème est de bienchoisir ce bruit gaussien. Sil est trop petit, les d eplacements dans lespace sont insufsants en d ebutde convergence, et lalgorithme peut rester bloqu e dans un optimum local. Si le bruit est trop fort, lAGtrouvera certes une zone contenant loptimum, mais sera incapable de converger localement. Il sagitdonc de modier le bruit au l des g enerations. Pour ce faire, on calcule l ecart moyen pour chacunedes coordonn ees entre le meilleur element a la g eneration et tous les autres elements : ce nombre estalors utilise comme ecart type du bruit gaussien sur la coordonn ee en question ` a la g eneration .

Lefcacit e de cette methode est demontr ee dans la section 2.1.1.

1.4.3 Clustering adaptatif Nous avons vu dans la section 1.3.4 une technique de sharing clusteris e permettant de diminuer lacomplexite du sharing traditionnel. Cependant, comme nous lavons soulign e, les quantit es et

sont difciles ` a calculer à priori. Nous pr esentons ici un algorithme permettant de calculerautomatiquement ces quantit es de facon adaptative pendant lex ecution de lalgorithme g enetique.

Au d epart on initialise le processus avec et . Ensuite à chaque generation onutilise ce qui suit :

1. Calcul de et :

2. Evaluation de la distance moyenne des individus par rapport aux centrodes des clusters :

si lon note le centre du groupe et le nombre total de clusters.

3. on compte ensuite le nombre de clusters dont le meilleur individu a une tness sup erieure a uncertain pourcentage 5 de celle du meilleur element de la population , on le note

5Egal au taux de sharing.

32


33/187

4. on met `a jour le param` etre en utilisant la r` egle :

si etsi et

reste inchang e dans les autres cas

Les valeurs et designent deux seuils : si beaucoup de clusters sont sufsamment bons (cesta dire quand leur proportion d epasse ) alors on diminue et pour accrotre le nombretotal de groupes et ainsi chercher dautres optima. Au contraire, sils sont peu nombreux alors onva diminuer la quantit e de clusters en augmentant les deux distances an de rechercher des zonesinteressantes de lespace d etat.Les valeurs utilis ees habituellement pour les seuils sont et .

Cette technique donne dexcellents r esultats pour rechercher les optima multiples de fonctions

reelles.

1.5 Parall elisme

Lint eret de la parall elisation des algorithmes g enetiques est de gagner en temps de calcul. Il existepour cela au moins deux m ethodes utilis ees classiquement (on pourra se reporter ` a [BD93],[CJ91],[Muh89],[PLG87]et [SPF93] pour plus de pr ecisions sur les mod` eles de parall elisme utilisables dans les AG):

la premi ere consiste ` a diviser la population de taille en sous-populations et ` a les r epartirsur lensemble des machines dont on dispose.

la seconde maintient la population totale sur une seule machine mais se sert des autres pour yenvoyer les evaluations an quelles se fassent en m eme temps.

Dans les deux cas il est n ecessaire davoir un m ecanisme de communication inter-processus. Lesresultats present es ici ont ete obtenus en utilisant PVM. PVM a ete r ealis e par le Oak Ridge NationalLaboratory. Il permet ` a un r eseau h eterog ene de machines dapparatre comme une seule entit e ayantplusieurs processeurs capables de communiquer entre eux (comparable ` a un ordinateur ` a m emoiredistribu ee). La communication entre les divers composants de cette machine virtuelle se fait par len-voi de paquets contenant des donn ees ou encore des messages de contr ole. Pour plus de d etails, onpeut se reporter ` a [GBD 94].

1.5.1 Parall elisme par lotsLid ee ici est de faire fonctionner plusieurs algorithmes g enetiques en parall` ele avec une popula-tion r eduite pour chacun. Le programme matre lance occurrences du programme dalgorithmesgenetiques appel ees esclaves sur des machines diff erentes en passant ` a chacune les param` etres n ecessairesa leur bon fonctionnement comme le montre la gure 1.13.

Ensuite chaque processus fait evoluer sa population ind ependamment jusqu` a ce quil decide (se-lon une probabilit e x ee a lavance) de rassembler ses meilleurs individus pour en transmettre unecertaine quantit e (proportionnelle ` a la taille de la population) ` a une autre machine de son choix. Lamachine receptrice int`egre alors ces nouveaux elements dans sa propre population en eliminant lesmoins bons de ses individus. Lint eret du parallelisme par lots est quil offre la possibilit e de travail-ler sur de grandes populations ( ) tout en donnant des r esultats dans un temps raisonnable puisque

33


34/187

SLAVE 2SLAVE 1 SLAVE N

MASTER

Population taille n Population taille n Population taille n

RsultatsRsultats

Rsultats

Envoi des meilleurs lments

Paramtres initiaux

Figure 1.13: Principe de fonctionnement du parall elisme par lots

la dur ee n ecessaire est ` a peu de choses pr` es celle quil faudrait pour une population de taille siest le nombre dordinateurs disponibles et si lon n eglige les temps de communication.

La m ethode introduit un clustering forc e car chaque lot peut etre considere comme un clustersubdivis e en petits groupes. Chaque machine a la possibilit e de converger vers des optima qui serontdiff erents de ceux calcul es sur les autres ce qui correspond au comportement introduit avec le clus-tering. Dautre part, le surco ut de temps pass e pour les communications nest a priori pas excessif puisquil ny a de gros paquets ` a transmettre que de temps en temps. Il faut tout de m eme garder `alesprit quune subdivision en sous-populations de taille trop r eduite risque de conduire ` a faire tournerdes algorithmes g enetiques non ables statistiquement. En effet, il faut quand m eme quune popula-

tion contienne sufsamment dindividus pour que lespace d etat puisse etre explore de facon correctean que les r esultats aient une certaine valeur.

Des tests ont ete faits par Yann LeFablec [LeF95]pour d eterminer lefcacit e de la methode (voirgure 1.14). Il ne faut sattacher qu` a la forme g enerale de la courbe, dans la mesure o` u les chargeslocales des machines peuvent modier de facon sensible les r esultats. Lefcacit e de la methode estcependant largement mise en evidence.

1.5.2 Parall elisation des calculs

Contrairement ` a la m ethode qui vient d etre d ecrite qui divise la population totale, on utilise ici desdemons de calcul de tness dont la seule fonction est de recevoir un individu et de renvoyer sonadaptation. Pour utiliser la puissance de calcul parall` ele offerte de mani` ere optimale, il faut retarder aumaximum les calculs pour les envoyer en blocs aux d emons et faire en sorte quaucun ne reste inactif.Le principe se trouve r esum e sur la gure 1.15 : le programme matre se charge de faire la s election,les croisements, etc. . . en dautres termes il fait evoluer la population, puis r epartit les calculs dont ila besoin sur lensemble des d emons. Enn, d` es quil a recu tous les r esultats, lalgorithme commenceune nouvelle g eneration.

Il faut noter que ce m ecanisme demande un grand nombre de communications pour envoyer lesdonn ees et les evaluations. La m ethode nest donc int eressante que si le temps pass e pour un calculdadaptation est grand devant le temps de communication, elle sera par cons equent utilisee pour desprobl emes dont les evaluations de tness prennent du temps, on pense essentiellement ` a des cas faisantappel a des r eseaux de neurones ou ` a de gros calculs matriciels.

34


35/187

0

200

400

600

800

1000

1200

1400

1600

1800

1 2 3 4 5 6 7 8

Figure 1.14: Evolution des temps de calcul

MASTER

Population taille n

DEMON 1 DEMON NDEMON 2

Envoi dune donne valuer

Envoi du rsultat

et de la donne

Figure 1.15: Principe de fonctionnement de la parall elisation des calculs

35


36/187

0

20

40

60

80

100

120

140

160

180

200

0 5 10 15 20 25 30

T e m p s

Nombre de machines50

100

150

200

250

300

350

400

450

8 10 12 14 16 18 20 22 24 26 28 30

communication*1communication*20communication*40

Figure 1.16: Evolution du temps de calcul

La courbe 1.16 montre comment evolue le temps de calcul en fonction du nombre de machines etdu temps de communications. On constate que plus on utilise de machines, plus la p enalisation dueaux communications est forte.

1.5.3 Conclusion

La parallelisation est extr emement efcace pour acc elerer les temps de r esolution des algorithmesgenetiques. Il faut certes bien etudier le probl` eme an dutiliser le bon m ecanisme de parall elisme,mais les gains en temps sont alors importants.

1.6 R esultats th eoriques sur les algorithmes binaires

Historiquement, les algorithmes g enetiques binaires sont les plus anciens et ont donc ete les plusetudi es sur le plan th eorique. Goldberg [Gol89a] a largement d evelopp e cette theorie r esum ee dans[AS92]. Nous allons tout dabord les etudier avant de pr esenter les mod elisations theoriques bas eessur les chanes de Markov.

1.6.1 D enitions fondamentales

Denition 1.1 (S equence) On appelle s equence de longueur une suite avec.

En codage binaire, les chromosomes sont des s equences.

Denition 1.2 (Sch ema) On appelle sch ema de longueur une suite avec.

Une en position signie que peut etre indifferemment ou .

Denition 1.3 (Instance) Une s equence est une instance dun sch ema si pour tout tel que on a .

36


37/187

Ainsi, est un schema et les sequences et sont des instances de(ce sont meme les seules).

Denition 1.4 (Position xe, position libre) Soit un sch ema . On dit que est une position xe desi ou . On dit que est une position libre de si .

Denition 1.5 (Ordre dun sch ema) On appelle ordre du sch ema le nombre de positions xes de. On note lordre de .

Par exemple, le sch ema a pour ordre , le sch emaa pour ordre . On remarquera quun sch ema de longueur et dordre admet

instances diff erentes.

Denition 1.6 (Longueur fondamentale) On appelle longueur fondamentale du sch ema la distance

s eparant la premi ere position xe de de la derni ere position xe de . On note cette longueur fon-damentale .

Ainsi, le sch ema a pour longueur fondamentale , le sch emaa pour longueur fondamentale , et pour le schema

nous avons .

Denition 1.7 (Adaptation dune s equence) On appelle adaptation dune s equence une valeur positive que nous noterons .

est la fonction objectif ou tness du probl` eme a r esoudre.

Denition 1.8 (Adaptation dun sch ema) On appelle adaptation dun sch ema la valeur

ou les d ecrivent lensemble des instances de , cest- a-dire la moyenne des adaptations de sesinstances.

1.6.2 Effets de la reproduction

Soit un ensemble de sequences de bits tir ees al eatoirement. Durant lareproduction, chaque s equence est reproduite avec une probabilit e :

Supposons quil y ait ` a linstant un nombre de s equences repr esentant le sch emadans la population . A linstant , statistiquement, ce nombre vaut :

Posons

37


38/187

repr esente la moyenne de ladaptation des s equences `a linstant . La formule pr ecedente devient :

Posons . On obtient alors :

Il est donc clair quun sch ema, dont ladaptation est au-dessus de la moyenne, voit son nombre derepresentants augmenter, suivant une progression qui est de type g eometrique si nous faisons lap-proximation que est constant dans le temps. Alors :

Si la reproduction seule etait en jeu, les sch emas forts elimineraient tr` es rapidement les sch emas

faibles.

1.6.3 Effets des croisements

Nous allons nous int eresser a la probabilit e de survie dun schema lors dune op erationde croisement. Par exemple, soit le sch ema . Supposons quune instance de ceschema soit crois ee avec une autre instance. Quelle est la probabilit e pour que la s equence resultantesoit encore une instance de ? Il est impossible de r epondre exactement ` a la question, tout au pluspeut-on donner une borne inf erieure de cette valeur. Il est clair que ne sera pas d etruit si le site decroisement qui est tir e au sort est inf erieur a 3 (avant le premier 1) ou sil est sup erieur a 6 (apr es ledernier 1) 6 .

On voit donc imm ediatement quune borne inf erieure de la probabilit e de d etruire un sch emaest . Donc la probabilit e de survie dans un croisement est . Si dautrepart on ne croise quune fraction de s equences dans une population donn ee, la probabilit e de survieest donnee par :

De ce r esultat et des r esultats precedents decoule la loi d evolution dune population 7 :

1.6.4 Effets des mutations

Soit la probabilite de mutation dun bit dans une s equence. Dans un sch ema , seules les positionsxes peuvent etre d etruites. La probabilit e de survie dun bit etant , la probabilit e de surviedun schema contenant positions xes est . La probabilit e de mutation etantsuppos ee petite devant , un d eveloppement limit e au premier ordre donne une probabilit e de survieegale a .

L equation nale s ecrit donc :

6Dans tous les autres cas, peut etre (ou ne pas etre) d etruit.7Les croisements et les mutations se font sur la population reproduite, et non sur la population initiale.

38


39/187

1.6.5 Conclusion sur le codage binaire

Des calculs pr ecedents decoulent deux r esultats :

les sch emas dont la longueur fondamentale est petite sont plus favoris es que les autres, lors dela g eneration dune nouvelle population.

les sch emas dont lordre est petit sont plus favoris es que les autres, lors de la g eneration dunenouvelle population.

Ces r esultats conditionnent la qualit e du codage des donn ees. En effet, les sch emas qui codentles donnees int eressantes pour le probl` eme considere doivent avoir un ordre et une longueur fonda-mentales faibles 8 , alors que les donn ees sans int eret doivent etre cod ees par des sch emas qui ont unordre et une longueur fondamentale elev es.

Les r esultats present es ci-dessus ne sont quune introduction ` a la th eorie des sch emas, il existede nombreux approfondissements. On trouvera dans les r eferences suivantes les principaux mod` elestheoriques sur la th eorie des sch emas et ses extensions : [Gol89c, Vos91, BM93, Gol89b, BG87, CS88,BM94, DM92, SGE91]

1.7 Mod elisation par cha ne de Markov

Cette dernière approche est la plus satisfaisante tant sur le plan math ematique, que sur celui de lamod elisation, les diff erents operateurs etant pr esent es comme perturbant un processus Markovienrepresentant la population ` a chaque etape. Ici encore il apparat que seul lop erateur de mutation estimportant, le croisement pouvant etre totalement absent.

Les principaux r esultats asymptotiques portant directement sur les algorithmes g enetiques, ont etedevelopp es par R. Cerf [Cer94] sur la base des travaux de Catoni [Cat90] et de Trouv e [Tro93]. Cestravaux se fondent sur la th eorie des petites perturbations al eatoires dun processus dynamique detype Markovien. Plus particuli` erement, la th eorie de Freidlin et Wentzell [FW83] constitue la pierredangle de ces etudes. Nous donnons ici, quelques uns des r esultats de la dynamique des algorithmesgenetiques developp es par Cerf. Nous les pr esentons simpli es et dans un cadre restreint, laissant lelecteur interess e se reporter ` a la difcile lecture des r eferences citees.

Nous travaillerons sur la base dun codage binaire, representant le nombre de bits utilis es pourle codage. La fonction d evaluation, est d enie sur lespace a valeurs dans .Le problème est donc de localiser lensemble des maxima globaux de , ou, a d efaut, de trouver

rapidement et efcacement des r egions de lespace o` u se situent ces maxima.Comme nous lavons vu, lalgorithme g enetique est un algorithme stochastique it eratif qui opèresur des ensembles de points, et qui est b ati a laide de trois op erateurs: mutation, croisement etselection, que nous pr esentons plus formellement ` a pr esent.

1.7.1 Description rapide dun algorithme g en etique

Soit la taille (xe) de la population, notons la population de la g eneration : il sagit dunematrice de dont les elements sont des chanes de bits (chromosomes)

8Les donnees int eressantes sont bien entendu les donn ees qui sont proches de la solution optimale. Un bon codage desdonn ees implique donc davoir une id ee de la forme de loptimum.

39


40/187

de taille . Le passage de la g eneration a l ag eneration cest a dire de a se d ecomposeen trois etapes :

Chacune de ces etapes peut etre modelisee formellement.

Mutation

Lop erateur consid ere ici est le suivant : pour chaque composante de chaque element une va-riable de Bernouilli de param` etre est tir ee ind ependamment et suivant le r esultat lelement binaireexamin e est change ou non. ( est change en et en ).

La probabilit e de mutation doit etre pr ealablement choisie et est g eneralement faible.Comme nous le verrons par la suite, cet op erateur joue un r ole cl e dans la convergence de lalgo-

rithme genetique.

Croisement

Lop erateur etudi e ici est loperateur a un point (slicing crossover). Ici encore, la probabilit e de croi-sement est x ee initialement. Pour construire la population couples sont form es a partirde la population (par exemple en appariant les individus cons ecutifs de , ou bien en choisissantau hasard et uniform ement des individus dans ). Pour chaque couple, une variable de Bernoulli deparam etre est tir ee pour decider si le croisement a lieu. Si cest le cas, un site de coupure est tir e

au hasard, et les segments naux des deux chromosomes sont echang es.Une nouvelle paire dindividus est ainsi obtenue (identique ` a lancienne sil ny a pas eu de croi-

sement) et est stock ee dans la population . En g eneral, le param` etre est choisi grand.Remarquons que les op erateurs de mutation et de croisement ne font pas intervenir la fonction ,

ce sont des op erateurs stochastiques dexploration. Cest le troisi` eme et dernier op erateur, la s election,qui guide la population vers les valeurs elev ees de la fonction

Selection

Les individus de la population sont obtenus apr` es s election des individus de . On conserve

ainsi les meilleurs individus de independamment ` a laide dune distribution de probabilit e quifavorise les individus de les mieux adapt es.

Le choix le plus fr equent est lunique distribution telle que la probabilit e dun individu soit pro-portionnelle ` a son adaptation, i.e la probabilit e de s election de lindividu est :

En tirant les individus dans la population conformement aux probabilit es , on constitue lanouvelle generation .

40


41/187

1.7.2 Mod elisation

La pr esentation rapide des op erateurs nous permet de mod eliser la suite des en une chane

de Markov, despace d etats . Lalgorithme g enetique ne doit donc pas etre interpretecomme une proc edure doptimisation mais plut ot comme une marche al eatoire dans lespace d etat,attiree vers les fortes valeurs de .

La propriete premi ere de cette formalisation est que la loi de est d etermin ee de manière uniquepar :

la loi de la generation initiale

lem ecanisme de transition de a mecanisme scind e en trois etapes detaill ee pr ecedemment.

Ce m ecanisme de transition poss` ede toutefois des propri etes essentielles qui font lint eret et lapuissance de cette formalisation, (voir [Cer94]) :

Il est homogène (cest à dire independant de la g eneration, consid eree)

Il est irr eductible, (la probabilit e de joindre deux points quelconques de lespace d etat, en unnombre ni de g enerations est non nulle) soit :

Le m ecanisme permet donc dexplorer tout point de lespace d etat, avec une probabilit e nonnulle.

Il est aperiodique, cette hypoth` ese nest cependant pas fondamentale.

Ces proprietes permettent de conclure ` a lergodicite de la chane de Markov, et ` a lexistence dunprocessus limite.

Th eor eme 1.1 Une cha ne de Markov homog ene irr eductible ap eriodique despace d etats ni est ergodique et poss ede une unique mesure de probabilit e stationnaire ou invariante.

Cette mesure stationnaire correspond ` a la loi regissant lequilibre du processus, elle est d enie ,pour tout comme:

Nous savons egalement que tout element de lespace d etat est de probabilit e non nulle pour cettemesure.

Toutefois, si ce r esultat nous permet de savoir quil existe une dynamique de fond de lalgorithmegenetique, il nous reste ` a en d eterminer les propri etes, linuence des op erateurs (et des param` etresassoci es) qui jouent un grand r ole dans le processus.

Pour cela nous introduisons les notations suivantes :Si est un element de et un point de , nous noterons :

De manière g enerale, les lettres designent des populations, i.e. des elements de ,et les lettres des points de .

41


42/187

Processus de fond

Cest a partir de ce processus de fond quest reconstitu e lalgorithme g enetique en etudiant ses per-

turbations al eatoires par les diff erents operateurs. Il est d eni comme processus limite, lorsque lesperturbations ont disparu. Cest egalement une chane de Markov sur dont le mecanisme de tran-sition est tr`es simple puisque correspondant ` a la situation limite suivante :

Les composantes de sont choisies ind ependamment et suivant la loi uniforme sur len-

semble

Les individus dont ladaptation nest pas maximale en , sont elimin es et napparaissent pasdans la generation

Les individus dont ladaptation est maximale, ont des chances de survies egales

Cette chane est tout dabord pi egee dans lensemble des populations ayant la m eme adaptation(ou ensemble des population d equi-adaptation ),

Cette population repr esente les attracteurs de la chane (voir 1.7.3 plus loin), puis elle est absorb eepar une population uniforme, de sorte que :

Lorsque la population est devenue uniforme et en labsence ici de perturbations, il ne se passe plusrien.

Ceci peut egalement se traduire en d enissant les populations uniformes comme les etats absor-bants de la chane Nous allons maintenant etudier la situation o` u ce processus est perturb e.

Processus perturb e

La mod elisation propos ee par Cerf, part du processus de fond decrit ci-dessus, qui est per-turbe al eatoirement, les perturbations sont indic ees par le param` etre La chane de Markovdevient donc une suite de chanes de Markov dont le mecanisme de transition est donn e par lasuccession des transformations g enerees par les op erateurs.

Il nous faut pour cela mod eliser precis ement les operateurs.

MutationLes mutations sont d enies comme de petites perturbations al eatoires independante des individus,

de la population . Il est assez naturel dintroduire la probabilit e de transition 9 de mutationentre les points et de comme un noyau Markovien

Trivialement on a :

9Cest la probabilit e pour un point de de se transformer par mutation en un point de

42


43/187

Sur la chane la probabilite de transition entre les points et de est:

Plus pr ecisement et an danalyser la dynamique de lorsque tend vers linni, nous repor-tons ici les hypoth` eses sur le mode et la vitesse de convergence des probabilit es de transition. Pourcela nous supposons lexistence dun noyau irr eductible, sur i.e. :(cest a dire un chemin dans ) tels que et tels que :

Lhypoth`ese dirreductibilite du noyau est essentielle, elle assure que tout point de lespace estpotentiellement visitable.

La vitesse de convergence du noyau est caracterisee par le reel positif tel que admette ledeveloppement suivant :

(1.1)

La condition de positivit e de nous permet de faire disparatre les perturbations lorsque tendvers linni.

(1.2)

Croisement Ici encore lop erateur est mod elise comme effectuant de petites pertur-bations aleatoires sur des couples de la population . Ces couples sont ici form es par les elementssuccessifs de la population, les transitions sont g erees par le noyau Markovien sur cettefois, de sorte que :

Pour ce noyau nous supposerons lexistence dun noyau irr eductible sur , la vitesse deconvergence est alors param etree par le reel positif tel que :

(1.3)

Levanouissement asymptotique des croisements est egalement impos ee par la positivit e de :

(1.4)

43


44/187

Selection Cest loperateur le plus compliqu e et egalement le plus importantpuisquil permet la convergence vers les optima de

Il est modelise a laide dune fonction de s election dont Cerf nous donne une d enition precise,pouvant etre r esum ee par :

telle que :

1. est une probabilit e sur

2. Cette probabilit e est independante de lindexation des (on peut permuter les )

3. La probabilit e favorise les elements associ es a des valeurs elevees (i.e.)

Cet outil nous permet d ecrire la probabilit e de transition correspondant ` a la derni`ere etape.

Ceci signie que la probabilit e de transition est le produit des probabilit es sur chacune descomposantes de

La probabilit e entre deux composantes est donnee par

De m eme que pour les autres op erateurs, la fonction de s election doit etre choisie et sa vitesse deconvergence caract erisee

(1.5)

Ce choix correspond bien ` a une probabilit e de s election avantageant les

Documents

Techniques d’optimisation stochastique appliqu´ees