PaperlayerView exact revision on arXiv

Source-linked AI summary

HEMO: Harness Self-Evolution for Multi-Objective Combinatorial Optimization

Jianghan Zhu, Cong Zhang, Ni Zhang, Yifan Yang, Yew Soon Ong, Zhiguang Cao

arXiv:2610.40023v1cs.NEcs.AI

TL;DR

LLM-based operator design for MOCO commonly evolves operators within a fixed search process, even as trade-offs and component interactions change. HEMO evolves the AOD harness itself through module updates and persistent experience, and reports strong results across tasks and evolutionary backbones, including effective transfer to related tasks.

  • Problem

    LLM-based AOD methods evolve operators within prescribed search processes, leaving the higher-level harness unchanged.

    Source: B. Multi-Objective Optimization · p. 3

  • Method

    HEMO adapts AOD harness decision modules through local updates while a memory filesystem retains optimization experience across states.

    Source: §I · p. 2, §IV · p. 4

  • Results

    Across tasks and two evolutionary backbones, HEMO reports strong performance and effective intra-family transfer; with NSGA-II, it achieves the highest HV in nine of twelve settings and the lowest IGD in nine settings.

    Source: §VI · p. 11, C. Additional Results with the NSGA-II… · p. 40

  • Takeaways & Limitations

    HEMO treats the harness as a persistent, adaptive optimization object for operator design, with reported effective transfer within task families.

    Source: §VI · p. 11

    The Proposer and Realizer use proprietary language models, making harness self-evolution dependent on external API access and cost.

    Source: C. Limitations and Future Directions · p. 11

Abstract

from arXiv · show

Automatic operator design (AOD) has increasingly adopted large language models (LLMs) to generate problem-specific search and variation operators for multi-objective combinatorial optimization (MOCO). Yet most methods evolve the operators while leaving the process that discovers them fixed. This limits adaptation as new Pareto trade-offs and operator interactions change where and how the search should proceed. We introduce HEMO, which makes the AOD harness itself a self-evolving optimization target. HEMO maintains a persistent harness state and updates one module at a time, revising the logic that determines which experience to retrieve, which operators to improve, which parents to select, and how to formulate the orchestration of search steps. Downstream solution quality and runtime guide these updates, while a discounted UCB scheduler directs adaptation toward promising modules as their utility changes. A persistent memory filesystem preserves candidate outcomes and diagnostic feedback across harness states, enabling successive states to build on accumulated optimization experience. Experiments across eight MOCO tasks and two structurally distinct evolutionary backbones demonstrate strong performance against conventional evolutionary, neural, and LLM-based AOD baselines, together with effective transfer to related tasks. HEMO extends automatic operator design beyond evolving individual operators to improving the search process that discovers them.

I. INTRODUCTION

LLM-based automatic operator design improves MOCO search components, but its surrounding control process is generally fixed as search conditions change. HEMO makes that harness a persistent, locally evolving target guided by downstream performance and accumulated experience.

I. INTRODUCTION

  • LLM-based AOD designs problem-specific search and variation operators, extending work on evolutionary algorithms and structured optimization components.MOCO methods include exact approaches, Pareto local search, and population-based algorithms, whose performance often depends on problem-specific representations and variation operators.Source: §I · p. 1
  • As MOCO search explores new trade-offs, candidate structures, and component interactions, effective decisions can change, while fixed harnesses cannot revise their predefined control logic.Independently generated high-level procedures also lack a persistent control-state trajectory.Source: §I · p. 1
  • HEMO evolves its persistent AOD harness through localized updates, assessing states by downstream operator-design performance while retaining and reusing experience in a memory filesystem.This extends harness adaptation beyond fixed outer procedures and independently generated high-level controllers.Source: §I · p. 2
  • Experiments span eight MOCO tasks and two evolutionary backbones, comparing HEMO with conventional evolutionary, neural, and LLM-based AOD baselines in within-task evaluation and cross-task transfer.The tasks cover routing, traveling salesman, knapsack, and scheduling.Source: §I · p. 2

A. Automated Algorithm Design

Prior work automates algorithm components and increasingly complex optimization structures, but commonly leaves the task-specific control harness unchanged. HEMO instead studies persistent harness evolution for LLM-based operator design in MOCO.

