Principes Mathématiques et Utilisations des Algorithmes Génétiques

Christophe Bontemps¹

18 Novembre 1995

Pdf Version
Abstract: Un algorithme génétique est un ``algorithme stochastique itératif'' qui opère sur des ensembles de points codés, à partir d'une population initiale, et qui est bâti à l'aide de trois opérateurs : croisement, mutation, sélection. Les deux premiers sont des opérateurs d'exploration de l'espace, tandis que le dernier fait évoluer la population vers les optima d'un problème. Nous détaillons ici les principes de fonctionnement de ces opérateurs ainsi que les fondements mathématiques sur lesquels ils reposent.

Ces méthodes ne se réduisent cependant pas à la simple recherche d'optima d'une fonction, et s'avèrent être également de puissants outils pour l'analyse de situations dynamiques complexes comme l'on en rencontre sur les marchés financiers, ou en théorie des jeux (voir Axelrod [6]). On peut ainsi modéliser les comportements d'agents ou de stratégies et examiner la survie et l'évolution de ceux-ci, c'est à dire l'émergence de certaines stratégies dominantes.

1 Introduction

Par définition même l'étude de l'économie se base sur l'optimisation, et les deux mots sont souvent associés. La sophistication des modèles économiques conduit de plus en plus souvent à des problèmes d'optimisation toujours plus complexes. Le seul contexte des modèles dynamiques nous fournit bon nombre de problèmes de résolution ou d'estimation. Les études économiques s'en trouvent limités, et le modélisateur doit alors incorporer des contraintes techniques pour faire face à ces problèmes. Cette situation est quelque peu paradoxale, si l'on considère l'augmentation des moyens et des puissances de calcul disponibles².

Un grand nombre de méthodes économétriques, comme les moindres carrées généralisés et le maximum de vraisemblance, reposent sur la maximisation d'une fonction souvent complexe. Parmi toutes les méthodes d'optimisation, les méthodes de gradient sont les plus exigeantes en matière de conditions nécessaires de convergence. Ce sont des méthodes d'optimisation locales, qui connaissent une grande popularité. Pour le maximum de vraisemblance, Cramer [CRAMER], recense les désagréments possibles lors de l'application de cette méthode. L'algorithme de maximisation peut ainsi ne pas converger en un temps acceptable, il peut ``s'éloigner'' et donner des valeurs infinies pour certaines composantes des paramètres, il peut également boucler, et revenir sans cesse au même point, etc.... Ces algorithmes d'optimisation conventionnels³ (de la famille du gradient ou de Newton-Raphson) sont des algorithmes ``grimpeurs'' qui se basent sur l'évaluation préalable du gradient, la pente, pour déterminer la direction de recherche de l'optimum. Goffe et al. [16] comparent cette situation à celle d'un aveugle cherchant le sommet d'une montagne. La connaissance du terrain passe alors uniquement par ses pieds. Pour peu que le terrain soit régulier et le point de départ bon, il atteindra le sommet. Toutefois ces deux conditions sont rarement simultanément réalisées. Avec beaucoup de chance, c'est à dire avec une très bonne sensibilité et beaucoup de points de départs, il pourra atteindre le sommet pour autant que ce dernier soit unique. De plus, les hypothèses sur les fonctions à optimiser sont souvent tres fortes⁴, et ne sont pas vérifiées dans la pratique.

A l'inverse, les techniques de recherche aléatoires pures ne requièrent aucune hypothèse particulière sur la fonction d'évaluation et explorent l'espace sans tirer partie des propriétés de la fonction objectif. Les algorithmes génétiques et le recuit simulé se situent entre ces deux extrêmes.

Une des particularités séduisantes des algorithmes génétiques et du recuit simulé, réside dans l'absence d'hypothèses particulière sur la régularité de la fonction objectif. Aucune hypothèse sur la continuité de cette fonction n'est requise, ses dérivées successives ne sont pas nécessaires, ce qui rend très vaste le domaine d'application de ces algorithmes.

Les premiers travaux sur les algorithmes génétiques ont commencé dans les années cinquante lorsque plusieurs biologistes américains ont simulé des structures biologiques sur ordinateur. Puis entre 1960 et 1970, John Holland [18], sur la base des travaux précédents, développa les principes fondamentaux des algorithmes génétiques dans le cadre de l'optimisation mathématique. Malheureusement, les ordinateurs de l'époque n'étaient pas assez puissants pour envisager l'utilisation des algorithmes génétiques sur des problèmes réels de grande taille. L'ouvrage de Goldberg [17] qui décrit l'utilisation des algorithmes génétiques dans le cadre de résolution de problèmes concrets a permis de mieux faire connaître ces derniers et a marqué le début d'un nouvel intérêt pour ces techniques.

Le peu d'hypothèses requises sur la fonction objectif permet de traiter des problèmes très complexes. La fonction objectif peut ainsi être le résultat d'une simulation. On peut même imaginer, pour régler certains paramètres de l'algorithme génétique lui-même tels que la taille de la population, les différents pourcentages de croisement et de mutation, d'utiliser un algorithme génétique. La rapidité de convergence du premier devenant ainsi fonction d'évaluation du second.

Ces méthodes ne se réduisent cependant pas à la simple recherche d'optima d'une fonction, et s'avèrent être également de puissants outils pour l'analyse de situations dynamiques complexes comme l'on en rencontre sur les marchés financiers, ou en théorie des jeux (voir Axelrod [6]). On peut ainsi modéliser les comportements d'agents par des suites d'éléments binaires correspondant à des stratégies et examiner la survie et l'évolution de ces agents, c'est à dire l'émergence de certaines stratégies⁵.

Ces méthodes ne sont apparues que très récemment dans la littérature économique et économétrique. Pourtant les modèles économétriques actuels génèrent bon nombre de problèmes de maximisation sur des espaces de dimensions grandissantes. Dorsey et Mayer [12] ont ainsi étudié récemment onze problèmes économétriques classiques en utilisant six procédures de maximisation différentes et leurs conclusions sont élogieuses envers les algorithmes génétiques. Andréoni et Miller [2] ont utilisé cet outil pour organiser des enchères, remplaçant les agents par des algorithmes adaptatifs basés sur des algorithmes génétiques. De leur étude, quoique fort restrictive, résulte une meilleure connaissance des procédures menant à l'équilibre de Nash dans différent types d'enchères.

Holland et Miller [19] proposent d'étendre encore le champ de ces techniques par l'utilisation d'Agents Artificiels Adaptatifs (AAA). Ils concluent leur article ainsi :

``By executing these models (AAA) on a computer we gain (..) an opportunity to check the various unfolding behavior for plausibility, a kind of ``reality check''. Whether or not agents behave in an optimal manner, the very act of contemplating such systems will lead to important questions and answers.''
Nous proposons ici une présentation simple de ces nouveaux outils que sont les algorithmes génétiques et le recuit simulé. Notre but est d'expliquer les mécanismes généraux de ces algorithmes et d'en faire découvrir les usages et potentialités. La présente section est consacrée aux principes généraux qui animent ces algorithmes. Des illustrations mathématiques, économiques et économétriques sont présentés dans la section 4.. Nous proposons une synthèse des résultats théoriques les plus récents dans la section 5. Ces résultats sont apparus très tardivement, probablement à cause de la complexité induite par ces algorithmes et il faudra attendre 1993 pour qu'une démonstration complète et rigoureuse de convergence stochastique soit établie par R. Cerf [11]. La section 6 est consacrée aux perspectives qu'offrent ces outils dans les différents domaines de l'économie mathématique et de l'économétrie. En outre, nous donnons en appendice le traitement complet d'un exemple simple.

2 Principes

Les algorithmes génétiques sont des procédures qui s'inspirent des mécanismes de sélection naturelle et des phénomènes génétiques. Le principe de base consiste à simuler le processus d'évolution naturelle dans un environnement hostile. Ces algorithmes utilisent un vocabulaire similaire à celui de la génétique, cependant, les processus auxquels ils font référence sont beaucoup plus complexes.

On parlera ainsi d'individu dans une population. L'individu est composé d'un ou plusieurs chromosomes. Les chromosomes sont eux-mêmes constitués de gènes qui contiennent les caractères héréditaires de l'individu. Les principes de sélection, de croisement, de mutation introduits dans ce cadre artificiel, s'appuient sur les processus naturels du même nom.

Pour un problème d'optimisation donné, un individu représente un point de l'espace d'état. On lui associe la valeur du critère à optimiser. L'algorithme génère ensuite de façon itérative des populations d'individus sur lesquelles on applique des processus de sélection, de croisement et de mutation. La sélection a pour but de favoriser les meilleurs élements de la population, tandis que le croisement et la mutation assurent une exploration efficace de l'espace d'état.

2.1 Principes généraux des algorithmes génétiques

Le mécanisme consiste à faire évoluer, à partir d'un tirage initial, un ensemble de points de l'espace vers le ou les optima d'un problème d'optimisation. l'ensemble du processus s'effectue à taille de population constante, que nous notons N. Par analogie avec la génétique, on parle alors de générations successives. L'ensemble du processus s'effectue à taille de population constante, que nous notons N, de sorte que les générations successives comportent toutes N individus.

Afin de faire évoluer ces populations de la génération k à la génération k+1, trois opérations (voir figure ??) sont effectuées pour tous les individus de la génération k :

ftbpFUX13.9991cm15.0007cm0ptPrincipe général des Algorithmes GénétiquesPRINCIPEchromoso.epslanguage "Scientific Word";type "GRAPHIC";display "FRAME";valid_file "F";width 13.9991cm;height 15.0007cm;depth 0pt;cropleft "0";croptop "0.9783";cropright "1.2037";cropbottom "0";filename 'C:/CHRIS/ALGOS/CHROMOSO.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1SO4X3.EPS';

Une sélection d'individus de la génération k est effectuée en fonction du critère à optimiser ou plus généralement du critère d'adaptation au problème (fitness), on cherche ainsi à privilégier la reproduction des ``bons'' éléments au détriment des ``mauvais⁶''.

Des opérateurs d'exploration de l'espace sont ensuite utilisés pour ``élargir'' la population et introduire de la nouveauté d'une génération sur l'autre.
L'opérateur de croisement est appliqué avec une probabilité P_c à deux éléments de la génération k (parents) qui sont alors transformés en deux nouveaux éléments (les enfants) destinés à les remplacer dans la génération k+1.
Certaines composantes (les gènes) de ces individus peuvent ensuite être modifiés avec une probabilité P_m par l'opérateur de mutation. Cette procédure vise à introduire de la nouveauté dans la population.

Cette procédure en trois points est ensuite renouvelée à taille de population constante. Les critères d'arrêts sont alors de deux natures :

Arrêt après un nombre de générations fixé a priori. C'est la solution retenue lorsqu'un impératif de temps de calcul est imposé.
Arrêt lorsque la population cesse d'évoluer ou n'évolue plus suffisamment rapidement, on est alors en présence d'une population homogène dont on peut penser qu'elle se situe à proximité du ou des optimums.

Il est a noter qu'a ce stade, aucune certitude concernant la bonne convergence de l'algorithme n'est assuréée. Comme dans toute procédure d'optimisation l'arrêt est arbitraire, et la solution ``en temps fini'' ne constitue qu'une approximation de l'optimum.

Pour utiliser un algorithme génétique sur un problème particulier on doit disposer des cinq éléments suivants :ftbFU14.5658cm3.1302cm0ptModélisation et codagecodagecodage.epslanguage "Scientific Word";type "GRAPHIC";display "PICT";valid_file "F";width 14.5658cm;height 3.1302cm;depth 0pt;cropleft "0";croptop "1.0022";cropright "0.9998";cropbottom "-0.3082";filename 'C:/CBONVIEU/ARTICLES/DJTBK0WS.EPS';tempfilename 'C:/CHRIS/ARTICLES/DL1SO6XB.EPS';

Un principe de codage des éléments de l'espace admissible du problème, en éléments sur lesquels peuvent s'appliquer les trois opérateurs présentés ci-dessus. Ce codage intervient après une phase indispensable de modélisation mathématique du problème (voir figure ??).

Le choix du codage des données dépend du problème traité et conditionne l'efficacité (vitesse de convergence, précision,..) de l'algorithme génétique.
Un mécanisme de génération de la population initiale. C-ette population initiale, qui sert de base aux générations futures, doit être la plus hétérogène possible.
Une fonction d'utilité f, permettant de calculer l'adaptation de chaque élément au problème. Ce critère retourne une valeur de R⁺ appelée fitness.
Des opérateurs permettant de diversifier et d'améliorer la population d'une génération sur l'autre ainsi que d'explorer le plus largement possible l'espace admissible.
Des paramètres dimensionnels : taille de la population, critère d'arrêt, probabilités de croisement (P_c) et de mutation (P_m).

