CS Paper Radar

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

Zhuoliang Xie, Changliang Zhou, Genghui Li, Zhenkun Wang

cs.AI ·submitted 2026-10-02 13:53 UTC · v2

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

From Search to Signal: Search-Value Credit for Evolutionary Automatic Heuristic Design

cs.LG cs.AIcs.NE ·2026-09-30 ·Yilun Yuan, Tianyu Zhou, Zhenzhou Tang
similarity 0.70
Abstract · 80 pages, including supplementary material. Substantially revised version introducing Search-Value Credit (SVC), with a redesigned reward me…

Large language models generate candidate programs for automatic heuristic design, while evolutionary search evaluates and selects them to guide further generation. Online post-training uses rewards from candidate evaluations to adapt the generator. Retained programs can also guide later generation as parents. This motivates rewards that reflect their reuse opportunities beyond immediate fitness. We propose Search-value credit (SVC), which constructs response-level rewards from actual admission to the retained set and a short-term parent-exposure proxy. Admission determines reward eligibility; the proxy weights eligible responses by reuse opportunities under existing parent-selection rules. Rewards are computed after candidate evaluation, without evaluating descendants. SVC retains the search and learning procedures of the Co-Evolution of Algorithms and Language Model (CALM) framework. Across four combinatorial optimization tasks with the same base model and response budget, SVC achieves the best mean final search performance on three tasks among six conditions. Under identical prompts and parents on traveling salesman and capacitated vehicle routing tasks, SVC-trained generators yield a higher mean proportion of responses whose programs outperform the best prompting parent than those trained with CALM's native reward. These findings support reward construction using search retention and selection information.

0.24

LLM-Driven Joint Evolution of Coupled Heuristics Components for Routing Optimization

cs.NE ·2026-09-02 ·Juntao Wei, Yangming Zhou, Zhibin Jiang, Shan Jiang
similarity 0.68
Abstract

Heuristic design for combinatorial optimization remains heavily reliant on expert knowledge, while existing large language model (LLM)-enhanced evolutionary methods typically evolve isolated algorithmic components, even when one determines the search state on which another operates. This paper proposes LLM-driven Heuristic Components Joint Generation (LLM-HCJG), a population-based framework that jointly generates and co-evolves interdependent heuristic components under a shared design blueprint. Applied to guided local search (GLS), LLM-HCJG couples solution initialization with penalty construction and embeds the generated pair into an enhanced online search mechanism. The resulting form is further transferred from the traveling salesman problem (TSP) to the capacitated vehicle routing problem (CVRP). Theoretical analysis establishes the non-separable state-transition effects between the two components and the advantage in generation consistency. Across synthetic instances and 41 public TSPLIB/CVRPLIB benchmarks, LLM-HCJG attains consistently low optimality gaps, including best or tied-best results on 28 of 29 TSPLIB instances and all 12 CVRPLIB instances. Ablation and structural analyses further indicate that these gains are associated with cross-component compatibility and alignment rather than isolated-component recombination. These results support effective cross-instance transfer within the evaluated routing settings under limited-sample, modest-cost training.

0.31

Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design

cs.AI ·2026-10-22 ·Jianghan Zhu, Jianan Zhou, Fei Liu, Ni Zhang, Yaoxin Wu +2 more
similarity 0.66
Abstract · 46 pages, 9 figures, 19 tables. The main paper, including references, is 13 pages; appendices are included

Large language models (LLMs) have demonstrated strong potential to automate heuristic design for NP-hard combinatorial optimization (CO) tasks without human intervention. Recent methods predominantly rely on evolutionary computation (EC) frameworks, where heuristic diversification is mainly induced through EC-like operators or downstream selection, while the direction of heuristic transformation remains largely unharnessed. In this paper, we propose a multi-directional Perturbation-Rewrite Search (PRS) framework for automatic heuristic design that factorizes heuristic transformation through directional search primitives at the generation level. Specifically, PRS operates on heuristic ideas through three complementary directions: expansion toward richer and more expressive designs, compression toward simpler and less specialized designs, and steering for fine-grained refinement, together enabling broader and more sustained exploration of diverse regions in the heuristic design space. PRS further organizes candidate exploration within a breadth-first search-based process with adaptive operator control, which ensures thorough candidate utilization and sustained exploration, and maintains strong search dynamics while preventing premature convergence. Extensive empirical results across diverse CO tasks show that PRS consistently discovers high-quality heuristics, demonstrating the effectiveness and generality of explicitly directional exploration design.

0.24

Solving Few-Shot Multiobjective Multitask Optimization via Iterative Sequential Transfer

cs.LG cs.AIcs.NE ·2026-09-10 ·Tingyang Wei, Haofeng Wu, Ananda Phan Iman, Zhao Wei, Jiao Liu +1 more
publishedbenchmark similarity 0.66
Abstract · Accepted paper in WCCI/CEC 2026

