• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Genetic Algorithm Approach for the Three-Matching Problem

Mika Johnsson, Gábor Magyar, Olli Nevalainen, Genetic Algorithm Approach for the Three-Matching Problem. TUCS Technical Reports 113, Turku Centre for Computer Science, 1997.

Abstract:

<p>In this paper we discuss the solving of the Three-Matching Problem (3MP) by a genetic algorithm. In the 3MP we want to partition a set of n=3l points into l disjoint subsets, each consisting of three points (called triplets), and to minimize the total cost of the triplets. It has been shown that the 3MP is NP-complete. This paper describes the components of a genetic algorithm (GA) for the 3MP. Our empirical tests show that the GA outperforms other heuristic methods like simulated annealing and local search, which we have studied previously.

<p>Contact Mika Johnsson (johnsson@cs.utu.fi) for the complete report.

BibTeX entry:

@TECHREPORT{tJoMaNe97b,
  title = {Genetic Algorithm Approach for the Three-Matching Problem},
  author = {Johnsson, Mika and Magyar, Gábor and Nevalainen, Olli},
  number = {113},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {1997},
  ISBN = {952-12-0016-2},
}

Edit publication