Il s'agit donc d'un ``algorithme stochastique itératif'' qui opère sur des ensembles de points codés, à partir d'une population initiale, et qui est bâti à l'aide de trois opérateurs : croisement, mutation, sélection. Les deux premiers sont des opérateurs d'exploration de l'espace, tandis que le dernier fait évoluer la population vers les optima du problème. Nous détaillons dans la section suivante les différentes phases de l'algorithme ainsi les principes de fonctionnement de ces opérateurs.

2.2 Codage et Opérateurs

2.2.1 Coder ou ne pas coder ?

Historiquement, les individus intervenant dans un algorithme génétique étaient codés sous forme de chaînes de bits⁷. Ce codage binaire contenant toute l'information nécessaire à la description d'un point dans l'espace d'état (voir également Alliot et Schiex [1]). Les opérateurs précités agissent alors sur les individus codés, c'est à dire sur de chaînes de bits.

A titre d'exemple, considérons le problème de maximisation d'une fonction f(x) définie sur le domaine [0,1], dont le maximum est atteint pour x^*=0.5.

Pour traiter ce problème, on associe les points du domaine [0,1] à une chaîne de bits V dont la longueur P déterminera la précision de résolution. La chaîne V sera donc composée de P éléments binaires V=(v_i)_i=1,..,P où v_iÎ {0,1}. Le point x_V correspondant sera défini par :

x_V=

i=1

v_i· 2^-(i-1)

Ceci nous permet d'obtenir 2^P éléments différents dans l'intervalle [0,1], ce qui nous donne une précision de 12^P-1

En examinant le codage au voisinage de 0.5, on constate que deux points très proches dans l'espace d'état peuvent être codés très différemment⁸.

En effet :

Variable	Codage
0.49999...	0111111111...
0.50000...	1000000000...

On évite cet inconvénient en utilisant un codage de Gray⁹.

Pour des problèmes d'optimisation dans des espaces de dimension supérieure, on concatène les chaînes de bits bout à bout. Par exemple, pour une fonction de deux variables z=f(x,y), on code x et y sur leur domaine respectif puis on concatène x et y en une chaîne unique xy. Ce type de codage fonctionne bien mais présente l'inconvénient de perdre la structure du problème en fusionnant x et y dans une chaîne unique.

Il est également possible de ne pas coder les éléments de l'espace admissible du problème. Les opérateurs agissant directement sur les éléments de la population. Ainsi, les algorithmes génétiques utilisant des vecteurs réels étudiés par Golberg [GOL91] et Wright [WRIGHT] évitent ce problème en conservant les variables du problème dans le codage de l'élément de population sans passer par le codage binaire intermédiaire. L'exemple précédent serait codé à l'aide d'un vecteur à deux dimensions, on conserve ainsi la structure du problème dans le codage.

Nous verrons par la suite comment agissent les opérateurs sur des éléments codés sous forme de chaînes de bits, et sur des éléments réels.

2.2.2 Gestion des contraintes

La gestion des contraintes liées au problème est une tâche difficile et sensible pour laquelle l'utilisateur aura à arbitrer entre différentes techniques suivant son appréhension du problème. Ces contraintes sont de diverses natures et peuvent intervenir sur l'espace d'état (contraintes de signe, restrictions à un sous-espace, etc..), ou de manière plus complexe dans le problème lui même.

Dans le cas de contraintes sur l'espace dans lequel doit se faire la recherche, on pourra sélectionner les individus rapidement (sans avoir à les réévaluer) par différentes méthodes. Un individu ``hors champ'' pourra être :

rejeté brutalement et remplacé par un autre individu tiré aléatoirement sur l'espace admissible ;
ramené à la frontière la plus proche (principe du mur);
reporté à la frontière diamétralement opposée à la frontière la plus proche (principe du tore).

Enfin il est bon de noter qu'il peut être préférable de garder des individus ``hors champ''mais qui conservent une direction originale, plutôt que de confiner la population à un sous-espace.

Dans l'hypothèse où la gestion des contraintes ne peut se faire directement, les contraintes peuvent être incluses dans le critère à optimiser sous forme de pénalités. Ainsi, un individu qui viole une contrainte se verra attribuer une mauvaise fitness et sera donc éliminé, avec une forte probabilité, par le processus de sélection (voir section 2.2.4). Cette façon de gérer les contraintes est difficile. En effet, inclure les contraintes dans la fonction d'évaluation peut se faire de diverses façons, et un ``dosage'' s'impose pour ne pas favoriser la recherche de solutions admissibles au détriment de la recherche de l'optimum ou inversement. On risque alors de fournir une solution admissible certes, mais éloignée de l'optimum.

2.2.3 Génération aléatoire de la population initiale

Comme dans tout problème d'optimisation, une connaissance de ``bons'' points de départ conditionne la rapidité de la convergence vers l'optimum.

Si la position de l'optimum dans l'espace d'état est totalement inconnue, il est naturel de générer aléatoirement des individus en faisant des tirages uniformes dans chacun des domaines associés aux composantes de l'espace d'état, en veillant à ce que les individus produits respectent les contraintes.

Si par contre, des informations a priori sur le problème sont disponibles, il parait bien évidemment naturel de générer les individus dans un sous-domaine particulier afin d'accélérer la convergence.

Une nouvelle fois, les contraintes du problème pourront être incorporées (ou non) dans le tirage de la génération initiale.

Disposant d'une population d'individus non homogène, la diversité de la population doit être entretenue au cours des générations afin de parcourir le plus largement possible l'espace d'état, c'est le rôle des opérateurs de croisement et de mutation. Toutefois cette méthode diffère de la méthode de recherche aléatoire, puisque les générations successives doivent être évaluées et modifiées afin de converger, c'est ici qu'intervient l'opérateur de sélection.

2.2.4 Sélection

La sélection permet d'identifier statistiquement les meilleurs individus d'une population et d'éliminer les mauvais. On trouve dans la littérature un nombre important de principes de sélection plus ou moins adaptés aux problèmes qu'ils traitent. Les trois principes de sélection suivants ont retenu notre attention :

Ordonnancement,
Roue de la fortune,
Roue modifiée, voir Golberg [GOLD89].

Ordonnancement (Ranking)

