PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Junhao Qiu, Xin Chen, Liang Ge, Liyong Lin, Zhichao Lu, Qingfu Zhang

arXiv:2601.17899v2cs.NE

TL;DR

MOEA performance depends on operator interactions, while manual design is costly and recent LLM-based AHD methods mainly evolve isolated components. E2OC co-evolves operator strategies and code through progressive MCTS search; the paper reports advantages over existing AHD methods and sustained gains with continued resources.

  • Problem

    MOEA operator design is costly and expert-dependent, while LLM-based methods have mainly evolved isolated components rather than systematically addressing interdependent operators.

    Source: §1 · pp. 1–2

  • Method

    E2OC co-evolves design strategies and executable codes by progressively searching combinations of operator design thoughts with MCTS.

    Source: §1 · p. 2, §3.4 · p. 4

  • Results

    E2OC outperforms many existing AHD methods, improves manually designed MOEAs on two- or three-objective problems, and sustains enhancements with continued resource investment.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The reported results indicate that evolving design strategies can support sustained MOEA enhancements as resources continue to be invested.

    Source: §1 · p. 2

    Design-thought coupling relationships are expressed in language and knowledge, so conventional numerical methods cannot directly optimize them.

    Source: §3.3 · p. 3

Abstract

from arXiv · show

Neighborhood search operators are critical to the performance of Multi-Objective Evolutionary Algorithms (MOEAs) and rely heavily on expert design. Although recent LLM-based Automated Heuristic Design (AHD) methods have made notable progress, they primarily optimize individual heuristics or components independently, lacking explicit exploration and exploitation of dynamic coupling relationships between operators. In this paper, multi-operator optimization in MOEAs is formulated as a Markov decision process, enabling the improvement of interdependent operators through sequential decision-making. To address this, we propose the Evolution of Operator Combination (E2OC) framework for MOEAs, which achieves the co-evolution of design strategies and executable codes. E2OC employs Monte Carlo Tree Search to progressively search combinations of operator design strategies and adopts an operator rotation mechanism to identify effective operator configurations while supporting the integration of mainstream AHD methods as the underlying designer. Experimental results across AHD tasks with varying objectives and problem scales show that E2OC consistently outperforms state-of-the-art AHD and other multi-heuristic co-design frameworks, demonstrating strong generalization and sustained optimization capability.

1 Introduction

MOEAs address NP-hard multiobjective combinatorial problems, but their performance depends on costly expert-designed operators and interactions that single-operator LLM methods do not systematically model. E2OC co-evolves operator design strategies and code, and is reported to outperform existing AHD methods while sustaining gains with continued resources.

1 Introduction

  • MOEAs depend on domain-specific operator selection and interaction, while manually designing and tuning operators is costly and relies heavily on expert knowledge.Exact algorithms for obtaining entire Pareto sets or frontiers are challenging for these NP-hard problems.Source: §1 · p. 1
  • LLM-based heuristic design has advanced single-operator evolution, but these methods focus on isolated components rather than multi-operator systems.The paper frames operator interactions as important to balancing exploration and exploitation.Source: §1 · p. 2
  • E2OC searches combinations of different operators’ design thoughts to model interdependencies and co-evolves those strategies with executable code.Its design thoughts are improvement suggestions for existing operators, rather than only semantic descriptions of operators.Source: §1 · p. 2
  • E2OC uses progressive design-strategy search and operator rotation to explore operator combinations while supporting mainstream AHD methods as underlying designers.The framework is presented as requiring minimal hand-crafting.Source: §1 · p. 2
  • E2OC outperforms many existing AHD methods, including EoH and MCTS-AHD, improves manually designed MOEAs on two- or three-objective problems, and sustains gains with continued resources.The results cover benchmarks of two widely studied MCOPs.Source: §1 · p. 2

2 Multi-Operator Optimization in MOEAs

