Au cours des trois dernieres decennies, les algorithmes heuristiques ont permis de realiser des progres remarquables dans la resolution des problemes diciles d'optimisation combinatoire. Cependant, la conception de ces algorithmes releve encore plusieurs challenges importants { en particulier, il semble qu'il est toujours dicile d'integrer dans une heuristique une vue d'ensemble sur l'evolution de la recherche ou sur sa trajectoire. Prenant comme cadre experimental le probleme bien connu de la coloration de graphe, nous presentons de nouvelles strategies qui font appel a certains mecanismes d'apprentissage pour rendre le processus de recherche plus \auto-conscient". Nous introduisons un algorithme qui est capable d'enregistrer sa trajectoire et d'interpreter sa propre evolution. Une analyse de l'espace de recherche a montre que les meilleures congurations visitees sont relativement proches les unes des autres, regroupees dans des spheres de rayon xe. Avec ce type d'informations apprises, nous avons concu : (i) des algorithmes de diversication qui \prennent garde" a ne pas visiter la m^eme sphere a plusieurs reprises, (ii) des algorithmes d'intensication qui se focalisent sur l'exploration d'un perimetre limite en utilisant un parcours en largeur des spheres de ce perimetre, et (iii) des approches evolutionnistes pour gerer la diversite de sorte que les individus soient a la fois de bonne qualite eu egard a la fonction objectif et susamment distants les uns des autres. En fait, nous presentons une gamme de techniques (e.g. nouvelles fonctions d'evaluation) qui peuvent rendre la recherche heuristique \bien informee".

Au cours des trois dernières décennies, les algorithmes heuristiques ont permis de réaliser des progrès remarquables dans la résolution des problèmes difficiles d'optimisation combinatoire. Cependant, la conception de ces algorithmes relève encore plusieurs challenges importants - en particulier, il semble qu'il est toujours difficile d'intégrer dans une heuristique une vue d'ensemble sur l'évolution de la recherche ou sur sa trajectoire. Prenant comme cadre expérimental le problème bien connu de la coloration de graphe, nous présentons de nouvelles stratégies qui font appel à certains mécanismes d'apprentissage pour rendre le processus de recherche plus "auto-conscient". Nous introduisons un algorithme qui est capable d'enregistrer sa trajectoire et d'interpréter sa propre évolution. Une analyse de l'espace de recherche a montré que les meilleures configurations visitées sont relativement proches les unes des autres, regroupées dans des sphères de rayon fixe. Avec ce type d'informations apprises, nous avons conçu : (i) des algorithmes de diversification qui "prennent garde" à ne pas visiter la même sphère à plusieurs reprises, (ii) des algorithmes d'intensification qui se focalisent sur l'exploration d'un périmètre limité en utilisant un parcours en largeur des sphères de ce périmètre, et (iii) des approches évolutionnistes pour gérer la diversité de sorte que les individus soient à la fois de bonne qualité eu égard à la fonction objectif et suffisamment distants les uns des autres. En fait, nous présentons une gamme de techniques (e.g. nouvelles fonctions d'évaluation) qui peuvent rendre la recherche heuristique "bien informée".