Sex-Fair Stable Marriage Problem and Its GA Solution

概要

論文の詳細を見る
In this paper we consider a sex-fair matching in the stable marriage problem. The sex-fair stable matching defined in this paper has a property that the sum of partner's ranks of individual men in their preference lists is as close as possible to the sum of partner's ranks of individual women in their preference lists. However, the sex-fair stable marriage problem is known as one of important open problems in the stable marriage problems. The main result of this paper is to propose a method for adapting a genetic algorithm (GA) to the sex-fair problem to find the sex-fair matching effectively. In the method we transform the sex-fair marriage problem into a graph problem whose decision version is shown to be NP-complete. The graph problem representation is suitable for GA application, that is, easier coding, easier and more effective definition of genetic operators. Computer experiment reports effectiveness of the GA solution.
社団法人電子情報通信学会の論文
1995-06-25