Applying knowledge transfer across multiple optimization tasks, multitask optimization (MTO) emerges as a promising approach to solving synergistic optimization tasks simultaneously. However, the development of effective knowledge transfer mechanisms in MTO fundamentally relies on aligning elite solution distributions across tasks. This dependency creates a critical bottleneck in few-shot optimization regimes, as restricted evaluation budgets impede the identification of elite solution distributions required for beneficial transfer. This challenge is exacerbated in multiobjective multitask problems, where each optimizer must approximate a continuous Pareto manifold rather than a single optimal point. This paper introduces Iterative Sequential Transfer (IST) to circumvent this bottleneck. We model MTO as a sequence of sequential transfer optimization problems, concentrating evaluations on a single target per iteration. We propose a likelihood-informed task prioritization mechanism to maximize transfer utility by identifying the task most likely ready for knowledge integration. Empirical results on benchmark and real-world problems verify the effectiveness of the proposed method under tight budgets.

0.44

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

cs.NE cs.AI ·2026-10-29 ·Jianghan Zhu, Cong Zhang, Ni Zhang, Yifan Yang, Yew Soon Ong +1 more
similarity 0.62
Abstract · 48 pages, including supplementary material; 5 figures and 13 tables

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.

0.16

EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design

cs.AI cs.CL ·2026-10-12 ·Oguzhan Gungordu, Ayse Tursucular, Siheng Xiong, Faramarz Fekri
code/data similarity 0.61
Abstract

LLM-based automated heuristic design (AHD) discovers heuristics for combinatorial optimization problems (COPs), where an LLM generates candidates in an evolutionary search. Existing frameworks freeze the generator or fine-tune it on a scalar fitness signal hiding which instances each heuristic covers. Reflection-based frameworks improve heuristics with natural-language feedback, but it stays in the prompt and never reaches the generator's weights. We propose EPOCH, which makes instance coverage the objective of the evolutionary search and fine-tunes the generator to internalize reflection. Parent selection, operator allocation, and stagnation recovery all optimize how well the heuristics jointly cover the training instances, so the search returns a complementary heuristic ensemble. The generator learns from its own search by experiential preference optimization. A teacher LLM returns a natural-language insight on the generated heuristics, and the generator produces new heuristics with this insight. These improvements join the preference pairs for direct preference optimization (DPO). Since DPO only teaches the generator to rank these improvements, a reflective self-distillation (RSD) term makes it more likely to generate them on its own, and the gains accumulate over the long horizon of the search. Across COPs and open-source LLM backbones, EPOCH's heuristic ensembles outperform inference-only and fine-tuned baselines and generalize across problem scales.

0.23

Tailoring Optimization Approaches with Domain Knowledge in Industry Process for Meta-heuristic Development

cs.NE cs.AI ·2026-11-10 ·Jakub Cebula, Konrad Gmyrek, Paweł B. Myszkowski, Marko Đurasević, Łukasz P. Olech +1 more
similarity 0.61
Abstract

The paper presents an Industry Process for Meta-heuristic Development (IPMD) schema, a systematic methodology for applying meta- and hyper-heuristic applications to optimization problems. In this context, we present a case study of Balancing Non-dominated Tournament Genetic Programming (BNTGP) applied to solve two NP-hard multi-objective optimization problems: routing (Capacitated Vehicle Routing Problem with Time Windows) and scheduling (Multi-Skill Resource Constrained Project Scheduling Problem). The BNTGP method is based on a metaheuristic design. Its genetic programming-based representation makes BNTGP a hyper-heuristic, as it enables the exploration of a search space of heuristics for solving problems in general. The resulting heuristic can then be applied across a set of problem instances.

0.27

GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning

cs.LG cs.AIcs.NE ·2026-09-01 ·Wenjian Wu, Zesheng Jia, Jiaying Tang, Benyuan Yang, Jin Wang
similarity 0.61
Abstract

Multi-agent combinatorial optimization problems are notoriously challenging due to their NP-hard nature. Recent parallel autoregressive neural solvers improve inference efficiency by allowing agents to make decisions simultaneously, but their performance often degrades on large-scale instances. This is largely attributable to weak modeling of local geometric structures and the fact that conflicting task selections are handled only after action generation. To address these limitations, we propose GeoPAR, a geometry-guided parallel autoregressive reinforcement learning framework for scalable multi-agent combinatorial optimization. GeoPAR integrates three key components: (1) a projection-window sparse geometry mechanism that builds lightweight local candidate neighborhoods through multi-directional projections, (2) sparse edge-biased attention that injects these geometric relations into node representations, and (3) cache-guided conflict-aware assignment that reuses the geometric cache during decoding to suppress duplicate selections of exclusive tasks. Experiments on heterogeneous vehicle routing and open multi-depot pickup-and-delivery problems show that GeoPAR improves large-scale zero-shot generalization while substantially reducing rollout steps and maintaining efficient inference.

0.19