STABLE MARRIAGE PROBLEM

Abstract

The Stable marriage problem (SMP) is basically the problem of finding a stable matching between two sets of persons, the men and the women, where each person in every group has a list containing every person that belongs to other group ordered by preference. The first ones to discover a stable solution for the problem were D. Gale and G.S. Shapley. Today the problem and most of its variations have been studied by many researchers, and for most of them polynomial time algorithms do not exist. Lately genetic algorithms have been used to solve such problems and have often produced better solutions than specialised polynomial algorithms. In this thesis we study and show that the Stable marriage problem has a number of important real world applications. It the experimentation, we model the original problem and one of its variations and show the benefits of using genetic algorithms for solving the SMP.