Accueil > Enseignement > Cours gratuits > Optimisation et algorithmes génétiques
Optimisation et algorithmes génétiques
Tout ce qui existe dans l’univers est le fruit du hasard et de la nécessité. Jacques Monod.
Les Algorithmes Génétiques sont basés sur la théorie de l’évolution de Darwin. Ils consistent à faire évoluer une population de dispositifs à l’aide de différents opérateurs : sélection, croisements, mutations. Ils sont en particulier utilisés pour les problèmes d’optimisation comportant de nombreux paramètres et des objectifs multiples.
Ce cours est basé sur le dernier chapitre de ma thèse soutenue le 22 octobre 1998 à Lille 1.
-
Convergence de l’AG
7 juillet 2006, par Vincent MAGNIN
Convergence et temps de calcul
On peut constater figure 11 que l’amélioration de la population est très rapide au début (recherche globale) et devient de plus en plus lente à mesure que le temps passe (recherche locale) . Le bruit dans la moyenne est essentiellement dû aux mutations.
On voit que la valeur moyenne de la fonction d’adaptation a tendance à se rapprocher de celle de l’individu le plus adapté. Cela correspond à une uniformisation croissante de la population. Nous avons donc introduit (...)
-
Exemple d’optimisation par AG
7 juillet 2006, par Vincent MAGNIN
Nous présentons l’optimisation de commutateurs à réflexion interne totale (ou commutateurs TIR ), étude effectuée dans le cadre d’une collaboration entre l’IEMN et Dassault Electronique. Un commutateur directionnel permet d’aiguiller la lumière dans un guide ou un autre en faisant varier l’indice de réfraction au niveau de l’embranchement. Ces composants sont destinés à la réalisation de matrices de commutation pour la génération de retards temporels, afin de commander des antennes actives. Ils sont (...)
-
Le voyageur de commerce (applet Java)
7 juillet 2006, par Vincent MAGNIN
Voici un problème d’optimisation classique : un voyageur de commerce doit passer dans chaque ville d’une contrée, et ce une seule fois. Comment faire pour que le trajet soit le plus court possible ? Une méthode d’énumération exhaustive est exclue : s’il y a N villes, pour la seconde étape de son périple notre voyageur a N-1 possibilités, pour la troisième N-2, etc. Le nombre de combinaisons est donc (N-1) ! . Pour seulement 40 villes, cela fait à peu près 2E46 solutions à tester. En supposant que l’on (...)
-
Conclusion
7 juillet 2006, par Vincent MAGNIN
La modélisation est un outil puissant qui permet en particulier d’optimiser un dispositif avant de le fabriquer. Les algorithmes d’optimisation permettent de s’affranchir en grande partie de la méthode d’essai et erreur. Parmi ceux-ci nous avons abordé d’abord les méthodes Monte Carlo avant de passer aux Algorithmes Evolutionnaires et aux Algorithmes Génétiques (AG).
Les méthodes Monte Carlo
Dans le cadre de l’optimisation à paramètres multiples, les méthodes Monte Carlo sont intéressantes si le (...)
-
Bibliographie
7 juillet 2006, par Vincent MAGNIN
Les références sont classées alphabétiquement selon le nom du premier auteur. Pour les livres disponibles à la Bibliothèque Universitaire de Lille 1, la côte est indiquée en marron.
Sur la théorie de l’évolution Bergson H., L’évolution créatrice (téléchargeable en PDF) . Paris : PUF, 1907. Darwin C., The Origin of Species , 1859. Heudin J-C., L’évolution au bord du chaos . Paris : Hermès, 1998. BU : 539.1 HEU Jacob F., La logique du vivant, une histoire de l’hérédité. Gallimard, collection Tel, (...)
-
Liens
7 juillet 2006, par Vincent MAGNIN
Vous cherchez un code tout fait (C, Fortran, Java, Lisp...) ? Allez faire un tour sur le site "The Genetic Algorithms Archive" : http://www.aic.nrl.navy.mil/galist/
De nombreux articles nous ayant servi pour la réalisation de notre algorithme génétique sont disponibles sur Internet en format PostScript, en particulier sur les sites suivants : http://GAL4.GE.UIUC.EDU/illigal.home.html : Illinois Genetic Algorithms Laboratory, dirigé par D.E. Goldberg, un des grands spécialistes des AG. (...)