The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms

Abstract: “The Stable marriage problem (SMP) is basically the problem of finding a stable matchingbetween two sets of persons, the men and the women, where each person in every group has a listcontaining every person that belongs to other group ordered by preference. The first ones to discovera stable solution for the problem were D. Gale and G.S. Shapley. Today the problem and most of itsvariations have been studied by many researchers, and for most of them polynomial time algorithmsdo not exist. Lately genetic algorithms have been used to solve such problems and have oftenproduced better solutions than specialized polynomial algorithms. In this thesis we study and showthat the Stable marriage problem has a number of important real-world applications. It theexperimentation, we model the original problem and one of its variations and show the benefits ofusing genetic algorithms for solving the SMP.”