algorithme génétique - informatique.

algorithme génétique - informatique. 1 PRÉSENTATION algorithme génétique, méthode de programmation qui repose sur le principe de l'évolution pour effectuer la recherche d'une solution à un problème. 2 PRINCIPE Cette classe d'algorithme travaille sur une population d'entités abstraites munies d'un génotype formel (par exemple une suite de bits formant un octet : 10010001. Ce dernier possède une signification relative au problème posé, et il en constitue une solution potentielle. Partant d'une population construite aléatoirement, c'est-à-dire où chaque individu a un génotype différent, choisi au hasard, l'algorithme évalue la qualité de la solution proposée par chaque individu. Cette évaluation correspond à la notion biologique d'adaptation dans un écosystème. Les meilleurs individus sont alors sélectionnés pour appartenir à la génération suivante. Ils sont croisés entre eux, à l'image de la reproduction sexuée : les génotypes se recombinent par paire. Enfin, quelques individus choisis au hasard voient leur génotype modifié de façon aléatoire, ils subissent une mutation. La nouvelle génération est ainsi constituée, et le processus recommence jusqu'à ce qu'un critère d'arrêt soit respecté. Il existe de nombreuses variantes à cet algorithme, les algorithmes génétiques étant regroupés selon un paradigme de programmation, c'est-à-dire une méthode générale qu'il faut adapter pour des applications précises. Par exemple, il peut ne pas y avoir de mutation, ou bien la population peut être de taille fixe et évoluer pendant une durée déterminée à l'avance, comme elle peut être de taille variable. 3 APPLICATIONS La recherche du minimum absolu d'une fonction mathématique est un exemple typique de l'emploi d'algorithme génétique. D'une manière plus générale, les problèmes intéressants se ramènent à chercher des solutions dans un espace de recherche de très grande taille, espace notamment rencontré lorsque le nombre de cas à explorer avant d'être sûr d'avoir trouvé la meilleure solution grandit de manière exponentielle avec la taille du problème. On dit que ce sont des problèmes NP-complets, ou difficiles. Les algorithmes génétiques ont pour but de résoudre de tels problèmes par leur approche spécifique, différente des algorithmes d'optimisation les plus courants. Les algorithmes génétiques utilisent massivement des tirages de nombres pseudoaléatoires pour effectuer l'exploration des solutions. Le fait de travailler sur une population implique un parallélisme implicite : ce sont plusieurs solutions qui sont explorées simultanément. De plus, il est possible d'arrêter à tout moment un tel algorithme, il propose toujours une solution, qui n'est pas forcément la meilleure, mais qui n'est pas trop mauvaise non plus. Enfin les algorithmes génétiques évitent un piège très souvent rencontré dans les algorithmes d'optimisation : ils ne s'arrêtent pas dans les extrema locaux, c'est-à-dire qu'ils essayent constamment de trouver de meilleures solutions, même s'ils semblent les avoir atteintes. En conséquence, les algorithmes génétiques sont très robustes, mais ils souffrent de ne pas être prévisibles, et donc leur efficacité ne peut pas être calculée à l'avance. Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. Tous droits réservés.