CS Paper Radar

Surrogate-Assisted Genetic Programming with Phenotypic Characterisation in Dynamic Multi-Mode Project Scheduling

Yuan Tian, Yi Mei, Mengjie Zhang

cs.NE cs.AI ·submitted 2026-09-13 10:37 UTC · v1

Abstract

Dynamic multi-mode resource-constrained project scheduling requires decisions to be made under precedence constraints, limited resources, multiple execution modes, and uncertain activity durations. Genetic programming (GP) can automatically evolve heuristic rules for such problems, but its simulation-based fitness evaluation is computationally expensive. This study investigates phenotypic characterisation (PC) in surrogate-assisted GP to evolve higher-quality scheduling heuristics under a fixed budget of full simulation-based fitness evaluations. A key question is how GP individuals should be encoded into phenotypic characterisations to support effective fitness estimation. To answer this question, three PC encoding schemes with different levels of information richness are designed: priority-value encoding, which preserves raw rule outputs; rank encoding, which captures candidate ordering; and binary encoding, which represents final scheduling decisions. These encodings are combined with different distance metrics to measure behavioural similarity between GP individuals. The experimental results show that binary encoding with Euclidean distance provides the most effective and robust surrogate guidance. Further analyses show that surrogate estimation accuracy alone does not fully explain the performance differences. The PC representation also determines how effectively phenotypically redundant offspring are removed and how much behavioural diversity is retained after preselection. Ablation experiments further demonstrate that duplicate removal and surrogate preselection provide complementary benefits, with their combination producing the largest improvement. These findings highlight that effective surrogate-assisted GP depends not only on identifying promising offspring, but also on controlling redundancy and preserving useful diversity during evolutionary search.

Comment
15 pages, 18 figures, 7 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Accelerated Genetic Programming Hyper-Heuristics for Simulation-Based Scheduling via Agentic AI

cs.SE cs.AIcs.NE ·2026-08-19 ·Heyang Thomas Li, Alexander Pletzer, Yuan Tian, Yi Mei, Mengjie Zhang
similarity 0.66
Abstract

Python is widely used in scientific research because it enables rapid development and provides rich ecosystems for data analysis, artificial intelligence (AI), and machine learning. However, customized research code can become prohibitively slow as experiments scale. This challenge is particularly acute in discrete-event project-scheduling simulations, where sequential state updates, nested loops, conditional evaluations, and object-oriented structures limit the benefits of compiled numerical and GPU-accelerated libraries. Addressing these bottlenecks typically requires iterative profiling, refactoring, testing, and validation, yet researchers may lack the time or specialized software-engineering expertise for low-level optimization. This paper presents a systematic refactoring approach using Claude agentic AI on real-world project-scheduling workloads in a high-performance computing (HPC) environment. Guided by representative benchmarks and correctness checks, the agent identifies bottlenecks, implements targeted optimizations, and evaluates their effects, while the researcher retains final control. Testing runtime reduced from 1,298 seconds to under 200 seconds without changing outputs, saving four million core-hours (NZ\$320,000) annually.

0.41

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.58
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

GA-Agent: Large Language Models as Hyperparameter Optimizers for Evolutionary Controller Synthesis

eess.SY ·2026-09-23 ·Mohammad Narimani, Seyyed Ali Emami
similarity 0.57
Abstract