The section formulates multiobjective optimization and defines MOEA solvers through combinations of operators that generate candidate solutions. It also describes scalar performance evaluation and notes that the formulation does not explicitly capture operator interdependencies during search.

2 Multi-Operator Optimization in MOEAs

  • Multiobjective optimization seeks solutions balancing conflicting objectives; Pareto dominance and optimality define nondominated solutions and their frontier.The Pareto set is in decision space, and its mapping to objective space is the Pareto front.Source: §2 · p. 2
  • A multi-operator solver combines K operators to generate candidate solutions for instance d, with each operator instantiated by an algorithm generator guided by its prompt.The prompts contain reference information about the corresponding operator code templates.Source: §2 · p. 2
  • Multiobjective solution-set performance is mapped to a scalar score using an aggregation function such as HV or IGD, with multiple evaluations averaged to reduce stochastic variance.The passage specifies N independent evaluations for an instance.Source: §2 · p. 3
  • Operator combinations can be iteratively refined, but this formulation does not explicitly capture interdependencies during search, which the paper proposes analyzing through an MDP.The optimization objective is framed for a limited budget.Source: §2 · pp. 2–3

3 Methodology

E2OC co-evolves operator design strategies and executable codes by searching combinations of operator-specific improvement thoughts. It combines progressive MCTS search with rotating operator design and evaluation.

3.1 Overall Framework of E2OC

  • E2OC co-evolves operator combinations and design strategies, using improvement suggestions to search interdependencies and synergies between operators.The suggestions are textual descriptions of operator improvements, not merely semantic descriptions of the operators.Source: §3.1 · p. 3

3.2 Warm-Start Initialization of Multi-Operator Sets

  • Warm-start independently generates and evaluates candidate operators, then analyzes elite operators to extract improvement suggestions and reusable code templates.The resulting design knowledge and code family support later strategy search and coupled exploration.Source: §3.2 · p. 3

3.3 Language Space of Multi-Domain Thoughts

  • The language space distinguishes same-operator relationships from cross-operator dependencies, which may be complementary, conflicting, or mutually exclusive.Because design thoughts are expressed as language and knowledge rather than numerical variables, conventional numerical methods cannot directly optimize their coupling relationships.Source: §3.3 · p. 3

3.4 Progressive Design Strategy Search

  • Progressive MCTS explores synergistic paths through design thoughts, selecting and expanding tree branches and using operator-rotation evaluation to score completed strategies.Performance feedback is propagated along the search path, and the highest-scoring operator combination and prompt tuple are retained.Source: §3.4 · p. 4

3.5 Operator Rotation Evolution

  • Operator rotation sequentially replaces operators under a selected design strategy, evaluates each updated combination, and retains improvements to refine the operator set.Rotation continues through inner iterations, updating the best combination and its associated design prompts when fitness improves.Source: §3.5 · pp. 4–5

4 Experiments

E2OC is evaluated on bi- and tri-objective FJSP and TSP benchmarks against expert-designed operators, AHD methods, and multi-heuristic frameworks. It improves performance across the reported comparisons, with ablations also supporting progressive strategy search and operator rotation.

4.1 Experimental Setting

  • E2OC is evaluated on FJSP and TSP in bi- and tri-objective settings, using 15 Brandimarte FJSP instances and TSP scales k=20, 50, and 100; comparisons include MOEAs, AHD methods, and co-design frameworks, with equal budgets among AHD methods.Source: §4.1 · p. 5

4.2 Main results

  • E2OC improves HV by 22.00% on FJSP and 14.00% on TSP, and improves MOEA/D on TSP by 16.92% in bi-objective tests.Across all algorithms, reported improvements are at least 10%.Source: §4.2 · p. 5
  • E2OC improves HV by 17.36% in tri-objective FJSP under NSGA-II and achieves the highest average improvement across testing instances.The authors report generalization and robustness without overfitting to training data.Source: §4.2 · p. 5
  • On Bi-FJSP, E2OC outperforms single-heuristic methods across instances, while direct LLM-guided and CD- and UCB-based co-design frameworks degrade in performance.Win-UCB is second-best after E2OC overall, but its training-instance advantage over single-heuristic designs does not hold on other instances.Source: §4.2 · pp. 5–6

