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.