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

Many 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.