C'est le principe de sélection le plus simple, il consiste à attribuer à chaque individu son classement par ordre d'adaptation. Le meilleur (c'est à dire celui qui possède la meilleure fitness) sera numéro un, et ainsi de suite. On tire ensuite une nouvelle population dans cet ensemble d'individus ordonnés, en utilisant des probabilités indexées sur les rangs des individus. Cette procédure semble toutefois assez simpliste et exagère le rôle du meilleur élément au détriment d'autres élément potentiellement exploitables. Le second, par exemple, aura une probabilité d'être sélectionné nettement plus faible que celle du premier, bien qu'il puisse se situer dans une région d'intérêt. Des procédures plus évoluées permettent de pondérer cette dominance des meilleurs éléments, c'est le cas des principes de roulette.

Roue de la fortune (Roulette wheel selection)

Le principe de la Roue de la fortune consiste à associer à chaque individu q _i une probabilité P_i proportionnelle à sa fitness f(q _i) dans la population. Cette probabilité pourra être calculée comme :

P_i=

(

f(q _i)

)

j=1

(

f(q _j)

)

où S est une fonction régulière et croissante, au sens large.

Chaque individu est alors reproduit avec la probabilité P_i, certains individus (les ``bons'') seront alors ``plus'' reproduits et d'autres (les ``mauvais'') éliminés.

Remarque :

Dans la pratique, il est aisé de tirer N individus, affectés de la probabilité P_i, parmi N avec remise. Pour cela, on associe à chaque individu un segment dont la longueur est proportionnelle à sa fitness (ou à S(f(q _i)), plus exactement). On reproduit ici le principe de tirage aléatoire utilisé dans les roulettes de foire¹⁰ avec une structure linéaire. Ces segments sont ensuite concaténés sur un axe que l'on normalise entre 0 et 1 (voir figure ??). On tire alors un nombre aléatoire, de distribution uniforme entre 0 et 1, puis on ``regarde'' quel est le segment sélectionné. Avec ce système, les grands segments, c'est-à-dire les bons individus, seront plus souvent adressés que les petits, on privilégie ainsi les individus ayant une forte fitness au détriment des individus moins forts, tout en gardant une structure aléatoire, voir également l'exemple élémentaire détaillé en annexe..

Dans l'exemple présenté ci-dessous, la probabilité théorique de sélectionner l'individu q ₅ est de 20 pour cent¹¹.

Exemple :

Indices	1	2	3	4	5	6	7	8	9	10
Pop. initiale	q ₁	q ₂	q ₃	q ₄	q ₅	q ₆	q ₇	q ₈	q ₉	q ₁₀
Fitness	3.2	0.5	0.2	1.5	2.5	0.3	0.2	0.4	1.5	0.3
Proba. P_i	0.30	0.04	0.01	0.14	0.23	0.02	0.01	0.03	0.14	0.02
Nouvelle pop.	q ₁	q ₄	q ₂	q ₆	q ₉	q ₅	q ₁	q ₉	q ₅	q ₇

Mais au regard de la faible dimension de cette population (10) on constate qu'il sera difficile d'obtenir cette espérance mathématique de sélection en raison du peu de tirages effectués. Un biais de sélection plus ou moins fort existe suivant la dimension de la population. Certains individus sont ainsi représentés plusieurs fois (q ₅, q ₁), tandis que d'autres disparaissent (q ₁₀, q _3,..), d'autres enfin survivent ``par chance'', bien qu'ayant un adaptation faible (q ₇). La roue modifiée permet d'éviter ce genre de problèmes.

Roue modifiée (Stochastic remainder without replacement)

Décrivons ce principe de sélection à l'aide de l'exemple simple proposé ci-dessus (N=10) :ftbFUX12.2813cm6.0583cm0ptSélection de la roue de la fortunerouletteroulette.epslanguage "Scientific Word";type "GRAPHIC";display "USEDEF";valid_file "F";width 12.2813cm;height 6.0583cm;depth 0pt;cropleft "0";croptop "1.0002";cropright "0.9996";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/ROULETTE.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1SAH2B.EPS';

Le principe consiste à créer un sous-tableau T_M un tableau de dimension M (M<N) tel que :

Tous les individus ayant une fitness supérieure à la moyenne figurent dans T_M,
Chaque individu q _i est représenté N_i fois où N_i est la partie entière du rapport de la fitness à la moyenne des fitness µ ,

N_i=Ent æ
ç
ç
è

f(q _i)

µ
ö
÷
÷
ø

Sur notre exemple, µ =1.06, ainsi l'individu aura 3 représentants dans ce tableau (f( q ₁) /µ =3.01). Pour notre exemple, T_M est de dimension M=7 :

Indices du tableau	1	2	3	4	5	6	7
Individus	q ₁	q ₁	q ₁	q ₄	q ₅	q ₅	q ₉

La création de ce tableau est purement déterministe. L'assurance d'un nombre précis de représentants pour la génération suivante élimine le biais du principe de sélection décrit précédemment. L'ajout d'un principe aléatoire permet de ne pas éliminer complètement les mauvais individus. En effet, dans la pratique, ces individus sont nécessaires car ils peuvent occuper des positions stratégiques pour l'obtention de l'optimum. Le tableau T_M est alors étendu à T_N de dimension N, de la façon suivante :

Pour chaque individu q _i, on calcule la partie fractionnaire du rapport de sa fitness à la moyenne (on obtient donc un nombre a _i entre 0 et 1).
On tire ensuite aléatoirement h entre 0 et 1, autant de fois qu'il manque d'individus, c'est à dire (N-M) fois .
- Si h <a _i, l'élément q _i est ajouté dans le tableau T_M.
- Sinon, on passe à l'indice i+1.
Quand on arrive à l'élément d'indice N on repasse à l'élément 1.

Sur notre exemple, T_M pourrait être complété de la façon suivante :

Indices du tableau	1	2	3	4	5	6	7	8	9	10
Individus	q ₁	q ₁	q ₁	q ₄	q ₅	q ₅	q ₉	q ₁	q ₃	q ₆

A cette étape du processus, on dispose déjà de ``bons'' individus pour la nouvelle population, certains ont déjà été éliminés (comme q ₂, q ₇, et q ₁₀). Pour assurer la non homogénéité de la population, on effectue un brassage aléatoire du tableau d'indices T_N avant de reconstituer la nouvelle population et d'élargir la recherche à l'aide des opérateurs de croisement et de mutation.

2.2.5 Croisement

Le croisement a pour but d'enrichir la diversité de la population en manipulant les composantes des individus (chromosomes). Classiquement, les croisements sont envisagés avec deux parents et génèrent deux enfants.

Initialement, le croisement associé au codage par chaînes de bits ou chromosomes, est le croisement à découpage de chromosomes (slicing crossover). Pour effectuer ce type de croisement sur des chromosomes constitués de M gènes, on tire aléatoirement une position de découpage. On échange ensuite les deux sous-chaînes terminales de chacun des deux chromosomes (les parents) P₁ et P₂, ce qui produit deux nouveaux chromosomes (les enfants) C₁ et C₂ (voir figure ?? ).ftbFUX10.379cm9.988cm0ptCroisement chromosomique à un pointchromosochromoso.epslanguage "Scientific Word";type "GRAPHIC";display "FULL";valid_file "F";width 10.379cm;height 9.988cm;depth 0pt;cropleft "0";croptop "1.0003";cropright "0.9998";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/CHROMOSO.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RT8XI.EPS';

On peut étendre ce principe en découpant le chromosome non pas en deux sous-chaînes mais en trois, quatre, etc.. Ce type de croisement est illustré par la figure ?? (voir Bridges et Goldberg [BRID]).ftbhFUX13.6169cm7.6311cm0ptCroisement chromosomique à deux pointschromoso2slicing2.epslanguage "Scientific Word";type "GRAPHIC";display "FULL";valid_file "F";width 13.6169cm;height 7.6311cm;depth 0pt;cropleft "0";croptop "1.0005";cropright "0.9995";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/SLICING2.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RTBAL.EPS';

Le croisement à découpage de chromosomes est très rapide à mettre en oeuvre lorsqu'on travaille sur des problèmes utilisant des codages entiers (binaires ou autres).

Pour les problèmes où l'on utilise un codage réel, un croisement ``barycentrique'' est souvent utilisé. Deux parents P₁et P₂ sont sélectionnés ; deux nouveaux points sont créés sur la droite qui les relie créant ainsi C₁ et C₂ de la façon suivante (voir également la figure ??) :

ì
í
î

C₁=a P₁+(1-a )P₂

C₂=(1-a )P₁+a P₂

où a est un coefficient de pondération aléatoire adapté au domaine d'extension des gènes¹².

Le croisement barycentrique permet de générer des points entre, ou à l'extérieur des deux éléments considérés. Toutefois ce type de croisement peut connaître des limitations importantes si les individus se situent sur la même droite (ou plus généralement dans le même sous espace). L'opérateur de croisement, utilisé seul, ne permet alors pas de rechercher les nouveaux éléments en dehors de cette droite.

Dans le cas particulier d'un chromosome matriciel constitué par la concaténation de vecteurs, on peut étendre ce principe de croisement aux vecteurs constituant les gènes. Deux composantes P₁(i) et P₂(i) sont sélectionnés dans chacun des parents à la même position i. Ils définissent deux nouveaux éléments par pondération. On crée ainsi C₁(i) et C₂(i) de la façon suivante : ftbhFX9.2082cm10.6954cm0ptBARYcroiseme.epslanguage "Scientific Word";type "GRAPHIC";display "FULL";valid_file "F";width 9.2082cm;height 10.6954cm;depth 0pt;cropleft "0";croptop "1.0003";cropright "1.0003";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/CROISEME.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RTF2T.EPS';

ì
í
î

C₁(i) = a P₁(i) + (1 - a) P₂(i)

C₂(i) = (1 - a) P₁(i) + a P₂(i)

On peut imaginer et tester des opérateurs de croisement plus ou moins complexes sur un problème donné mais l'implémentation de ces principes est souvent liée intrinsèquement au problème.

Remarque :

Cette méthode de diversification des éléments rappelle la méthode du simplexe ou des polytopes. Dans cette méthode, les solutions du problèmes sont recherchée de manière itérative en considérant une population initiale¹³ constituant des sommets de polytopes de l'espace d'état et où les éléments successifs sont construits de manière barycentriques. Nous pouvons pousser la comparaison, puisque les éléments sont réévalués après cette diversification dans les deux méthodes. Les algorithmes génétiques offrent cependant un aspect stochastique important (les éléments sont reproduits avec la probabilité P_c) et une efficacité supérieure.

2.2.6 Mutation

L'opérateur de mutation apporte aux algorithmes génétiques l'aléa nécessaire à une exploration efficace de l'espace. Cet opérateur nous garantit que l'algorithme génétique sera susceptible d'atteindre tous les points de l'espace d'état, sans pour autant les parcourir tous dans le processus de résolution. Ainsi, en toute rigueur, l'algorithme génétique peut converger sans croisement, et certaines implantations fonctionnent de cette manière (Fogel et al.[FOGEL]) et sont conformes aux résultas théoriques de R. Cerf [11], voir section 5. Les propriétés de convergence des algorithmes génétiques sont donc fortement dépendantes de cet opérateur.

Pour bien comprendre l'utilité de l'opérateur de mutation, considérons un problème discret pour lequel les individus sont codés sous forme de chaînes chromosomiques constituées de trois valeurs entières et prenons une population de dix individus. On suppose de plus que le croisement utilisé est un croisement à découpage de chromosomes à un point peu importe lequel. Si par malchance, la population initiale ne présente pas de ``7'' en troisième position, par exemple :

q ₁:	5	4	0
q ₂:	7	3	3
q ₃:	4	6	6
q ₄:	2	7	4
q ₅:	6	8	5
q ₆:	5	5	2
q ₇:	9	8	8
q ₈:	4	9	9
q ₉:	7	3	0
q ₁₀:	8	2	3

et que l'optimum se trouve en ``4.5.7'' , il est impossible d'atteindre ce point avec l'opérateur de croisement. L'opérateur de mutation permet alors de faire varier aléatoirement la valeur des composantes de ces termes, c'est à dire des gènes.

La mutation consiste généralement à tirer aléatoirement un gène dans le chromosome et à le remplacer par une valeur aléatoire (voir ci dessous). Si la notion de distance existe, cette valeur peut être choisie dans le voisinage de la valeur initiale. Dans le cas d'éléments codés en binaire, on remplacera la valeur ``0'' par ``1'' et vice-versa.

element initial

g₁

g₂

g_i

g_i+1

g_n

¾®

æ
ç
ç
ç
ç
ç
è

mutation de g_i

g_i g

ö
÷
÷
÷
÷
÷
ø

¾®

g₁

g₂

g_i

g_i+1

g_n

element mute

Dans les codages réels, on procède un peu de la même manière en tirant aléatoirement un élément, auquel on ajoute un bruit aléatoire en veillant à ce que l'élément résultant reste dans le domaine d'extension qui lui est propre.

Le choix pratique des probabilités P_m et P_c dépend de la complexité du problème étudié, cependant il parait souhaitable de faire dépendre ces paramètres de la génération courante, afin d'explorer plus largement l'espace, au ``début'' de l'algorithme, et moins sur la ``fin''.

Comme nous l'avons déjà précisé, les opérateurs de croisement et de mutation ne font pas intervenir la fonction à optimiser, ce sont des opérateurs stochastiques d'exploration du domaine admissible. C'est l'opérateur de sélection qui guide la population vers les valeurs élevées de la fonction.

3 Améliorations classiques

3.1 Introduction

Les processus de sélection présentés sont très sensibles aux écarts d'adaptation entre individus et dans certains cas, un très bon individu risque d'être reproduit trop souvent et peut même provoquer l'élimination complète de ses congénères ; on obtient alors une population homogène contenant un seul type d'individu. Ainsi, dans l'exemple de la figure ?? le second mode M₂ risque d'être le seul représentant pour la génération suivante et seule la mutation pourra aider à atteindre l'objectif global M₁ au prix de nombreux essais successifs.ftbhFUX10.0012cm7.9891cm0ptExemple où les sélections classiques risquent de ne reproduire qu'un individuselectionhyper.epslanguage "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display "FRAME";valid_file "F";width 10.0012cm;height 7.9891cm;depth 0pt;cropleft "0";croptop "0.5544";cropright "0.7044";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/HYPER.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RTQL1.EPS';

Pour éviter ce comportement, il existe d'autres modes de sélection ainsi que des principes (scaling, sharing) qui empêchent les individus ``forts'' d'éliminer complètement les plus ``faibles''.

3.2 Scaling

Le scaling ou mise à l'échelle, modifie les fitness afin de réduire ou d'amplifier artificiellement les écarts entre les individus. Le processus de sélection n'opère plus sur la fitness réelle mais sur son image après scaling. On souhaite ainsi aplatir ou dilater la fonction d'évaluation. La perte de précision¹⁴ qui s'ensuit est au prix d'une meilleure convergence.

Parmi les fonctions de scaling, on peut envisager le scaling linéaire et le scaling exponentiel.

3.2.1 Scaling linéaire

Dans ce cas la fitness initiale f_r est redéfinie en une nouvelle fitness f_s par l'opération homothétique suivante (voir Michalewicz [21])

f_s = a f_r +b

En règle générale, le coefficient a est inférieur à un, ce qui permet de réduire les écarts de fitness et donc de favoriser l'exploration de l'espace. Par contre ce scaling est statique par rapport au numéro de génération et pénalise la fin de convergence lorsque l'on désire favoriser les modes dominants.

3.2.2 Scaling exponentiel

Il est défini de la façon suivante (voir figure ??):

f_s=(f_r)^n(k)

ftbhFUX8.9688cm8.9688cm0ptFonction de scaling exponentiellescalingfscalin2.epslanguage "Scientific Word";type "GRAPHIC";display "FRAME";valid_file "F";width 8.9688cm;height 8.9688cm;depth 0pt;cropleft "0";croptop "0.9998";cropright "0.9998";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/FSCALIN2.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RTUP6.EPS';

où k est la génération courante.

Pour n(k) proche de zéro, on réduit fortement les écarts de fitness ; aucun individu n'est vraiment favorisé et l'algorithme génétique se comporte comme un algorithme de recherche aléatoire et permet d'explorer l'espace.
Pour n(k) proche de 1, le scaling est inopérant.
Pour n(k)>1 les écarts sont exagérés et seuls les bons individus sont sélectionnés ce qui produit l'émergence des modes.

Dans la pratique, on fait généralement varier n(k) des faibles valeurs vers les fortes valeurs au cours des générations. Pour cela on utilise une fonction de type de celle représentée par la figure ??, et dont la formule est donnée par :

n(k)=a ₁

æ
ç
ç
è

tan

é
ê
ê
ë

æ
ç
ç
è

K+1

ö
÷
÷
ø

ù
ú
ú
û

ö
÷
÷
ø

a ₂

k étant la génération courante, K le nombre total de générations prévues, et a ₁et a ₂ sont des paramètres à choisir. L'évolution de n(k) en fonction de la génération k est donnée par la figure ??.ftbhFUX12.3824cm6.4625cm0ptAllure de l'évolution de n(k) en fonction des générationsCOURBEfscalin1.epslanguage "Scientific Word";type "GRAPHIC";display "FRAME";valid_file "F";width 12.3824cm;height 6.4625cm;depth 0pt;cropleft "0";croptop "1";cropright "1.0003";cropbottom "0";filename 'C:/CBONVIEU/ARTICLES/DJTDPQRO.EPS';tempfilename 'C:/CHRIS/ARTICLES/DL1RTUBK.EPS';

Ce dernier principe de scaling donne dans la pratique de meilleurs résultats que le scaling linéaire. Dans le cas des fonctions objectifs possédant plusieurs modes et présentant des optimaux quasi équivalents, cette technique de scaling, en amplifiant les écarts de fitness en fin de convergence, va effectivement favoriser le mode dominant mais aussi masquer les modes sous-optimaux qui peuvent tout de même présenter un intérêt. Le scaling permet donc une bonne exploration de l'espace d'état mais ne favorise pas la répartition des individus sur les différents optima de la fonction objectif. Cette répartition souhaitable est obtenue en utilisant l'opérateur de partage.

3.3 Partage (sharing)

L'objectif du partage est de répartir sur chaque sommet de la fonction à optimiser, un nombre d'individus proportionnel à la fitness associée à ce sommet. La figure ?? présente deux exemples de répartitions de populations dans le cas d'une fonction à cinq sommets : le premier sans partage, le second avec partage.ftbhFUX13.9991cm6.9984cm0ptObjectif du ``partage''sharingobjeshar.epslanguage "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width 13.9991cm;height 6.9984cm;depth 0pt;cropleft "0";croptop "1.0012";cropright "1.0004";cropbottom "-0.3371";filename 'C:/CBONTEMP/ARTICLES/GRAPH/OBJESHAR.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RTW6N.EPS';

3.3.1 Principe

De la même façon que le scaling, le partage consiste à modifier la fitness utilisée par le processus de sélection. Pour éviter le rassemblement des individus autour d'un sommet dominant, le partage pénalise les fitness en fonction du taux de concentration (voir la remarque ci-dessous) de la population dans le voisinage d'un individu. Plus cet individu est entouré, plus on pénalisera sa reproduction¹⁵. Il requiert l'introduction d'une notion de distance. Dans la pratique, il faut définir une distance indiquant la dissimilarité entre deux individus. Ce qui n'est pas toujours chose facile¹⁶. Cette distance est alors utilisée pour calculer la nouvelle fitness de la façon suivante :

(q _i)=

f(q _i)

j=1

(

d(q _i,q _j)

)

(1)

avec

S(d)=

ì
ï
ï
í
ï
ï
î

(

ds _share

)

si d<s _share

si d>s _share

Le paramètre s _share permet de délimiter le voisinage d'un point et dépend du problème traité. La figure ?? donne l'allure de S(d) pour différentes valeurs de a .

Remarque :

Ce calcul du terme pénalisant (au dénominateur) est très proche d'un calcul de densité par estimation non paramétrique. Le dénominateur m_i intervenant en (3.3.1), jouant le rôle d'estimateur de la densité autour de l'individu q _i, la fonction S faisant office de noyau et s _share de fenêtre. Il s'agit donc d'un opérateur qui pondère la fitness d'un individu par l'inverse de sa densité. On pénalise donc bien les individus se situant dans une zone ``dense''.

Suivant la valeur donnée à a le partage sera plus ou moins efficace. Ainsi pour a <1, on pénalise les groupes très agglomérés. A titre d'exemple, la figure ?? donne les fitness moyennes après partage pour deux répartitions possibles d'une population, dans le cas d'une fonction bi-modale (dans le cas 1, tous les points sont sur le même sommet, dans le cas 2 les points sont répartis sur les deux sommets). Le cas 2 donne une fitness moyenne, sur les individus, double de celle du cas 1, ce qui justifie l'intérêt du partage.ftbhFUX11.3543cm5.2675cm0ptAllure de S( ds _share)S(d)sharing1.epslanguage "Scientific Word";type "GRAPHIC";display "FRAME";valid_file "F";width 11.3543cm;height 5.2675cm;depth 0pt;cropleft "0";croptop "1.0015";cropright "1.0001";cropbottom "-0.5061";filename 'C:/CBONTEMP/ARTICLES/GRAPH/SHARING1.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RU1BZ.EPS';

Dans la pratique ce type de partage donne effectivement de bons résultats mais au prix de N² calculs de distances entre chromosomes à chaque génération pour une population de taille N. Or les algorithmes génétiques induisent une complexité en N sans partage et le fait de passer en N² est très pénalisant.ftbhFUX12.457cm9.7266cm0ptInfluence du partage dans le cas d'une fonction bi-modalesharing2.epslanguage "Scientific Word";type "GRAPHIC";display "FULL";valid_file "F";width 12.457cm;height 9.7266cm;depth 0pt;cropleft "0";croptop "0.9999";cropright "1";cropbottom "0";filename 'C:/CBONTEMP/ARTICLES/GRAPH/SHARING2.EPS';file-properties "NPEU";tempfilename 'C:/CHRIS/ARTICLES/DL1RU2T9.EPS';

Pour réduire ce nombre de calculs , on utilise un partage par ``bouquets¹⁷''.

3.3.2 Partage par bouquets (Clustered sharing)

Pour effectuer ce type de partage (voir [AGSH6]), on commence par identifier les différents ``bouquets '' d'individus dans la population. On utilise pour cela utilise deux paramètres d_min et d_max afin de fusionner des bouquets ou en créer de nouveaux. Initialement, chaque individu de la population est considéré comme le centre d'un bouquet. On applique alors successivement deux principes, l'un intervenant sur les bouquets, le second sur les individus eux-mêmes :

si deux centres sont à une distance inférieure à d_min, on fusionne ces derniers dans un bouquet unique dont le centre résultant est le barycentre des deux centres initiaux.
un nouvel individu est agrégé à un bouquet si sa distance au centre le plus proche est inférieure à d_max.
- Dans ce cas, on calcule de nouveau le centre du bouquet global.
- Sinon, on crée un nouveau bouquet contenant ce seul individu. Cet individu devient alors le centre d'un nouveau bouquet réduit à lui seul.

Ce principe de fusion-agrégation permet d'obtenir un nombre de bouquets fluctuant avec la répartition des individus dans l'espace d'état. On applique ensuite le principe de partage en modifiant les fitness de la façon suivante :

f_i

; ou m

=n_c

æ
ç
ç
ç
ç
ç
è

æ
ç
ç
è

d_ic

2d_max

ö
÷
÷
ø

ö
÷
÷
÷
÷
÷
ø

avec

n_c : nombre d'individus contenus dans le bouquet auquel appartient l'individu i.
a : coefficient de sensibilité.
d_ic : distance entre l'individu i et le centre du bouquet c.

Ces améliorations ont été développées au sein du LOG¹⁸

Remarque :

La quantité m_i représente une sorte de densité intra-bouquet, on cherche ainsi à pénaliser les bouquets trop denses ou trop importants au profit de bouquets plus petits, qui peuvent révéler des optimums locaux.

On montre que ce type de partage induit une complexité en O(Nlog N) (voir e.g.[AGSH6]), pour des résultats tout à fait comparables à ceux fournis par le partage classique. Dans la pratique, on remarque que le réglage des coefficients d_min et d_max est assez délicat car l'efficacité de ces derniers dépend essentiellement de la connaissance a priori des distances entre les optimums dans l'espace d'état, distance inconnue qu'il est très difficile d'estimer.

3.4 Algorithmes génétiques et recuit simulé

3.4.1 Introduction

Les algorithmes génétiques et le recuit simulé étant deux techniques d'optimisation stochastique travaillant sur les mêmes types de problèmes, il est logique de chercher à les associer afin de tirer partie de leurs avantages respectifs. Il semble (voir Chansou [CHANSOU]) que le recuit simulé converge plus vite vers la solution optimale mais ne donne qu'une solution dans le cas des problèmes à optimums multiples, ceci confirme les résultats donnés dans ??? [AGRS4]. A l'inverse, les algorithmes génétiques fournissent plusieurs solutions quasi-optimales mais au prix d'un temps de convergence plus long. Il semble alors naturel d'associer ces deux techniques afin d'améliorer la convergence des algorithmes génétiques.

Il y a eu de nombreuses tentatives de fusion entre les algorithmes génétiques et le recuit simulé, les travaux les plus intéressants étant ceux de Mahfoud et Goldberg [AGRS3].

3.5 Recuit simulé

3.5.1 Principe

3.6 Croisement avec recuit

3.6.1 Principe du croisement avec recuit simulé

Pour appliquer ce principe de croisement, on commence par sélectionner deux parents P₁ et P₂ dans la population (voir figure ??). On applique ensuite l'opérateur de croisement classique qui génère deux enfants C₁ et C₂. Un tournoi est alors effectué entre les parents et les enfants pour lequel les deux vainqueurs sont sélectionnés par le schéma de recuit suivant. On considère l'individu C₁. On tire ensuite aléatoirement un des deux parents, soit P_i ce parent :

si C₁ est meilleur que P_ialors C₁ est sélectionné.
sinon C₁ est sélectionné avec la probabilité :

P=e

- æ
è

|f

C₁
-f

P_i
|
t_n ö
ø

où t_n est un coefficient décroissant en fonction de la génération courante (n).

On fait de même pour C₂ avec le parent restant et l'on détermine ainsi deux individus C₁ et C₂.

L'évolution de la variable t_n se fait de la façon suivante. On utilise un schéma de recuit standard géométrique à un palier de basculement. Pratiquement, on calcule trois ``températures'' dont les valeurs dépendent de la connaissance des écarts min et max des fitness de la population initiale.

ì
í
î

t_s=-D f_max

(

1k-1

)

k=0.75

Température initiale

t_x=-D f_max

(

1k-1

)

k=0.99

Température de basculement

t_f=-D f_min

(

1k-1

)

k=0.99

Température finale

où D f_min, D f_max représentent les écarts minimum et maximum des fitness de la population initiale. Le schéma géométrique fait évoluer la température courante de la façon suivante :

ì
í
î

t₀=t_s

t_n+1=a ₁t_n pour t_s >t_n > t_x;

t_n+1=a ₂t_n pour t_x >t_n > t_f;

avec 0 < a ₁ < a ₂ < 1 .

Pour chaque palier, on calcule le nombre d'itérations de stabilisation à l'aide des formules :

N₁=

(

t_xt_s

)

ln a ₁

N₂=

(

t_ft_x

)

ln a ₂

Ces deux formules, nous permettent de calculer le nombre total de générations pour un problème donné.

4 Utilisation et exemples

Comme nous l'avons déjà remarqué ces techniques permettent de fournir des éléments de population correspondant à une ``zone optimale'' pour un problème donné. Ces éléments, ou individus, ne donnent pas précisément une solution du problème mais des positions proches de l'optimum. C'est en sens qu'il faut interpréter les algorithmes de façon pratique. Ainsi, lorsqu'on utilise un algorithme génétique dans une optique de maximum de vraisemblance par exemple, il convient de prolonger cette procédure par un algorithme classique ``grimpeur'', afin d'augmenter la précision de la recherche et d'obtenir le(s) maximum(s) de manière précise (voir Goffe et al. [16], ou Dorsey et Mayer [12]).

Dans un cadre économique, il s'agira moins de déterminer le maximum précisément que d'en comprendre la signification. En effet, si l'on modélise la stratégie d'un joueur par ses actions passées dans un jeu répété, la population initiale comportera des éléments interprétables, puisque issus de comportements théoriques que l'on souhaite examiner. Il n'en sera pas de même de la population après quelques générations, les opérateurs de croisement et de mutation ayant effectué des bouleversements importants dans la structure même des individus (voir Andreoni et Miller [2], ou les vulgarisations autour du dilemme du prisonnier [SCIENCE1] et [SCIENCE2]).

Ces mêmes algorithmes génétiques peuvent également être utilisés comme aides à la décision dans une situation évoluant rapidement, on ne demande alors pas la meilleure solution mais une solution raisonnable dans un temps limité. Cette situation, qui est à l'étude dans le cadre de procédures d'évitement d'avions (voir Durand[13]), pourrait également s'appliquer aux marchés financiers.

Nous proposons ici une revue d'ensemble des problèmes économiques et économétriques traités, en totalité ou en partie, par algorithme génétique.

Optimisation (Alliot et Schiex [1])

Economie : Exemple du dilemme du prisonnier d'Axelrod [6] et des enchères d'Andréoni et Miller [2]

Econométrie 11 exemples( Dorsey et Mayer [12]) +2 en projet (avec C. Bisiere et E. Malin).

Autres : Evitement des avions (Durand [13]), Othello (Alliot et Schiex [1]), Sectorisation (Delahaye [DELA]), etc..

5 Résultats théoriques

Les algorithmes génétiques ont monté leur efficacité pratique bien avant que les résultats de convergence théorique ne soient établis. Nous disposons aujourd'hui de trois approches théoriques différentes permettant de mieux comprendre le fonctionnement des algorithmes génétiques, ces trois approches donnant des résultats asymptotiques.

La théorie des Shémas développée par Holland [18], constitue une première approche du problème. S'appliquant sur des chaînes de bits, elle étudie le comportement asymptotique de l'algorithme et l'effet des différents opérateurs sur la structure des shémas, que nous détaillerons pas ici.
La deuxième approche découle des résultats de convergence stochastique sur des méthodes de recuit simulé développées par Laarhoven et Aarts [LAA]. Sous certaines hypothèses, on montre la convergence asymptotique grâce à l'opérateur de mutation. Ce résultat est d'ailleurs conforme à l'intuition, puisque seul cet opérateur permet réellement l'exploration aléatoire de l'espace.
L'approche théorique la plus récente est proposée par Raphaël Cerf [11] et utilise une modélisation par chaîne de Markov de l'algorithme génétique. Les résultats asymptotiques sont obtenus grâce à la théorie de Freidlin et Wentzell [15].

Cette dernière approche est la plus satisfaisante tant sur le plan mathématique, que sur celui de la modélisation, les différents opérateurs étant présentés comme ``perturbant'' un processus Markovien représentant la population à chaque étape. Ici encore il est démontré l'importance de l'opérateur de mutation, le croisement pouvant être totalement absent. Nous présentons ici une version simplifiée de cette théorie et les principaux résultats de convergence.

5.1 Modélisation de l'algorithme génétique

Les principaux résultats asymptotiques portant directement sur les algorithmes génétiques, ont étés développés par R. Cerf [11] sur la base des travaux de Catoni [10] et de Trouvé [24]. Ces travaux se fondent sur la théorie des petites perturbations aléatoire d'un processus dynamique de type Markovien. Plus particulièrement, la théorie de Freidlin et Wentzell [15] constitue la pierre d'angle de ces études. Nous donnons ici, quelques résultats particulièrement révélateurs de la dynamique des algorithmes génétiques, développés par Cerf. Nous les présentons simplifiés et dans un cadre restreint, laissant le lecteur intéressé se reporter à la difficile lecture des références citées ici.

Afin de préciser le cadre de cette section, nous travaillerons ici sur la base d'un codage binaire à , P représente le nombre d'éléments binaires (bits) utilisés pour le codage(voir section 2.2 pour plus de détails). La fonction d'évaluation, f sera donc définie sur l'espace E={0,1}^P à valeurs dans R⁺. Le problème est donc de localiser l'ensemble des maxima (globaux ou non) de f , ou, à défaut, de trouver rapidement et efficacement des régions de l'espace, où se situent ces maxima.

Comme nous l'avons vu l'algorithme génétique est un algorithme stochastique itératif qui opère sur des ensembles de points, et qui est bâti à l'aide de trois opérateurs: mutation, croisement et sélection, que nous présentons plus formellement a présent.

5.2 Description rapide de l'algorithme

Soit N la taille (fixe) de la population, notons X_k la population de la génération k : il s'agit d'une matrice X_k=(X_k¹,X_k²,.. X_k^N) de E^N dont les N éléments sont des vecteurs (chromosomes) de taille P composés de 0 et de 1(les gènes)¹⁹. Le passage de la génération k à la génération k+1, c'est à dire de X_k à X_k+1 se décompose en trois étapes :

X_k

Mutation

¾®

Y_k

Croisement

¾®

Z_k

Selection

¾®

X_k+1

chacune de ces étapes peur être modélisée formellement.

5.2.1 Mutation X_k¾® Y_k

L'opérateur considéré ici est l'opérateur de mutation chromosomique binaire (voir section ??). Pour chaque composante de chaque élément X_kⁱ, une variable de Bernouilli de paramètre P_c est tirée indépendamment et suivant le résultat l'élément binaire examiné est changé ou non. S'il y a mutation les ``0" sont changés en ``1'' et vice versa.

La probabilité P_c est la probabilité de mutation doit être préalablement choisie et est généralement ``faible''.

Comme nous le verrons par la suite, cet opérateur joue un rôle clé dans la convergence de l'algorithme génétique.

5.2.2 Croisement Y_k¾® Z_k

L'opérateur étudié ici est l'opérateur chromosomique à un point de découpage (slicing crossover). Ici encore, un paramètre P_m est fixé initialement, c'est la probabilité de croisement. Pour construire la population Z_k, N/2 couples sont formés à partir de la population Y_k (par exemple en appariant les individus consécutifs de Y_k, ou bien en choisissant au hasard et uniformément des individus dans Y_k). Pour chaque couple, une variable de Bernoulli de paramètre P_m est tirée pour décider si le croisement a lieu. Si c'est le cas, un site de coupure est tiré au hasard, et les segments finaux des deux chromosomes sont échangés.

Une nouvelle paire d'individus est ainsi obtenue (identique à l'ancienne s'il n'y a pas eu de croisement) et est stockée dans la population Z_k. En général, le paramètre P_m est choisi ''grand''.

