Abstract FR:

Les algorithmes genetiques sont des algorithmes evolutifs introduits par john holland dans les annees 70. Ils sont utilises pour resoudre les problemes d'optimisation. Le travail realise dans cette these se concentre autour de l'idee de convergence dans ces algorithmes sur le plan theorique et pratique. Tout d'abord, deux modeles sont elabores dans le but d'acceder a une demonstration purement mathematique d'un theoreme enonce par holland, le theoreme des schemas, concernant les structures preservees lors d'un cycle de l'algorithme genetique. En ce qui concerne l'action de la selection, il faut utiliser les distributions de bernoulli afin d'arriver a un resultat en accord avec celui de holland. Le meme modele n'etant pas exploitable pour les autres operateurs, un modele dynamique plus classique est construit a l'aide des chaines de markov. Ce modele est utilise afin d'approcher le theoreme des schemas sous un autre angle, en utilisant une generalisation de la notion de schema. L'aspect pratique de la convergence est aussi etudie a l'aide d'un outil introduit par davidor : l'epistasie. La definition de celle-ci etant assez obscure au depart, une analyse en detail a ete faite, grace a une decomposition dans la base de walsh. Ce travail met en lumiere la signification profonde de l'epistasie et sa relation etroite avec une approximation lineaire. A l'aide des resultat theoriques demontres, qui permettent de calculer l'epistasie de maniere acceleree, une campagne de tests a ete menee sur divers aspects de la convergence et de la difficulte d'un probleme pour l'algorithme genetique. Une etude sur le choix de l'estimateur de l'epistasie permet de mettre en evidence l'importance des resultats obtenus pour une estimation efficace. Enfin, les relations entre epistasie et performance de l'operateur de croisement sont mises en lumiere.