A Restarting Rule Based on the Schnabel Census for Genetic Algorithms

摘要

A new restart rule is proposed for Genetic Algorithms (GAs) with multiple restarts. The rule is based on the Schnabel Census method, transfered from the biometrics, where it was originally developed for the statistical estimation of a size of animal population. In this paper, the Schnabel Census method is applied to estimate the number of different solutions that may be visited with positive probability, given the current distribution of offspring. The rule consists in restarting the GA as soon as the maximum likelihood estimate reaches the number of different solutions observed at the recent iterations. We demonstrate how the new restart rule can be incorporated into a GA on the example of the Set Cover Problem. Computational experiments on benchmarks from OR-Library show a significant advantage of the GA with the new restarting rule over the original GA. On the unicost instances, the new rule also tends to be superior to the well-known rule, which restarts an algorithm when the current iteration number is twice the iteration number when the best incumbent was found.