# Geometric Crossovers for Multiway Graph Partitioning

### Authors

### Abstract

Geometric crossover is a representation-independent generalization of the traditionalcrossover defined using the distance of the solution space. By choosing a distance firmly

rooted in the syntax of the solution representation as a basis for geometric crossover,

one can design new crossovers for any representation. Using a distance tailored to the

problem at hand, the formal definition of geometric crossover allows us to design new

problem-specific crossovers that embed problem-knowledge in the search.

The standard encoding for multiway graph partitioning is highly redundant: each

solution has a number of representations, one for each way of labeling the represented

partition. Traditional crossover does not perform well on redundant encodings.

We propose a new geometric crossover for graph partitioning based on a

labelingindependent distance that filters out the redundancy of the encoding. A

correlation analysis of the fitness landscape based on this distance shows that it is

well suited to graph partitioning.

A second difficulty with designing a crossover for multiway graph partitioning is that of

feasibility: in general recombining feasible partitions does not lead to feasible

offspring partitions. We design a new geometric crossover for permutations with

repetitions that naturally suits partition problems and we test it on the graph

partitioning problem. We then combine it with the labeling-independent crossover and

obtain a much superior geometric crossover inheriting both advantages.