PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yuan Tian, Yi Mei, Mengjie Zhang

arXiv:2609.14418v1cs.NEcs.AI

TL;DR

Dynamic multi-mode project scheduling combines uncertain durations with precedence, resource, and mode decisions, while simulation-based GP fitness evaluation is costly. This paper studies PC encodings and distances for surrogate-assisted GP; Binary–Euclidean performs most consistently, with redundancy control and diversity also contributing to the reported advantage.

  • Problem

    The study addresses how to design PC encodings and distance metrics for surrogate-assisted GP in DMRCPSP, where existing encodings do not directly represent changing states, mode choices, and group selection.

    Source: §I · p. 2, 2) Phenotypic Characterisation-Based… · p. 4

  • Method

    The framework combines problem-specific PC representations and distance measures with surrogate-assisted GP, duplicate removal, and offspring preselection under a fixed full-evaluation budget.

    Source: §I · p. 2

  • Results

    Binary–Euclidean achieved the strongest and most consistent optimisation performance with relatively low computational overhead; duplicate removal and surrogate preselection were complementary, and together produced the largest improvement.

    Source: F. Discussion · p. 13, §VII · p. 14

  • Takeaways & Limitations

    PC representations should be assessed across the full evolutionary process, including redundancy control and behavioural diversity, rather than by surrogate estimation accuracy alone.

    Source: F. Discussion · p. 13, §VII · p. 14

Abstract

from arXiv · show

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.

I. INTRODUCTION

Dynamic multi-mode project scheduling must handle precedence and resource constraints, multiple execution modes, and uncertain durations. This study examines problem-specific behavioural representations and distances for surrogate-assisted genetic programming under costly simulation-based fitness evaluation.

I. INTRODUCTION

  • Dynamic scheduling revises decisions as new information arrives during execution, while each activity may require a choice among modes with different duration-resource trade-offs.Decisions include selecting activities and assigning their execution modes.Source: §I · p. 1
  • Genetic programming can evolve heuristic rules from scheduling features and operators, addressing the difficulty of manually designing rules that generalize across changing project scenarios.Rules that perform well in one scenario may not generalize when project structures, resource constraints, or uncertainty levels change.Source: §I · p. 1
  • Simulation-based fitness evaluation is costly, and existing phenotypic-characterisation designs do not directly cover DMRCPSP’s changing states, mode choices, and activity-group decisions.The study investigates how PC encodings and distance metrics affect surrogate estimation and scheduling performance.Source: §I · pp. 1–2

A. Problem Description

  • DMRCPSP combines precedence constraints, renewable-resource limits, multiple execution modes, and uncertain activity durations, with project makespan as the objective.Each mode specifies duration and resource needs, and durations are realized during project execution.Source: A. Problem Description · pp. 2–3

B. Genetic Programming for Project Scheduling

Genetic programming has been applied to multiple project-scheduling settings, including dynamic problems, while DMRCPSP adds mode selection to activity selection. Existing approaches use different decision sequences and activity-group strategies, but simulation costs make search under limited evaluation budgets challenging.

B. Genetic Programming for Project Scheduling

  • GP research for RCPSP has explored representation, fitness functions, and rollout approaches, and has extended to multi-project, spatially constrained, and dynamic settings.Machine-learning methods such as feature selection and ensemble learning have also been adapted to RCPSP.Source: B. Genetic Programming for Project… · p. 3
  • DMRCPSP requires choosing both activities and their execution modes, increasing schedule possibilities and decision complexity relative to other RCPSP variants.Prior strategies include selecting activities before modes, modes before activities, or treating activity–mode pairs as decision units.Source: B. Genetic Programming for Project… · p. 3
  • Activity-group selection combines activity–mode pairs into feasible groups, but evaluating multiple candidate groups raises simulation costs and makes limited-budget heuristic evolution a challenge.Group-selection approaches select a group based on priority evaluation.Source: B. Genetic Programming for Project… · p. 3

