Dans ce mémoire, nous appliquons les algorithmes génétiques à des problèmes de matching. Dans un premier temps, nous passons en revue toute la théorie du matching, tant d'un point de vue économique que d'un point de vue algorithmique. Nous analysons trois problèmes de matching : le cas simple du one-to-one matching ou mariage; le many-to-one matching sans contrainte et le many-to-one matching avec contraintes. Dans un deuxième temps, nous décrivons brièvement les algorithmes génétiques, leur mode de fonctionnement et leurs adaptations. Nous les intégrons dans un problème simple de matching : le problème du mariage afin de les tester. Ensuite, nous les appliquons à un cas réel de répartition des élèves dans les écoles belges. Ce problème est sujet à des contraintes imposées par le décret "missions". Ce cas de many-to-one matching avec contraintes et indifférences n'a pas encore été traité dans la littérature existante et les algorithmes génétiques donnent de bons résultats. Dans un dernier temps, nous appliquons encore les algorithmes génétiques à un autre problème de matching : la formation de coalitions. Dans ce cas également, l'apport de ces algorithmes s'avère intéressant.
Matching on school choice: theory and algorithms
MARELLI, V. (Auteur). 24 juin 2013
Student thesis: Master types › Master en sciences mathématiques