Introducing the cumulation to the population based incremental learning and the compact GA to relax genetic drift

The population based incremental learning (PBIL) and the compact genetic algorithm (cGA) are both Bernoulli distribution based search algorithm for optimization of binary variables. The probability parameter that controls the probability of each bit being one is updated based on the ranking of the population from the current distribution. We often observe some parameters move randomly and tend to converge towards undesired values. Such a behavior is called genetic drift and it happens due to a large variance of the parameter update compared to a small expectation of the parameter update. To prevent genetic drift, the learning rate for the parameter update needs to be sufficiently small, but it results in a slow convergence. In this paper, we propose a mechanism to detect genetic drift and prevent parameters from being updated randomly. For this purpose, we introduce the so-called cumulation that is employed in the covariance matrix adaptation evolution strategy. Experimental results show that the cumulation allows PBIL and cGA to use a greater learning rate for the parameter update, leading to a speed up, especially on functions with high redundancy such as LeadingOnes function.