Remarquons que les opérateurs de mutation et de croissement ne font pas intervenir la fonction f, ce sont des opérateurs stochastiques d'exploration. C'est le troisième et dernier opérateur, la sélection, qui guide la population vers les valeurs élevées de la fonction f.

5.2.3 Sélection Z_k¾® X_k+1

Les N individus de la population X_k+1 sont obtenus d'après la sélection effectuée sur les individus de Z_k. On sélectionne ainsi les ``meilleurs'' individus de Z_k, indépendamment à l'aide d'une distribution de probabilité qui favorise les individus de Z_k les mieux adaptés.

Le choix le plus fréquent est l'unique distribution telle que la probabilité d'un individu soit proportionnelle à son adaptation, i.e la probabilité de sélection de l'individu Z_kⁱ est :

P_i=P(Z_kⁱ)=

f(Z_kⁱ)

j=1

f(Z_k^j)

En tirant les individus dans la population Z_k conformément aux probabilités P_i, on constitue la nouvelle génération X_k+1.

5.3 Modélisation

La présentation rapide des opérateurs nous permet de modéliser la suite des (X_k)_kÎ_N en une chaîne de Markov, d'espace d'états E=( {0,1}^P) ^N. L'algorithme génétique ne doit donc pas être interprété comme une procédure d'optimisation mais plutôt comme une marche aléatoire dans l'espace d'état, attirée vers les fortes valeurs de f .