C. Surrogate-Assisted GP for Evolving Scheduling Heuristics

Surrogate-assisted GP estimates fitness to reduce expensive evaluation costs, using simplified simulations or behavioural characterisations. This study addresses gaps in PC encoding and distance design for DMRCPSP and applies the approach within a framework that removes duplicates and preselects offspring.

C. Surrogate-Assisted GP for Evolving Scheduling Heuristics

1) Simplified Simulation-Based Approaches

  • Simplified simulations can reduce evaluation cost while preserving relative performance to some extent, but effectiveness depends on problem characteristics and instance configurations.Selecting suitable simplification configurations may itself require extensive empirical testing.Source: 1) Simplified Simulation-Based… · pp. 3–4

2) Phenotypic Characterisation-Based Approaches

  • PC-based surrogates avoid complete simulations and can support clustering or diversity selection, but PC encoding and distance choices have received relatively little attention.Reference-rule rank encoding records the final choice but ignores how the rule ranks other candidates and makes distances indirect.Source: 2) Phenotypic Characterisation-Based… · p. 4
  • Existing one-of-many PC schemes do not directly encode DMRCPSP’s selection of subsets of activity–mode pairs, motivating problem-specific encodings and distance metrics.Direct subset enumeration would grow combinatorially; prior work offered an initial ranking-based design without comparing alternative encodings.Source: 2) Phenotypic Characterisation-Based… · p. 4

A. Overall Framework

  • The adopted framework uses two heuristic trees and, each generation, removes intermediate offspring with identical PC vectors before surrogate preselection and full simulation evaluation.The two rules prioritize activity–mode pairs and select among feasible groups.Source: A. Overall Framework · pp. 4–5

B. Heuristic-Guided Scheduling Procedure

The scheduling procedure uses two heuristic rules within a discrete-event simulation: one orders eligible activity–mode pairs, while the other selects a feasible activity group. The process repeats as project status and resource availability change until completion.

B. Heuristic-Guided Scheduling Procedure

  • The procedure builds on a scalable knee-point-guided activity-group selection mechanism, whose ordering and group decisions provide the behaviour characterized in the study.Source: B. Heuristic-Guided Scheduling Procedure · p. 5
  • At each decision time, the simulation updates project status and resource availability, identifies eligible activity–mode pairs, and assigns priorities to those pairs.Source: B. Heuristic-Guided Scheduling Procedure · p. 5
  • Knee-point selection identifies promising pairs for constructing resource-feasible simultaneous activity groups, and the group-selection rule chooses the group with the lowest priority value.After resources are allocated, simulation advances and repeats until activities finish, returning the schedule and project makespan.Source: B. Heuristic-Guided Scheduling Procedure · pp. 5–6

C. Phenotypic Characterisation

Phenotypic characterisations are built from representative decision situations, encoding each GP individual's responses and concatenating those responses into a vector. Three encodings retain progressively less information: priority values, candidate rankings, and final choices.

1) Decision Situation Preparation

  • Representative decision situations are recorded from simulations, filtered, and sampled to provide consistent contexts for comparing GP individuals.Each situation contains the state needed for decisions, including eligible activity–mode pairs, resource availability, and completed and ongoing activities.Source: 1) Decision Situation Preparation · p. 6

2) Encoding Scheme Design

  • The three encodings preserve progressively less information: priority-value encoding records raw priorities, rank encoding records candidate order, and binary encoding records selected choices.For activity group selection, priority and rank vectors cover feasible groups, while binary vectors mark the activity–mode pairs in the selected group.Source: 2) Encoding Scheme Design · p. 6, Figure 7 · p. 6

3) PC Vector Construction

D. Surrogate Model

A 1-nearest-neighbour surrogate estimates an unevaluated individual's fitness from the evaluated individual nearest to it in PC space. The study compares distance measures suited to different behavioural encodings.

