CS Paper Radar

A restart rule for genetic algorithms based on Schnabel census

Anton Eremeev, Yulia Zakharova

cs.NE ·submitted 2026-10-15 16:59 UTC · v1
publishedunusual

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.

Journal ref
Eremeev A., Zakharova Yu. A restart rule for genetic algorithms based on Schnabel census. Siberian Electronic Mathematical Reports. 2026. Vol. 23, N 1. pp. 554-570
DOI
10.33048/semi.2026.23.034

Closest papers

Nearest neighbours by meaning across the whole index.

T-GADE: Thermodynamical Generative-AI-Driven Evolution of LLM Artifacts

cs.AI cs.NE ·2026-09-10 ·Kyoko Ogawa, Naoki Mori
theory similarity 0.57
Abstract · v2: 12 pages, 4 figures, 6 tables. Presents T-GADE as a general diversity-aware framework for LLM-based evolutionary computation with an EoH…

Introducing large language models (LLMs) into evolutionary computation enables semantic generation of candidates, but the classical problem of maintaining population diversity remains. Inspired by the thermodynamical genetic algorithm (TDGA), we propose T-GADE (Thermodynamical Generative-AI-Driven Evolution of LLM Artifacts), an evolutionary computation framework extended through LLMs. T-GADE keeps the notions of a population and genetic operators, takes structured artifacts generated by an LLM as individuals, and implements crossover and mutation as LLM operators. It further introduces the HoxLM, an LLM that attempts self-repair of an individual after evaluation and before survival selection; two update schemes, generational and steady-state; and Fermi-type and Bose-type occupancy rules that define solution identity and whether duplicates are permitted. Survival selection is unified as minimization of the free energy $F_T=\langle E\rangle-TH$, and the selection temperature $T$ explicitly controls the balance between quality and diversity. We tested an implementation example aligned with Evolution of Heuristics (EoH) on the online bin-packing task, where the excess is the bin count in excess of the volume lower bound, relative to that bound. The HoxLM-equipped configuration reached lower excess with fewer total LLM calls than EoH. In the preregistered comparison at 400 total calls it won 9 of 10 seed-paired runs, with a median sealed excess of 0.836% against 3.912%, and it was also better in the mean and in the worst case. Temperature controls the spread of the retained population under both update schemes, and a small positive temperature improves training quality over the collapsed $T=0$ point in the generational Bose-type scheme. The evolved heuristics are shown as readable scoring rules.

0.30

Genetic Programming with Behaviour-based Niching for Learning Guided Local Search in Vehicle Routing Problems

cs.NE ·2026-09-21 ·Saining Liu, Yi Mei, Mengjie Zhang
similarity 0.56
Abstract · 15 pages, 3 figures

Genetic Programming Guided Local Search (GPGLS) learns utility functions that guide local search for vehicle routing. Its evolving programs can have similar fitness while inducing different search behaviour, making fitness alone an incomplete basis for population diversity management. We propose GPGLS with Behaviour-based Niching (BN-GPGLS), which characterises programs through six operator-level descriptors collected during local search. A current-generation archive selects fitness-competitive, compact representatives from strata of a behaviour score. Fixed policies use archive parents continuously, whereas adaptive policies activate them using training-fitness and standardised behaviour-dispersion signals, optionally with a tree-size condition. We compare four behaviour-based variants with a no-archive GPGLS control and fitness-based niching over 30 seed-matched runs on generated 200-customer instances. BN-Adaptive achieves the best descriptive average rank on a separate 90-instance monitoring set; aggregate routing-cost differences are small. All five archive policies produce lower final-population median tree sizes than the GPGLS control, with paired Wilcoxon comparisons remaining significant after Holm adjustment. These results identify useful solution-quality and program-size trade-offs within the evaluated setting, without attributing the size reductions to behaviour representation alone.

0.41

Hybrid metaheuristics for architectural design optimization under small evaluation and wall-clock budgets

cs.NE cs.CEmath.OC ·2026-10-19 ·Luciano Ambrosini
similarity 0.52
Abstract · 39 pages, 10 figures, 6 tables

Architectural and structural design optimization in parametric software affords about a thousand evaluations of an expensive model for problems with tens of variables, a regime for which most metaheuristics were not designed. On the side of artificial intelligence, two hybrid metaheuristics are proposed: a covariance matrix adaptation evolution strategy (CMA-ES) whose sampling is enriched with differential-evolution trial vectors, and a particle swarm with success-history parameter adaptation, differential-evolution injection and local refinement. A budget-aware delay of population-size reduction in adaptive differential evolution is also proposed. Under a hard cap of 1,200 evaluations, all counted, the CMA-ES hybrid ranks first on seven shifted and rotated functions at 10 and 30 variables and beats CMA-ES on six of seven functions at 30 variables. Ablations attribute this gain to the injection and show that a local search pays off only when its result re-enters the population. The delayed schedule improves three adaptive differential-evolution variants in 40 of 51 comparisons, with no loss. On the side of engineering application, in Grasshopper the CMA-ES hybrid and plain CMA-ES are never significantly worse than the optimizers of Galapagos, SilverEye, Opossum and Tunny on travelling-salesman instances and on a built 85-variable free-form shell, where they end 48 % below the best external tool in 15 minutes. On a 22-variable building-performance problem with binary choices, differential evolution leads instead. Shifting and rotating the functions reverses the rank of Harris hawks optimization. Solvers should therefore be selected by problem structure and stopping time, not by a single ranking.