La propriété première de cette formalisation est que la loi de X_k est déterminée de manière unique par :

- la loi de la génération initiale X₀
- le mécanisme de transition de X_k à X_k+1, mécanisme scindé en les trois étapes détaillée ci-dessus.

Ce mécanisme de transition possède toutefois des propriétés essentielles qui font l'intérêt et la puissance de cette formalisation, voir Cerf ([11], chapitre 1) :

Il est homogène (c'est à dire indépendant de la génération, k, considérée)
Il est irréductible, (la probabilité de joindre deux points quelconques de l'espace d'état, en un nombre fini de générations est non nulle) soit :

" x,yÎ E $ rÎ N P [ X_k+r=y| X_k=x ] >0

Le mécanisme permet donc d'explorer tout point de l'espace d'état, avec une probabilité non nulle.
Il est apériodique, cette hypothèse n'est cependant pas fondamentale.

Ces propriétés permettent de conclure à l'ergodicité de la chaîne de Markov, et à l'existence d'un processus limite.

Une chaîne de Markov homogène irréductible apériodique d'espace d'états fini est ergodique et possède une unique mesure de probabilité stationnaire ou invariante.

Cette mesure stationnaire correspond à la loi régissant l'équilibre du processus, elle est définie , pour tout y, comme :

µ (y)=

lim

k® ¥

[

X_k=y| X₀=x

]

Nous savons également que tout élément de l'espace d'état est de probabilité non nulle pour cette mesure.

Toutefois, si ce résultat nous permet de savoir qu'il existe une dynamique de fond de l'algorithme génétique, il nous reste à en déterminer les propriétés, l'influence des opérateurs (et des paramètres associés) qui jouent un grand rôle dans le processus.

Pour cela nous introduisons les notations suivantes :

Notations

Si x=(x₁,...,x_N) est un élément de E^N et i un point de E, nous notons :

f(x)

f(x₁,...,x_N)=max

{

f(x_i):1£ i£ N

}

{

x_kÎ arg maxf(x)

}

[

]

{

x_k : 1£ k£ N

}

De manière générale, les lettres z, y, z, u, v.. désignent des populations, i.e. des éléments de E^N, et les lettres i, j des points de E.

5.3.1 Processus de fond (X_k^¥)

C'est à partir de ce processus de fond qu'est reconstitué l'algorithme génétique en étudiant ses perturbations aléatoires par les différents opérateurs. Il est défini comme processus limite, lorsque les perturbations ont disparu. C'est également une chaîne de Markov sur E^N dont le mécanisme de transition est très simple puisque correspondant à la situation limite suivante :

Les N composantes de X_k+1^¥ sont choisies indépendamment et suivant la loi uniforme sur l'ensemble X_k^¥.

Les individus dont l'adaptation n'est pas maximale en k, sont éliminés et n'apparaissent pas dans la génération k+1,
Les individus dont l'adaptation est maximale, ont des chances de survies égales

Cette chaîne est tout d'abord piégée dans l'ensemble S des populations ayant la même adaptation (ou ensemble des population d'équi-adaptation),

{

x=(x₁,...,x_N)Î E^N : f(x₁)=f(x₂)=··· =f(x_N)

}

Cette population représente les attracteurs de la chaîne (voir 5.4 plus loin), puis elle est absorbée par une population uniforme, de sorte que :

" xÎ E^N P

é
ê
ê
ë

$ x_iÎ x

$ K " k³ K X

=x_i| X

=x_ini

ù
ú
ú
û

Lorsque la population est devenue uniforme et en l'absence ici de perturbations, il ne se passe plus rien.

Ceci peut également se traduire en définissant les populations uniformes comme les états absorbants de la chaîne X_k^¥.

Nous allons maintenant étudier la situation ou se processus est perturbé.

5.3.2 Processus perturbé (X_k^l)

La modélisation proposée par Cerf, part du processus de fond (X_k^¥),décrit ci-dessus, qui est perturbé aléatoirement, les perturbations sont indicées par le paramètre l. La chaîne de Markov (X_k^¥) devient donc une suite de chaînes de Markov (X_k^l), dont le mécanisme de transition est donné par la succession des transformations générées par les opérateurs.

X_k^l

Mutation

¾®

U_k^l

Croisement

¾®

V_k^l

Selection

¾®

X_k+1^l

Il nous faut pour cela modéliser précisément les opérateurs.

Mutation X_k^l¾® U_k^l

Les mutations sont définies comme de petites perturbations aléatoires indépendante des individus, de la population X_k^l. Il est assez naturel d'introduire la probabilité p_l(i,j) de transition²⁰ de mutation entre les points i et j de E, comme un noyau Markovien p_l.

Trivialement on a " iÎ E _{jÎ E}p_l(i,j)=1. Sur la chaîne X_k^l, la probabilité de transition entre les points x et u de E^N est :

[

U_k^l=u| X_k^l=x

]

=p_l(x₁,u₁)· p_l(x₂,u₂)··· p_l(x_N,u_N)

Plus précisément et afin d'analyse la dynamique de (X_k^l) lorsque l tend vers l'infini, nous reportons ici les hypothèses sur le mode et la vitesse de convergence des probabilité de transition. Pour cela nous supposons l'existence d'un noyau irréductible, a , sue E, i.e. :

" i,jÎ E, $ i_o, i_1,··· , i_r (c'est à dire un chemin dans E) tels que i₀=i et i_r=j tels que :

0£ s£ r-1

a (i_k,i_k+1)>0

L'hypothèse d'irréductibilité du noyau a est essentielle, elle assure que tout point de l'espace est potentiellement visitable.

La vitesse de convergence du noyau p_l, est caractérisée par le réel positif a, tel que p_l admette le développement suivant :

" i,jÎ E " s p_l(i,j)=

ì
ï
í
ï
î

a (i,j)·

-a

+o(l^-s)

si i¹ j

1-a (i,j)·

-a

+o(l^-s)

si i=j

(2)

La condition de positivité de a nous permettent de faire disparaître les perturbations lorsque l tend vers l'infini.

" i,jÎ E

lim

l® ¥

p_l(i,j)=d (i,j)=

ì
í
î

0		si i¹ j
1		si i=j

(3)

Croisement U_k^l¾® V_k^l

Ici encore l'opérateur est modélisé comme effectuant de petites perturbations aléatoires sur des couples de la population U_k^l. Ces couples sont ici formés par les éléments successifs de la population, les transitions sont gérées par le noyau Markovien q_l sur E× E, cette fois, de sorte que :

[

V_k^l=v| U_k^l=u

]

=q_l

(

(u₁,u₂)· (u₃,u₄)··· (u_N-1,u_N)

)

Pour ce noyau q_l nous supposerons l'existence d'un noyau irréductible b sur E× E, la vitesse de convergence est alors paramétrée par le réel positif b tel que :

(

i₁,j₁

)

Î E× E "

(

i₂,j₂

)

Î E× E " s

q_l

(

i₁,j₁

)

(

i₂,j₂

)

ì
ï
í
ï
î

(

i₁,j₁

)

(

i₂,j₂

)

-b

+o(l^-s)

(

i₁,j₁

)

(

i₂,j₂

)

1-b

(

i₁,j₁

)

(

i₂,j₂

)

-b

+o(l^-s)

(

i₁,j₁

)

(

i₂,j₂

)

(4)

L'évanouissement asymptotique des croisements est également imposée par la positivité de b :

" i₁, i₂, j₁, j₂Î E

lim

l® ¥

q_l

(

(i₁,i₂)(j₁,j₂)

)

=d (i₁,i₂)· d (j₁,j₂) (5)

Sélection V_k^l¾® X_k+1^l

C'est l'opérateur le plus compliqué et également le plus important puisqu'il permet la convergence vers les optima de f.

Il est modélisé à l'aide d'une fonction de sélection F_l dont Cerf nous donne une définition précise, pouvant être résumée par :

F_l :

{1,··· ,N}×

(

R⁺

)

¾®

[

0,1

]

(

i, f₁,f₂,··· f_N

)

¾® F_l

(

i, f₁,f₂,··· ,f_N

)

telle que :

i) F( · ,f₁,f₂,··· f_N) est une probabilité sur {1,··· ,N}
ii) Cette probabilité est indépendante de l'indexation des f₁,f₂,··· f_N (on peut permuter les f_i )
iii) La probabilité favorise les éléments i associés à des valeurs élevées (i.e.)

Si f₁³ f₂³ ··· ³ f_N Alors

F_l ( 1, f₁,f₂,··· ,f_N ) ³ F_l ( 2, f₁,f₂,··· ,f_N ) ³ ··· ³ F_l ( N, f₁,f₂,··· ,f_N )

