Document Type
Working Paper
Date
1991
Keywords
parallel genetic algorithm, graph partitioning, heuristic algorithm
Language
English
Disciplines
Computer Sciences | Mathematics
Description/Abstract
A parallel genetic algorithm for the graph partitioning problem is presented, which combines general heuristic algorithms with techniques that are described in evolution theory. In the parallel genetic algorithm the selection of a mate is restricted to a local neighborhood. In addition, the parallel genetic algorithm executes an adaptation step after an individual is generated, with the genetic operators crossover and mutation. During the adaptation step the solution is improved by a common algorithm. Another selection step decides if the adapted descendant should replace the parent individual. Instead of using a uniform crossover operator a more intelligent crossover operator, which copies subsets of nodes, is used. Basic parameters of the parallel genetic algorithm are determined for different graphs. The algorithm found for a large sample instance a new unknown solution.
Recommended Citation
von Laszewski, Gregor, "Intelligent Structural Operators for the k-way Graph Partitioning Problem" (1991). Northeast Parallel Architecture Center. 30.
https://surface.syr.edu/npac/30
Additional Information
4th International Conference on Genetic Algorithms, Plenum, Morgan-Kaufman pp. 45-52