Exact computation of the expectation surfaces for uniform crossover along with bit-flip mutation

Abstract

Uniform crossover and bit-flip mutation are two popular operators used in genetic algorithms to generate new solutions in an iteration of the algorithm when the solutions are represented by binary strings. We use the Walsh decomposition of pseudo-Boolean functions and properties of Krawtchouk matrices to exactly compute the expected value for the fitness of a child generated by uniform crossover followed by bit-flip mutation from two parent solutions. We prove that this expectation is a polynomial in ρ, the probability of selecting the best-parent bit in the crossover, and μ, the probability of flipping a bit in the mutation. We provide efficient algorithms to compute this polynomial for Onemax and MAX-SAT problems, but the results also hold for other problems such as NK-Landscapes. We also analyze the features of the expectation surfaces.