Soutenance mémoire
AG : généralités et améliorations
Principes généraux
Les algorithmes génétiques sont des algorithmes d’optimisation s’appuyant sur des techniques dérivées de la génétique et de l’évolution naturelle : croisements, mutations, sélection, etc. Les algorithmes génétiques ont déjà une histoire relativement ancienne, puisque les premiers travaux de John Holland sur les systèmes adaptatifs remontent à 1962 [Hol62]. L’ouvrage de David Goldberg [Gol89c] a largement contribué à les vulgariser.
Un algorithme génétique recherche le ou les extrema d’une fonction définie sur un espace de données. Pour l’utiliser, on doit disposer des cinq éléments suivants :
1. Un principe de codage de l’élément de population. Cette étape associe à chacun des points de l’espace d’état une structure de données. Elle se place généralement après une phase de modélisation mathématique du problème traité. Le choix du codage des données conditionne le succès des algorithmes génétiques. Les codages binaires ont été très employés à l’origine. Les codages réels sont désormais largement utilisés, notamment dans les domaines applicatifs, pour l’optimisation de problèmes à variables continues.
2. Un mécanisme de génération de la population initiale. Ce mécanisme doit être capable de produire une population d’individus non homogène qui servira de base pour les générations futures. Le choix de la population initiale est important car il peut rendre plus ou moins rapide la convergence vers l’optimum global. Dans le cas où l’on ne connaît rien du problème à résoudre, il est essentiel que la population initiale soit répartie sur tout le domaine de recherche.
3. Une fonction à optimiser. Celle-ci prend ses valeurs dans R+ et est appelée fitness ou fonction d’évaluation de l’individu. Celle-ci est utilisée pour selectionner et reproduire les meilleurs individus de la population.
4. Des opérateurs permettant de diversifier la population au cours des générations et d’explorer l’espace d’état. L’opérateur de croisement recompose les gènes d’individus existant dans la population, l’opérateur de mutation a pour but de garantir l’exploration de l’espace d’état.
5. Des paramètres de dimensionnement : taille de la population, nombre total de générations ou critère d’arrêt, probabilités d’application des opérateurs de croisement et de mutation.
Description détaillée
Codage des données
Historiquement, le codage utilisé par les algorithmes génétiques était représenté sous forme de chaînes de bits contenant toute l’information nécessaire à la description d’un point dans l’espace d’état. Ce type de codage a pour intérêt de permettre de créer des opérateurs de croisement et de mutation simples. C’est également en utilisant ce type de codage que les premiers résultats de convergence théorique ont été obtenus.
Génération aléatoire de la population initiale
Le choix de la population initiale d’individus conditionne fortement la rapidité de l’algorithme. Si la position de l’optimum dans l’espace d’état est totalement inconnue, il est naturel d’engendrer 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 [MJ91]. Si par contre, des informations a priori sur le problème sont disponibles, il paraît bien évidemment naturel d’engendrer les individus dans un sous-domaine particulier afin d’accélérer la convergence. Dans l’hypothèse où la gestion des contraintes ne peut se faire directement, les contraintes sont généralement incluses dans le critère à optimiser sous forme de pénalités.
Gestion des contraintes
Un élément de population qui viole une contrainte se verra attribuer une mauvaise fitness et aura une probabilité forte d’être éliminé par le processus de sélection. Il peut cependant être intéressant de conserver, tout en les pénalisant, les éléments non admissibles car ils peuvent permettre de générer des éléments admissibles de bonne qualité. Pour de nombreux problèmes, l’optimum est atteint lorsque l’une au moins des contraintes de séparation est saturée, c’est-à-dire sur la frontière de l’espace admissible. Gérer les contraintes en pénalisant la fonction fitness est difficile, un “dosage” s’impose pour ne pas favoriser la recherche de solutions admissibles au détriment de la recherche de l’optimum ou inversement. 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.
Opérateur de croisement
Le croisement a pour but d’enrichir la diversité de la population en manipulant la structure des 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 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 dans chacun des parents. On échange ensuite les deux sous-chaînes terminales de chacun des deux chromosomes, ce qui produit deux enfants C1 et C2 .
Algorithmes génétiques et recuit simulé
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 parti de leurs avantages respectifs. Après plusieurs évaluations de ces deux techniques sur les mêmes problèmes test, on remarque que le recuit simulé converge généralement plus vite vers la solution optimale lorsque le problème est de taille raisonnable. Toutefois, il ne donne qu’une solution dans le cas des problèmes multi-modes, ceci confirme les résultats donnés dans [IR92b]. A l’inverse, les algorithmes génétiques fournissent plusieurs solutions quasi-optimales mais au prix d’un temps de convergence généralement 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 d’hybridation entre les algorithmes génétiques et le recuit simulé, les travaux les plus intéressants étant ceux de Mahfoud et de Goldberg [MG92].
Recherche multiobjectif
Dans le cadre de la recherche multi objectif, on cherche à optimiser une fonction suivant plusieurs critères, dont certains peuvent d’ailleurs être antagonistes. On définit alors la classique notion de dominance : on dit que le point A domine le point B si, ∀i, fi(A) ≥ fi(B) et ∃i, fi(A) > fi(B), où les fi représentent les critères à maximiser. L’ensemble des points qui ne sont dominés par aucun autre point forme le front de Pareto. Tout point du front de Pareto est “optimal”, dans la mesure où on ne peut améliorer la valeur d’un critère pour ce point sans diminuer la valeur d’au moins un autre critère. Les algorithmes génétiques peuvent permettre de trouver l’ensemble de la surface de Pareto, car il est possible de répartir la population de l’algorithme génétique sur ladite surface.
Technique employée
La technique employée dérive directement des travaux de Jeffrey Horn et Nicholas Nafpliotis ([HN93]). Le principal changement induit concerne le processus de sélection : en multiobjectif, comment décider qu’un individu est meilleur qu’un autre ? On introduit alors une variante de la notion de dominance, que l’on définit ainsi : on peut par exemple décider que l’élément Ei domine Ej si le nombre des valeurs contenues dans son vecteur d’adaptation qui sont supérieures aux valeurs correspondantes dans Ej dépasse un certain seuil. A partir de là, la technique proposée pour effectuer la sélection est simple : on tire deux individus au hasard, ainsi qu’une sous-population à laquelle ils n’appartiennent pas, et qui va servir à les comparer. Trois cas se présentent alors :
– si le premier élément domine tous ceux de la sous-population et que ce n’est pas le cas pour le second, alors le premier sera sélectionné.
– inversement, si seul le second domine l’ensemble de la sous-population, alors c’est lui qui sera conservé.
– restent maintenant deux possibilités : soit les deux sont dominés, soit les deux dominent. On ne peut se prononcer sans ajouter un autre test, c’est pourquoi, dans ce cas, il est fait usage d’un nouveau type de sharing, qui opère sur l’espace objectif.
|
Table des matières
INTRODUCTION
1 AG : généralités et améliorations
1.1 Principes généraux
1.2 Description détaillée
1.2.1 Codage des données
1.2.2 Génération aléatoire de la population initiale
1.2.3 Gestion des contraintes
1.2.4 Opérateur de croisement
1.2.5 Opérateur de mutation
1.2.6 Principes de sélection
1.3 Améliorations classiques
1.3.1 Introduction
1.3.2 Scaling
1.3.3 Sharing
1.3.4 Sharing clusterisé
1.3.5 Algorithmes génétiques et recuit simulé
1.3.6 Recherche multiobjectif
1.3.7 Association des AG avec des méthodes locales
1.4 Parallélisme
1.4.1 Parallélisme par îlots
1.4.2 Parallélisation des calculs
1.4.3 Conclusion
1.5 Résultats de convergence théorique des algorithmes génétiques
2 Elaboration d’un croisement adapté aux problèmes partiellement séparables
2.1 Séparabilité partielle
2.1.1 Définition
2.1.2 Opérateur de croisement adapté
2.2 Etude théorique sur un exemple simple
2.2.1 Probabilité d’amélioration
2.2.2 Vitesse de convergence avec l’opérateur de croisement adapté
2.2.3 Probabilité de sélection
2.3 Résultats expérimentaux
2.3.1 Algorithme génétique sans sharing
2.3.2 Algorithme génétique avec sharing
2.3.3 Influence du sharing
2.4 Exemple de fonctions de test
2.4.1 Une fonction totalement séparée : la fonction de Corana
2.4.2 La fonction de Griewank
2.5 Conclusion
3 Exemple d’application : optimisation de la circulation des aéronefs sur un aéroport
3.1 Introduction
3.1.1 Modélisation
3.1.2 Fonction de coût
3.1.3 L’aéroport
3.1.4 Le trafic
3.2 Simulation
3.2.1 BB : Méthode 1 contre n
3.2.2 GA et GA+BB : algorithmes génétiques
3.3 Résultats
3.3.1 Simulations
3.3.2 Comparaison des stratégies
3.3.3 Remarques
3.4 Conclusion
4 Le problème de résolution de conflits
4.1 Complexité du problème de résolution de conflit
4.2 Approche centralisée, approche autonome
4.3 Les projets d’automatisation existants
4.3.1 La tentative américaine abandonnée, AERA
4.3.2 ARC2000 et ses dérivés
4.3.3 Le projet SAINTEX
4.3.4 Le Projet FREER
4.3.5 Les méthodes de forces répulsives
4.3.6 Résolution par programmation linéaire en nombres entiers
CONCLUSION