1) Nearest-Neighbour-Based Fitness Estimation

  • The 1-NN surrogate assigns a query individual the evaluated fitness of its nearest neighbour in PC space, updating its database as new individuals are evaluated.The lazy-learning setup avoids explicit model training and focuses comparisons on PC encodings and distance metrics.Source: 1) Nearest-Neighbour-Based Fitness… · p. 7

2) Distance Metrics

  • Euclidean distance applies across encodings, Kendall tau counts reversed candidate pairs for rankings, and Pearson or Spearman correlations measure value or rank similarity.For priority values, min-max normalisation is applied within each decision situation before Euclidean distance is computed; situation-level distances are aggregated across contexts.Source: 2) Distance Metrics · p. 7, Table II · p. 7

IV. EXPERIMENTAL DESIGN

The experiments compare six surrogate-assisted GP encoding–distance variants with GP across two offspring multipliers. Evaluation uses simulated 200-activity projects with varied precedence complexity and uncertain durations.

A. Design of Comparisons

  • Six SGP variants spanning value, rank, and binary encodings with compatible distance metrics are compared with GP, using offspring multipliers λoff ∈ {2, 4}.The variants are Value–Euclidean/Pearson, Rank–Euclidean/Kendall/Spearman, and Binary–Euclidean.Source: A. Design of Comparisons · p. 7

B. Simulation Model

  • Projects have 200 activities, 12 renewable resource types, and durations realized within ±3 units of expected values; precedence complexity uses OS values 0.75, 0.5, or 0.25.Each of three scenarios evaluates five independent project instances; fitness is average makespan normalized by the corresponding lower bound across instances, and testing averages performance over 10 duration realisations per instance.Source: B. Simulation Model · pp. 7–8

C. Parameter Settings

Binary–Euclidean is the strongest and most consistent surrogate-assisted variant across tested scenarios and offspring multipliers. The experiments also describe PC sampling and report that increasing the offspring pool does not uniformly improve performance.

C. Parameter Settings

  • GP uses project features grouped as time-based, precedence-based, and resource-based terminals, with parameters following commonly adopted GP configurations.Parameter settings and terminal definitions are listed in Tables III and IV.Source: C. Parameter Settings · p. 8, Table III · p. 8, Table IV · p. 8
  • For each scenario, 10 fixed decision situations per decision type are sampled from simulated cases with more than 10 candidates and reused to construct PC vectors.The cases are generated using LFT and Duration terminals as the activity ordering and group selection rules, respectively.Source: C. Parameter Settings · p. 8

A. Test Performance

  • Binary–Euclidean has the lowest mean objective value in all three scenarios at both multipliers, with overall average rank improving from 2.76 at λoff = 2 to 2.36 at λoff = 4.Rank–Spearman has the second-best average rank at both settings; Value–Pearson is generally less competitive and only limitedly improves on GP in several cases.Source: A. Test Performance · p. 8, Table V · p. 9
  • Increasing λoff from 2 to 4 benefits Binary–Euclidean and Rank–Spearman, but several other variants change little, so a larger intermediate pool does not guarantee proportional optimisation gains.The performance comparison covers 30 independent runs; Table V reports means and standard deviations, with pairwise Wilcoxon signed-rank tests.Source: A. Test Performance · pp. 8–9
  • At λoff = 4, surrogate-assisted variants generally reach lower objective values than GP at the same generation, and Binary–Euclidean maintains among the lowest values across all three scenarios.Fig. 10 shows convergence curves over 30 runs; Rank–Spearman also converges favourably, while Value–Pearson remains near GP for much of evolution.Source: A. Test Performance · p. 9, Figure 10 · p. 9

B. Population Improvement

Surrogate-assisted GP improves overall population quality, while PC generation and surrogate estimation add relatively little runtime compared with full fitness evaluation. The accompanying analyses use shared GP-generated offspring sets to isolate surrogate-related mechanisms.