0.24

Coronavirus Optimization Algorithm: A Success-History Adaptive Evolutionary Framework with Archive-Assisted Search and Stagnation Recovery for Global Optimization

cs.NE cs.AIcs.CC ·2026-08-24 ·Hari Mohan Pandey
benchmarkunusual similarity 0.52
Abstract

This paper proposes the Coronavirus Optimization Algorithm (COA), a SARS-CoV-2-inspired success-history adaptive evolutionary optimizer for box-constrained continuous global optimization. COA does not model disease transmission; instead, it maps selected coronavirus mechanisms to explicit search operators, including elite-guided attraction, trial-vector generation, adaptive parameter variation, stagnation recovery, and population-size scheduling. The algorithm combines opposition-based initialization, current-to-pbest mutation, binomial crossover, an external archive, success-history adaptation, population reduction, and partial restart. COA is evaluated on 29 CEC 2017 benchmark functions at 10, 30, and 50 dimensions against 15 competitive optimizers. Results show that COA achieves the best overall Friedman rank across all dimensions, with particularly strong performance on composition functions. The findings demonstrate that COA is a compact, transparent, and competitive adaptive evolutionary optimizer, while also highlighting limitations on some hybrid functions and the need for further high-dimensional validation.

0.32

The Modular CMA-ES: A Framework for Modern Evolution Strategies

cs.NE ·2026-10-07 ·Jacob de Nobel, Diederick Vermetten, Anna V. Kononova, Carola Doerr, Thomas Bäck
benchmark similarity 0.52
Abstract

Since their introduction, modern evolution strategies, such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), have become established as powerful methods for continuous black-box optimization. This success has led to a wide range of proposed modifications, each designed to improve performance or behavior in specific optimization scenarios. However, because these developments have largely been introduced and studied in isolation, their interactions remain comparatively underexplored. In this paper, we present the Modular CMA-ES (ModCMA), a configurable framework that integrates a wide range of mechanisms from modern evolution strategies within a single implementation. By decomposing CMA-ES into modules with interchangeable options for sampling, selection and recombination, step-size adaptation, matrix adaptation, and restarting, ModCMA enables systematic exploration of a large design space of modern evolution strategies and facilitates the construction, comparison, and automated configuration of new algorithm variants. We illustrate the benefits of this modular approach through two example studies. First, we compare several matrix-adaptation mechanisms in terms of their computational cost and optimization performance. Second, we use automated algorithm configuration to specialize ModCMA to individual benchmark problems and analyze the resulting configurations. Together, these examples demonstrate how the framework can be used both to study individual algorithmic design choices and to explore their combinations in a systematic and reproducible manner.

0.43

Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup

cs.LG cs.AIcs.NE ·2026-11-11 ·Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
publishedbenchmarktheory similarity 0.51
Abstract · Accepted as a poster at NeurIPS 2026. To appear in the conference proceedings

Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the Max problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length $n$. We prove that the expected time for the ($1$+$1$) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in $n$, specifically at most $O(\log^9{n})$. This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.

0.35

Identifying potentiating events in evolutionary search using replay experiments

cs.NE ·2026-08-10 ·Austin J. Ferguson, Alexander Lalejini
position similarity 0.51
Abstract

In this work, we introduce analytical replay experiments to the evolutionary computing community. Replay experiments originated in the context of laboratory experimental evolution as an empirical approach to identifying potentiating events that increased the likelihood of an observed evolutionary outcome. By restarting a population's evolution from different historical time points, replay experiments sample the distribution of what could have evolved from different points in time, which allows us to quantify how a population's potential for different evolutionary outcomes changed as a result of that population's history. In this work, we give a step-by-step guide to designing replay experiments for evolutionary computing systems. We then provide a demonstrative example replay experiment that measures how potentiation for problem-solving success changed in an evolved genetic programming population, showing that increases in potential for success do not necessarily correspond with increases in a population's fitness. Broadly, we argue that analytical replay experiments can be a powerful tool for expanding the theoretical foundations of evolutionary computing, and we offer suggestions for promising future research directions enabled by replay experiments.

0.34

DCL-GPGLS: Dynamic Curriculum Learning for Genetic Programming Guided Local Search in Large-Scale Vehicle Routing

cs.NE ·2026-09-21 ·Saining Liu, Yi Mei, Mengjie Zhang
similarity 0.50
Abstract · 14 pages, 3 figures

Genetic Programming Guided Local Search (GPGLS) uses genetic programming to evolve utility functions for guided local search in large-scale vehicle routing problems (LSVRPs). Evaluating every GP individual on every training instance at every generation is expensive, so GPGLS is usually trained on small instance batches. Existing curriculum-based GPGLS orders these batches mainly by instance size. Adaptive Curriculum Learning GPGLS (ACL-GPGLS) improves training efficiency by adapting when the search moves between fixed curriculum stages, but the instance difficulty order remains predefined. We propose DCL-GPGLS, which estimates the difficulty of each training instance from the current population's solution quality and updates the estimates during evolution. Each generation then receives a batch near a scheduled difficulty level, with a correction that limits repeated selection of the same instances. Experiments on a fixed training-test split of the CVRPLIB X set show that DCL-GPGLS achieves the best observed average rank and mean test cost among six training policies. It obtains the lowest mean cost on 36 of 65 unseen test instances and is significantly better than the static feedback-derived curriculum, matched in total evaluator calls, on 6 instances, with no significant difference on the remaining 59.

0.32