4.3 Ablation Studies

  • Ablations report performance degradation when progressive search is removed, and find operator rotation more efficient at finding local optima than sequential independent design.The operator designer also affects performance, with EoH achieving the best results.Source: §4.3 · p. 6

5 Discussion and Future Works

E2OC performs best among the tested MCTS variants, and successive runs further improve its performance. Future work targets semantic-level optimization, human–AI collaboration, and more autonomous algorithm evolution.

5.1 Discussion

  • Stronger general-purpose LLMs do not consistently produce better design or improvement summarization, while deepseek-chat offers a favorable overall trade-off.gpt-4.1-mini performs best on some instances, but deepseek-chat has competitive performance, lower evaluation cost, and a higher quality-cost ratio.Source: §5.1 · p. 6, Table 4 · p. 7
  • Under a fixed evaluation budget, E2OC achieves the best performance across training, testing, and all instance sets among the compared MCTS variants.Its HV values are 0.1985 (training), 0.2467 (testing), and 0.2435 (all).Source: §5.1 · p. 6, Table 5 · p. 7
  • Reusing each run's strategies and operators as the next run's inputs yields consistent performance improvements in the second and third E2OC runs.The authors describe iterative reconstruction of the design-thought space as a continuous optimization capability.Source: §5.1 · pp. 6–7, Table 5 · p. 7

5.2 Future Works

  • LLM-based AHD remains at an early stage; future work calls for principled tools for semantic-level optimization.The proposed search space and dynamics would be defined by language and knowledge representations.Source: §5.2 · p. 7
  • E2OC's strategies improve interpretability, but deployment under complex constraints requires expert knowledge; interactive preference or evaluation input is proposed.Such input could guide and accelerate algorithm design.Source: §5.2 · pp. 7–8
  • Future work proposes using LLM self-reflection and multi-agent coordination for autonomous, iterative algorithm-system evolution.This direction calls for systematic modeling of algorithm representations and their dynamic evolution.Source: §5.2 · p. 8

6 Conclusion

E2OC co-evolves operator design strategies and executable code, using progressive MCTS search and operator rotation to identify operator combinations. Across the evaluated problems and MOEAs, it outperforms expert-designed operators and state-of-the-art AHD methods.

6 Conclusion

  • E2OC co-evolves design strategies with executable codes for interdependent MOEA operators.It uses progressive Monte Carlo tree search to explore design-thought combinations and operator rotation to determine combinations.Source: §6 · p. 8
  • The framework supports mainstream AHD methods as the underlying algorithm generator.Source: §6 · p. 8
  • Across bi-objective and tri-objective FJSP and TSP evaluations, E2OC consistently outperforms mature human-designed operators across multiple MOEAs.Source: §6 · p. 8
  • By explicitly modeling operator interdependencies, E2OC also achieves superior performance to state-of-the-art AHD methods.Source: §6 · p. 8

A Reproducibility Statement

The section surveys automated heuristic design, operator design and selection, and MCTS-based methods before formulating interdependent operator evolution as an MDP. It also records materials provided for reproducing the experiments.

A Reproducibility Statement

  • The supplementary material documents problem and operator settings, hyperparameters, comparison methods, additional results, and source code for replication.The cited locations include Appendices E, F, G, I.2, I.3, and J.Source: A Reproducibility Statement · p. 12

B.1 Automatic Heuristic Design (AHD)

  • GP-based AHD evolves encoded heuristics but relies on manually designed genetic operators and fixed symbol sets, and can produce structures that limit scalability and practical use.LLM-driven AHD searches by generating and modifying algorithmic code; approaches include EoH, MEOH, MCTS-AHD, and neighborhood search.Source: §B.1 · p. 12

