cs.NEOct 15, 2026

A restart rule for genetic algorithms based on Schnabel census

Authors: Anton Eremeev, Yulia Zakharova

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

metricGA (mode C)GA (mode B)GA (mode A)GAEAXGA_{EAX}
Δaver\Delta_{\mathrm{aver}}0.000480.000910.00170.00029
Δbest\Delta_{\mathrm{best}}0.000120.000410.00100.000024
CaverC_{\mathrm{aver}}1229542.621229547.391229555.991229539.10
CbestC_{\mathrm{best}}1229537.121229540.441229547.331229535.35
Таблица 1. Comparison of results for algorithms: our GA (modes A, B, C) and GAEAXGA_{EAX} on ATSP instances
AlgorithmTime, sec.nhitn_{hit}noptn_{opt}Δaver\Delta_{aver}
GA-LI29.11–100%0
PVNS6.19100%100%0
m-VNS0.908100%100%–
GA (mode C)0.05100%100%0
GA (mode B)0.05100%100%0
GA (mode A)0.92100%100%0
Таблица 2. Results for TWTP series with n=40n=40 .
AlgorithmTime, sec.nhitn_{hit}noptn_{opt}Δaver\Delta_{aver}
GA-LI41.02–99.2%0.000
PVNS12.15100%100%0
m-VNS1.62100%100%–
GA (mode C)0.12100%100%0
GA (mode B)0.14100%100%0
GA (mode A)1.1194%100%0
Таблица 3. Results for TWTP series with n=50n=50 .
AlgorithmTime, sec.nhitn_{hit}noptn_{opt}Δaver\Delta_{aver}
GA-LI118.97–66.4%0.02
PVNS183.47100%100%0
m-VNS5.84599.84%100%–
GA (mode C)1.4100%100%0
GA (mode B)1.5100%100%0
GA (mode A)3.1867%74%0.017
Таблица 4. Results for TWTP series with n=100n=100 .
More in this topic

Genetic Algorithms

Genetic algorithms use selection, mutation, and recombination to search complex spaces of candidate solutions.

See all 49 papers

Explore similar work

CardsList

  1. An interpretable Good--Turing restart criterion for k-means++

    Jul 9, 2026Renato Cordeiro de AmorimEarly StoppingClustering

    School of Computer Science and Electronic Engineering, University of Essex, Colchester, UK.

  2. MSC-CMA-ES: Structure-Aware Restarts for CMA-ES via Cyclic Nearest-Better Basin Discovery

    Jun 14, 2026Dimitar Nedanovski, Svetoslav Nenov, Dimitar PilevEvolutionary OptimizationCovariance Matrix Adaptation Evolution Strategy

    Faculty of Mathematics and Informatics Sofia University St. Kliment Ohridski James Baucher Blvd., 1164 Sofia, Bulgaria · Department of Mathematics University of Chemical Technology and Metallurgy Sofia, Bulgaria · Department of Informatics University of Chemical Technology and Metallurgy Sofia, Bulgaria

  3. Mathematical perspective on genetic algorithms with optimization guided operators

    Jun 10, 2026Anna Brandenberger, Ilan Doron-Arad, Elchanan MosselQuery ComplexityGenetic Algorithms

    Department of Mathematics, MIT