The Competing Genes Evolutionary Algorithm: Avoiding Genetic Drift Through Competition, Local Search, and Majority Voting

An estimation-of-distribution algorithm is an evolutionary algorithm that uses a probabilistic model to represent its population. It iteratively draws solutions from its model and, considering their fitnesses, uses these solutions to update the model’s parameters. However, there is a risk of reinforcing random noise from sampling back into the model—a problem termed genetic drift. We propose the competing genes evolutionary algorithm that optimizes a fitness function over a binary search space and avoids this problem by updating only one model parameter at a time. The algorithm uses the model not only to sample solutions but also to select a parameter in each iteration that it pins to a value for the rest of the search process. We obtain upper bounds on the number of fitness evaluations the algorithm needs to solve well-known benchmark functions as a function of its population size and observe better or comparable results to other evolutionary algorithms. We attribute these favorable results to the algorithm’s efficient use of its samples to explore its dwindling search space. We also introduce two variants of the algorithm. The first version eliminates the need to preset the number of solutions to sample per iteration, and the second seeks to escape local optima. We provide evidence that these variants achieve their goals.