Document Type

Working Paper




parallel genetic algorithm, graph partitioning, heuristic algorithm




Computer Sciences | Mathematics


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.

Additional Information

4th International Conference on Genetic Algorithms, Plenum, Morgan-Kaufman pp. 45-52



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.