Mixed Binomial Distributions for Binary Mutation Operators

Mutation operators are crucial for evolutionary algorithms to make progress through a search landscape. Sometimes a mutation strategy that works in one part of the landscape is less effective in other regions of the landscape. If nothing is known about the best mutation operator, many strategies (such as self-adaptation, heavy-tailed mutation, variable neighborhood search) exist to overcome this. However, in some cases, some limited information may be available, either a priori or after probing. In this paper, we study the setting of a mixture of binomial distributions for pseudo-Boolean optimization. We show that, when a limited amount of information is available, evolutionary algorithms using mutation based on a mixture of binomial distributions can hill-climb and escape local optima efficiently.