Cet outil, dont on voit qu'il modélise les probabilité de sélection définies section ??, nous permet d'écrire la probabilité de transition correspondant à la dernière étape.

[

X_k+1^l=x| V_k^l=v

]

r=1

¡ _l(x_r,v_r)

ceci signifie que la probabilité de transition est le produit des probabilités sur chacune des N composantes de E.

La probabilité ¡ _l entre deux composantes (x_r,v_r) est donnée par :

¡ _l(x_r,v_r)=

k : v_k=x_k

F_l

(

k, f(v₁),f(v₂),··· ,f(v_N)

)

De même que pour les autres opérateurs, la fonction de sélection doit être choisie et sa vitesse de convergence caractérisée :

F_l

(

i, f₁,f₂,··· ,f_N

)

exp

(

c· f_i· ln (l)

)

r=1

exp

(

c· f_r· ln (l)

)

(6)

Ce choix correspond bien à une probabilité de sélection avantageant les fortes adaptation au détriment des faibles, le réel positif c indexant cette fonction.

Le mécanisme de sélection opérant sur le processus de fond (X_k^¥), correspond à la fonction de sélection F_¥ définie par :

(

k,f(x₁),f(x₂),··· ,f(x_N)

)

=1_x(x_k)card(x)

C'est à dire, la loi uniforme sur l'ensemble x= { x_kÎ arg max f(x)}

La suite (F_l)_lÎ_N des fonctions de sélection tend vers cette loi uniforme

" xÎ E^N " k

lim

l® ¥

F_l

(

k,f(x₁),f(x₂),··· ,f(x_N)

)

(

k,f(x₁),f(x₂),··· ,f(x_N)

)

(7)

Les conditions 5.3.2, 5.3.2, et 5.3.2 nous permettent d'assurer que le mécanisme de transition de la chaîne (X_k^l) converge vers celui du processus de fond (X_k^¥) :

" y,zÎ E^N

lim

l® ¥

[

X_k+1^l=z| X_k^l=y

]

= P

é
ê
ê
ë

k+1

=z| X

ù
ú
ú
û

C'est également en ce sens que l'on interprète la chaîne (X_k^l) comme une perturbation de la chaîne (X_k^¥).

Les vitesses de convergence intervenant dans chacun des opérateurs jouent un rôle important. La formulation proposée en (5.3.2), (5.3.2) et (5.3.2), permet un ajustement équitable de ces vitesses (elles sont logarithmiquement du ordre) de sorte qu'aucun opérateur ne domine les autres dans la dynamique. lorsque l tend vers l'infini, les conditions (5.3.2), (5.3.2), et (5.3.2) nous permettent d'assurer que le mécanisme de transition de la chaîne (X_k^l) converge vers celui du processus de fond (X_k^¥), et on a²¹ :

" y,zÎ E^N

lim

l® ¥

[

X_k+1^l=z| X_k^l=y

]

= P

é
ê
ê
ë

k+1

=z| X

ù
ú
ú
û

La chaîne (X_k^l) se comporte alors comme le ferait (X_k^¥). La théorie de Freidlin-Wentzell nous donne les outils pour simplifier l'étude de ces processus à temps continu.

5.4 La théorie de Freidlin et Wentzell

5.4.1 Principe

Soit le système différentiel de R^N satisfaisant les équations déterministes :

ì
í
î

dx_t=b(x_t) dt

x₀=x_ini

(8)