B. Population Improvement

  • SGP variants generally have lower population training-fitness distributions than GP, indicating improvements beyond the best individual’s performance.The comparison covers generations 10, 30, 50, 70, and 90 over 30 runs with λoff = 4; comparisons are restricted to algorithms within the same generation because seed rotation changes the training environment.Source: B. Population Improvement · p. 9

C. Computational Overhead

  • PC vector generation and surrogate estimation together remain substantially cheaper than real fitness evaluation across configurations.PC vector generation accounts for most added overhead, takes similar time across variants, and increases with λoff; duplicate removal takes approximately one second per generation.Source: C. Computational Overhead · p. 10, Table VI · p. 10
  • Rank-based Spearman and Kendall estimation takes substantially longer than Euclidean and Pearson estimation, with Rank-Kendall especially expensive for large candidate sets.The reported complexity is approximately O(PS_s log n_s) for Spearman ranking and O(PS_s) for the implemented Kendall pairwise comparisons.Source: C. Computational Overhead · p. 10

A. Intermediate Offspring Analysis Setup

  • The analyses evaluate encoding and distance choices retrospectively on the same GP-generated offspring sets, with true fitness known for every offspring.Populations from 30 GP runs are sampled every 10 generations; 4000 offspring are generated per sampled population, with the first 2000 used for the smaller-pool setting.Source: A. Intermediate Offspring Analysis Setup · p. 10

B. Surrogate Fitness Estimation and Preselection Quality

Rank–Spearman usually has the strongest global fitness correlations, but that advantage does not consistently produce better top-subset retention or overall test performance. Binary–Euclidean remains competitive in estimation and preselection quality.

B. Surrogate Fitness Estimation and Preselection Quality

  • Rank–Spearman generally achieves the highest true-versus-estimated fitness correlations, while Normalised Value–Euclidean and Binary–Euclidean also maintain relatively high correlations.Rank–Euclidean and Rank–Kendall are more scenario-dependent, and Value–Pearson starts with weak correlations before improving its ranking accuracy.Source: B. Surrogate Fitness Estimation and… · p. 10
  • Normalised Value–Euclidean consistently outperforms unnormalised Value–Euclidean because unnormalised priority ranges can dominate distance calculations.Situation-wise normalisation is applied before concatenating decision vectors into the complete PC vector.Source: B. Surrogate Fitness Estimation and… · p. 11
  • At Generation 0 in <0.75/R12>, Rank–Spearman, Binary–Euclidean, and Value–Euclidean show clearer positive fitness associations than Value–Pearson, which assigns similar estimates to offspring with differing true fitness.The example is one sampled offspring set.Source: B. Surrogate Fitness Estimation and… · p. 11, Figure 13 · p. 11
  • With 2000 offspring, most variants retain about 0.75–0.85 of true top-1000 offspring versus random 0.5; with 4000, later ratios are 0.45–0.55 versus 25%.Rank–Spearman generally has the highest overlap for the 2000-offspring setting; Value–Euclidean and Binary–Euclidean also perform well.Source: B. Surrogate Fitness Estimation and… · p. 11, Figure 14 · p. 11
  • Higher global correlation did not yield the best overall test performance: Binary–Euclidean led, so estimation accuracy alone does not explain variant differences.Global correlation measures ordering across the pool, whereas preselection depends on retaining offspring in the selected top subset.Source: B. Surrogate Fitness Estimation and… · p. 11

C. Duplicate Removal Capacity

The strongest ablation result comes from combining duplicate removal with surrogate preselection; binary encoding also removes the most duplicates and preserves greater behavioural diversity. These effects extend to retained high-quality offspring, while oracle preselection adds only limited final improvement.

C. Duplicate Removal Capacity

  • Binary encoding removes the most duplicate offspring, rank encoding fewer, and priority-value encoding the fewest across scenarios and pool sizes.Duplicate counts rise with larger pools and generally increase over generations; binary encoding’s increase is particularly pronounced.Source: C. Duplicate Removal Capacity · p. 11