A. Automated Algorithm Design

  • AAD and AHD span hyper-heuristics, genetic programming, LLM-driven heuristic search, and complete-algorithm design, while design spaces and composition rules often remain human-specified.Examples include FunSearch, EoH and ReEvo [14],, and LLaMEA.Source: A. Automated Algorithm Design · pp. 2–3

B. Multi-Objective Optimization

  • MOCO approaches include evolutionary solvers and learned policies, while AOD methods evolve problem-specific operators within prescribed search processes, leaving the higher-level harness unchanged.Examples include NSGA-II, MOEA/D, and E2OC [19].Source: B. Multi-Objective Optimization · p. 3

C. Harness Engineering and Evolution

  • Agent harness research automates context, workflows, and search control, but does not generally make the complete task-specific execution harness the direct search object.Meta-Harness [20] and Self-Harness [53] evolve harnesses for general agent tasks; HEMO instead adapts decision modules for MOCO while keeping the execution-critical scaffold fixed.Source: C. Harness Engineering and Evolution · pp. 3–4

A. Multi-Objective Combinatorial Optimization

  • MOCO solvers approximate Pareto fronts under limited budgets, balancing proximity to the true front with coverage across objective trade-offs.The paper uses SEMO and NSGA-II as structurally distinct evolutionary backbones.Source: A. Multi-Objective Combinatorial… · p. 4

B. AOD Harnesses

An AOD harness governs how an LLM-based operator search uses experience, constructs design context, coordinates evaluation, and maintains state. HEMO separates fixed execution infrastructure from self-evolving decision modules, with downstream task performance guiding updates and memory persisting across episodes.

B. AOD Harnesses

  • An AOD harness is the task-specific execution structure that governs experience exposure, design context, candidate generation and evaluation, and search-state maintenance across iterations.It operates around the LLM’s search over operator candidates.Source: B. AOD Harnesses · p. 4

IV. METHODOLOGY

  • HEMO adapts decision modules for experience retrieval, target and parent selection, and candidate evolution, while recording new optimization experience in persistent memory.Module-specific rewards from downstream task performance guide state transitions; the Proposer specifies a module blueprint, the Realizer converts it to code, and the Executor evaluates the child harness.Source: §IV · p. 4

A. Stateful Harness Self-Evolution

  • Initialization generates alternative harness blueprints, evaluates the resulting pool, and selects an initial state from a Pareto archive before subsequent localized module updates.A harness state comprises its code and a blueprint specifying its evolvable modules; the memory filesystem retains experience across states.Source: A. Stateful Harness Self-Evolution · p. 4

OUTER HARNESS STATE TRANSITION

HEMO evolves its harness through localized state transitions, retaining accumulated experience while evaluating downstream operator-design performance. A discounted UCB scheduler selects which decision module to revise as module utility changes.

OUTER HARNESS STATE TRANSITION

  • The harness uses search context and retrieved memory to choose an improvement target, then proposes a module blueprint and synthesizes an executable candidate from parents and experience.The illustrated parent-selection example uses a stagnation redirect and multi-parent generation under the same required signature.Source: OUTER HARNESS STATE TRANSITION · p. 5
  • A MOCO evaluator returns candidate score and validity, while each harness evaluation records its mean negative-HV and runtime outputs with an execution trace.Candidate outcomes and traces are stored in the memory filesystem.Source: OUTER HARNESS STATE TRANSITION · p. 5
  • Each outer step revises one selected decision module and incorporates it into the parent harness to form the child harness for the next evaluation episode.The child is evaluated, and accepted modifications update the harness state while new experience is retained in memory.Source: OUTER HARNESS STATE TRANSITION · p. 5, Figure 2 · p. 5
  • HEMO computes scale-insensitive parent-to-child improvement for each lower-is-better evaluation dimension and uses scalar reward for adaptive module credit assignment.The original multidimensional evaluation remains available for Pareto comparison and archival.Source: OUTER HARNESS STATE TRANSITION · pp. 5–6
  • Discounted UCB selects the next module, favoring recent outcomes while preserving an exploration bonus as module utility changes with the harness state.Older module observations are downweighted, so previously unproductive modules can become useful again after other modules change.Source: OUTER HARNESS STATE TRANSITION · p. 6

