Breaking the search space symmetry in partitioning problems An application to the graph coloring problem

AbstractMany problems consist in splitting a set of objects into different groups so that each group verifies some properties. In practice, a partitioning is often encoded by an array mapping each object to its group numbering. In fact, the group number of an object does not really matter, and one can simply rename each group to obtain a new encoding. That is what we call the symmetry of the search space in a partitioning problem. This property may be prejudicial for optimization methods such as evolutionary algorithms (EA) which require some diversity during the search.This paper aims at providing a theoretical framework for breaking this symmetry. We define an equivalence relation on the encoding space. This leads us to define a non-trivial search space which eliminates symmetry. We define polynomially computable tools such as equality test, a neighborhood operator and a distance metric applied on the set of partitionings. This work has been applied to the graph coloring problem (GCP). A new distance has been proposed, which is quicker to compute and closer to the problem structure. Computing this distance has been reduced to the linear assignment problem which can be solved polynomially. Using this distance, the analysis of the landscape of the GCP has been carried out