Abstract FR:

Le sujet de cette these est l'optimisation stochastique. Dans la premiere des trois parties, nous presentons plusieurs problemes d'optimisation combinatoire et des algorithmes approches de resolution, en particulier les algorithmes genetiques. Nous abordons egalement les methodes issues de la physique statistique, en particulier les systemes de spins et l'echantillonnage de gibbs que nous appliquons a la coloration de graphes. Dans la deuxieme partie, nous presentons des algorithmes d'optimisation qui travaillent sur une representation de l'espace de recherche, au contraire des algorithmes de la premiere partie. Par representation, nous entendons une probabilite sur l'espace de recherche decrite par un nombre fini de parametres. L'optimisation est controlee par un systeme dynamique a gradient, a l'instar de l'apprentissage dans les reseaux de neurones, qui agit sur les parametres de la probabilite et maximise un critere statistique. Nous avons introduit deux nouveaux criteres statistiques qui conduisent a des algorithmes d'apprentissage par selection. Dans le cas des vecteurs binaires, nous utilisons les mesures de bernoulli, et dans le cas euclidien, les densites gaussiennes. La troisieme partie porte sur un probleme d'optimisation en radiotelephonie mobile, la planification cellulaire. Apres avoir presente le modele, nous proposons une methode de resolution qui incorpore plusieurs des notions rencontrees dans les deux premieres parties. Elle fait appel en particulier a la recherche locale, aux systemes de spins, a l'echantillonnage de gibbs, au recuit simule et a l'apprentissage par renforcement. La methode est evaluee sur des jeux de donnees reelles de grande taille et comparee a d'autres methodes.