Genetic algorithms restart more effectively using schnabel census method
A restart rule for genetic algorithms based on Schnabel census
Neural and Evolutionary Computing
Summary
Genetic algorithms are computer programs that try to solve problems by trying many possible solutions and improving them over time. Sometimes they get stuck and need to start over to find better answers. The authors came up with a new way to decide when to restart these algorithms, inspired by a method originally used to estimate animal populations. Their approach estimates how many different solutions the algorithm is likely to explore and triggers a restart when it seems to have explored all currently likely options. Tests show this restart method helps the algorithm find better solutions faster compared to older restart rules.
What this means in practice
- •For software engineers: Improve combinatorial optimization software by adding an adaptive restart method that better predicts when to restart genetic algorithms.
- •For operations research teams: Enhance operational problem-solving by applying a more effective genetic algorithm restart strategy to scheduling and routing tasks.
Authors
Anton Eremeev, Yulia Zakharova
Abstract
A new adaptive restart rule for Genetic Algorithms (GAs) is considered. The rule is based on the Schnabel Census method, originally developed for statistical estimation of a size of animal population. In this paper, the Schnabel Census method is applied as a heuristic 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 a 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 applied in a GA with steady-state replacement scheme, using three different combinatorial optimization problems as examples. Computational experiments on well-known benchmarks show a statistically significant advantage of the GAs with the new restarting rule over the original versions of GAs. The new restart rule also tends to be superior to the well-known rule, which restarts an algorithm when the current iteration number is twice the number of iterations till the current best incumbent was found.