Sous de ``bonnes'' hypothèses, il existe une solution (trajectoire) unique, x(t) à l'équation (5.4.1) et à la condition initiale associée. l'une des préoccupation immédiates est de savoir si cette solution va, ou non, tendre vers un équilibre (qui n'est pas forcément unique). Et si oui, quel en est l'ensemble de stabilité. L'équilibre est défini comme une fonction constante x^* telle que x^*=lim_{t® ¥} x_t , et l'ensemble de stabilité comme l'ensemble K( x^*) des points de départ qui mènent à cet équilibre²². On peut élargir cette notion, d'équilibre et de stabilité, par celles, très proches, d'attracteur et de bassin d'attraction.

Un attracteur du système est le voisinage compact K_i d'un point visité une infinité de fois, et le bassin d'attraction l'ensemble des points de départ qui mènent à cet attracteur. Nous supposerons que R^d possède un nombre fini d'attracteurs K₁, ··· ,K_r.

La théorie de Freidlin-Wentzell étudie la perturbation du système 5.4.1, par des perturbation Browniènes, d'intensité . Le système déterministe 5.4.1 devient alors un système différentiel stochastique.

ì
ï
ï
í
ï
ï
î

=b(X

) dt+ dw _t

=x_ini

(9)

Le processus (X_t)_tÎ_R^₊ est maintenant un processus stochastique perturbé par le mouvement brownien (w _t)_tÎ_R^₊ et dépendant de . La situation change alors puisque les perturbations brownienne permettent au processus de s'échapper de n'importe quel bassin d'attraction, et en fait le processus les visite tous.

De plus, le processus est ergodique et admet une unique mesure de probabilité invariante, i.e.

" B borelien de R

lim

t® ¥

é
ê
ê
ë

Î B

| X

=x_ini

ù
ú
ú
û

=µ

( B)

existe est la probabilité de présence du processus dans le Borélien B , lorsque le système a atteint son état d'équilibre. Cette probabilité µ est invariante avec le point de départ x_ini.

Lorsque les perturbation cessent, le processus se comporte comme dans 5.4.1 et reste presque sûrement au voisinage V(K₁È ··· È K_r) des attracteur,.tandis que la probabilité de présence dans n'importe quel Borélien A disjoint de K₁È ··· È K_r disparaît.

lim

® 0

(

V(K₁È ··· È K_r)

)

lim

® 0

(

)

Le résultat principal de Freidlin et Wentzell repose sur l'équivalence du processus (X_t)_tÎ_R^₊ à temps continu et espace d'état R^d et du processus (Z_n)_nÎ_N à temps discret et espace d'état fini {1,··· .r} décrivant les visites au nième attracteur.

La construction précise de (Z_n)_nÎ_N, n'est pas reportée ici mais nous en donnons un aperçu afin de mieux comprendre ce dernier processus.

Si x_ini est ``proche'' de l'attracteur K_h alors Z_o=hÎ {1,··· .r}
puis le processus, sous l'influence de (w _t), est attiré par K_s et Z₁=s
etc..

La chaîne de Markov²³ ainsi crée a pour espace d'états {1,··· .r}, est irréductible, et possède une unique mesure de probabilité invariante n .

L'étude du comportement asymptotique de la mesure µ est ``équivalente'' à l'étude du comportement asymptotique de la mesure n

Nous passons sous silence l'étude des probabilité de transition P[ Z_n=i| Z_n=j] de la chaîne (Z_n)_nÎ_N qui s'écrivent comme des intégrales sur l'ensemble des fonctions f qui lient les attracteurs K_i et K_j, laissant le lecteur intéressé se reporter à la lecture de Freidlin et Wentzell [15], ou de Cerf [11].

Notons toutefois que ces probabilité de transition s'écrivent :

é
ê
ê
ë

=i| Z

ù
ú
ú
û

ln ~ exp -

V(i,j)

où V(i,j)=inf {V(f ), f (· ) continue [ 0.1] R^d, f ( 0) Î K_i, f ( T) Î K_j}

et V(f )=ò₀¹| f ( t) -b( f ( t) ) ^·| ²dt. est une constant associée à f et caractérisant sa vitesse de convergence.

La quantité V(i,j) ou coût de communication, mesure le coût de passage de l'attracteur K_i à l'attracteur K_j.

Les intensités de transitions de la chaîne (Z_n)_nÎ_N, nous ouvrent la voie pour déterminer la mesure invariante n .

5.4.2 Mesure invariante n

Les outils qui permettent de déterminer cette mesure invariante ont été développés, une nouvelle fois par Freidlin et Wentzell, nous aurons besoins de certains d'entre eux.

Définition :Soit i un élément de {1,...,r}.

Un i-graphe sur {1,...,r} est un graphe g sur {1,...,r} possédant les propriétés suivantes :

" j¹ i, le graphe g contient une unique flèche issue de j
Il existe un chemin dans g qui mène de j à i
g ne contient pas de flèche issue de i

Il s'agit donc d'un graphe sans cycles formé de chemins qui aboutissent en i. On note G(i) l'ensemble des i-graphes sur {1,...,r}.

Définition :La fonction d'énergie virtuelle W est la fonction de {1,...,r} dans R⁺ définie par :

" iÎ {1,...,r} W(i)=

min

gÎ G(i)

(

a ® b

)

Î g

V(a ,b )

a cette fonction est associé l'ensemble W^* des minima globaux de W.

Finalement, la mesure invariante n est caractérisée par :

" iÎ {1,...,r} n

(i)ln ~ exp -W(i)-W(W^*) ²

où W(W^*)=min { W(i) : iÎ {1,...,r}} .

Le comportement asymptotique de n (et par la même occasion de µ ) est donc connu : la mesure n se concentre sur les attracteurs dont l'indice est dans W^* et décroît vers zéro à la vitesse exp -Cste/ ² pour les autres attracteurs. Il existe donc un sous-ensemble de W^* de l'ensemble des attracteurs sur lequel se concentre la mesure invariante du processus.

lim

® 0

lim

t® ¥

é
ê
ê
ë

Î V

æ
ç
ç
è

iÎ W^*

K_i

ö
÷
÷
ø

| X

=x_ini

ù
ú
ú
û

La dynamique du processus est donc caractérisable.

5.4.3 Dynamique du processus.

Dans sa thèse, Cerf nous donne une très claire interprétation de la hiérarchie des cycles qui caractérisent la dynamique du processus. Supposons que le processus soit initialement dans le bassin d'attraction de K₁. I1 quitte K₁ au bout d'un temps fini. Parmi toutes les trajectoires de sortie, il en existe une plus ``probable'' que les autres, qui l'amène vers un nouvel attracteur; par exemple K₂ puis, bientôt K₃. L'ensemble des attracteurs étant par hypothèse fini, le processus finit par revisiter un attracteur formant un cycle d'ordre 1 sur lequel le processus tourne longtemps, très longtemps. Englobons maintenant ces trois attracteurs dans une boîte. Comme toujours, les perturbations browniennes finissent par pousser le processus hors de cette boîte, et ici encore, il existe une trajectoire de sortie canonique qui fait tomber le processus dans un nouveau bassin d'attraction, ou plus généralement, dans un autre cycle d'ordre 1.

Les cycles d'ordre 1 sont aussi en nombre fini, et le processus finit par revisiter un cycle d'ordre 1: un cycle d'ordre 2 est alors formé, dans lequel le processus reste piégé très très longtemps. En continuant de la sorte, il est possible de construire toute une hiérarchie de cycles qui épuise l'ensemble des attracteurs et fournit une image très précise de la dynamique asymptotique du processus. A chaque transition entre cycles est associée une constante qui caractérise la difficulté de la transition.

Enfin, lorsque décroît avec le temps, i.e. = (t) est une fonction de t qui tend en décroissant vers 0, nous obtenons un processus de Markov inhomogène (le mécanisme de transition dépend du temps).

Si (t) décroît très lentement, de sorte qu'à chaque instant la loi de X_t soit proche de l'état d'équilibre associé au niveau de perturbation (t), la situation ne change pas fondamentalement. La loi limite correspond à la limite de la suite des lois d'équilibre.
Si au contraire (t) décroît très rapidement, le processus risque de rester piégé dans certains sous-ensembles d'attracteurs: plus précisément, dans la hiérarchie des cycles, certaines transitions ne pourront être effectuées qu'un nombre fini de fois, alors que d'autres, plus ''faciles'', seront réalisées une infinité de fois avec probabilité 1. La loi limite dépend alors fortement du point de départ.

La hiérarchie des cycles permet ainsi de décrire les dynamiques possibles de (X_t) en fonction de la vitesse de décroissance de (t).

5.5 Résultats de convergence

Lorsque l croit vers l'infini, les perturbations affectant le processus (X_k^l) diminuent de sorte que cette chaîne se comporte, presque sûrement, comme la chaîne (X_k^¥). Plus précisément, nous savons que les attracteurs de la chaîne (X_k^¥) sont les population d'équi-adaptation S et les populations uniformes (attracteurs stables). La chaîne (X_k^l) va donc être attirée par ses attracteurs, en commençant par l'ensemble S.

La théorie de Freidlin et Wentzell nous permet de reporter cette étude sur celle de la chaîne des (Z_k^l) des visites successives de (X_k^l) à l'ensemble S. Nous poserons donc Z_k^l=X_T_{_k}^l où T_k est l'instant de la kième visite de (X_k^l) dans S.

Les probabilité de transition de la chaîne (Z_k^l), sont estimées à l'aide des opérateurs définis en 5.3 et selon le shéma développé ci-dessus. Les fonctions de coût de communication V(i,j) et d'énergie virtuelle W sont définies et estimées.

Nous savons alors que la suite des mesures stationnaires de la chaîne (X_k^l) se concentre sur l'ensemble W^* des minima de W :

" x_iniÎ E^N

lim

l® ¥

lim

k® ¥

[

X_k^lÎ W^*| X₀^l=x_ini

]

L'un des principaux résultats indique qu'il existe une taille de la population de (X_k^l), (taille critique) telle que les maxima de f soient atteints asymptotiquement avec probabilité 1.

5.5.1 Taille critique

Supposons fixés l'espace d'état E, la fonction d'adaptation f, les noyaux de transition de mutation a et de croisement b , ainsi que les constantes positives gérant les trois opérateurs a, b, et c.

(Cerf 1993)

Il existe une valeur critique N^*, telle que lorsque la taille de la population de l'algorithme génétique dépasse N^*, l'ensemble f^* des maxima globaux de f, contient l'ensemble W^*.

Cette taille critique N^* , dépend fortement de l'espace d'état E, de la fonction d'adaptation f, des noyaux a et de croisement b , ainsi que des paramètres a, b, et c.

Une borne grossière, mais lisible de N^* est :

N^*£

aR+c(R-1)D

min (a,

, cd )

où :

R est le nombre minimal de transition permettant de joindre deux points arbitraires de E par mutation
D et d sont des paramètres d'échelle :
- D =max { | f(i)-f(j)| :i,jÎ E} paramètre mesurant les écarts maximaux de f
- d =min { | f(i)-f(j)| :i,jÎ E, f(i)¹ f(j)} mesurant les écarts minimaux.

Il est intéressant de relever que le résultat est obtenu sans faire intervenir l'opérateur de croisement, qui n'est donc pas indispensable. L'exploration par mutation et le guide de la force de sélection suffisent à assurer la convergence vers f^*.

Ce premier résultat nous indique que des que N³ N^*, la suite des mesures stationnaires de la chaîne (X_k^l) se concentre asymptotiquement sur f^* lorsque l tend vers l'infini. L'étape suivante consiste donc à faire évoluer l , et donc l'intensité des perturbations, en fonction de la génération pour obtenir un algorithme génétique correspondant à ceux présentés dans la section 2. Nous obtenons alors une chaîne de Markov inhomogène (X_k^l(k)) dont le mécanisme de transition dépend alors de la génération k.

5.5.2 Vitesse de convergence

Le principal problème est de savoir si cette chaîne inhomogène peut avoir un comportement proche de celui de la chaîne homogène (X_k^l), et si oui, sous quelles conditions. La vitesse de croissance de l(k) vers l'infini, est bien évidemment, au centre du débat.

Si l(k) croît ``lentement'', alors la loi de X_k sera proche de la loi stationnaire µ ^(l(n)) de niveau de perturbation (l(n)) associé à l(n).
Si l(k) croît ``rapidement'', alors X_k risque de rester piégé dans des bassins d'attraction ne correspondant pas aux maxima de f, l'intensité des perturbation devenant trop faible pour pouvoir s'en échapper.

La vitesse recherchée se situe entre ces deux extrêmes, permettant à X_k de s'échapper des ``mauvais'' bassins d'attraction (ne correspondant pas à des maxima de f) et de rester piéger dans le ``bon'' (celui des points de f^*).

La vitesse de convergence de la suite l(k) est caractérisée par l'exposant de convergence²⁴, l .

Définition :

L'exposant de convergence l de la suite l(k) est l'unique réel l tel que :

kÎ N

l(k)

-q

®		converge pour q >l

®		diverge pour q <l

Deux conditions pour la colonisation de f^* sont également données par Cerf, l'une nécessaire, l'autre suffisante.

Condition nécessaire pour la colonisation de f^*

Pour que :

" x_iniÎ E^N P

é
ë

$ K " k³ K

é
ë

T_k

ù
û

Ì f^*| X₀=x_ini

ù
û

c'est à dire, pour que la chaîne Z_k=X_T_{_k} des visites successives des attracteurs soit piégée dans f^* après un nombre fini K de transitions,

il est nécessaire que l'exposant de convergence l de la suite l(k) appartienne à l'intervalle ] f ,y [ .

Les constantes f et y sont des caractéristiques du problème,l'intervalle ] f ,y [ est alors non vide pour N assez grand.

Condition suffisante pour la colonisation de f^*

Il existe deux constantes h et r tel que si l'exposant de convergence l de la suite l(k) appartient à l'intervalle ] h ,r [ , alors :

" x_iniÎ E^N P

é
ë

$ K " k³ K

é
ë

T_k

ù
û

Ì f^* , X_kÌ f^*| X₀=x_ini

ù
û

ce qui signifie qu'après un nombre fini de transitions, nous avons presque sûrement, la situation suivante :

la chaîne X_T_{_k} est piégée dans f^*,
la population X_k contient toujours un ou des individus appartenant à f^*.

5.5.3 En guise de conclusion

D'autres résultats existent, tant dans le travail de Cerf, que dans la littérature citée dans cette section. Ils demandent cependant un investissement supplémentaire dans la compréhension des outils développés. Le but de cette section était de convaincre le lecteur que l'étude théorique des algorithmes génétiques donne (déjà) de sustantiels résultats. De nombreuses interrogations demeurent cependant concernant les relations réelles entre les différents paramètres caractérisant l'algorithme génétique et les choix pratiques de ceux ci. Dans ce domaine, la pratique devance encore la théorie, même si les mécanismes commencent à être plus clairs. Il reste également à étudier les nombreux raffinements présentés dans la section 2, et aujourd'hui en application. Comment incorporer les opérateurs de partage, et leur implémentation par bouquets ? Comment trouver de nouveaux algorithmes génétiques encore plus efficaces ? Autant de questions qui trouverons sans doute des réponses dans les travaux futurs.

L'exemple de l'aspirine nous vient à l'esprit, ce n'est que dans les années 70 que l'on comprit réellement les mécanismes de son action, cela ne l'a pas empêché d'agir depuis ça découverte en 18??.

6 Perspectives

7 Appendice : Un exemple élémentaire.

Soit le problème de maximisation suivant :

ì
í
î

max f(x)=4x(1-x)

xÎ [0,1]

La fonction f(x) admet un maximum unique en x=0,5 pour lequel f(x) vaut 1, comme le montre la représentation graphique ci-dessous.

itbpFX7.6508cm5.0786cm0cmPlot language "Scientific Word";type "MAPLEPLOT";width 7.6508cm;height 5.0786cm;depth 0cm;display "FULL";plot_snapshots TRUE;function 4x(1-x);linecolor "black";linestyle 1;linethickness 1;pointstyle "point";xmin "-0.02";xmax "1.02";xviewmin "-0.02";xviewmax "1.02";yviewmin "-0.1032";yviewmax "1.022";rangeset"X";recompute TRUE;phi 45;theta 45;plottype 4;numpoints 60;axesstyle "normal";xis x;var1name x;valid_file "T";tempfilename 'C:/CBONVIEU/ARTICLES/DJTEJIVV.wmf';

Codage

Afin de bien visualiser les propriétés des opérateurs nous décidons de traiter ce problème en codant les éléments de [0,1] en chaînes de bits de longueur 8. Par exemple, 10111010 constituera un élément de la population.

Population initiale (Génération zéro)

L'algorithme génétique consiste tout d'abord à tirer une population initiale de N=4 éléments, (q _i)_i=1,..4 donnés dans le tableau ci dessous, nous évaluons par la même occasion leur adaptation, c'est à dire ici f(q _i).

Eléments	Eléments Codés	Adaptation : f(q _i)
q ₁	10111010	0,794678
q ₂	11011110	0,460693
q ₃	00011010	0,364990
q ₄	01101100	0,975586

(10)

Il va s'agir maintenant de sélectionner les éléments en fonction de leur adaptation. On le voit ici, les éléments q ₄ et q ₁ sont les meilleurs.

Sélection

Pour sélectionner ces candidats à reproduction, nous allons utiliser la sélection de la roue de la fortune et attribuer à chacun une probabilité de reproduction égale à :

P_i=f(q _i)

j=1

f(q _j)

et donc le tableau 7 s'élargit de cette probabilité de reproduction de chaque élément.

Eléments	Eléments Codés	f(q _i)	P_i
q ₁	10111010	0,794678	0,794/2,59=0,31
q ₂	11011110	0,460693	0,460/2,59=0,18
q ₃	00011010	0,364990	0,364/2,59=0,14
q ₄	01101100	0,975586	0,975/2,59=0,37
mathbfCumul		mathbf2,593

Un problème pratique se pose : Comment ``tirer'' 4 nombres parmi 4 avec replacement en affectant à chacun cette probabilité ?

Il existe pour cela une méthode simple et rapide, il suffit d'attribuer un segment de taille P_i à l'individu q _i et de reporter ces segments bouts-à-bouts dans l'intervalle²⁵ [0,1]. Les individus sont identifiés par un segment particulier de longueur P_i .

Sur l'exemple cela donne :

q ₁ est ainsi caractérisé par l'intervalle [0,0.31] de longueur 0,31

q ₂ est caractérisé par l'intervalle [0.31,0.49] de longueur 0,18

q ₃ par l'intervalle [0.49,0.63] de longueur 0,14

et q ₄ par [0.63,1] de longueur 0,37.

On tire ensuite h uniformément dans [0,1] et l'on reproduit 4 fois ce tirage, on détermine ainsi 4 nouveaux éléments grâce à ce tirage. Ici le tirage de h donne ; 0.47(q ₂ est sélectionné), 0.89 (q ₄), 0.18 (q ₁) et 0.75 (q ₄ de nouveau). A ce stade q ₃ est éliminé de la population tandis que q ₄ est reproduit deux fois.

Les opérateurs de croisement et de mutation s'appliqueront donc sur la nouvelle population constituée de (q ₂, q ₄, q ₁ et q ₄) renommés b ₁, b ₂, b ₃ et b ₄.

Eléments	Eléments Sélectionnés	Renommés
q ₁	q ₂=10111010	b ₁
q ₂	q ₄=01101100	b ₂
q ₃	q ₁=01101100	b ₃
q ₄	q ₄=01101100	b ₄

Croisement

La probabilité de croisement P_c est ici fixée à 50% (on ne peut faire moins étant donné la taille de la population considérée), cela signifie que l'on va tirer un couple au hasard et lui appliquer le croisement chromosomique à un point. (b ₁, b ₃) constitue le couple destiné à être transformé, il faut encore déterminer la position du croisement dans les composantes (gènes) de ces éléments. Cette position peut être elle aussi tirée au hasard ou choisie arbitrairement. Nous décidons d'effectuer les croisements sur le milieu afin de rendre l'exemple plus parlant.

Les parties terminales des individus b ₁et b ₃ sont donc échangées, comme suit :

ì
í
î

b ₁=10111010		1011 1100=l ₁

b ₃=01101100		0110 1010=l ₃

engendrant ainsi deux nouveaux individus (les enfants) l ₁ et l ₃.

On peut, sur la base de ces nouveaux individus muter aléatoirement l'une des composantes de l'un des individus constituant la nouvelle population (l ₁, b ₂, l ₃ et b ₄).

Mutation

La probabilité de mutation est ici de P_c=0.25, de sorte qu'un individu sur les quatre sera choisi. Il s'agit de l ₃ dont une des composantes sera changée. On peut, pour cela, décider de cette composante dans le processus ou tirer celle ci aléatoirement. La 7ème composante sera ici changée.

l ₃=01101010

01101000=l ₃^*

Il est intéressant de noter que l ₃ a été muté sans qu'aucune évaluation n'ait été effectuée.

Nouvelle population (Génération un)

Nous pouvons maintenant examiner la nouvelle population, correspondant à la deuxième génération et réitérer le processus. Réévaluons ces nouveaux individus.

Nouveaux Eléments (renomés)	Eléments Codés	Adaptation : f(a _i)
l ₁ a ₁	10111100	0,980225
b ₂ a ₂	01101100	0,794678
l ₃^* a ₃	01101000	0,483398
b ₄ a ₄	01101100	0,975586
mathbfCumul		3.232

(11)

Lorsqu'on compare les tableaux 7 et 7, plusieurs remarques viennent à l'esprit et méritent d'être notées :

Le meilleur individu a ₁ est un individu nouveau (issu du croisement de q ₂ et de q ₄)
Cet individu permet d'avoir une adaptation supérieure à celle du meilleur individu de la population originale (0.98 pour a ₁ contre 0.97 pour q ₄)
Ce dernier élément est d'ailleurs toujours présent ici (il est ici renommé a ₄)
L'adaptation totale (et donc l'adaptation moyenne) est supérieure à sa valeur de départ (3.232 contre 2.593 pour la génération zéro).

