Exact computation of the expectation curves for uniform crossover

Abstract

Uniform crossover is a popular operator used in genetic algorithms to combine two tentative solutions of a problem represented as 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 from two parent solutions. We prove that this expectation is a polynomial in , the probability of selecting the best-parent bit. We provide efficient algorithms to compute this polynomial for ONEMAX and MAX-kSAT problems, but the results also hold for domains such as NK-Landscapes.