Abstract FR:

Dans cette thèse, deux problèmes réputés NP-difficiles sont étudiés, à savoir : le problème de satisfiabilité maximale MAX-SAT et le problème de la détermination du gagnant dans les enchères combinatoires PDG. Notre but principal est de contribuer à la résolution de ces deux problèmes par des méthodes évolutives et de recherche locale. Nous proposons, tout d’abord, une nouvelle stratégie de sélection qui se base sur la diversité et la qualité pour choisir une collection d’individus qui vont participer à la phase de reproduction et donner une descendance. Ensuite, nous utilisons un opérateur de combinaison spécifique au problème à étudier pour générer de nouveaux enfants qui sont améliorés par une recherche locale stochastique (SLS). Dans le but de tester et de prouver l’efficacité de nos approches, une étude comparative avec quelques algorithmes de l’état de l’art concernant MAX-SAT et PDG est faite dans la thèse.