D. Offspring Diversity

  • After duplicate removal, binary encoding yields the largest average nearest-neighbour distance, indicating the least local behavioural crowding among the retained offspring.The comparison measures distances in a common binary-PC Euclidean space; the pattern holds across scenarios and pool sizes.Source: D. Offspring Diversity · p. 12, Figure 16 · p. 12
  • Binary–Euclidean generally preserves greater diversity after preselection, including among top-500 offspring likely to supply parents; λoff = 4 often retains less diversity than λoff = 2.For top-200 offspring, its advantage appears in two scenarios; in <0.5/R12>, Binary–Euclidean, Rank–Kendall, and Rank–Euclidean show similar diversity.Source: D. Offspring Diversity · p. 12, Figure 17 · p. 12

E. Ablation Study

  • Duplicate removal plus surrogate preselection significantly outperforms GP and either component alone across all three scenarios.The ablation uses binary encoding, Euclidean distance, and λoff = 4; the reported comparison is shown in Table VII and Figure 18.Source: Figure 18 · p. 13, Table VII · p. 13, E. Ablation Study · p. 13
  • Duplicate removal alone improves over GP more consistently than surrogate preselection alone, which remains statistically comparable to GP across the three scenarios.GP + Duplicate Removal significantly outperforms GP in two scenarios and is comparable in the third; it beats GP + Surrogate Preselection in two scenarios.Source: E. Ablation Study · pp. 12–13
  • Perfect preselection yields slightly lower mean objective values than surrogate preselection in all three scenarios, but final differences are not statistically significant.Its convergence curves generally decrease faster and remain slightly below the surrogate-based variant; the additional final improvement is limited.Source: E. Ablation Study · p. 13, Figure 18 · p. 13

F. Discussion

The discussion argues that overall search performance depends on more than surrogate accuracy: PC encoding also shapes redundancy removal and retained diversity. Binary–Euclidean offers the best trade-off among the tested configurations, while transfer to other domains remains open.

F. Discussion

  • Surrogate estimation accuracy alone cannot explain variant performance: top-offspring retention becomes more similar after early generations, and perfect preselection adds only limited final improvement.The authors conclude that the current surrogate is sufficiently accurate for guiding search and that further ranking-accuracy gains are unlikely to add substantial benefit.Source: F. Discussion · p. 13
  • Binary encoding removes more redundant offspring and is associated with larger nearest-neighbour distances, including after preselection among high-quality offspring.The ablation results show duplicate removal alone improves more consistently than preselection alone, while their combination performs best.Source: F. Discussion · p. 13
  • Increasing λoff does not guarantee proportional optimisation gains: larger pools can contain more duplicates and yield retained offspring that are no more diverse, or less diverse.The authors conclude that added candidates help only when redundancy is controlled and useful diversity is preserved.Source: F. Discussion · p. 13
  • Among tested configurations, Binary–Euclidean provides the most favourable overall trade-off through strong optimisation, competitive preselection, stronger duplicate removal, diversity preservation, and low overhead.Euclidean distance has considerably lower computational overhead than rank-based correlation distances.Source: F. Discussion · p. 13

VII. CONCLUSIONS

  • Whether Binary–Euclidean’s advantage generalises to other GP domains and behavioural characterisations remains open; future work includes adaptive PCs, diversity management, and noise-aware surrogates.The proposed noise-aware models target stochastic fitness variation introduced by seed rotation.Source: F. Discussion · p. 14, §VII · p. 14
  • The conclusion presents a dynamic multi-mode scheduling SGP framework combining duplicate removal with 1-NN offspring preselection, with Binary–Euclidean strongest and most consistent across examined scenarios.The authors recommend evaluating PC representations by their effects on the overall evolutionary search, not surrogate accuracy alone.Source: §VII · p. 14
Loading 2609.14418v1…