B.2 Operator Selection and Design in Evolutionary Algorithms

  • MOEAs need operator sets and selection mechanisms that account for dynamic Pareto fronts and inter-operator interactions, rather than evaluating operators in isolation.Operators must balance convergence toward the Pareto front with preservation of solution diversity.Source: §B.2 · p. 13

B.3 MCTS with LLM for Structured Reasoning and Decision-Making

  • LLM–MCTS methods pair LLM-generated candidates with tree-guided search; MCTS-AHD uses progressive expansion, while MOTIF co-designs multiple strategies through turn-based optimization between two LLM agents.MCTS balances exploration and exploitation through selection, expansion, simulation, and backpropagation.Source: §B.3 · p. 13

B.4 Reflective Prompting

  • Reflective prompting uses a generate–reflect–revise loop, and ReEvo and LLM4EO apply reflection to algorithm search and operator design, respectively.The passage associates these methods with self-assessment and learning from past errors.Source: §B.4 · p. 13

C Markov Decision Process for Multi-Operator Optimization

  • The MDP state contains the current operator combination and its prompts; actions select an operator and whether to rewrite its prompt, while rewards track scalarized performance improvement.Transitions depend on sampled operator combinations’ performance, and the objective is to maximize expected cumulative reward within budget T.Source: C Markov Decision Process for… · pp. 13–14

D Methodology Details

E2OC extracts operator design thoughts, searches combinations of them with MCTS, and evaluates complete strategies through operator rotation. Its methodology also describes prompt construction and alternative MCTS variants.

D.1 Warm-start

  • Warm-start generates and evaluates candidate operators, then extracts design thoughts from higher-performing operators to initialize the prompt storage used in search.The initial operator templates, instance set, and number of added prompts are specified before this phase.Source: §D.1 · p. 14

D.2 Progressive Search

  • Progressive search uses MCTS selection, expansion, simulation, and backpropagation to assemble design thoughts across operators and identify a high-scoring strategy.Operator-rotation evaluation is performed when a path reaches the total number of operators; shorter paths receive temporary evaluations using randomly sampled thoughts.Source: §D.2 · p. 14

D.3 Operator Rotation Evolution

  • Operator rotation generates and evaluates candidates for each operator in turn, replacing an operator when a superior one is found and using the resulting scores to update search-tree branches.The evaluator uses average HV performance over multiple NSGA-II runs.Source: §D.3 · pp. 14–15

D.4 Prompt Engineering

  • Design-strategy prompts use elite operators, expert-designed templates, and output templates to elicit revised algorithm templates with explicit improvement suggestions.The resulting strategies are incorporated into downstream algorithm-design prompts.Source: §D.4 · p. 15

E Different MCTS variants

  • The four MCTS variants differ in whether nodes represent operators, strategy tuples, or individual design thoughts, and whether thought spaces are sampled or predefined.E2OC is the warm-start variant with predefined thought spaces; thought-based variants require an additional operator-design stage after a complete strategy is found.Source: E Different MCTS variants · pp. 15–16

F.1 Problem Description

  • The FJSP allows each operation to run on multiple eligible machines with different processing times; Bi-FJSP uses makespan and maximum machine load, while Tri-FJSP adds total machine load.These objectives can conflict, and the Brandimarte instances provide a standard test platform.Source: §F.1 · p. 17

F.2 Operator Implementation Details

The FJSP operators address separate parts of a two-part solution encoding, but their effects are coupled. The TSP description identifies TSPLIB as a common source of benchmark instances.

F.2 Operator Implementation Details

  • Four FJSP operators act on a two-part encoding: sequencing crossover and mutation modify operation order, while assignment crossover and mutation refine machine choices.Each operator targets its own encoding segment and is designed for that function.Source: §F.2 · p. 17
  • Sequencing changes affect machine-assignment performance and vice versa, so independent operator design can yield suboptimal results when one operator offsets another.The passage frames coordinated evolution as necessary for balancing exploration and exploitation while maintaining feasibility across two- and three-objective FJSPs.Source: §F.2 · p. 17

