Abstract FR:

Les métaheuristiques sont une classe de méthodes qui fournissent des solutions de bonne qualité en temps raisonnable à des problèmes combinatoires réputés difficiles. Il existe de nombreux travaux d'application de ces méthodes mais très peu d'études s'intéressent à leur aspect fondamental. Ainsi la dynamique et le comportement des métaheuristiques restent méconnus. Cette thèse est dédiée à l'étude de quelques questions fondamentales sur les métaheuristiques. Nous avons adopté une méthodologie en trois axes : 1) l'étude des propriétés et mesures des problèmes combinatoires, 2) l'étude des comportements des métaheuristiques, 3) la mise en relation des mesures des problèmes et des comportements de métaheuristiques. Pour valider cette approche nous l'avons appliquée à deux problèmes NP-complets : MAX-CSP et SAT. Nous avons développé pour le premier axe un état de l'art qui réunit un grand nombre de mesures existantes, puis nous avons classé ces mesures. Nous avons ensuite appliqué et analysé les mesures densité d'état (DOS), distance dans un niveau (DDN), distance entre niveaux (DEN), autocorrélation et densité des coûts du processus (DCP). Concernant le deuxième axe nous avons développé la notion de performance qui fait partie des comportements d'une métaheuristique et nous avons proposé un nouveau critère d'évaluation de la performance basé sur la mesure DCP. Enfin, nous avons dans le troisième axe mis en évidence des relations entre comportements et mesures en analysant les conséquences sur les métaheuristiques, des mesures que nous avons étudiées. Ces mises en relation nous permettent de prévoir ou d'expliquer le comportement et la dynamique des métaheuristiques.