B. Persistent Memory and Long-Horizon Feedback

HEMO stores long-horizon operator-search experience outside the transient LLM context and periodically turns accumulated history into compact diagnostic feedback for later harness decisions.

B. Persistent Memory and Long-Horizon Feedback

  • The memory filesystem stores evaluated-candidate experience as structured optimization events, preserving designs, results, parent information, validity or failure, Pareto status, and search metadata across harness states.Persistent records remain reusable across successive states.Source: B. Persistent Memory and Long-Horizon… · p. 6
  • Periodic heartbeat tools summarize the search trajectory and diagnose stagnation or repeated patterns, providing abstracted signals without rescanning the full history.The latest summary report and stagnation report are kept as the only active reference records.Source: B. Persistent Memory and Long-Horizon… · p. 6
  • Because long-horizon AOD can generate hundreds or thousands of candidates, exposing the complete history at every step is impractical and repeated summarization can bias context toward recent attempts.Persistent storage alone does not ensure that records are effectively available to the model.Source: B. Persistent Memory and Long-Horizon… · p. 6

C. MOCO-Specific Harness Design

HEMO keeps execution and bookkeeping interfaces fixed while allowing decision roles to adapt their behavior to the current MOCO search state. Its outer procedure evaluates localized module revisions and retains candidate and harness records in Pareto archives and memory.

C. MOCO-Specific Harness Design

  • A fixed execution scaffold preserves the evaluation protocol, candidate Pareto filtering, diagnostic tools, and memory-writing schema across harness-state transitions.The evaluation interface is specified to prevent harness changes from altering the protocol or gaming the objective.Source: C. MOCO-Specific Harness Design · p. 6
  • Experience retrieval chooses which historical candidate records and search-pattern reports to surface for the current step, rather than merely compressing context.The memory filesystem supports adaptive selection of useful portions of the long-horizon history.Source: C. MOCO-Specific Harness Design · p. 6
  • Target selection chooses which solver component receives a design intervention, while parent selection supplies previously evaluated candidates as references for the next generation action.Target selection may be trivial for solvers with only one evolvable component.Source: C. MOCO-Specific Harness Design · p. 6
  • The outer procedure selects a module with discounted UCB, proposes and realizes its revision, then runs a bounded evaluation episode and updates archives and module reward when successful.A child harness is retained when the parent does not dominate it; failed repair retries retain the parent and assign reward -1.Source: C. MOCO-Specific Harness Design · p. 7
  • Candidate evolution controls how successive candidates are generated and evaluated, permitting iterative, population-based, trajectory-based, staged, or hybrid strategies.Each harness evaluation starts its local candidate population from the same fixed seed pool for controlled comparison and cleaner credit assignment.Source: C. MOCO-Specific Harness Design · p. 7

V. EXPERIMENTS

The experiments evaluate HEMO across eight MOCO tasks, using SEMO and NSGA-II backbones and comparisons with conventional, neural, and LLM-based methods. Evaluation covers source-task performance and intra-family transfer, with solution quality and runtime considered during operator design.

Benchmarks and generalization protocol

  • The benchmark suite contains eight MOCO tasks spanning knapsack, vehicle routing, TSP, and scheduling, with source-to-target pairs used for intra-family transfer evaluation.Synthetic problems use multiple sizes, while FJSP final evaluation uses Brandimarte benchmark instances.Source: §V · p. 7

HEMO configuration

  • HEMO is instantiated with SEMO and NSGA-II, with at most 200 harness-state evaluations for each backbone and different candidate-evaluation budgets.SEMO evaluations generate 50 candidates; NSGA-II evaluations allow 100 complete operator-combination evaluations.Source: §V · p. 7

Objectives and evaluation metrics

  • During AOD, operator candidates are evaluated by negative HV and runtime; final performance is reported with HV, runtime, and IGD.Negative HV and runtime use a lower-is-better convention, while higher HV and lower IGD indicate better Pareto-front coverage and smaller distance to the reference front.Source: §V · pp. 7–8

Compared baselines and evaluation protocol

  • Comparisons include conventional MOEAs, a neural MOCO method, and LLM-based AOD methods, with specified candidate budgets, timeout, and four independent trials for LLM-based results unless otherwise stated.The selected evolved harness is applied to both each source task and its corresponding transfer task.Source: §V · p. 8

