title: Geometric crossovers for multiway graph partitioning.
abstract: Geometric crossover is a representation-independent generalization of the traditional crossover 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 labeling-independent 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.
authors.affiliation: Centre for Informatics and Systems of the University of Coimbra Polo II - Pinhal de Marrocos, 3030 Coimbra, Portugal. moraglio@dei.uc.pt
authors.forename: Alberto
authors.initials: A
authors.lastname: Moraglio
authors.forename: Yong-Hyuk
authors.initials: YH
authors.lastname: Kim
authors.forename: Yourim
authors.initials: Y
authors.lastname: Yoon
authors.forename: Byung-Ro
authors.initials: BR
authors.lastname: Moon
mesh_terms: D000465:Algorithms; D008957:Models, Genetic; D008962:Models, Theoretical