G.1 Problem Description

  • Figure 4 presents a prompt for design-thought analysis and prompt rewriting.Source: Figure 4 · p. 18
  • TSPLIB instances are commonly used to evaluate MOEAs on multi-objective TSPs.The objectives are formed using different weights on distance, with trade-offs among criteria.Source: §G.1 · p. 18

G.2 Operator Implementation Details

The TSP operators share a path representation, have overlapping functions, and can affect one another, complicating coordinated multi-objective search.

G.2 Operator Implementation Details

  • TSP operators share a path encoding but explore differently through segment reordering, edge exchange, or route inversion, so one operator can enhance or interfere with another.The passage identifies independent design as insufficient and says coordination is needed to balance exploration and exploitation across objectives.Source: §G.2 · p. 18

H Metric Definition

The section defines HV and IGD as measures of Pareto-front performance and RI as a percentage comparison against a baseline.

H Metric Definition

  • Higher HV and lower IGD indicate better convergence and diversity of the obtained Pareto fronts.The study uses both metrics to assess overall performance.Source: H Metric Definition · p. 18

H.1 HV

  • HV measures the objective-space volume dominated by a Pareto front relative to a reference point.The reference point is manually set to dominate all obtained solutions; the volume is formed by hyper-rectangles between solutions and the reference point.Source: §H.1 · p. 18

H.2 IGD

  • IGD measures the average distance from obtained solutions to a reference Pareto front formed from the union of compared algorithms’ non-dominated solutions.Lower IGD means solutions are closer to and more uniformly distributed along that reference front.Source: §H.2 · p. 19

H.3 RI

  • RI quantifies the percentage performance improvement of a new method relative to a baseline.A is the new method’s performance value and B is the baseline’s.Source: §H.3 · p. 19

I.1 Experimental Design.

The experiments assess E2OC against MOEAs, AHD methods, and multi-heuristic design frameworks across FJSP and TSP settings. Comparisons use defined evaluation resources and shared benchmark configurations.

I.1 Experimental Design.

  • The experiments test whether E2OC improves on expert-designed operators and competing design methods, generalizes across objectives and instances, supports continued optimization, and benefits from its modules.Comparisons include bi- and tri-objective FJSP and TSP, single-heuristic AHD, and multi-operator strategies.Source: §I.1 · pp. 19–20

I.2 Comparison Method Detail

  • Comparison frameworks are categorized by explicit algorithmic thoughts, prompt rewriting, and warm-start, while collaborative-search approaches include coordinate descent, UCB, MCTS, and LLM-driven methods.EoH is used as the foundational single-heuristic module across the compared multi-heuristic frameworks.Source: §I.2 · pp. 20–21, Table 6 · p. 20

I.3 Other Parameter Settings

  • Offline design uses deepseek-chat, and E2OC combines outer MCTS, middle operator rotation, and inner algorithm generation and evaluation.FJSP and TSP use different offline iteration and population settings, with three assessments per problem.Source: §I.3 · p. 21, Table 7 · p. 21

I.4 Resource Consumption

  • Methods are compared at similar fitness-evaluation counts, while E2OC’s evaluation resources depend on generated algorithms and its design-loop parameters.E2OC’s prompt generator adds K × AP LLM calls; repeated validations of operator combinations add computational cost.Source: §I.4 · pp. 21–22, §I.5 · p. 22

I.5 MOEAs Parameter Settings

  • NSGA-II, NSGA-III, and MOEA/D serve as baselines, with default parameters adjusted for problem scale and complexity.All algorithms use the same initial neighborhood operators and identical reference points across benchmark instances.Source: §I.5 · p. 22