A. Main Results

Across SEMO and NSGA-II evaluations, HEMO produces strong heuristic quality on source and transferred tasks, while remaining competitive in runtime and offering favorable quality–runtime trade-offs.

A. Main Results

  • HEMO achieves the highest HV in seven of nine SEMO source-task settings, including 0.5700 versus 0.5381 on Bi-CVRP N = 100 and 0.3619 versus 0.3350 on Bi-KP N = 200.It is also the fastest method in several larger settings, including Bi-TSP N = 100 and Bi-KP N = 100 and N = 200.Source: A. Main Results · p. 8
  • On NSGA-II, HEMO achieves the best HV and IGD in five of six TSP settings and the best overall FJSP solution quality, with limited setting-specific exceptions.The fixed transferred harness achieves the best HV and IGD at all three Tri-TSP sizes; on Tri-FJSP, E2OC has marginally higher HV on Mk15, while HEMO performs better on OOD instances.Source: A. Main Results · p. 9, Table III · p. 9

B. Further Analysis

  • Against PMOCO, HEMO-SEMO achieves higher HV in 11 of 16 settings and lower empirical IGD in 12 of 16, though its relative advantage is problem dependent.It outperforms PMOCO on both metrics across all Tri-TSP and Bi-KP settings.Source: B. Further Analysis · p. 9, Table IV · p. 9
  • At N = 150 and N = 200, HEMO-SEMO beats PMOCO on HV and empirical IGD for both Bi-TSP and Tri-TSP without additional training.The comparison uses the same training size for both methods.Source: B. Further Analysis · p. 9
  • Figure 3 shows HEMO reaching the highest final mean heuristic-front HV across ID and OOD tasks, with favorable quality–runtime fronts but no universal dominance on OOD tasks.On ID tasks, HEMO often matches solution quality at lower runtime and offers alternatives across computational budgets.Source: Figure 3 · p. 10, B. Further Analysis · p. 10
  • Ablations show that the unevolved seed harness performs worst, while sequential module selection and restricted or removed memory access reduce performance.The reported seed-harness HV reductions are 0.3450 on Bi-TSP and 0.3576 on Tri-TSP; the authors attribute gains jointly to harness self-evolution, adaptive scheduling, and the memory filesystem.Source: B. Further Analysis · p. 10, Table V · p. 10
  • Across LLM backbones, GPT-4.1-nano is among the fastest and least expensive but yields weaker final heuristic performance than stronger models.The paper uses it for high-volume candidate generation, where inference speed and cost matter; larger models can slightly improve final quality at considerably higher API cost or runtime.Source: B. Further Analysis · pp. 10–11, Table VI · p. 11

C. Limitations and Future Directions

HEMO’s limitations include dependence on proprietary LLM access, costly candidate evaluation, and nonuniform generalization across problem families. The conclusion presents persistent harness adaptation and retained experience as a direction for improving operator design.

C. Limitations and Future Directions

  • HEMO’s Proposer and Realizer currently require proprietary language models, making self-evolution dependent on external API access and cost.The authors suggest adapting smaller or open-weight models, potentially through distillation, to improve accessibility.Source: C. Limitations and Future Directions · p. 11
  • Candidate evaluation is computationally demanding, and cross-task experiments transfer the harness but not task-specific memory accumulated during search.The authors propose transferable memory that separates reusable design knowledge from task-specific observations, with safeguards against negative transfer.Source: C. Limitations and Future Directions · p. 11
  • HEMO’s advantage over PMOCO is not uniform across problem families: PMOCO remains stronger on Bi-CVRP, while HEMO is stronger in several larger Bi-TSP and Tri-TSP settings.The authors suggest more diverse design instances and evaluation criteria that explicitly assess robustness to distribution shifts.Source: C. Limitations and Future Directions · p. 11

VI. CONCLUSION

  • The conclusion frames HEMO as a persistent, adaptive harness that evolves through localized state transitions while retaining optimization experience in a memory filesystem.The paper reports strong performance across diverse tasks and two evolutionary backbones, alongside effective intra-family cross-task transfer.Source: §VI · p. 11

APPENDIX CONTENTS