Tuning PID controllers to satisfy competing objectives - low tracking error, fast settling, limited overshoot, and moderate control effort - is labor-intensive and requires expertise. Genetic algorithms (GAs) offer gradient-free optimization of controller gains against a weighted fitness function, but success depends on meta-level choices: population size, generation budget, gain bounds, and fitness weights. These are usually set by manual trial-and-error or costly bilevel optimization, exposing a tension: GAs excel at dense numerical search, but configuring them needs high-level, context-dependent semantic reasoning. We propose GA-Agent, which decouples these modes. A standard GA handles low-level PID gain optimization. A large language model (LLM) agent operates at the meta-level: it observes completed GA runs, diagnoses gaps versus user control objectives, and proposes updated GA configurations. The architecture uses structured memory, quantitative goal translation, resource-aware termination, and outcome-driven routing. We evaluate GA-Agent on eight control case studies with diverse dynamics (DC motor, inverted pendulum, aircraft pitch, autonomous underwater vehicle, and others). GA-Agent achieves 100% success on all benchmarks, outperforming a Regular GA with fixed hyperparameters in solution quality and sample efficiency. It matches or surpasses a Cascade-GA baseline while reducing function evaluations by one to two orders of magnitude, typically converging in one to three optimization attempts. Sensitivity analysis shows robustness across LLM backbones and memory configurations. A compact memory buffer (size 2-3) and cost-effective models (DeepSeek-V4-Flash at about $0.002 per run) achieve superior performance.

0.23

The Cost of Becoming: Developmental Encoding Increases Phenotypic Diversity but Reduces Locality and Recombination Robustness in Evolved Robots

cs.NE ·2026-09-14 ·Lyes Saad Saoud
benchmarkposition similarity 0.57
Abstract

Developmental encodings are often motivated by the expectation that a structured genotype-to-phenotype process can improve evolvability, robustness, and adaptation. Yet an encoding that expands phenotypic variation may simultaneously make useful parental structure harder to preserve under mutation and recombination. We test this trade-off in a controlled evolutionary-robotics benchmark comparing three matched representations: direct encoding, a static generative encoding, and a temporal zygotic developmental encoding. All three conditions use 34 genome parameters, 34 adult-controller parameters, identical initial genome matrices, the same optimizer, the same mutation and crossover operators, the same environments, and the same number of fitness evaluations. Across 30 paired evolutionary runs per representation, developmental encoding does not reliably exceed direct encoding in final training or out-of-distribution fitness. It does, however, substantially increase final population phenotypic diversity and mutant-reachable phenotype diversity. The same representation exhibits lower mutation viability, lower genotype--phenotype locality, sharply reduced crossover offspring fitness and viability, and increased recombination novelty. Continued developmental dynamics also attenuate damage applied early in development relative to otherwise identical late damage. These results identify a representation-level trade-off: development can enlarge the neighborhood of reachable phenotypes and provide within-development damage attenuation while degrading the local inheritance of already-adapted structure. We argue that developmental encodings should therefore be evaluated not by performance alone, but by a joint geometry of generativity, locality, robustness, and inheritance compatibility.

0.25

MeanField Surrogate Modeling for Scalable Runtime Scheduling of Concurrent Heterogeneous AI Inference on Shared GPUs

cs.DC cs.AI ·2026-09-02 ·Youssef Ennouri, Soonhoi Ha
published similarity 0.57
Abstract · 4 pages, 3 figures, 2 tables. Accepted for publication in IEEE Embedded Systems Letters

Deploying heterogeneous AI models concurrently on a shared GPU introduces resource contention that complicates runtime scheduling. While surrogate models avoid costly online benchmarking, their profiling requirements typically grow combinatorially with the number of co-running models, limiting scalability. We propose a MeanField surrogate that predicts per-model performance from local configuration and aggregate GPU state rather than explicitly modeling all joint interactions. Experiments on concurrent LLM and vision workloads across $N \in \{2,3,4,5,6\}$ show high predictive accuracy ($R^2 \approx 0.96$) with an empirical sample budget that grows approximately linearly in $N$, in contrast to the combinatorial cost of fully joint profiling. Integrated into a genetic algorithm scheduler, the surrogate scales to an $N=5$ problem with 78,732 feasible joint configurations, remaining within 0.10% of the exhaustive search with zero SLA violations across eight dynamic workload scenarios, while complete online GA decisions take 26 ms median, about $5\times$ faster than exhaustive surrogate search.

0.19

Trust, but Verify: Rigorously Profiling Best-Effort High-Performance Computing for Digital Evolution

cs.NE cs.DC ·2026-08-25 ·Matthew Andres Moreno, Santiago Rodriguez Papa, Charles Ofria, Luis Zaman, Emily Dolson
position similarity 0.57
Abstract

