Mutation operator characterization: Exhaustiveness, locality, and bias

When designing an evolutionary algorithm, one question which arises is what a good mutation operator should look like. In order to be able to anticipate which operators may perform well and which may perform poorly, knowledge about the behavior of the mutation operator is necessary. To this end, we formally define three operator properties: Exhaustiveness, locality and unbiasedness. Furthermore, we provide statistical measures that allow to compare operators that work on the same optimization problem. The novelty of our approach is that the properties are formally defined in a unified manner, and that the measures can be calculated on arbitrary decision spaces, only assuming that a distance measure between solutions in decision space is given. Tests on a binary decision space using several mutation operators with known properties show that the statistical measures presented in this paper are able to reflect the properties well. Also, the measures are calculated for mutation operators of a more complex problem, namely the cluster partitioning problem. To test the validity of our measures, we introduce an exploration benchmark that measures how well the solutions can move across the decision space when applying a mutation operator to them. Tests on both the binary and the partitioning problem show that our measures reflect the operator behavior well.