Evolving Interdependent Operators with Large Language Models for Multi-Objective Combinatorial Optimization

Abstract

Neighborhood search operators are critical to the performance of Multi-Objective Evolutionary Algorithms (MOEAs), yet their design remains heavily reliant on domain expertise. While recent LLM-based Automated Heuristic Design (AHD) methods have made notable progress, they focus on optimizing individual operators independently, overlooking the dynamic coupling relationships between operators that collectively determine MOEA performance.

We formulate multi-operator optimization in MOEAs as a Markov Decision Process (MDP), enabling the improvement of interdependent operators through sequential decision-making. Building on this formulation, we propose E2OC (Evolution of Operator Combination), a framework that achieves the co-evolution of design strategies and executable codes. E2OC employs Monte Carlo Tree Search to progressively explore combinations of operator design thoughts, coupled with an operator rotation mechanism to systematically identify effective operator configurations. The framework supports plug-and-play integration of mainstream AHD methods as the underlying operator designer.

Comprehensive experiments on bi- and tri-objective FJSP and TSP demonstrate that E2OC consistently outperforms expert-designed operators by 10%–22% in Hypervolume, surpasses all state-of-the-art AHD methods, and exhibits strong cross-problem generalization and sustained continuous optimization capability.

邻域搜索算子是MOEA性能的关键，但其设计高度依赖专家经验。现有LLM-based AHD方法仅独立优化单个算子，忽视了算子间的动态耦合关系。本文将多算子优化形式化为MDP，提出E2OC框架，实现设计策略与可执行代码的协同进化。在双/三目标FJSP和TSP上，E2OC以10%–22%的HV提升超越专家设计，全面优于SOTA AHD方法，并展现出强大的跨问题泛化与持续优化能力。

1. Problem & Motivation

Multi-Objective Combinatorial Optimization Problems (MCOPs) — such as production scheduling, vehicle routing, and engineering design — are NP-hard. MOEAs like NSGA-II, NSGA-III, and MOEA/D are the workhorse solvers, but their effectiveness hinges critically on the selection and interplay of domain-specific search operators (crossover, mutation, local search).

The fundamental gap: In MOEAs, different operators act on overlapping or interacting decision subspaces. Modifying one operator changes the generation distribution and effectiveness of others — they may complement or conflict with each other. Designing operators independently systematically leads to suboptimal overall performance. However, both expert-driven and existing LLM-driven approaches lack mechanisms to reason about these inter-operator interactions and sequencing effects.

多目标组合优化问题（生产调度、路径规划、工程设计等）多为NP-hard。MOEA的性能高度依赖邻域搜索算子的选择与配合。核心问题：MOEA中不同算子作用于相互耦合的决策子空间，修改一个算子会改变其他算子的生成分布与效果——它们可能互补也可能冲突。独立设计算子系统性导致全局次优。

Design Paradigms Compared

Design Paradigm Comparison: Expert Design vs Single-Operator AHD vs E2OC Co-Design

Three design paradigms: Expert hand-crafted design → Single-operator AHD (independent optimization) → E2OC co-design (coupled optimization of interdependent operators).

Paradigm	Limitation
Expert Design	Costly, domain-specific, hard to generalize across problems
Genetic Programming (GP)	Requires manually defined primitive/terminal sets; limited cross-domain transfer
LLM Single-Operator AHD (EoH, FunSearch, MCTS-AHD, ReEvo)	Optimizes each operator in isolation; ignores coupling effects between operators
E2OC (Ours)	Co-evolution of interdependent operators via MDP-guided MCTS search

2. MDP Formulation

A key theoretical contribution: we formalize the multi-operator co-evolution process as a Markov Decision Process (S, A, P, R):

State — the current operator combination and associated prompt information: s_t = (O₁, O₂, ..., O_K | P_t)

Action — select which operator i to evolve, and decide whether to rewrite its design prompt: a_t = (i, w_i)