Developments in high-performance computing (HPC) technology continue to drastically increase quantities of available processing power. In the context of digital evolution, this explosive growth offers opportunities to advance both hypothesis-driven explorations of multi-scale biological phenomena and application-driven evolutionary optimization targeting hard problem domains. A particular opportunity arises from emerging next-generation AI/ML hardware accelerator platforms, such as the 880,000-processor Cerebras Wafer-Scale Engine (WSE). Such hardware, however, constrains on-device data storage and movement --- a challenge compounded by vulnerability to failures arising over numerous device components. Best-effort relaxations that depart from a traditional deterministic computing paradigm can help accommodate such constraints, but complicate reproducibility and risk introducing artifactual biases. We explore these concerns, developing a framework to measure runtime behavior of best-effort code and examining case studies of best-effort computing in digital evolution projects. The first case study applies best-effort CPU-cluster multiprocessing to a multicellularity evolution model, which provides 92% scaling efficiency at 64 processes ($2.1\times$ speedup) and exhibits robust median quality of service, even under hardware anomalies. The second case study examines WSE-based simulations, demonstrating best-effort strategies to track spatiotemporal population history --- through sparse, asynchronous device-to-host sampling that tolerates hardware faults. In sum, across potential forms and scopes of best-effort relaxation, we argue that digital evolution is uniquely positioned to contribute in developing post-deterministic HPC paradigms.

0.17

Galop: Billion-Scale Genetic Programming on a Single GPU

cs.NE ·2026-11-10 ·Xavier Hill Roy, Stephen Kelly
code/data similarity 0.56
Abstract · 16 pages, 6 figures. Submitted to EuroGP 2027

Genetic programming (GP) evolves populations of heterogeneous programs, whereas GPUs achieve their highest throughput when groups of threads execute the same instructions. To better align GP evaluation with GPU execution, we present Galop, a hybrid CPU-GPU linear GP system that assigns one individual to each CUDA warp, a group of 32 threads that execute the same instructions across different fitness cases. We compare Galop against EvoGP, a recent high-performance GPU-based tree GP system, on data-rich symbolic regression across two unique GPUs, varying population size and fitness-case count. Galop completes evolutionary runs faster than EvoGP in 27 of the 28 main comparisons, with speedups of up to 13.6 times. Solution quality comparisons favour EvoGP overall, although Galop remains competitive on several problems. Galop also completes a full generation with 2.15 billion individuals on a single H100 GPU, approximately 4.0 times the largest population achieved by any other tested GP system. All five runs at this population complete 100 generations, with a median wall-clock time of 2.23 hours. These results make it practical to study GP populations in the billions on a single GPU. Galop's source code, experimental data, and reproducibility scripts are publicly available at https://github.com/xavierhillroy/Galop.

0.31

A Surrogate-based Approach for Fast Multi-objective Architectural Refactoring Optimization

cs.SE ·2026-09-07 ·J. Andrés Diaz-Pace, Daniele Di Pompeo, Antonela Tommasel
published similarity 0.56
Abstract

Software model optimization is a process that generates architecture alternatives aimed at improving quantifiable non-functional properties of software systems, such as performance and reliability. Multi-objective evolutionary algorithms are commonly used to explore the search space and help designers identify trade-offs among competing non-functional properties (e.g., through a Pareto front). However, such algorithms face efficiency challenges in complex software models and large design spaces, since evaluating the fitness (i.e., the quality) of each architecture requires analysis tools that become computationally expensive when repeatedly invoked during the search process. In this paper, we explore the construction of surrogate models based on regression techniques to approximate the outputs of these analysis tools at significantly lower computational cost, while maintaining reasonable output accuracy. Our experimental results suggest that surrogate models provide savings of up to $30\%$ in computational time and maintain the Pareto front quality provided by evolutionary algorithms. Also, we observed some differences in the architectural models produced by our approach. Overall, surrogate models constitute a promising approach for scaling multi-objective architecture optimization to larger spaces and complex architectural models.

0.43