En 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, (...)
Chercheur à l’IEMN (Institut d’Electronique de Microélectronique et de Nanotechnologie),
enseignant à Polytech Lille dans le département Matériaux.
Articles les plus récents
-
Algorithmes Evolutionnaires et Algorithmes Génétiques
7 juillet 2006, par Vincent MAGNIN -
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, (...) -
Liens
7 juillet 2006, par Vincent MAGNINVous 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. (...) -
Moteurs de recherche
6 juillet 2006, par Vincent MAGNINComment fonctionne un moteur de recherche ?
Un moteur de recherche est une base de données que l’on peut en fait diviser de la façon suivante : le moteur lui-même, que l’utilisateur interroge via une interface graphique, le robot d’indexation, chargé de nourrir la base de données.
Le moteur
Quand l’utilisateur tape des mots-clés dans son navigateur, ceux-ci sont transmis à un serveur du moteur de recherche. Le serveur cherche les mots-clés dans la base de données, récupère la liste des adresses (...) -
Recherche d’articles, thèses, livres...
6 juillet 2006, par Vincent MAGNINPour la recherche d’articles scientifiques
Ces sites vous renverront généralement vers les sites des éditeurs. Vous pourrez accéder à l’article en PDF si l’organisme auquel vous appartenez est abonné ou si l’article est en open access (accès libre). Google Scholar : outil gratuit, très simple, à la Google... Microsoft Academic Research : gratuit. Scopus : moteur payant, très puissant. HAL : "L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion d’articles scientifiques de (...)
