Note publique d'information : Cette thèse traite de l’utilisation des algorithmes évolutionnaires (AE) pour résoudre
des problèmes de satisfaction de contrainte (CSP) en domaines finis dans spécialisation
ni hybridation particulière. Après avoir présenté les CSP et les méthodes couramment
utilisées pour les résoudre (chapitres 1 et 2), nous présentons le paradigme évolutionnaire
et ses applications (chapitres 3 et 4). Ensuite, nous proposons une comparaison entre
les méthodes de recherche arborescente et les métaheuristiques sur des coloriages
de graphe sur-contraints, dans un contexte de réglage des paramètres minimal (chapitre
5). Nous étudions le paysage de recherche pour comprendre les raisons des différences
d’efficacité des méthodes. Enfin, nous proposons de nouveaux opérateurs génétiques
(croisement, mutation, diversification) dont le paramétrage est moins fastidieux qu’avec
les opérateurs classiques (chapitre 6). Nous concluons sur l’intérêt d’exploration
des réseaux de neutralité.
Note publique d'information : This thesis deals with the use of evolutionary algorithms (EA) to solve constraint
satisfaction problems (CSP) in finite domains, without any particular specialization
nor hybridization. Having presented the CSP and general methods used to solve those
(chapters 1 and 2), we present the evolutionary paradigm and its applications (chapter
3 and 4). Then, we propose a comparison between the tree search methods and metaheuristics
on over-constrained graph coloring in a context of minimal regulation of the parameters
(chapter 5). We study the research landscape for understanding the reasons of the
operators (crossover, mutation, diversification), the parameter setting of which is
less difficult than with the classical operators (chapter 6). We conclude on the interest
of investigating the neutrality networks.