Abstract FR:

Les methodes heuristiques sont une classe generale de methodes qui, de maniere schematique, utilisent des criteres empiriques au cours de leur resolution pour fournir, en un temps raisonnable, des solutions sous-optimales de bonne qualite. Ces methodes posent des problemes de conception et de mise au point pour lesquels, a l'heure actuelle, aucune methodologie n'a ete clairement definie. Le premier objectif de notre travail consiste donc a repondre, meme de maniere partielle, a ces problemes. Pour cela, nous avons defini une architecture et une methodologie adaptees a la conception et a l'analyse des methodes heuristiques. Pour valider notre approche, nous avons applique cette methodologie et cette architecture sur une famille de problemes np-complet : la coloration et la t-coloration, et sur une application reelle : l'affectation de frequences dans les reseaux radio-mobiles. Des methodes de recherche locale, evolutives et hybrides ont ete developpees pour chacun de ces problemes et testees sur de nombreux jeux de tests references (> 150 benchmarks) comprenant jusqu'a 2000 variables et plus de quatre millions de contraintes. Au niveau des performances, nos algorithmes rejoignent les meilleurs resultats connus sur ces problemes. En particulier pour la coloration de graphes, nous obtenons, grace a un croisement adapte, les meilleurs resultats actuels sur certaines instances aleatoires. De meme, les resultats obtenus dans le cadre de l'affectation de frequences ont ete integres au progiciel actuellement en exploitation a france telecom. Il s'en suit que la qualite de l'ensemble des resultats obtenus dans cette etude confirme l'interet de notre approche pour la conception de methodes heuristiques.