Exact computation of the expectation curves of the bit-flip mutation using landscapes theory

Abstract

Bit-flip mutation is a common operation when a genetic algorithm is applied to solve a problem with binary representation. We use in this paper some results of landscapes theory and Krawtchouk polynomials to exactly compute the expected value of the fitness of a mutated solution. We prove that this expectation is a polynomial in p, the probability of flipping a single bit. We analyze these polynomials and propose some applications of the obtained theoretical results.