The appendices define the performance metrics and benchmark problems used to evaluate HEMO. They describe HV and IGD, normalization choices, and knapsack and routing task formulations and settings.

APPENDIX A MULTI-OBJECTIVE PERFORMANCE METRICS

C. Objective Normalization and Reference Points

  • HV uses problem-specific reference and ideal points, with a shared pair for methods within each benchmark setting; the appendix specifies separate normalization for FJSP and other benchmarks.FJSP scales objectives using instance processing times; knapsack, routing, and TSP use fixed points, with HV normalized by reference-box volume.Source: A. Hypervolume · p. 15, C. Objective Normalization and… · pp. 15–16

B. Inverted Generational Distance

  • IGD compares an algorithm’s non-dominated set with a reference front, which is formed from compared methods’ solutions when an exact front is unavailable.The same reference front is used for all methods in a benchmark setting.Source: B. Inverted Generational Distance · p. 15

A. Knapsack Problems

  • Knapsack benchmarks include Bi-KP and Bi-MDKP, with the latter adding multiple resource constraints; Bi-KP uses 50 fixed instances at sizes 50, 100, and 200.The described Bi-KP implementations use different coefficient scales across SEMO and NSGA-II.Source: A. Knapsack Problems · p. 17

B. Routing Problems

  • Bi-CVRP minimizes routing cost and a measure that penalizes disproportionately long routes, with 50 fixed instances at each of three sizes.Instances use uniformly sampled coordinates and demands; vehicle capacity is set by size.Source: B. Routing Problems · p. 18
  • Bi-SPDP minimizes travel distance and required vehicle capacity; capacity is determined by maximum route load rather than imposed as a fixed constraint.Its synthetic test suite contains 50 fixed instances at each of sizes 20, 50, and 100.Source: B. Routing Problems · p. 18

C. Traveling Salesman Problems

The appendices describe TSP and scheduling benchmarks, two evolutionary backbones, and HEMO’s backbone-specific execution contracts. SEMO and NSGA-II expose different control structures and operator-design spaces.

C. Traveling Salesman Problems

  • Bi-TSP and Tri-TSP use independent two-dimensional coordinate spaces for each objective, with 50 fixed instances at sizes 20, 50, and 100.The variants use two and three objectives, respectively.Source: C. Traveling Salesman Problems · p. 18

D. Scheduling Problems

  • Bi-FJSP minimizes makespan and maximum machine load, while Tri-FJSP adds total machine load; the held-out test suite spans 10–30 jobs and 4–15 machines.SEMO uses synthetic design instances, whereas NSGA-II uses Mk15 for operator design and holds Mk01–Mk14 out.Source: D. Scheduling Problems · p. 19

A. SEMO

  • SEMO incrementally evaluates one offspring and updates a variable-size archive of non-dominated solutions, keeping its control structure simple.The stated properties make it suitable for isolating harness-induced changes and evaluating generated heuristics repeatedly.Source: A. SEMO · p. 19

B. NSGA-II

  • NSGA-II uses tournament selection, non-dominated sorting, and crowding distance, selecting a new population after collecting an offspring population.Its standard population management remains fixed while task-specific variation operators form the design space.Source: B. NSGA-II · pp. 20–21

C. Why Two Backbones?

  • SEMO exposes a single neighborhood operator, whereas NSGA-II exposes multiple interacting operators whose effects emerge through population-level selection.Testing both backbones examines adaptation across different evolutionary control structures and operator-design granularity.Source: C. Why Two Backbones? · p. 22

APPENDIX D ALGORITHMIC DETAILS OF HEMO

  • HEMO has four decision modules: memory retrieval, target selection, parent selection, and candidate evolution; which modules evolve depends on the backbone.SEMO fixes target selection, while NSGA-II evolves all four modules.Source: Appendix D · p. 22
  • The SEMO and NSGA-II execution contracts keep evaluation and recording helpers fixed while exposing specified search-control modules for evolution.Under NSGA-II, each attempt targets an operator within a combination, evaluates it in that combination, and retains the accompanying operator identities as context.Source: Appendix D · pp. 22–23

APPENDIX E PROMPTS

Appendix E presents prompt templates for designing, realizing, and operating a self-evolving heuristic-design harness. The prompts specify evolvable decision modules, candidate-generation inputs, and diagnostic feedback workflows.