I.6 Implementation of different AHD methods

  • AHD comparisons normalize computational resources, distributing the single-heuristic budget across tasks and defining a standard design resource for multi-heuristic frameworks.The resource rules align rotation and search budgets across frameworks, so performance differences are assessed under equivalent design resources.Source: §I.6 · pp. 22–23

J.1 More Visualization Results

Across the reported comparisons, E2OC performs well on test instances and across problem scales, while its strategy search, operator interactions, and design choices are illustrated through parameter, process, and operator analyses.

J.1 More Visualization Results

  • E2OC achieves the best performance on training and testing instances, with optimization on new instances significantly better than other methods.The results contrast with multi-operator co-search methods whose performance degrades sharply on test instances; E2OC’s prior design-knowledge surface and strategic local search are reported as more effective than fixed generation distributions.Source: §J.1 · p. 23, Figure 10 · p. 26

J.2 Different Parameters

  • AP = 3 delivers the most stable and best overall performance across instances and the test set, so it is used in subsequent experiments.AP = 5 has the best training-set HV, while larger AP values increase illegal-code branches and search difficulty.Source: §J.2 · p. 26, Table 8 · p. 27

J.3 Comparison with Expert-Designed Operators

  • On Bi-TSP, standalone 2opt has the best HV among expert-designed operators, but E2OC surpasses it on TSP50 and TSP100.Manual operator permutations degrade, while adding local search to ox and swap also degrades performance; Figure 12 shows HV, IGD, and Pareto fronts for Bi-TSP.Source: §J.3 · pp. 26–27, Figure 12 · p. 28, Table 9 · p. 29

J.4 Generalization Comparison on TSPs with Different Scales

  • E2OC has the best average HV across small-scale, large-scale, and complete Bi-TSP benchmarks, including relative improvements of 30.93% on Bi-TSP150 and 22.06% on Bi-TSP200 over oropt 2opt 3opt.The 2opt operator’s performance deteriorates as scale increases; Figure 13 compares HV, IGD, and Pareto fronts across scales.Source: §J.4 · p. 29, Table 10 · p. 29, Figure 13 · p. 30

J.5 Interpretability Analysis

  • E2OC’s design space combines thoughts for operation crossover and mutation, and machine crossover and mutation, whose interactions may reinforce, compete, or be redundant.The language space is illustrated for Bi-FJSP with AP = 3 and NSGA-II as the warm-start baseline; design suggestions provide different operator focuses.Source: §J.5 · pp. 29–30, Table 11 · p. 30, Figure 14 · p. 31

J.6 Evolutionary Process Visualization

  • In the Bi-FJSP evolution example, strategy (1,1,1,1) reaches HV 181.9 at generation 12, improving on the initial strategy.The same strategy can receive different performance outcomes across generations, motivating iterative evaluation sampling.Source: §J.6 · pp. 31–32, Figure 15 · p. 32

J.7 Designed Operators

  • E2OC’s operation-sequence crossover uses fitness-aware interpolation in a continuous geometric space, unlike the positional segment exchange used by manual and EoH operators.For machine-selection crossover, E2OC adapts recombination strength to parent similarity using objective-space distance; its reported advantages are attributed to exploring and validating strategy interactions rather than greater operator complexity.Source: §J.7 · pp. 32–33, Figure 16 · p. 33

K Limitations

E2OC has shown promising performance, but its design-thought search is costly and its effectiveness depends on the quality of domain knowledge supplied by the LLM.

K Limitations

  • E2OC has achieved promising performance in MOEAs compared with existing single-heuristic design methods.Source: K Limitations · p. 33
  • Expanding the search for design thoughts substantially increases evaluation resource demands, challenging efficient algorithm iteration in practice.The limitation is framed as a practical obstacle to efficient iteration.Source: K Limitations · pp. 33–34
  • E2OC’s effectiveness is constrained by the quality of domain knowledge, which depends on the underlying LLM’s capabilities.Source: K Limitations · p. 34
Loading 2601.17899v2…