Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > An Adaptive Hybrid GA for the ...

An Adaptive Hybrid GA for the 3-Matching Problem

Gábor Magyar, Mika Johnsson, Olli Nevalainen, An Adaptive Hybrid GA for the 3-Matching Problem. TUCS Technical Reports 166, Turku Centre for Computer Science, 1998.

Abstract:

This paper presents a hybrid genetic algorithm (GA) with an adaptive application of genetic operators for solving the Three-Matching Problem (3MP), which is an NP-complete graph problem. In the 3MP we are searching for the partition of a point set into triplets of a minimal total cost where the cost of a triplet is the Euclidean length of the minimal spanning tree of the three points. One common problem with GAs applied to hard combinatorial optimization problems like the 3MP or TSP is to incorporate efficiently the problem-dependent local search operators to the GA in order to find high-quality solutions. We introduce several general/heuristic crossover and local hill-climbing operators for the 3MP and apply adaptation at the level of choosing among the operators. Our GA combines these operators to form an effective problem solver. The algorithm is hybridized as it incorporates local search heuristics and it is adaptive as the individual recombination/improvement operators are fired according to their online performance. Our test results show that this approach gives approximately the same or even slightly better results than our previous, fine-tuned GA without adaptation. The major advantage of the new algorithm is that the adaptive combination of genetic and local search operators eliminates a large set of parameters of the traditional GA, making the method more robust, and it presents a convenient way to build a hybrid problem solver. We therefore suggest this approach to other hard optimization problems.

<p>Contact authors for the complete report.

BibTeX entry:

@TECHREPORT{tMaJoNe98a,
  title = {An Adaptive Hybrid GA for the 3-Matching Problem},
  author = {Magyar, Gábor and Johnsson, Mika and Nevalainen, Olli},
  number = {166},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {1998},
  keywords = {genetic algorithm, hybridization, adaptation, optimization, matching problem},
  ISBN = {952-12-0174-6},
}

Edit publication