Source-linked AI summary
Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs
Zhouliang Xie, Changliang Zhou, Genghui Li, Zhenkun Wang
TL;DR
MECo addresses the repeated search required to design heuristics for new problem definitions when target-task feedback is unavailable. It evolves and selects heuristics using source-task feedback, then applies the selected set to targets without further search or adaptation. Across 32 VRP and FJSP variants, it achieves lower mean costs than eight AHD baselines under matched proposal budgets.
Problem
Heuristic design for new problem definitions often requires repeated problem-specific search, while direct zero-shot transfer from source-task feedback remains challenging.
Source: §1 · pp. 1–2Method
MECo uses a transfer gap to guide interactions among task-conditioned heuristic populations, then selects a complementary heuristic set using source feedback for target application without further search or adaptation.
Source: §1 · p. 2Results
Across 32 VRP and FJSP variants, MECo achieves lower mean costs than eight AHD baselines under matched proposal budgets and improves the performance of integrated AHD methods.
Source: §1 · p. 2Takeaways & Limitations
Experiments on VRP and FJSP support coordinated multi-task search as an approach to heuristic sets that generalize beyond their source problems.
Source: §5 · p. 10The design setting uses feedback only from source tasks with different underlying optimization problems; target datasets are held until testing.
Source: §2.2 · p. 3
Abstract
from arXiv · showhide
Designing effective heuristics for diverse combinatorial optimization problems requires substantial expertise and repeated search. Large language models (LLMs) automate heuristic generation and refinement, but heuristic search typically depends on evaluation feedback from the problem being optimized. Generalizing to new problem definitions using only source-task feedback therefore remains a central challenge. We introduce MECo, an LLM-driven multi-task evolutionary framework for zero-shot cross-problem generalization. MECo maintains task-conditioned heuristic populations and uses a transfer gap based on cross-task population performance to guide their interactions. These interactions enable the transfer and recombination of heuristics. A complementary selection criterion then constructs a compact heuristic set by rewarding each member's additional coverage of source combinations. The selected set is applied to target problems without further search or adaptation. Experiments on 32 problem variants across vehicle routing (VRP) and flexible job-shop scheduling (FJSP) show that MECo achieves the lowest mean costs compared with eight automated heuristic design (AHD) baselines under the same budgets. On out-of-domain problems, it outperforms the strongest baseline in each family. Moreover, integrating the framework of MECo with different AHD methods improves their ID and OOD performance in both families, supporting its effectiveness across different methods.
1 INTRODUCTION
Heuristic design for new combinatorial optimization problems often requires repeated, problem-specific search, while joint multi-task design does not guarantee direct transfer to unseen problems. MECo evolves and selects heuristics using source-task feedback for zero-shot application to targets.
1 INTRODUCTION
- Task-specific AHD uses LLMs to generate and refine heuristics with problem feedback, but applying it to another problem typically requires another round of search.The passage describes population-based evolutionary search, reflection, and diversity-oriented evolution among existing approaches.Source: §1 · pp. 1–2
- Cross-task AHD jointly develops heuristics for multiple problems, yet does not ensure direct application to new problems without additional search.New combinations of operational requirements can define distinct tasks, increasing design costs when each requires a fixed search budget; evaluation data may also be unavailable.Source: §1 · p. 2
- MECo evolves populations for combined task specifications, using a transfer gap to guide compatible population interactions and heuristic transfer or recombination.Offspring are evaluated on available source datasets, and the selected heuristic set is applied to target problems without further search or adaptation.Source: §1 · p. 2
- MECo selects a small heuristic set for complementary coverage of source combinations, with evolution and selection relying exclusively on source data.The selected programs are applied to target problems without further search or adaptation.Source: §1 · p. 2
- Across 32 VRP and FJSP variants, MECo achieves lower mean costs than eight AHD baselines under matched proposal budgets.The framework also improves the performance of three existing AHD methods when integrated with them.Source: §1 · p. 2
2 PRELIMINARY
The preliminary section defines optimization and heuristic-design tasks, establishes a source-only setting for cross-problem generalization, and formulates related problems through combinations of constraint attributes.
2.1 OPTIMIZATION PROBLEMS AND HEURISTIC-DESIGN TASKS
- An optimization problem specifies instances, feasible solutions, and costs; a heuristic-design task seeks a heuristic evaluated across instances, with LLM-based heuristics represented as programs.The single-task AHD objective optimizes the heuristic, rather than the individual solutions, across the task's evaluation dataset.Source: §2.1 · pp. 2–3
2.2 SOURCE-ONLY DESIGN FOR CROSS-PROBLEM GENERALIZATION
- In the source-only setting, source-task feedback is available during design, while target datasets are held until testing and the heuristic set is evaluated without further search or task-specific adaptation.Source and target tasks have different underlying optimization problems; evaluation on new instances of source problems separately measures in-domain generalization.Source: §2.2 · p. 3
2.3 COMPOSITIONAL PROBLEM FAMILIES
- Compositional problem families are formed by subsets of constraint attributes applied to a base problem, with targets comprising the base problem and combinations of two or more attributes.The paper studies VRP and FJSP as independent families under this formulation.Source: §2.3 · p. 3
3 METHOD
MECo evolves task-conditioned heuristic populations through combined tasks, using source feedback to guide interactions and evolution. It then selects a compact set of complementary heuristics and freezes it for zero-shot target evaluation.
3.1 GENERALIZATION THROUGH JOINT TRAINING
- Joint source feedback can improve generalization to combined VRP problems over separate source training, with the same number of additional heuristic proposals for each branch.Figure 2 compares the best heuristic from each branch on the same combined problems.Source: §3.1 · p. 3, Figure 2 · p. 4
3.2 FRAMEWORK OVERVIEW
- MECo starts with one population per source task, then repeatedly combines two existing populations to evolve heuristics for their combined task.Task-level search chooses populations using transfer gaps, while program-level evolution generates and selects heuristics; source datasets remain fixed throughout.Source: §3.2 · p. 4, Figure 3 · p. 4
3.3 TRANSFER-GUIDED EVOLUTION
- MECo prioritizes eligible pairs that create unexplored tasks, then favors smaller symmetric transfer gaps based on relative population-quality losses in both directions.Different pairs can contribute to the same combined task, whose populations are merged after inner evolution.Source: §3.3 · pp. 4–5
- For combined tasks, offspring inherit parent heuristics through composition, conflict-resolving or exploratory crossover, and transfer-oriented mutation, then local survival retains candidates with varied source strengths and behaviors.The LLM receives parent programs, task descriptions, and source scores; successful heuristics are selected by task cost and behavioral priority.Source: §3.3 · p. 5
3.4 HEURISTIC SET SELECTION FOR ZERO-SHOT EVALUATION
- MECo selects K=4 heuristics by minimizing average best-member cost across source combinations of two or more, then freezes the set for target evaluation.Selection starts with the lowest mean normalized source-cost heuristic and adds members by their reduction in the current set score.Source: §3.4 · pp. 5–6
4 EXPERIMENTS
Experiments compare MECo with automated and classical heuristic-design baselines across VRP and FJSP variants, then test framework hybrids, component ablations, and generator models. MECo leads the aggregate generalization comparisons, and its framework also improves three existing AHD methods.
4.1 EXPERIMENTAL SETUP
- The study tests 16 variants per family, training on four single-constraint tasks and evaluating on four ID and 12 OOD variants.The families are VRP and FJSP; the OOD set comprises 11 combined-constraint problems and the base problem.Source: §4.1 · p. 6
4.2 CROSS-PROBLEM GENERALIZATION
- MECo achieves the lowest mean costs across source and unseen problems in both families, with the lowest average rank and relative gap across the variant aggregates.Figure 4 also shows higher OOD aggregate costs for both task-specific and cross-task baselines in both families.Source: Table 2 · p. 7, §4.2 · pp. 7–8, Figure 4 · p. 8
- VRP costs versus MoH fall from 21.88 to 21.60 on ID tasks and from 22.55 to 22.11 on OOD tasks; FJSP OOD mean cost falls from 1487.3 to 1474.4.MECo's average rank on VRP is 2.31 versus 3.97 for HSEvo; on FJSP, its OOD standard deviation is 1.1 versus 11.9 for MoH.Source: §4.2 · pp. 7–8
4.3 FRAMEWORK EFFECTIVENESS
- All three MECo hybrids have lower ID and OOD mean costs than their baseline engines in both families.EoH-MECo reduces mean OOD cost relative to EoH by over 5% on VRP and 2% on FJSP.Source: Table 3 · p. 8, §4.3 · p. 8
4.4 COMPONENT ABLATIONS
- Removing any single component raises mean costs on both ID and OOD tasks in both families; transfer-gap guidance and transfer-oriented mutation matter most on VRP.On FJSP, removing exploratory crossover yields the highest makespan and substantial run-to-run variance.Source: Table 4 · p. 9, §4.4 · p. 9
4.5 GENERATION-MODEL SENSITIVITY
- Gemini-3.1-flash-lite achieves the lowest ID and OOD costs for both families, while the relative ordering of GPT-4o-mini and GPT-5.4-nano reverses between VRP and FJSP.The comparison uses the same budget of 2,000 heuristic proposals.Source: Table 5 · p. 9, §4.5 · p. 9
- With a shared budget of 1,000 proposals across TSP, VRP, and FJSP, MECo has lower TSP and VRP costs than EMO-STA and MoH, and improves over EMO-STA on FJSP.MoH performs best on FJSP in this comparison.Source: §4.5 · p. 9
5 CONCLUSION
MECo uses source-feedback-guided multi-task evolution and complementary heuristic-set selection for zero-shot generalization. Experiments in VRP and FJSP show improved ID and OOD performance under a shared budget.
5 CONCLUSION
- MECo uses transfer gaps to guide interactions among task populations, adapting and recombining heuristics using source feedback without target evaluation during design.A complementary selection criterion constructs a heuristic set from source feedback.Source: §5 · p. 10
- Across VRP and FJSP, MECo improves ID and OOD performance under a shared design budget, and integration with EoH, ReEvo, and HSEvo consistently improves performance.The authors conclude that coordinated multi-task search is effective for designing heuristic sets that generalize beyond their source problems.Source: §5 · p. 10
- The authors used generative AI for translation and readability editing, verified translations with two authors, and reviewed the AI-assisted work.They report no use for data generation, methodology, experiments, implementation, analysis, or theoretical development.Source: AI USE STATEMENT · p. 10
A.1 TASK-SPECIFIC AUTOMATED HEURISTIC DESIGN
Task-specific AHD methods automate heuristic search through varied ways of generating programs and using feedback, but typically remain tied to individual tasks. Cross-task methods share knowledge in different forms, while transfer research studies task relationships and exchange.
A.1 TASK-SPECIFIC AUTOMATED HEURISTIC DESIGN
- Task-specific AHD explores program spaces through evolutionary search, reflection, diversity-aware methods, Monte Carlo tree search, neighborhood search, and feedback reuse.Instance-specialization, multi-objective, and other task-specific work also seek complementary strengths or trade-offs.Source: §A.1 · p. 14
A.2 CROSS-TASK AUTOMATED HEURISTIC DESIGN
- Cross-task AHD transfers task-agnostic templates, learns heuristic optimizers, or shares program archives before downstream task-specific adaptation.The reusable knowledge ranges from abstract search principles to executable programs.Source: §A.2 · p. 14
A.3 KNOWLEDGE TRANSFER ACROSS OPTIMIZATION TASKS
- Related transfer research includes shared multi-task VRP solvers and evolutionary cross-task reproduction, while task relationships are characterized through learned representations or predictive transfer graphs.These approaches distinguish representational similarity from empirical transfer utility.Source: §A.3 · p. 14
B MORE METHOD DETAILS
MECo searches over combinations of task attributes using source evaluations, evolves task-conditioned populations, and selects a fixed heuristic set before target evaluation. Its method combines transfer-aware task pairing, heuristic generation and survival, and marginal-coverage selection.
B.1 SEARCH PROCEDURE
- MECo explores task combinations in a directed acyclic graph, using source populations and a shared proposal budget to guide expansions and merge populations for repeated tasks.Unions are prioritized when unexplored; among equally prioritized pairs, the smallest transfer gap is preferred.Source: §B.1 · p. 15
B.2 SOURCE FEEDBACK AND TRANSFER
- The symmetric transfer gap averages directional deterioration between populations on the same destination sources, with no deterioration contributing zero.Normalized source scores make constituent sources comparably influential in combined-task quality.Source: §B.2 · pp. 15–16
B.3 HEURISTIC GENERATION
- Heuristic generation combines compatible mechanisms, resolves conflicting rules, explores contrasting source-performance profiles, or mutates a strong local heuristic while retaining its backbone.Parent selection favors lower combined-task scores, and shared-state behavior grouping prevents repeated candidates from dominating selection.Source: §B.3 · p. 16
B.4 POPULATION SURVIVAL
- Population survival first favors nondominated source-score trade-offs and then behaviorally distinct heuristics, while repeated task combinations pool their retained populations.Behavior is compared through actions on common construction states; representatives are chosen in quality order.Source: §B.4 · p. 17
B.5 FINAL HEURISTIC SET SELECTION
- Final selection greedily adds the heuristic with greatest marginal reduction in source-combination cost, counting only improvements over the set’s current best scores.The selected set is drawn from explored populations and frozen before target evaluation.Source: §B.5 · p. 17
B.6 CONSTRUCTIVE DECISION INTERFACE
- Within each problem family, heuristics rank feasible actions from the current instance and partial solution, then construction updates that partial solution.Task-specific feasibility masks determine admissible actions.Source: §B.6 · p. 17
C TASK DEFINITIONS AND CONSTRAINT SEMANTICS
The study defines VRP and FJSP task families by combining optional attributes with their base-problem rules. The resulting task specifications govern feasibility and cost conventions during construction.
C TASK DEFINITIONS AND CONSTRAINT SEMANTICS
- The study uses base problems with four optional attributes per family, whose active combination determines feasibility rules and cost conventions.The joint instances and augmentation parameters define the task families used in the study.Source: C TASK DEFINITIONS AND CONSTRAINT… · p. 18
C.1 VRP
- VRP variants combine open routes, time windows, route-length limits, and mixed deliveries and pickups while preserving capacity and customer-coverage requirements.Open routes omit the depot return leg; time windows constrain service starts, route limits bound distance, and mixed loads bound delivered and collected quantities separately.Source: §C.1 · p. 18
C.2 FLEXIBLE JOB SHOP SCHEDULING
- FJSP variants add release dates, cross-job assembly precedence, sequence-dependent machine setups, or transportation delays to ordered operations assigned to eligible machines.The base objective is makespan; the model imposes no competition for a finite transport-vehicle fleet.Source: §C.2 · pp. 18–19
D.1 COMPLETE VARIANT SPECIFICATION
The benchmark contains 16 variants each for VRP and FJSP, formed from optional attributes added to each family’s base problem. Four single-attribute variants are in distribution; the base task and eleven multi-attribute combinations are held out.
D.1 COMPLETE VARIANT SPECIFICATION
- Each family has 16 variants: a base problem plus combinations of four optional attributes.The four attributes are added to family-specific base constraints.Source: §D.1 · p. 20, Table 6 · p. 20
- Four single-attribute variants supply training instances; the base task and eleven multi-attribute combinations are held out.Thus, four task types are ID and twelve are OOD.Source: §D.1 · p. 20
D.2 PROBLEM PARAMETERS AND DATA CONSTRUCTION
This section specifies how the VRP and FJSP data are constructed and split, how methods select final heuristic sets under a shared search protocol, and which deterministic rules provide classical references.
D.2 PROBLEM PARAMETERS AND DATA CONSTRUCTION
- Training uses single-attribute tasks, while tests cover source and unseen task types; VRP and FJSP instances follow distinct construction and template protocols.FJSP test templates are disjoint from training and validation, and validation data are excluded from search feedback.Source: §D.2 · pp. 20–21, Table 7 · p. 21, Table 8 · p. 21
D.3 SEARCH AND BASELINE PARAMETERS
- Search uses source-task feedback under a common proposal budget, and final heuristic sets are selected using training feedback alone.Selection procedures differ by method, including greedy coverage-based selection for EoH-S and dominance-dissimilarity ranking for MEoH.Source: §D.3 · p. 22, Table 9 · p. 22
D.4 CLASSICAL CONSTRUCTIVE REFERENCE RULES
- Classical references use deterministic feasibility-aware construction, with nearest-feasible and savings-priority rules for VRP and ECT-based dispatching for FJSP.The rules use shared feasibility masks and state transitions; group means weight variants equally.Source: §D.4 · pp. 22–23, Table 10 · p. 23
E.1 COMPLETE TASK RESULTS
The results compare methods across all benchmark variants and examine performance profiles, composition depth, engine transfers, target adaptation, and larger VRP instances. MECo’s reported advantages vary by setting, including lower FJSP ID and OOD costs after framework transfer and strong average rank under a reduced adaptation allowance.
E.1 COMPLETE TASK RESULTS
- The complete results cover sixteen variants per family; ranks average per-variant midranks, and relative gaps use the best observed method mean rather than a known optimum.Tables 11 and 12 report the VRP and FJSP variant results.Source: §E.1 · p. 24, Table 11 · p. 24, Table 12 · p. 25
E.2 PERFORMANCE PROFILES ACROSS ALL VARIANTS
- Per-variant relative-gap profiles use a log(1 + g) radius, where smaller radii indicate lower costs relative to the best observed method.Shaded regions identify methods, not uncertainty, and their areas are not aggregate scores.Source: §E.2 · p. 26, Figure 6 · p. 26
E.3 PERFORMANCE BY COMPOSITION DEPTH
- MECo leads at composition depths two and three in VRP and all reported depths in FJSP, while HSEvo has the lowest mean on four-constraint VRP.The comparison summarizes multi-constraint variants by active optional-constraint count.Source: §E.3 · p. 26, Table 13 · p. 27, Figure 7 · p. 27
E.4 TRANSFERRING THE FRAMEWORK ACROSS LOCAL SEARCH ENGINES
- All four Holm-adjusted tests support lower FJSP ID and OOD costs for MECo counterparts of EoH and ReEvo across ten searches.Searches, not individual instances, are the independent observations.Source: §E.4 · pp. 27–28, Table 14 · p. 28
E.5 VRP TARGET ADAPTATION
- MECo has the best average rank in VRP target adaptation and uses half as many additional proposals as task-specific baselines, although it is not lowest-cost on either target.Final programs are selected using target training feedback.Source: §E.5 · p. 28, Table 15 · p. 29
E.6 GENERALIZATION TO LARGER VRP INSTANCES
- On 1,000-customer VRP instances, frozen MECo sets have lower aggregate costs than the 100-customer MTNCO checkpoint in both ID and OOD groups.This is a scale-generalization comparison, not an equal-training-budget comparison.Source: §E.6 · p. 29, Table 16 · p. 29
E.7 SEARCH ACROSS HETEROGENEOUS TASKS
The section reports joint design across TSP, VRP, and FJSP, then describes resource use, prompt and interface construction, generation instructions, and representative evolved heuristics. The joint-design results concern participating tasks, not zero-shot transfer to an unseen problem type.
E.7 SEARCH ACROSS HETEROGENEOUS TASKS
- MECo has lower TSP and VRP costs than EMO-STA and MoH at both test sizes, and improves over EMO-STA on FJSP, where MoH performs best.Each method shares 1,000 new programs across the three participating tasks; the study does not test transfer to an unseen problem type.Source: §E.7 · p. 29, Table 17 · p. 30
E.8 RESOURCE USE
- The resource-use comparison reports training time, test time, and token use per search.Training includes generation, source evaluation, and final selection; testing covers frozen evaluation.Source: §E.8 · p. 30, Table 18 · p. 31
F GENERATION PROMPTS AND INTERFACES
- Generation prompts combine task descriptions, function interfaces, active-constraint descriptions, operator instructions, parent programs, and source scores.These components are presented in that order.Source: F GENERATION PROMPTS AND INTERFACES · p. 32
F.1 TASK DESCRIPTIONS AND INPUT TEMPLATES
- Task interfaces direct heuristics to compose behavior from active-constraint primitives and return feasible choices from admissible actions.VRP route continuation checks feasibility; the FJSP interface supplies ready and eligible actions.Source: §F.1 · p. 32, §F.2 · p. 33
F.3 GENERATION INSTRUCTIONS
- Generation instructions ask for compatible mechanisms, conflict-resolving rules, or candidates that address under-covered dimensions of the root-performance Pareto set.The instructions reject pasted-together score functions and superficial diversification by renaming variables or perturbing constants.Source: §F.3 · pp. 33–34
G.1 VRP EXAMPLE
- The VRP example combines feasibility filtering with travel-distance and temporal-feature scoring, then can end a route using an additional route-budget check.Source: §G.1 · p. 35
G.2 FJSP EXAMPLE
- The FJSP example estimates start times from release dates, precedence, transport delays, and machine availability, then adds a setup penalty when setups are active.The environment continues to enforce action feasibility.Source: §G.2 · p. 36
H LICENSES
- Table 19 lists licenses and URLs for the baseline implementations used in the work.Source: H LICENSES · p. 37, Table 19 · p. 37