Research map / Large language models / Agents, code and math
Multi-Objective Evolution of Heuristic Using Large Language Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MEoH, an LLM-driven multi-objective evolutionary framework that searches for a set of non-dominated heuristics (optimality gap vs. running time) in one run, using a dominance-dissimilarity mechanism based on AST code similarity.
Problem
Existing LLM-based automatic heuristic design optimizes only solution quality on a target problem, ignoring criteria such as efficiency, scalability, and code complexity, and single-objective scalarization yields only one trade-off heuristic.
Approach
Model LLM-based heuristic design as multi-objective optimization and select/manage the population with a dominance-dissimilarity score that combines Pareto dominance in objective space (masking) with AST-based code dissimilarity in search space, while the LLM acts as zero-shot search operator (five EoH-style operators).
Key results
- On BPP C100 average, MEoH (Best) reached 0.706% gap in 19.97s versus EoH 0.560% in 169.81s and FunSearch 2.239% in 66.20s.
- MEoH's fast heuristic ran up to 10x faster than EoH at comparable gaps on several BPP and TSP settings.
- On BPP C500, FunSearch's gap degraded to 43.6% average, while MEoH achieved 0.411% and EoH 0.108%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multi-objective MEoH instead of EoH | online BPP, C100 · BPP C100 avg. | Time/s: 169.809 -> 19.973 | Helped |
| Use multi-objective MEoH instead of EoH | online BPP, C500 · BPP C500 avg. | Time/s: 218.279 -> 7.495 | Helped |
| Use MEoH (Best) instead of FunSearch | TSP100 · TSP100 | Time/s: 1.452 -> 1.373 | Helped |
| Use MEoH (Fast) instead of FunSearch | TSP100 · TSP100 | Time/s: 1.452 -> 0.175 | Helped |
| Use MEoH (Best) instead of FunSearch | TSP1000 · TSP1000 | Gap: 2.344% -> 4.208% | Hurt |
| Use MEoH (Best) instead of FunSearch | TSP1000 · TSP1000 | Time/s: 161.124 -> 26.844 | Helped |
| Use MEoH instead of FunSearch | TSPLIB instances up to 200 nodes · TSPLIB (0-200) avg. | Gap: 0.050% -> 0.018% | Helped |
| Use MEoH instead of FunSearch | TSPLIB instances up to 200 nodes · TSPLIB (0-200) avg. | Time/s: 3.418 -> 2.354 | Helped |
| Use MEoH instead of EoH | TSPLIB instances with 201-1002 nodes · TSPLIB (201-1002) avg. | Gap: 1.376% -> 1.50% | Hurt |
| Use MEoH instead of EoH | TSPLIB instances with 201-1002 nodes · TSPLIB (201-1002) avg. | Time/s: 1515.992 -> 355.754 | Helped |
| Use MEoH rather than EoH's single-objective search | BPP and TSP heuristic evolution · BPP and TSP | Hypervolume (HV) | Helped |
| Use MEoH rather than EoH's single-objective search | BPP and TSP heuristic evolution · BPP and TSP | IGD | Helped |
Surprising findings
- FunSearch heuristics degrade drastically on out-of-distribution bin capacity (C500), while EoH and MEoH remain robust.
- MEoH's fastest TSP heuristic leaves edge distances unchanged, deviating from its textual description.
Limitations
- Evaluated mainly with two objectives; many-objective cases not studied
- Only two combinatorial problems (online BPP and TSP GLS perturbation) demonstrated
- Some LLM-generated heuristics are illegal code, leaving population gaps early on
Experimental setup
Datasets: Weibull bin packing instances randomly generated TSP100 instances TSPLIB
Benchmarks: online BPP Weibull instances (5k, 10k, 100k; capacity 100 and 500) randomly generated TSP (100, 500, 1000 nodes) TSPLIB instances up to 1002 nodes
Metrics: optimality gap running time hypervolume IGD
Baselines: FunSearch EoH NSGA-II MOEA/D
Builds on: EoH FunSearch NSGA-II MOEA/D
Closest papers by meaning
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (ICML 2024 · similarity 0.92)
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.91)
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.88)
- Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design (ICML 2025 · similarity 0.88)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.87)
- Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.