APPENDIX E PROMPTS

  • The appendix presents the prompt templates for harness design, code realization, inner heuristic generation, and diagnostic tool calls, while omitting repeated context and fixed-call details.Complete prompts, seed implementations, and NSGA-II backbone prompts are provided in supplementary materials.Source: Appendix E · p. 25

A. Evolvable Harness-Module Prompts

  • The module prompts define how to retrieve experience, choose operators or parents, and organize candidate search, with each blueprint specifying goals, signatures, decision logic, and local hyperparameters.SEMO is used to illustrate the prompts; its single heuristic target makes target selection trivial.Source: A. Evolvable Harness-Module Prompts · p. 25
  • Memory retrieval can adapt its queries, tags, or top_k to search stage, Pareto-archive progress, failures, or stagnation, while exposing diverse trade-offs and useful failure patterns.The prompt recommends bounded, compact records and avoiding routine analysis reports unless useful for stagnation redirection.Source: A. Evolvable Harness-Module Prompts · p. 25
  • Parent selection is prompted to filter for valid, scored heuristics and sample from a high-quality but diverse archive region, including complementary Pareto regions.The parent count specifies the generation setting: multiple parents, one parent, or open generation with none.Source: A. Evolvable Harness-Module Prompts · p. 26

B. Harness Initialization and Code-Realization Prompts

  • The initialization prompt coordinates memory retrieval, parent selection, and evolution, while code-realization prompts implement only designated modules and preserve fixed infrastructure and compatible interfaces.Blueprints are converted into executable methods with explicit local parameter values.Source: B. Harness Initialization and… · pp. 26–27

C. Inner Heuristic Generation Prompt

  • The inner-generation prompt supplies the task template, parent implementations, retrieved records, and diagnostic feedback as context for generating one candidate heuristic.Generated code must preserve the template interface and feasibility constraints, avoid excessive runtime overhead, and include a short description for memory recording.Source: C. Inner Heuristic Generation Prompt · p. 28

D. Memory Summary and Stagnation Report Prompts

  • Heartbeat diagnostics summarize useful and weak patterns, open questions, and recommendations; stagnation reports identify overused patterns and propose a concrete structural pivot.Reports are stored in memory, with each new report replacing the active report of its type.Source: D. Memory Summary and Stagnation… · p. 29

APPENDIX F SEED AND EVOLVED HARNESS MODULES

This appendix presents seed and evolved harness modules for SEMO and NSGA-II, focusing on retrieval, operator targeting, parent selection, and search orchestration. It describes feedback- and history-driven adaptations in evolved harnesses alongside seed implementations and their fixed rotation and pairing schedule.

Seed SEMO harness

  • The seed SEMO harness scored (HV, runtime) = (0.316323, 1.553284 s) on Bi-CVRP and used a fixed loop for retrieval, parent selection, generation, evaluation, and recording.It retrieved valid Pareto records for the current task and sampled one or two parents ranked by nondomination and crowding distance.Source: Appendix F · p. 30

Seed NSGA-II harness

  • The seed NSGA-II harness scored (HV, runtime) = (0.458934, 1.633936 s) on Bi-TSP, rotating target operators and prioritizing parents linked to combination-archive improvements.Within its inner budget, it generates candidates from distinct nondominated parent pairs, then from individual parents, refreshing the parent pool.Source: Appendix F · p. 31

Evolved NSGA-II harness

  • The NSGA-II retrieval module uses search progress and stagnation to prioritize records on HV, runtime, archive improvements, Pareto membership, operator interactions, failures, and related tasks.It interleaves source groups, deduplicates records, and reduces the total retrieval cap during stable progress.Source: Appendix F · p. 32

select_target_algorithm

  • select_target_algorithm scores unseen or underused operator slots using gains, failures, interaction evidence, exploration signals, and context overlap with other operators in the current combination.During stagnation it favors targets with observed improvement and strong interactions, while penalizing plateaus, conflicts, and immediate repetition unless the repeated target is strictly best.Source: Appendix F · pp. 33–34

select_parent_algorithm

  • select_parent_algorithm balances candidate quality, diversity, novelty, and compatibility with the current operator combination, strengthening novelty and diversity during stagnation.It retains the current implementation as a fallback and alternates quality-ranked candidates with compatible candidates not already represented by code or context.Source: Appendix F · pp. 33–34

