Intelligent Structural Operators for the k-way Graph Partitioning Problem

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