Chacune des opération décrites ici ne prend que quelques centièmes de secondes sur un ordinateur, on trouve une valeur de x=0,499959 après 100 générations et 2,5s de calcul.

y=x²sin (x^0.5)· zln

(

cos (z)

)

itbpF4.3647in2.9092in3.0294inPlot language "Scientific Word";type "MAPLEPLOT";width 4.3647in;height 2.9092in;depth 3.0294in;display "USEDEF";plot_snapshots TRUE;function xsin (x^0.5)· zln ( cos (z)) ²;linecolor "black";linestyle 1;linethickness 1;pointstyle "point";xmin "-5";xmax "5";ymin "-5";ymax "5";recompute TRUE;phi 45;theta 26;plottype 5;num-x-gridlines 20;num-y-gridlines 20;plotstyle "wireframe";axesstyle "frame";plotshading "Z";lighting 2;xis x;yis z;var1name x;var2name z;valid_file "T";tempfilename 'C:/CBONVIEU/ARTICLES/DJTEJJSJ.wmf';

z=x(10-x)sin (x^0.5)· yln

(

cos (y)

)

itbpF4.8551in3.2353in0inPlot language "Scientific Word";type "MAPLEPLOT";width 4.8551in;height 3.2353in;depth 0in;display "USEDEF";plot_snapshots TRUE;function x(10-x)sin (x^0.5)· yln ( cos (y)) ²;linecolor "black";linestyle 1;linethickness 1;pointstyle "point";xmin "-5";xmax "10";ymin "-8";ymax "3";xviewmin "-5";xviewmax "10";yviewmin "-5";yviewmax "5";rangeset"X";recompute TRUE;phi 45;theta 45;plottype 5;num-x-gridlines 20;num-y-gridlines 20;plotstyle "wireframe";axesstyle "frame";plotshading "Z";lighting 2;xis x;yis y;var1name x;var2name y;valid_file "T";tempfilename 'C:/CBONVIEU/ARTICLES/DJTEJJAG.wmf';

References

[1]: Alliot J.M. and T. Schiex (1993) : ``Intelligence artificielle et informatique théorique'', Cépadues Editions.
[2]: Andreoni J. and J. Miller (1995) : ``Auctions with Artificial Adaptative Agents'', Games and Economic behavior, Vol. 10, pp 39-64.
[3]: Arifovic J. (1994) : `` Genetic algorithm learning and the cobwell model'', Journal of Economic Dynamic and Control, No 18, pp.2-28.
[4]: Arifovic J. and C. Eaton (1995) : `` Coordination via Genetic Learning'', Computational Economics, Vol.8, No. 3, pp. 181-203.
[5]: Arthur W. B. (1991) : ``Designing Economic Agents that Act Like Human Agents : A Behavioral Approach to Bounded Rationality'', AEA Papers and proceedings, Vol. 81, No.2.
[6]: Axelrod R. (1987) : ``The Evolution of Strategies in the Iterated Prisoner's Dilemma'', in Genetic Algoritms and Simulated Annealing, L. Davis editor, Pitman, London.
[7]: Beaumont P. and P. Bradshaw (1995) : `` A distributed Parallel Genetic algorithm for solving optimal Growth Models'', Computational Economics, Vol.8, No. 3, pp. 159-179.
[8]: Birchenhall C. (1995) : ``Introduction of Computational Economics special issue on Genetic algorithm'', Computational Economics, Vol.8, No. 3, pp. 155-158.
[9]: Birchenhall C. (1995) : ``Modular technical change and Genetic algorithms'', Computational Economics, Vol.8, No. 3, pp. 233-253.
[10]: Catoni O. (1990) : ``Large deviations for Annealing'', Thèse de Doctorat, Université de Paris XI..
[11]: Cerf R. (1994) : ``Une théorie asymptotique des algorithmes génétiques'', These de Doctorat, Université de Montpellier II.
[12]: Dorsey R. E. and W. J. Mayer (1995) : ``Genetic Algorithms for Estimation Problems With Multiple Optima, Nondifferentiability, and Other Irregular Features'', Journal of Business and Economic Statistics, Vol.13, No 1.
[13]: Durand N., N.Alech, J. M. Alliot and M. Shoenauer (1994) : ``Genetic Algorithms for Optimal Air Trafic Conflict Resolution'' In Proceedings of the second Singapore conference on Intelligent Systems, SPICIS.
[14]: Farley A. M. and S. Jones (1994) : ``Using a Genetic Algorithm to determine an Index of Leading Economic Indicators'', Computational Economics, Vol. 7, No 3.
[15]: Freidlin M. I. and Wentzell (1983) : ``Random Perturbations of Dynamical Systems'', Springer Verlag, New-York.
[16]: Goffe L., Ferrier G. D. and J. Roger (1994) : ``Global optimization of statistical functions with simulated annealing'', Journal of Econometrics, Vol. 60, pp. 65-99.
[17]: Goldberg D. (1989) : ``Genetic Algorithms'' Addison Wesley editor.
[18]: Holland J. H. (1975) : ``Adaptation in Natural and Artificial Systems'' , University of Michigan press.
[19]: Holland J. H.and J. H Miller (1991) : ``Artificial Adaptation Agents in Economic Theory'', American Economic Review papers Proceedings, Vol. 81, no 2.
[20]: Herrnstein R. J. (1991) : ``Experiments on stable Suboptimality in Individual Behavior'', AEA Papers and proceedings'', Vol. 81, No.2.
[21]: Michalewicz Z. (1991) : `` Genetic Algorithms + Data Structures = Evolution programs'' Springer Verlag, New-York.
[22]: Petit-Singeot F. and R. Cazoulat (1994) `` Réplicateurs Adaptatifs et Théorie des Jeux'' , in Journées Evolution Artificielle, 20-23 septembre 94, ENAC.
[23]: Tordjman H. (1994) : `` Dynamiques spéculatives, hétérogénéité des agents et apprentissage : Le cas des taux de change'', These de Doctorat, C.E.F.I;, Université d' Aix Marseille II.
[24]: Trouvé A. (1993) : ``Parallélisation massive du recuit simulé'', Thèse de Doctorat, Université de Paris XI..
[25]: Vriend N. J. (1995) : `` Self-Organisation of Markets : An Example of a Computational Approach'', Computational Economics, Vol.8, No. 3, pp. 205-231.
[26]: Yin X. and N. Germay (1993) : ``A Fast Genetic Algorithm with sharing scheme using cluster analysis methods in Multimodal function optimization'', in Proceedings of the Artificial neural Nets and Genetic algorithms.

1

Un grand merci à Jean-Marc Alliot, Christophe Bisière, Nicolas Durand, Nathalie Lenoir et Eric Malin.

2

La vitesse de calcul du premier CRAY, le 1S, est désormais dépassée par celle d'un pentium 133 MgH - voir Goffe et al.[16] , pour une intéressante comparaison des matériels courament utilisés dans le monde.

3

Les logiciels statistiques les plus utilisés comme GAUSS, SAS, RATS, utilisent des algorithmes plus ou moins évolués de ce type.

4

fonction approximativement quadratique, unicité du maximum, de telle sorte qu'un maximum local est global, etc..

5

La stratégie ``oeil pour oeil'' survit ainsi très bien dans le cadre du dilemme du prisonnier répété (voir Axelrod [6], ou Petit-Singeot et Cazoulat [22]).

6

Ces qualificatifs n'étant que relatifs à la population et à la fonction d'adaptation f considérés.

7

Par analogie avec la biologie on parle également de ``chromosomes'', les bits représentant les ``gènes'' composant ce chromosome.

8

On utilise souvent la ``distance de Hamming'' comme mesure de la dissimilarité entre deux éléments de population pour le codage binaire. Cette mesure compte les différences de bits de même rang de ces deux sequences.

9

Un code de gray possède la propriété de ne faire differer que d'un bit deux entier successifs.

10

Les ``roues de la fortune'' que l'on rencontre dans les foires ont souvent des secteurs de tailles différentes suivant l'importance du lot. C'est ce principe qui est reproduit ici.

11

On calcule cette probabilité théorique en calculant le rapport de la fitness de l'individu à la somme des fitness des autres individus, ici : 2,510,6

12

Il n'est pas nécessairement compris entre 0 et 1, il peut par exemple prendre des valeurs dans l'intervalle [-0.5,1.5] afin de générer des points hors du segment, et éviter un appauvrissement de population.

13

Cette population est constituée de d+1 éléments où d est la dimension de l'espace admissible.

14

Une procédure d'optimisation ``classique'' peut être ajoutée à la fin de l'algorithme de manière à afiner le résultat.

15

Un principe d'élitisme sera toutefois appliqué afin de conserver le meilleur élément d'un groupe.

16

Comment, en effet, déterminer la distance séparant deux stratégies d'enchères ? Deux équilibres de Nash dans un jeu en comportant d'autres ? Deux chemins dans le problème du voyageur de commerce ?

17

Mot qu nous utiliserons pour traduire le terme ``cluster''

18

Laboratoire d'Optimisation Globale CENA-ENAC (Centre d'Etudes de la Navigation Aérienne, Ecole Nationale de l'Aviation Civile).

19

On peut associer ces chromosomes à des ``mots'' composés sur l'alphabet {0,1}, les gènes sont alors les ``lettres'' 0 ou 1.

20

C'est la probabilité P_l(i,j) pour un point i de E de se transformer par mutation en un point j de E

21

C'est également en ce sens que l'on interprète la chaine (X_k^l) comme une ``perturbation'' de la chaine (X_k^¥).

22

L'ensemble de stabilité de l'équilibre x^* est :

K(x^*)=

ì
í
î

x_iniÎ R^N, t.q. pour x_t solution de 5.4.1

;

lim

t® ¥

x_t=x^*

ü
ý
þ

Pour chaque équilibre on définit ainsi son ensemble de stabilité. Cet équilibre est stable s'il contient un voisinage de l'équilibre, et instable s'il existe des points de départ infiniment proche de l'équilibre qui ne menent pas à celui-ci.

23

La nature Markovienne de w _t, nous permet de montrer qu'il s'agit bien là d'une chaine de Markov.

24

Egalement appelé rayon de convergence.

25

La somme des P_i vaut, en effet, 1.

This document was translated from L^AT_EX by H^EV^EA.

Principes Mathématiques et Utilisations des Algorithmes Génétiques

Christophe Bontemps1

18 Novembre 1995

1 Introduction

2 Principes

2.1 Principes généraux des algorithmes génétiques

2.2 Codage et Opérateurs

2.2.1 Coder ou ne pas coder ?

2.2.2 Gestion des contraintes

2.2.3 Génération aléatoire de la population initiale

2.2.4 Sélection

Ordonnancement (Ranking)

Roue de la fortune (Roulette wheel selection)

Roue modifiée (Stochastic remainder without replacement)

2.2.5 Croisement

2.2.6 Mutation

3 Améliorations classiques

3.1 Introduction

3.2 Scaling

3.2.1 Scaling linéaire

3.2.2 Scaling exponentiel

3.3 Partage (sharing)

3.3.1 Principe

3.3.2 Partage par bouquets (Clustered sharing)

3.4 Algorithmes génétiques et recuit simulé

3.4.1 Introduction

3.5 Recuit simulé

3.5.1 Principe

3.6 Croisement avec recuit

3.6.1 Principe du croisement avec recuit simulé

4 Utilisation et exemples

5 Résultats théoriques

5.1 Modélisation de l'algorithme génétique

5.2 Description rapide de l'algorithme

5.2.1 Mutation Xk¾® Yk

5.2.2 Croisement Yk¾® Zk

5.2.3 Sélection Zk¾® Xk+1

5.3 Modélisation

5.3.1 Processus de fond (Xk¥)

5.3.2 Processus perturbé (Xkl)

Mutation Xkl¾® Ukl

Croisement Ukl¾® Vkl

Sélection Vkl¾® Xk+1l

5.4 La théorie de Freidlin et Wentzell

5.4.1 Principe

5.4.2 Mesure invariante n

5.4.3 Dynamique du processus.

5.5 Résultats de convergence

5.5.1 Taille critique

5.5.2 Vitesse de convergence

5.5.3 En guise de conclusion

6 Perspectives

7 Appendice : Un exemple élémentaire.

References

Christophe Bontemps¹

5.2.1 Mutation X_k¾® Y_k

5.2.2 Croisement Y_k¾® Z_k

5.2.3 Sélection Z_k¾® X_k+1

5.3.1 Processus de fond (X_k^¥)

5.3.2 Processus perturbé (X_k^l)

Mutation X_k^l¾® U_k^l

Croisement U_k^l¾® V_k^l

Sélection V_k^l¾® X_k+1^l