Les hommes ont observé le monde depuis des temps immémoriaux. L’observation les a menés à établir des théories permettant d’expliquer les régularités de la nature. Parmi les premières observations et théories, on compte certainement celles concernant le ciel. Il s’agissait alors de répondre à des questions telles que : pourquoi le soleil se lève tous les jours, quand reviennent les saisons, les astres ont-ils une influence sur le destin des êtres humains ? Avec l’avènement de l’agriculture il a fallu (...)
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.
-
Introduction
7 juillet 2006, par Vincent MAGNIN -
L’optimisation
7 juillet 2006, par Vincent MAGNINParmi les problèmes rencontrés par le chercheur et l’ingénieur, les problèmes d’optimisation occupent à notre époque une place de choix. Nous n’aborderons pas le problème de l’optimisation d’un point de vue mathématique, mais simplement du point de vue d’un ingénieur pragmatique. Cette partie du cours ne sera donc pas exhaustive.
Le terme dispositif , que nous emploierons tout au long de ce cours, désignera l’objet, matériel ou non, que nous voulons étudier et optimiser : une molécule, un composant (...) -
Méthode Monte Carlo
7 juillet 2006, par Vincent MAGNINLes méthodes Monte Carlo consistent en des simulations expérimentales ou informatiques de problèmes mathématiques ou physiques, basées sur le tirage de nombres aléatoires. Généralement on utilise en fait des séries de nombres pseudo-aléatoires générées par des algorithmes spécialisés. Les propriétés de ces séries sont très proches de celles d’une véritable suite aléatoire.
On peut par exemple approcher la valeur de Pi par une méthode Monte Carlo : on considère le cercle de rayon 1 inscrit dans un carré de (...) -
Algorithmes Evolutionnaires et Algorithmes Génétiques
7 juillet 2006, par Vincent MAGNINEn vérité, aux tout premiers temps, naquit Chaos. Hésiode
To create a little flower is the labour of ages. William Blake
Les Algorithmes Evolutionnaires (AE) sont inspirés du concept de sélection naturelle élaboré par Charles Darwin. Le vocabulaire employé est directement calqué sur celui de la théorie de l’évolution et de la génétique. Nous parlerons donc d’individus (solutions potentielles), de population , de gènes (variables), de chromosomes , de parents , de descendants, de reproduction, (...) -
Méthodes de l’AG
7 juillet 2006, par Vincent MAGNINCodage des variables
La première étape est de définir et de coder convenablement le problème. A chaque variable d’optimisation xi (à chaque paramètre du dispositif), nous faisons correspondre un gène . Nous appelons chromosome un ensemble de gènes. Chaque dispositif est représenté par un individu doté d’un génotype constitué d’un ou plusieurs chromosomes. Nous appelons population un ensemble de N individus que nous allons faire évoluer.
D’un point de vue informatique, nous utilisons dans notre (...) -
Convergence de l’AG
7 juillet 2006, par Vincent MAGNINConvergence 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 MAGNINNous 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 MAGNINVoici 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 MAGNINLa 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 MAGNINLes 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, (...)
0 | 10