evolve_target_algorithm

  • evolve_target_algorithm chooses generation modes using Beta sampling, observed rewards, and a UCB bonus, then updates parent credits from offspring outcomes.It forces repair after repeated non-improvement, encourages exploration early, and adds a late bias toward exploitation.Source: Appendix F · p. 34

Harness result

  • Harness 4 (ID 98) achieved Bi-TSP validation HV 0.468633 and runtime 1.656327 s, and had the best validation HV during self-evolution.The passage reports the validation HV and runtime as a paired result.Source: Appendix F · p. 34

retrieve_memory

  • retrieve_memory interleaves evidence about solution quality, runtime, operator interactions, and related tasks, adding failures and reports when search history indicates they are relevant.The retrieval implementation caps and deduplicates records, with failures and reports included conditionally.Source: Appendix F · pp. 32, 34

APPENDIX G WHY DISCOUNTED CREDIT IS SUITABLE FOR STATEFUL HARNESS SELF-EVOLUTION

HEMO credits a module update using downstream harness performance, with expected utility conditioned on the current harness state. Discounting attenuates older credit as the harness changes, supporting module selection under nonstationary utility.

APPENDIX G WHY DISCOUNTED CREDIT IS SUITABLE FOR STATEFUL HARNESS SELF-EVOLUTION

  • The module reward averages normalized, clipped parent-to-child improvements across score dimensions, and the expected utility of updating a module depends on the current harness state.The resulting reward lies in [−1, 1].Source: Appendix G · p. 35
  • As other decision modules change, a module’s expected benefit can also change, making module selection a nonstationary credit-assignment problem.Source: Appendix G · p. 35

A. Attenuation of Stale Module Credit

  • With discount factor γ in (0, 1), an observation from step s contributes weight γ^(t−s) at step t, so older observations lose weight geometrically.Source: A. Attenuation of Stale Module Credit · p. 35
  • After a harness regime change, earlier module credit attenuates geometrically even if that module is not selected again; undiscounted estimates retain historical weight until later observations dilute it.Source: A. Attenuation of Stale Module Credit · p. 35

B. Recovery of Exploration Pressure

The section describes discounted-UCB exploration recovery and persistent memory, then reports HEMO’s results across TSP, FJSP, routing, and knapsack evaluations.

B. Recovery of Exploration Pressure

  • Discounting attenuates earlier module credit and increases neglected modules’ exploration bonuses, helping the scheduler respond when module utility changes.The stated motivation is changing utility across harness states; discounted UCB is not claimed to universally dominate standard UCB.Source: B. Recovery of Exploration Pressure · p. 36

A. Memory Filesystem and Record Schema

  • HEMO’s persistent memory stores candidate records and diagnostic reports, retaining Pareto and operator-composition context for later search decisions.The memory annotations track archive contribution and quality–efficiency position, while operator fields preserve the context of interacting components.Source: A. Memory Filesystem and Record Schema · p. 36

B. Harness Self-Evolution and Inference Protocols for HEMO and AOD Baselines

  • Harness self-evolution is a one-time cost reused at inference; across four source-task settings, its maximum reported runtime is about 216.56 hours and token cost about $29.52.The evaluation protocol uses fixed candidate-generation budgets and, for final testing, five independent solver runs whose mean is reported.Source: B. Harness Self-Evolution and… · pp. 36, 38

A. Comparison with Expert-Designed TSP Operators

  • HEMO has the highest mean HV across Bi-TSP sizes, though 2-opt is slightly better at N = 20; several manual sequences trail strong individual operators.HEMO’s operator combination is 1.911× faster than the slowest method, with runtime close to the fastest combination at the largest size.Source: A. Comparison with Expert-Designed TSP… · pp. 38–39, Table XV · p. 39

B. Additional Results with the SEMO Backbone

C. Additional Results with the NSGA-II Backbone

  • HEMO achieves the highest HV in nine of twelve NSGA-II settings and the lowest IGD in nine, with advantages varying by task and size.On Bi-CVRP, it leads HV at every size; on Bi-MDKP, E2OC leads HV at sizes 50 and 100, while HEMO has the lowest runtime at all three sizes.Source: C. Additional Results with the NSGA-II… · p. 40, Table XVII · p. 40

