Multiobjective fitness functions for stable marriage problem using genetic algrithm

Ngo Anh Vien*, Tae Choong Chung

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)

Abstract

In this paper we propose a genetic algorithm (GA)-based approach to find out stable matchings in the stable marriage problem depending on different criteria such as stable matching with man-optimal, woman-optimal, egalitarian and sex-fair. The stable marriage problem is an extensively-studied combinatorial problem with many practical applications. Gale-Shapley (GS) algorithm is well known by which the stable matching found is extremal among many (for the worst case, in exponential order) stable matchings. So that Gale-Shapley algorithm can only search the man-optimal (or woman-pessimal) stable matching. The proposed algorithm has been evaluated by simulation experiment compared to other existing algorithms. It has been found that the proposed algorithm is quite efficient in finding stable matchings depending on different criteria.

Original languageEnglish
Title of host publication2006 SICE-ICASE International Joint Conference
Pages5500-5503
Number of pages4
DOIs
Publication statusPublished - 01 Dec 2006
Externally publishedYes
Event2006 SICE-ICASE International Joint Conference - Busan, Korea, Republic of
Duration: 18 Oct 200621 Oct 2006

Conference

Conference2006 SICE-ICASE International Joint Conference
CountryKorea, Republic of
CityBusan
Period18/10/200621/10/2006

Keywords

  • Genetic algorithm
  • Stable marriage
  • Stable matching

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Multiobjective fitness functions for stable marriage problem using genetic algrithm'. Together they form a unique fingerprint.

  • Cite this

    Vien, N. A., & Chung, T. C. (2006). Multiobjective fitness functions for stable marriage problem using genetic algrithm. In 2006 SICE-ICASE International Joint Conference (pp. 5500-5503). [4108766] https://doi.org/10.1109/SICE.2006.315686