LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization
Pith reviewed 2026-06-28 18:31 UTC · model grok-4.3
The pith
CoEvo-AHD co-evolves two LLM populations to design cooperative heuristics for problems with coupled decisions.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
CoEvo-AHD is an LLM-driven dual-population co-evolutionary framework for automated heuristic design in coupled combinatorial optimization. It co-evolves two closely related operator populations, using a cooperative evaluation mechanism with pairwise scoring and synergistic joint crossover to discover complementary operator logic for joint improvement across coupled decision subspaces, enabled by a tool-invocation environment library for standardized interfaces.
What carries the argument
The dual-population co-evolution with cooperative evaluation mechanism that explicitly captures interactions between route and selection operators through pairwise scoring.
If this is right
- CoEvo-AHD automatically discovers cooperative heuristic combinations for TTP and TPP.
- It achieves competitive solution quality against traditional heuristics.
- The tool-invocation environment library enables LLM-generated operators to use standardized interfaces.
- Pairwise scoring and synergistic joint crossover help identify complementary operator logic.
Where Pith is reading between the lines
- The method could extend to other problems with multiple coupled decision components beyond TTP and TPP.
- Standardized tool libraries might improve reliability of LLM-generated code in optimization tasks more generally.
- Co-evolutionary approaches may reduce the need for problem-specific manual tuning in heuristic design.
Load-bearing premise
The cooperative evaluation mechanism and pairwise scoring can accurately capture and exploit interactions between route and selection operators in coupled decision subspaces.
What would settle it
Running CoEvo-AHD on TTP or TPP instances and finding that the evolved heuristics do not match or exceed the solution quality of established traditional heuristics would challenge the claim of effective automatic discovery.
Figures
read the original abstract
While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing methods typically generate and evolve heuristics as a single operator or search strategy, limiting their ability to model strong coupling among multiple decision substructures in problems such as the Traveling Thief Problem (TTP) and the Traveling Purchaser Problem (TPP). In this work, we propose CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework for automated heuristic design in coupled combinatorial optimization. Unlike prior methods that evolve individual heuristics in isolation, CoEvo-AHD leverages LLMs to co-evolve two closely related operator populations. A cooperative evaluation mechanism explicitly captures interactions between route and selection operators, while pairwise scoring and synergistic joint crossover help discover complementary operator logic for joint improvement across coupled decision subspaces. We further design a tool-invocation environment library that encapsulates frequently used core operations, such as local-search delta computation, into callable functions, enabling LLM-generated operators to use standardized interfaces instead of reimplementing inefficient and error-prone problem-specific loops. Experiments on TTP and TPP show that CoEvo-AHD automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework for automated heuristic design in bi-component coupled combinatorial optimization problems such as the Traveling Thief Problem (TTP) and Traveling Purchaser Problem (TPP). It co-evolves route and selection operator populations using a cooperative evaluation mechanism with pairwise scoring and synergistic joint crossover to capture interactions across coupled decision subspaces, supported by a tool-invocation environment library that provides standardized callable functions for core operations. The central claim is that this framework automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics.
Significance. If the results hold with proper validation, the work would advance automated heuristic design by extending LLM-based methods from isolated operators to explicitly coupled multi-component problems, potentially improving solution quality where decision substructures interact strongly. The tool-invocation library addresses a practical barrier in LLM-generated code by reducing reimplementation of error-prone loops.
major comments (2)
- [Abstract] Abstract: The claim that 'Experiments on TTP and TPP show that CoEvo-AHD automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics' is presented without any reported experimental details, instance sets, baselines, quantitative metrics, statistical tests, or run counts. This absence prevents assessment of the central empirical claim.
- [Framework description] Framework description: The core claim that the dual-population mechanism, cooperative evaluation, pairwise scoring, and joint crossover exploit operator interactions rests on an untested assumption. No ablation is described that replaces pairwise cooperative scoring with independent fitness evaluation for each population (while holding LLM generation and the tool library fixed) to isolate whether the coupling mechanism, rather than general evolutionary search or the LLM environment, drives any observed gains.
minor comments (1)
- [Tool-invocation environment library] The description of the tool-invocation environment library would benefit from an explicit list of the encapsulated core operations and their interfaces to support reproducibility.
Simulated Author's Rebuttal
We thank the referee for the constructive comments, which highlight opportunities to strengthen the presentation of empirical claims and the validation of the co-evolutionary mechanism. We address each major comment below and commit to revisions that directly respond to the concerns raised.
read point-by-point responses
-
Referee: [Abstract] Abstract: The claim that 'Experiments on TTP and TPP show that CoEvo-AHD automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics' is presented without any reported experimental details, instance sets, baselines, quantitative metrics, statistical tests, or run counts. This absence prevents assessment of the central empirical claim.
Authors: We agree that the abstract, as currently written, is too concise and omits the specific experimental details needed to substantiate the central claim. In the revised manuscript we will expand the abstract to explicitly reference the instance sets (standard TTP and TPP benchmark suites from the literature), the traditional heuristic baselines, the primary quantitative metrics (solution quality and runtime), the number of independent runs, and the statistical tests employed. This change will allow readers to evaluate the empirical support without needing to consult the full experimental section. revision: yes
-
Referee: [Framework description] Framework description: The core claim that the dual-population mechanism, cooperative evaluation, pairwise scoring, and joint crossover exploit operator interactions rests on an untested assumption. No ablation is described that replaces pairwise cooperative scoring with independent fitness evaluation for each population (while holding LLM generation and the tool library fixed) to isolate whether the coupling mechanism, rather than general evolutionary search or the LLM environment, drives any observed gains.
Authors: We acknowledge that the current manuscript does not contain an ablation isolating the contribution of the cooperative evaluation components. While the overall performance results are reported, an explicit comparison that replaces pairwise cooperative scoring and joint crossover with independent fitness evaluation (keeping LLM generation and the tool-invocation library unchanged) would provide clearer evidence that the coupling mechanism is responsible for the observed gains. We will design, execute, and report this ablation study in the revised version. revision: yes
Circularity Check
No circularity; empirical framework with external benchmarks
full rationale
The paper proposes an LLM-driven co-evolutionary framework (CoEvo-AHD) for heuristic design on coupled problems like TTP and TPP. Its central claims rest on experimental results showing competitive solution quality against traditional heuristics, with the method described directly via dual populations, cooperative evaluation, pairwise scoring, and a tool library. No equations, fitted parameters, or predictions are presented that reduce by construction to inputs. No self-citation chains or uniqueness theorems are invoked as load-bearing. The work is self-contained against external problem benchmarks and does not rely on renaming known results or smuggling ansatzes.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption LLMs can generate functional and effective heuristic operators for combinatorial optimization problems
- domain assumption The tool-invocation environment library provides sufficient standardized interfaces without requiring problem-specific reimplementation
invented entities (1)
-
CoEvo-AHD dual-population co-evolutionary framework
no independent evidence
Reference graph
Works this paper leans on
-
[1]
Pawan Kumar, Emilien Dupont, Francisco J
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024. doi: 10.1038/s41586-023-06924-6
-
[2]
Le, Denny Zhou, and Xinyun Chen
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V . Le, Denny Zhou, and Xinyun Chen. Large Language Models as Optimizers. InThe Twelfth International Conference on Learning Representations, 2024
2024
-
[3]
Evolution of heuristics: Towards efficient automatic algorithm design using large language model
Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. InProceedings of the 41st International Conference on Machine Learning, volume 235 ofProceedings of Machine Learning Research, pages 32201–32223. PMLR, 2024
2024
-
[4]
ReEvo: Large language models as hyper-heuristics with reflective evolution
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. ReEvo: Large language models as hyper-heuristics with reflective evolution. InAdvances in Neural Information Processing Systems, vol- ume 37, 2024. URL https://papers.nips.cc/paper_files/paper/2024/hash/ 4ced59d480e07d290b6f29fc8798f195-Abstract-...
2024
-
[5]
Mohammad Reza Bonyadi, Zbigniew Michalewicz, and Luigi Barone. The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. In 2013 IEEE Congress on Evolutionary Computation, pages 1037–1044. IEEE, 2013. doi: 10.1109/CEC.2013.6557681
-
[6]
A comprehensive benchmark set and heuristics for the traveling thief problem
Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew Michalewicz, and Frank Neumann. A comprehensive benchmark set and heuristics for the traveling thief problem. InGECCO 2014: Proceedings of the 2014 Genetic and Evolutionary Computation Conference, pages 477–484. Association for Computing Machinery, 2014. ISBN 9781450326629. doi: 10.1145/2...
-
[7]
Daniele Manerba, Renata Mansini, and Jorge Riera-Ledesma. The traveling purchaser problem and its variants.European Journal of Operational Research, 259(1):1–18, 2017. doi: 10.1016/j. ejor.2016.12.017
work page doi:10.1016/j 2017
-
[8]
EoH-S: Evolution of heuristic set using LLMs for automated heuristic design
Fei Liu, Yilu Liu, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan. EoH-S: Evolution of heuristic set using LLMs for automated heuristic design. InProceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 37090–37098, 2026. doi: 10.1609/aaai.v40i43. 41038
-
[9]
Baoyun Zhao, He Wang, and Liang Zeng. G-LNS: Generative large neighborhood search for LLM-based automatic heuristic design.arXiv preprint arXiv:2602.08253, 2026
-
[10]
Junhao Qiu, Xin Chen, Liang Ge, Liyong Lin, Zhichao Lu, and Qingfu Zhang. Evolving inter- dependent operators with large language models for multi-objective combinatorial optimization. arXiv preprint arXiv:2601.17899, 2026. 10
-
[11]
Anomalygpt: Detecting industrial anomalies using large vision-language models
Nguyen Viet Tuan Kiet, Tung Dao, Cong Dao Tran, and Huynh Thi Thanh Binh. Motif: Multi-strategy optimization via turn-based interactive framework. InProceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 37000–37008, 2026. doi: 10.1609/aaai. v40i43.41028
-
[12]
HSEvo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using LLMs
Pham Vu Tuan Dat, Long Doan, and Huynh Thi Thanh Binh. HSEvo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using LLMs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 26931–26938,
-
[13]
doi: 10.1609/aaai.v39i25.34898
-
[14]
Monte carlo tree search for comprehensive exploration in LLM-based automatic heuristic design
Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte carlo tree search for comprehensive exploration in LLM-based automatic heuristic design. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofProceedings of Machine Learning Research, pages 78338–78373. PMLR, 2025. URL https://proceedings.mlr. press/v267/zheng25o.html
2025
-
[15]
Multi-objective evolution of heuristic using large language model
Shunyu Yao, Fei Liu, Xi Lin, Zhichao Lu, Zhenkun Wang, and Qingfu Zhang. Multi-objective evolution of heuristic using large language model. InProceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 27144–27152, 2025. doi: 10.1609/aaai.v39i25.34922
-
[16]
Approximate approaches to the traveling thief problem
Hayden Faulkner, Sergey Polyakovskiy, Tom Schultz, and Markus Wagner. Approximate approaches to the traveling thief problem. InProceedings of the Genetic and Evolutionary Computation Conference, pages 385–392, 2015
2015
-
[17]
Improving efficiency of heuristics for the large scale traveling thief problem
Yi Mei, Xiaodong Li, Flora Salim, and Xin Yao. Improving efficiency of heuristics for the large scale traveling thief problem. InProceedings of the Asia-Pacific Conference on Simulated Evolution and Learning, pages 631–643. Springer, 2014
2014
-
[18]
Mohamed El Yafrani and Belaïd Ahiod. Population-based vs. single-solution heuristics for the travelling thief problem. InProceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO ’16, pages 317–324, New York, NY , USA, 2016. Association for Computing Machinery. ISBN 9781450342063. doi: 10.1145/2908812.2908847
-
[19]
Stealing items more efficiently with ants: A swarm intelligence approach to the travelling thief problem
Markus Wagner. Stealing items more efficiently with ants: A swarm intelligence approach to the travelling thief problem. InProceedings of the International Conference on Swarm Intelligence, pages 273–281. Springer, 2016
2016
-
[20]
Exact approaches for the travelling thief problem.Algorithmica, 82:2090–2111, 2020
Junhua Wu, Sergey Polyakovskiy, Markus Wagner, and Frank Neumann. Exact approaches for the travelling thief problem.Algorithmica, 82:2090–2111, 2020
2090
-
[21]
Golden, Lawrence Levy, and Robert Dahl
Bruce L. Golden, Lawrence Levy, and Robert Dahl. Two generalizations of the traveling salesman problem.Omega, 9(4):439–441, 1981
1981
-
[22]
H. L. Ong. Approximate algorithms for the traveling purchaser problem.Operations Research Letters, 1(5):201–205, 1982
1982
-
[23]
W. L. Pearn and R. C. Chien. Improved solutions for the traveling purchaser problem.Computers & Operations Research, 25(11):879–885, 1998
1998
-
[24]
Boctor, Gilbert Laporte, and Jacques Renaud
Fayez F. Boctor, Gilbert Laporte, and Jacques Renaud. Heuristics for the traveling pur- chaser problem.Computers & Operations Research, 30(4):491–504, 2003. doi: 10.1016/ S0305-0548(02)00020-5
2003
-
[25]
Dynamic tabu search strategies for the traveling purchaser problem.Annals of Operations Research, 63:253–275, 1996
Stefan V oß. Dynamic tabu search strategies for the traveling purchaser problem.Annals of Operations Research, 63:253–275, 1996
1996
-
[26]
Boris Bontoux and Dominique Feillet. Ant colony optimization for the traveling purchaser problem.Computers & Operations Research, 35(2):628–637, 2008. doi: 10.1016/j.cor.2006.03. 023
-
[27]
Goldbarg, Ligia B
Marco C. Goldbarg, Ligia B. Bagi, and Elizabeth F. G. Goldbarg. Transgenetic algorithm for the traveling purchaser problem.European Journal of Operational Research, 199(1):36–45,
-
[28]
doi: 10.1016/j.ejor.2008.10.027. 11
-
[29]
A branch-and-cut algorithm for the undirected traveling purchaser problem.Operations Research, 51(6):940–951, 2003
Gilbert Laporte, Jorge Riera-Ledesma, and Juan-José Salazar-González. A branch-and-cut algorithm for the undirected traveling purchaser problem.Operations Research, 51(6):940–951, 2003
2003
-
[30]
Haofeng Yuan, Rongping Zhu, Wanlu Yang, Shiji Song, Keyou You, Wei Fan, and C. L. Philip Chen. Deep reinforcement learning for traveling purchaser problems.IEEE Transactions on Emerging Topics in Computational Intelligence, 10(1):425–439, 2026. doi: 10.1109/TETCI. 2025.3581113
-
[31]
Tomás Kapancioglu and Raquel Bernardino. An iterated local search algorithm for the traveling purchaser problem.European Journal of Operational Research, 324(3):759–772, 2025. doi: 10.1016/j.ejor.2025.02.024
-
[32]
The traveling purchaser problem for perishable foods.Computers & Industrial Engineering, 195:110424, 2024
Ilker Kucukoglu, Pieter Vansteenwegen, and Dirk Cattrysse. The traveling purchaser problem for perishable foods.Computers & Industrial Engineering, 195:110424, 2024
2024
-
[33]
Majid Namazi, M. A. Hakim Newton, Conrad Sanderson, and Abdul Sattar. Solving travelling thief problems using coordination based methods.Journal of Heuristics, 29(4–6):487–544,
-
[34]
doi: 10.1007/s10732-023-09518-7
-
[35]
Jorge Riera-Ledesma. TPPLIB. https://jriera.webs.ull.es/TPP.htm, 2012. Bench- mark instances for the Traveling Purchaser Problem, accessed 2026-05-07
2012
-
[36]
Efficiently solving the traveling thief problem using hill climbing and simulated annealing.Information Sciences, 432:231–244, 2018
Mohamed El Yafrani and Belaïd Ahiod. Efficiently solving the traveling thief problem using hill climbing and simulated annealing.Information Sciences, 432:231–244, 2018. doi: 10.1016/ j.ins.2017.12.011. A Additional Related Work and Positioning This appendix provides additional discussion on how CoEvo-AHD differs from existing LLM-driven automated heurist...
2018
-
[38]
The logic should be different from the provided reference operators to improve population diversity
-
[39]
Implement it in Python using the required function signature:{function_signature}
-
[42]
If helper functions are needed, define them inside the main function
-
[43]
Use the exposed environment tools when available
-
[45]
Prompt for Mutation You are an algorithm optimizer
Do not provide additional explanations outside the required output. Prompt for Mutation You are an algorithm optimizer. We have a{component_type} Operatorfor{problem_type}. Problem Description:{task_description} Strategy:{advice} Current Code:{operator_code} Optional Execution Profile:{profiling_report} Task:Refine and improve this operator code according...
-
[46]
Keep the required function signature unchanged:{function_signature}
-
[52]
Prompt for Homogeneous Crossover You are an expert in heuristic optimization
Do not provide additional explanations outside the required output. Prompt for Homogeneous Crossover You are an expert in heuristic optimization. Create a new{component_type} Operatorfor{prob- lem_type}by combining ideas from two parent operators of the same component type. Problem Description:{task_description} Parent Operator 1:{parent1_code} Parent Ope...
-
[53]
The description must be inside braces{...}
First, describe the new algorithm and its main steps in one sentence. The description must be inside braces{...}
-
[54]
Implement the new operator using the required function signature:{function_signature}
-
[55]
The function must return a feasible output for the corresponding component
-
[57]
Define helper functions inside the main function if needed
-
[58]
Use exposed environment tools when available
-
[60]
Prompt for Cross-Component Joint Crossover You are an expert in heuristic optimization
Do not provide additional explanations outside the required output. Prompt for Cross-Component Joint Crossover You are an expert in heuristic optimization. We use cross-component joint crossover to co-evolve two heterogeneous operators for{problem_type}. Component A Description:{task_description_A} Component B Description:{task_description_B} Best-perform...
-
[61]
The description must be inside braces{...}
First, describe the joint design idea and its main steps in one sentence. The description must be inside braces{...}
-
[62]
Return one code block containing both generated operators
-
[63]
Use the required function signatures: {function_signature_A} and{function_signature_B}
-
[64]
Each operator must return a feasible output for its corresponding component
-
[65]
Only use standard Python libraries and NumPy
-
[66]
Define helper functions inside each main function if needed
-
[67]
Use shared information and exposed environment tools when useful
-
[68]
Wrap code in“‘python ... “‘
-
[69]
D.2 Validation Pipeline for LLM-Generated Operators CoEvo-AHD does not directly trust raw LLM-generated code
Do not provide additional explanations outside the required output. D.2 Validation Pipeline for LLM-Generated Operators CoEvo-AHD does not directly trust raw LLM-generated code. The implementation validates gener- ated code before insertion and again during per-instance evaluation. Code extraction and registration.Generated text must contain a Python code...
2000
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.