Breaking the search space symmetry in partitioning problems: An application to the graph coloring problem |
| |
Authors: | El-Ghazali Talbi Benjamin Weinberg |
| |
Affiliation: | Université des Sciences et Technologies de Lille, LIFL - CNRS - INRIA, Bâtiment M3 Cité Scientifique, 59655 Villeneuve d’Ascq CEDEX, France |
| |
Abstract: | 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. |
| |
Keywords: | Partitioning problems Search space symmetry Graph coloring problem Landscape analysis |
本文献已被 ScienceDirect 等数据库收录! |