Reward — improvement in scalarized multi-objective performance: R = F̄(d | O') − F̄(d | O), where F̄ is the averaged Hypervolume over N independent evaluations.

This formulation explicitly captures the dynamic, non-stationary nature of multi-operator evolution, since modifying one operator continuously reshapes the search landscape for others.

关键理论贡献——将多算子协同进化形式化为MDP。状态为当前算子组合与提示信息，动作为选择算子并决定是否重写设计提示，奖励为多目标性能的标量化改进。该形式化显式捕捉了多算子进化的动态、非稳态特性。

3. The E2OC Framework

E2OC framework overview: Warm-Start → MCTS Strategy Search → Operator Rotation Evolution (the co-evolution loop of design strategies and executable code).

Phase 1: Warm-Start — Building the Design Thought Space

Establish an initial high-quality language space of multi-domain design thoughts — semantic-level improvement suggestions extracted from independently evolved elite operators. Through independent operator evolution, design thought extraction, and language space construction, E2OC builds a structured semantic space capturing both internal (within-operator) and external (cross-operator) coupling relationships.

建立高质量的跨域设计思想语言空间。通过独立算子进化、设计思想提取和语言空间构建，E2OC构造出捕捉算子内部拓扑关系和跨域耦合依赖的结构化语义空间。

Design Thought Extraction: Prompt Engineering Template

Structured prompt template for extracting design thoughts from independently evolved elite operators.

Phase 2: Progressive Design Strategy Search via MCTS

MCTS explores combinations of design thoughts across different operators to identify the most promising design strategy: a tuple (thought₁, thought₂, ..., thought_K) that guides downstream code generation. Key insight: E2OC pre-constructs a fixed set of high-quality design thoughts per operator during warm-start, bounding the branching factor from unbounded to O(AP^K), tractable for typical MOEA configurations (K = 3~4, AP = 3).

Each MCTS iteration executes Selection → Expansion → Simulation → Backpropagation, with UCB-based node selection balancing exploration and exploitation. Counter-intuitively, bounding the search space improves performance by concentrating evaluation budget on a curated high-quality subspace.

MCTS渐进式搜索设计思想的组合空间。关键设计：预热阶段为每个算子预构建高质量的固定设计思想集，将搜索复杂度从无界控制为O(AP^K)。反直觉的是，有界搜索空间反而优于无界动态生成——有限评估预算集中作用于高质量子空间。

Four MCTS variant architectures: E2OC's bounded warm-start approach consistently outperforms unbounded dynamic generation variants. Counter-intuitively, bounding the search space improves performance by concentrating evaluation budget.

Phase 3: Operator Rotation Evolution

Given a design strategy, an operator rotation mechanism generates actual executable operators and evaluates their collective performance. Each operator is evolved and evaluated in context, within the actual multi-operator system, rather than in isolation. The algorithm generator is pluggable, supporting integration of any state-of-the-art AHD method (EoH, FunSearch, MCTS-AHD, ReEvo) as the underlying designer.

算子轮转机制在真实多算子系统上下文中评估每个算子的贡献。算法生成器可插拔，支持集成EoH、FunSearch、MCTS-AHD、ReEvo等主流AHD方法。

4. Experimental Results

Setup

Dimension	Configuration
Problems	Bi-FJSP (Brandimarte mk01–mk15), Tri-FJSP, Bi-TSP (20/50/100 nodes), Tri-TSP
MOEA Backbones	NSGA-II, NSGA-III, MOEA/D
Operators Designed	FJSP: 4 operators; TSP: 3 operators
LLM	DeepSeek-Chat (best quality-cost trade-off)
Metrics	Hypervolume (HV↑), IGD↓, Relative Improvement (RI%)
Eval Budget	~15,500 operator evaluations (fair comparison)

E2OC vs. Expert-Designed MOEAs

E2OC-designed operators, when plugged into standard MOEAs, consistently and significantly outperform expert-crafted operator combinations:

Problem	MOEA	HV Gain (RI%)
Bi-FJSP	NSGA-II	+22.00%
Bi-FJSP	NSGA-III	+13.27%
Bi-FJSP	MOEA/D	+21.78%
Bi-TSP	NSGA-II	+14.00%
Bi-TSP	MOEA/D	+16.92%
Tri-FJSP	NSGA-II	+17.36%
Tri-FJSP	NSGA-III	+17.24%
Tri-TSP	NSGA-II	+6.30%

关键发现：基准MOEA越弱，相对增益越大——E2OC通过卓越的算子设计有效补偿算法弱点。在Pareto前沿可视化上，E2OC算子实现了更大的解多样性和更优的收敛性。

E2OC vs Expert-Designed MOEAs on Bi-Objective Problems

E2OC vs. expert-designed MOEAs on bi-objective FJSP and TSP benchmarks.

E2OC vs Expert-Designed MOEAs on Tri-Objective Problems

E2OC vs. expert-designed MOEAs on tri-objective FJSP and TSP benchmarks.

E2OC vs. State-of-the-Art AHD Methods

All methods design operators for NSGA-II on Bi-FJSP with identical evaluation budgets (~15,500 evaluations):

Type	Method	HV (All instances)	IGD (All instances)
Single	Random	0.2263	1.4193
Single	FunSearch	0.2265	1.4070
Single	EoH	0.2258	1.4352
Single	ReEvo	0.2185	1.6551
Single	MCTS-AHD	0.2269	1.3950
Multi	CD (Coordinate Descent)	0.2170	1.6536
Multi	UCB (Bandit)	0.2182	1.6300
Multi	LLM-driven	0.2148	1.8772
Multi	Win-UCB	0.2256	1.4619
Multi	E2OC	0.2435	1.1423

单算子AHD方法无法弥补缺乏协同设计意识的不足。naively赋予协同设计能力反而降低性能——"如何"协调与"是否"协调同等重要。纯LLM驱动的算子选择表现最差——显式的搜索机制不可或缺。

Comprehensive comparison against all state-of-the-art AHD methods under identical evaluation budget (~15,500 evaluations).

Ablation Study

Variant	What's Removed	HV (All)	Δ
E2OC	(full model)	0.2435	—
MCTS_OC	MCTS strategy search → fixed single strategy	0.2085	−14.4%
E2OC-SD	Operator rotation → sequential independent design	0.2187	−10.2%

Each core component is indispensable. Removing progressive strategy search causes the largest degradation. E2OC amplifies the capability of any underlying AHD designer: E2OC[EoH] = 0.2435, E2OC[FunSearch] = 0.2264, E2OC[MCTS-AHD] = 0.2269.

MCTS component ablation: each core component (strategy search, operator rotation) is indispensable. E2OC amplifies any underlying AHD designer.

Generalization & Continuous Optimization

Cross-scale: Operators trained on TSP-100 generalize to TSP-150 (+30.93% HV) and TSP-200 (+22.06% HV).
Continuous optimization: E2OC can bootstrap itself: Round 1 → HV=0.2435, Round 2 → 0.2454 (+0.8%), Round 3 → 0.2475 (+1.6%). Not trapped in local optima.
Cost: $1.14 per design task with DeepSeek-Chat, making automated operator design economically viable for real-world applications.

Convergence analysis: E2OC sustains continuous optimization across rounds (Round 1 → 2 → 3). Cross-scale generalization: operators trained on TSP-100 transfer to larger instances (TSP-150, TSP-200) with strong HV gains.

5. Design Philosophy

Semantic-Level Search > Code-Level Search

Traditional AHD mutates code syntax; E2OC searches in the space of design intents. A design thought constrains code generation toward a meaningful direction, dramatically improving sample efficiency.

传统AHD在代码语法层变异；E2OC在设计意图层搜索，大幅提升采样效率。

Bounded Space > Unbounded Space

In LLM-based search, more is not always better. E2OC's warm-start curation concentrates the budget where it matters most. The continuous optimization loop provides a principled escape mechanism.

有界搜索空间反直觉地优于无界空间——有限预算集中作用于高质量子空间。

Co-Design Reveals Functional Complementarity

Evolved operators spontaneously develop a clear division of labor: one specializes in adaptive machine assignment while minimizing sequence perturbation. This complementarity emerges from the co-design process and cannot be achieved by independent optimization.

进化出的算子自发形成功能分工——这种互补性从协同设计过程中涌现，独立优化无法实现。

BibTeX

@inproceedings{qiu2026e2oc, title = {Evolving Interdependent Operators with Large Language Models for Multi-Objective Combinatorial Optimization}, author = {Qiu, Junhao and Chen, Xin and Ge, Liang and Lin, Liyong and Lu, Zhichao and Zhang, Qingfu}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2026}, note = {arXiv:2601.17899} }