D. Visualization of Obtained Solutions

  • Figure 4 shows HEMO reaching shorter-distance regions on TSP tasks, while knapsack distributions overlap more; Figure 5 shows overlap on knapsack despite HEMO’s higher HV at every displayed size.The figures retain all final archive points; Figure 5 compares HEMO-designed and expert-designed operators under matched NSGA-II budgets.Source: D. Visualization of Obtained Solutions · p. 40, Figure 4 · p. 41, Figure 5 · p. 42

APPENDIX J REPRESENTATIVE DISCOVERED HEURISTICS AND OPERATOR COMBINATIONS

  • Appendix J presents representative HEMO and baseline designs as examples, while aggregate performance is evaluated in the broader experiments.The examples pair design explanations with executable heuristic or operator code and report each candidate’s score and identifier.Source: Appendix J · p. 43

A. Bi-TSP with SEMO: HEMO and MPaGE

The Bi-TSP comparison contrasts HEMO’s bounded neighborhood search with MPaGE’s broader move menu, showing how each selects parents and samples candidate tours.

A. Bi-TSP with SEMO: HEMO and MPaGE

  • Both designs filter the archive by Pareto dominance and use randomly weighted normalized tour costs to choose a parent; neither requires an improving move.If no sampled move changes the parent, both implementations use a swap fallback.Source: A. Bi-TSP with SEMO: HEMO and MPaGE · p. 43
  • MPaGE samples from a broader menu of six move options, including block relocation, segment reversal, and a no-operation option.It uses up to min(28, max(6, n)) trials and ranks valid sampled tours by normalized scalarized cost.Source: A. Bi-TSP with SEMO: HEMO and MPaGE · p. 43
  • HEMO selects a nondominated parent using normalized tour costs and Dirichlet(0.5, 0.5) weights, then samples block relocations and reversals of the same segment.It uses at most min(14, max(6, ⌊2n/3⌋)) perturbation rounds, deduplicates tours, and retains a swap fallback.Source: A. Bi-TSP with SEMO: HEMO and MPaGE · p. 43
  • With a similar sampling budget, HEMO explores two complementary changes per sampled segment and deduplicates neighbors, focusing trials on distinct alternatives.The paper reports that these mechanisms make more effective use of the budget, consistent with the selected heuristic’s higher HV and lower runtime.Source: A. Bi-TSP with SEMO: HEMO and MPaGE · p. 44

B. Bi-KP with NSGA-II: HEMO and E2OC

In Bi-KP with NSGA-II, HEMO’s operator combination preserves and refines inherited solutions, unlike E2OC’s repair, which rebuilds from an empty selection. The reported HEMO combination has higher hypervolume and lower runtime than the E2OC combination.

B. Bi-KP with NSGA-II: HEMO and E2OC

  • HEMO’s mutation mixes each incoming solution with a greedy selection under randomized objective weights, while its repair preserves and refines the result; E2OC’s final repair rebuilds from empty.HEMO’s repair can fill unused capacity and make feasible exchanges favoring higher-density items.Source: B. Bi-KP with NSGA-II: HEMO and E2OC · p. 45
  • HEMO’s crossover samples a density-guided shared mask and creates complementary children, preserving both parents’ bit values across the pair before repair.The crossover passage also describes paired children, overweight-row repair, and rare single-bit perturbations.Source: B. Bi-KP with NSGA-II: HEMO and E2OC · pp. 45–46
  • HEMO’s complete combination scores HV 0.624848 and runtime 0.873728 s, versus E2OC’s HV 0.620616 and runtime 1.727510 s.The HEMO score is reported with its kp_bitflip candidate; the E2OC score is reported with its complete operator combination.Source: B. Bi-KP with NSGA-II: HEMO and E2OC · pp. 45–46
  • HEMO’s kp_bitflip builds a feasible selection using randomized scalarized profit density, mixes it with the input chromosome, then repairs overweight selections.The combination also includes crossover and repair/mutation operators; the latter reconstructs rows from an empty selection using profit weights λ and 1−λ.Source: B. Bi-KP with NSGA-II: HEMO and E2OC · pp. 45–46
Loading 2610.40023v1…