ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
Authors: Haoran Ye
Jiarui Wang
Zhiguang Cao
Federico Berto
Chuanbo Hua
Haeyeon Kim
Jinkyoo Park
Guojie Song
Venue: NeurIPS 2024 poster (2024)
Keywords: combinatorial optimization
hyper-heuristic
heuristic
neural combinatorial optimization
large language model
evolutionary algorithm
Primary area: optimization
TL;DR: We use large language models to design heuristics for combinatorial optimization automatically.

Abstract: The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design. The long-standing endeavor of design automation has gained new momentum with the rise of large language models (LLMs). This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMs for heuristic generation, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM reflections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.

ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
Haoran Ye', Jiarui Wang", Zhiguang Cao², Federico Berto*, Chuanbo Hua", Haeyeon Kim", Jinkyoo Park*, Guojie Song!
!National Key Laboratory of General Artificial Intelligence,
School of Intelligence Science and Technology. Peking University
"Southeast University 'Singapore Management University KAIST SPKU-Wuhan Institute for Artificial Intelligence AI4CO!
hrye@stu. pku. edu. en, jiarui_wang@s edu. en, zgcao@smu edu.sg
(fberto, cbhua, haeyeonkim, Jinkyoo.parkk)aa.. parraaaaaiiss ac.kr, gjsongopku edu. cn
Project Website: https://aifco.giihbbbioeoer
Abstract
The omnipresence of NP-hard combinatorial optimization problems (COPs) com- pels domain experts to engage in trial-and-eme heuristic design. The long-standing endeavor design automation has gained new momentum with the rise large lan- guage models (LLMs).. This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMS for heuristic gen- eration, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM flections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of- of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.
1 Introduction
NP-hard combinatorial optimization problems (COPs) pervade numerous real-world systems, each characterized by distinct constraints and objectives. The intrinsic complexity and heterogeneity of these problems compel domain experts to laboriously develop heuristics for their approximate solutions [23]. Automation heuristic designs represents longstanding pursuit.
Classic Heapi--tessssicss (HHs) automate heuristic design by searching for the best heuristic (combi- nation) from a set of heuristics or heuristic components [64]. Despite decades of development, HHs are limited by heuristic spaces predefined by human experts [64]. The rise of large language models (LLMs)) opens up new possibilities for HHs. This paper introduces the general concept of Language Hlyper-eerrstte (IHH) advance beyond preliminary attempts in individual COP settings [68, 46]. LHH constitutes an emerging variant of HH that utilizes LLMs for heuristic generations. features minimal human intervention and open-ended heuristic spaces, showing promise to comprehensively shift the HH research paradigm.
Correspondence to: Guojic Song <gjsong www.ppp..ccc.ooooo edd. I Work made with contributions from the AI4CO open research community.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Pure LHH (e.g., LLM generations alone) is sample-inetne inefefiifff and exhibits limited inference capability for black-box COPs. This work elicits the power of LHH with Reflective Evolution (ReEvo). ReEvo couples evolutionary search for efficiently exploring heuristic spaces, with self-reflections to boost the reasoning capabilities of I.LMs. It emulates human experts by reflecting on the relative performance of two heuristics and gathering insights across iterations. This reflection approach is analogous to interpreting genetic cues and providing "verbal gradient" within search spaces. We introduce fitness landscape analysis and black-box prompting for reliable evaluation of LHHs. The dual-level reflections are shown to enhance heuristic search and induce verbal inference for black-box COPs, enabling ReEvo to outperform prior state-of-tue the-ar art (SOTA) LHH [47].
We introduce novel applications of LHHS and yield SOTA solvers with ReEvo: (1) We evolve penalty heuristics for Guided Local Search (GLS). which outperforms SOTA learning- -bsen [52, 24, 75] and knowledge-hand basee [1] (G)LS solvers. (2) We enhance Ant Colony Optimization (ACO) by evolving its heuristic measures, surpassing both neural-enhancee heuristics [94] and expert-designed heuristics [71, 6, 72, 17, 391. (3) We refine the genetic algorithm (GA) for Electronic Design Automation (EDA) by evolving genetic operators, outperforming expert-designed GA [63] and the SOTA neural solver [31] for the Decap Placement Problem (DPP). (4) Compared to a classic HH [15], ReEvo
generates superior constructive heuristics for the Traveling Salesman Problem (TSP). (5) We enhance
the generalization of SOTA neural combinatorial optimization (NCO) solvers [37, 51] by evolving heuristics for attention reshaping. For example, we improve the optimality gap of POMO [37] from 52% to 29% and LEHD [51] from 3.2% to 3.0% on TSP1000, with negligible additional time overhead and no need for tuning neural models.
We summarize our contributions as follows. (1) We propose the concept of Language Hyper- Heuristics (LHHs), which bridges emerging attempts using LLMMs for heuristic generation with a methodological group that enjoys decades of development. (2) We present Reflective Evolution (ReBvo), coupling evolutionary computation with humanoid reflections to elicit the power of LHHs. We introduce fitness landscape analysis and black-box prompting for reliable LHH evaluations, where ReEvo achieves SOTA sample efficiency. (3) We introduce novel applications of LHHs and present SOTA COP solvers with ReEvo, across five heterogeneous algorithmic types and six different COPs.
2 Related work
Traditional Hyper-Heuristies Traditional HHs select the best performing heuristic from a pre- defined set [13] or generate new heuristics through the combination of simpler heuristic compo- nents [15, 104]. HHs offer higher level of generality in solving various optimization problems [109, 96, 19, 44, 103, 58], but are limited by the heuristic space predefined by human experts.
Neural Combinatorial Optimization. Recent advances of NCO show promise in learning end- to-end solutions for COPs [2, 93, 3]. NCO can be regarded as variant of HH, wherein neural architectures and solution pipelines define a heuristic space, and training algorithms search within it. A well-trained neural network (NN), under certain solution pipelines, represents distinct heuristic. From this perspective, recent advancements in NCO HHs have led to better-aligned neural architectures [28, 51, 34, 73] and advanced solution pipelines [32, 52, 42, 89, 95, 12, 5] to define effective heuristic spaces, and improved training algorithms to efficiently explore heuristic spaces [33, 27, 14, 76, 18, 90, 79, 35], while targeting increasingly broader applications [9, 107, 54, 77]. In this work, we show that ReEvo-genen -eEvo-generated heuristics can outperform or enhance NCO methods.
LLMs for code generation and optimization. The rise of L.MMs introduces new prospects for diverse fields [88, 82, 105, 25, 50, 99]. Among others, code generation capabilities of LLMs are utilized for code debugging [10, 49], enhancing code performance [55], solving algorithmic competition challenges [41, 70], robotics [38, 43, 81], and general task solving [92, 102]. Interleaving
LLM generations with evaluations [74] yields powerful methods for prompt optimization [108, 83, 20], reinforcement learning (RL) reward design [53], algorithmic (self- jimproeeent [98, 48, 45], neural architecture search [8]. and general solution optimization [91, 4, 80], with many under evolutionary frameworks [57, 87, 21, 7, 40]. Most related to ReEvo, concurrent efforts by Liu et al. [47] and Hamera-Paredes, et al. [68] leverage L.MSs to develop heuristics for COPs. We go beyond and propose generic LHH for COPs, along with better sample efficiency, broader applications, more reliable evaluations, and improved heuristics. In addition, ReEvo contributes to smoother fitness landscape,

---

showing the potential to enhance other tasks involving LLMs for optimization. We present further discussions in Appendix A.
Self-reflections of LLMs. Shinn al. [70] propose to reinforce language agents via linguistic feedback, which is subsequently harnessed for various tasks [56, 84]. While Shinn et al. [70] leverage binary rewards indicating passing or failing test cases in programming. ReEvo extends the scope of verbal RI. feedback to comparative analysis of two heuristics, analogous to verbal gradient information [66] within heuristic spaces. Also, ReEvo incorporates reflection within an evolutionary framework, presenting a novel and powerful integration.
Language Hyper- for Combinatorial Optimization
HHs explore a search space of heuristic configurations to select or generate effective heuristies, indirectly optimizing the underlying COP. This dual-level framework is formally defined follows.
Definition 3.1 (lyper--euristic)) For COP with solution space S and objective function f S - R, a Hyper-Heuristie (HH) searches for the optimal heuristic h in heuristic space such that a meta-objective function F H R is minimized, i.e., h" argminnen F(h).
Depending on how the heuristic space H is defined, traditional HHs can be categorized into selection and generation HHs, both entailing manually defined heuristic primitives. Here, we introduce a novel variant of HHs, Language LHHs dispense with the need for predefined H, and instead leverage LLMs to explore an open-ended heuristic space. We recursively define LHHS as follows.
(LHH), wherein heuristics in H are generated by LLMs.
Definition 3.2 (Language Syper-Heuristie A Language Hyper-Heuristic (LHH) is an HH variant where heuristics H are generated by LLMs.
In this work, we define the meta-objective function F as the expected performance of a heuristic for certain COP. It is estimated by the average performance on dataset of problem instances.
Language Hyper-Heuristic with ReEvo
LHH takes COP specifications as input and outputs the best inductive heuristic found for this COP. Vanilla LHH can be repeated LLM generations to randomly search the heuristic space, which is sample-inefficient and lacks reasoning capabilities for complex and black-box problems (see $ 6). Therefore, propose Reflective Evolution (ReEvo) to interpret genetic cues of evolutionary search and unleash the power of LHHs.
ReEvo is schematically illustrated in Fig. 1. Under an evolutionary framework. LLMs assume two roles: generator L.M for generating individuals and reflector I.LM for guiding the generation with reflections. ReEvo, as an LHH, features a distinct individual encoding, where each individual is the code snippet of heuristic. Its evolution begins with population initialization, followed by five iterative steps: selection, short-term reflection, crossover, long-term reflection, and elitist mutation. evaluate the meta-objective all heuristics, both after crossover and mutation. Our prompts are gathered in Appendix B.
Individual encoding. ReEvo optimizes toward best-performing heuristics via evolutionary process, specifically a Genetic Programming (GP). diverges from traditional GPs in that (I) individuals are code snippets generated by LLMs, and (2) individuals not constrained by any predefined encoding format, except for adhering to specified function signature.
Population initialization. ReEvo initializes a heuristic population by prompting the generator LLM with a task specification. A task specification contains COP descriptions (if available). heuristic designation, and heuristic functionality. Optionally, including seed heuristics, either trivial or expertly crafted improve upon, can provide in-context examples that encourage valid heuristic generation and bias the search toward more promising directions.
A ReEvo iteration contains the following five sequential steps.
3

---

Parformance indicator
Long-term Rellection
Long-term Rellection
Long-term Rellection
A population
population hnuuristies
population
heuristios
heuratics
Short-term Reflection
Long-term Reflection
Relative Farformance
Short-torm Reflections
Previous Long
Reflection
Long
Reflection
Reflector LLM
RefLoctor
Evaluste
Tesk
Offspring Heuristics
Generator LLM
</>
Gereration Instructions
long-term Reflection
</>
</>
</>>
</s
</>
</>
Generator
Filte
</>s
Mutsted Heuristion
Selection
(a) BeEvo pipeline. Top: BeEvo evolves population of heuristies. Insights and knowledge verbalized as long-terun reflections and accumulated throughout iterations. Bottom: A ReEvo iteration contains five sequential steps: selection, short-term reflection, crossover, long-term reflection, and clitist mutation.
Worse Parent Hoaale
F= 24.18
Elite Houristic
6.36
rputserngg
A. Hauristis for
epti Ton
rp-eoplt.01 reture FANCEE
40%
Hnurlettc
Butter Parent Hourstic
10.71
proetis scores wwweclesttttiine ater attre)
hoar www.attstttttttttooo (ounderrep) reueserroys
artortty snrmaliped_atte
Long torm
aapratattasaaaa couasalattt... areerat spoilenn returs beariersr_satpur
BeToocur LLM
tealyytie exphastringg statistical distric (ooncaess
kertssss and rubool statistice Hadiaay, H80) for olye
Short-tom Refeeciion
Heuritic
Reflectur
The butter performance inverse acoring actted Lever attribute valana andseace nere prenisirg expea. sajes
heuristicafodge attr (ountarcay) to mo-ndrrray
Lan 30-1
avataal anderstanding
mediarual wwwaddtntedgeaate
Offipring Heursbic
6.42
aad wiz
def heurssticnreppe
casu lan
LLM
Surtaste
Gemendaaa LMM
(asunaeledge atTr) RE- te-ntrcedge. aetr) speclies marmallese LEEsE atirabites
motaet,nall tranctormnt attre toueca
awraaalir faliennca asueg mp.ggr((aattssas)
returs prartee ceoree
retum trasffored atrre, flattett
Crossover Shor-term Reflaction
Long-term Reflection
(b) Examples of reflections for black-bos TSP Heuristics are designed for Ant Colony Optimization (see 5.2). Left: Given pair parent heuristics, ReEvo concetlly infers TSP objective and generates better offspring accordingly. Right Given clite bouristic and accumulated long-term reflections, BeEvo incorporates the suggested statistics and yields a better mutated heuristic.
Figure 1: An illustration of ReEvo.
Selection. ReEvo selects parent pairs from successfully executed heuristics at random, while avoiding pairing heuristics with identical meta-objective value F.
Short-term reflection. For each pair of heuristic parents, the reflector LLM reflects upon their relative performance and gives hints accordingly for improved design. Unlike prior work [70], ReEvo integrates the reflections into evolutionary search and reflects by performing comparative analyses. Our proposed approach is analogous to interpreting genetic cues and providing verbal gradients within search spaces, which leads to smoother fitness landscapes and better search results (see 6.1).
Crossover. ReEvo prompts the generator LLM to generate offspring heuristic, given task spec- ifications, a pair of parent heuristics, explicit indications of their relative performance, short-term reflections over the pair, and generation instructions.

---

Long-term reflection. ReEvo accumulates expertise in improving heuristics via long-term reflec- tions. The reflector LLM, given previous long-term reflections and newly gained short-term ones, summarizes them and gives hints for improved heuristic design.
Elitist mutation. ReEvo employs an elitist mutation approach. Based on long-term reflections, the generator LLM samples multiple heuristics to improve the current best one. A mutation prompt consists of task specifications, the elite heuristic, long-term reflections, and generation instructions.
Viewing ReEvo from the perspective of an LLM agentic architecture [88], short-term reflections interpret the environmental feedback from each round interaction. Long-term reflections distill accumulated experiences and knowledge, enabling them to be loaded into the inference context without causing memory blowups.
Heuristic generation with ReEvo
This section presents novel applications of LHH across heterogeneous algorithmic types and diverse COPs. With ReEvo, we yield state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers.
Hyperparameters of ReEvo and detailed experimental setup are given in Appendix C. We apply ReEvo to different algorithmic types across six diverse COPs representative of different areas: Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), and Orienteering Problem (OP) for routing problems; Multiple Knapsack Problem (MKP) for subset problems; Bin Packing Problem (BPP) for grouping problems; and Decap Placement Problem (DPP) for electronic design automation (EDA) problems. Details of the benchmark COPs are given in Appendix D. The best. BeEvo-generated heuristics are collected in Appendix E.
5.1 Penalty heuristics for Guided Local Search
We evolve penalty heuristics for Guided Local Search (GLS) [1]. GLS interleaves local search with solution perturbation. The perturbation is guided by the penalty heuristics to maximize its utility. ReEvo searches for the penalty heuristic that leads to the best GLS performance.
We implement the best heuristic generated by ReEvo within KGLS [T] and refer to such coupling as KGLS-ReEvo. In Table 1, we compare KGLS-ReEvo with the original KGLS, other GLS variants [24, 75, 47], and SOTA NCO method that learns to improve a solution [52]. The results show that single heuristic for
ReEvo can improve KGLS and outperform SOTA baselines. In addition, TSP20 to 200, while NCO baselines require training models specific to each problem size.
Table 1: Evaluation results of different local search (LS) variants. We report optimality gaps and per-instance
exccution time.
Method
Type
Opt. gap (%)
TSP20
Time
Opt. (%)
TSPS0
Time
Opt. gap (%)
TSP100
Time
TSP200
(%)
Time (s)
NeuOpe* [52]
LS+RI.
0.000
0.124
0,000
1.32
0.027
2.67
0.403
4.81
GNNGLS [24]
GLS+SL
0.000
0.116
0.052
3,83
0.706
6.78
3.522
9.92
NeumlGLSS [75]
10.01
0.470
BoHl [47]
GLS+LHH
0.000
0.563
0.000
1.90
0.025
5.87
0.338
17.52
KGLS1
0.002
1.55
0.284
KGLS-ReBvot
GLS+LHH
0,000
0.001
0.000
0.03
0.000
1,55
0.216
2.52
*; All instances are solved in one batch. D2A=1; T=500, 4000, 5000, and 5000 for 4 problem sizes, respactively. The results drawn from the original literature, They bused GLS implementationn.
5.2 Heuristic measures for Ant Colony Optimization
Solutions to COPs can be stochastically sampled, with heuristic measures indicating the promise of solution components and biasing the sampling. Ant Colony Optimization (ACO), which interleaves stochastic solution sampling with pheromone update, builds on this idea. We generate such heuristic measures for five different COPs: TSP, CVRP, OP, MKP, and BPP.
Under the ACO framework, we evaluate the best ReEvo-generated heuristics against the expert- designed ones and neural heuristics specifically leamed for ACO [94]. The evolution curves displayed
5

---

TEP3N
IS7A00
23--
4011
700
2011
ASB
3/B
300
CUSPS
CYRTUO
CVEPS0
CUSPSN
CYRPTOD
800
6.02
200
400
3/0
630
640
182
142
Publos
Felmika dk
Fal
81953)
BIPOE
X/0
200
DegglCC
DegiCC
Figure 2: Comparative evaluations of ACO using expert-designed heuristics [71, 6, 72, 17, 391, neural heuristies [94], and ReEvo heuristics. For each COP, the same neural hcuristic the ReEvo heuristic applicd across all problem sizes; both hcuristics are trained exclusively on smallest problem size among the five. Left: Relative performance improvement of DeepACO and ReEvo over human baselines w.r.t problem sizes. Right: ACO evolution curves, plotting the all-time best objective value w.r.t. the number of solution evaluations. The curves averaged three in which only small variances observed (e.g., 0.01 for TSP50).
in Fig. 2 verify the consistent superiority of ReEvo across COPs and problem sizes. Notably, on 3 out of 5 COPs, ReEvo outperforms DeepACO [94] even when the latter overfits the test problem size (TSP50, OP50, and MKP100). We observe that most ReEvo-generate heuristics show consistent performance across problem sizes and distributions. Hence, their advantages grow as the distributional shift increases for neural heuristics.
5.3 Genetic operators for Electronic Design Automation
Expert-designed GAs are widely adopted in EDA [69, 97, 11, 26). Besides directly solving EDA problems, GA-generated solutions can be used to train amortized neural solvers [31]. Here, show that ReEvo can improve the expert-designed GAs and outperform DevFormer [31], the SOTA solver for the DPP problem. We sequentially evolve with ReEvo the crossover and mutation operators for the GA expert-designed by Park et al. [63]. Fig. compares online and offline learned methods, DevFormer, the original expert-designed GA, and the GA with leEvo-generated operators, showing that the ReEvo-designed GA outperforms previous methods and, importantly, both the expert-designed GA and DevFormer.
5.4 Constructive heuristics for the Traveling Salesman Problem
Heuristics be used for deterministic solution construction by sequentially assigning values each decision variable. We evaluate the constructive heuristic for TSP generated by ReEvo on real-world benchmark instances from TSPLIB [67] in Table ReEvo can generate better heuristics than GHPP [15], a classic HH based on GP.
5.5 Attention reshaping for Neural Combinatorial Optimization
Autoregressive NCO solvers suffer from limited scaling-up generalization [29], partially due the dispersion of attention scores [85]. Wang al. [85] design distance-aware heuristic to reshape

---

Table 2: Comparisons of constructive heuristics designed by human, GHPP [15], and ReEvo. We report the average optimality gap of each instance, where the baseline results drawn from [1.5] and the results of ReEvo are averaged over runs with different starting nodes.
Instance
Nearest Neighbour
GHPP [15]
ReEvo
Instance
Nearest Neighbour
GHPP [15]
ReEvo
ts225
16.8
7.7
6.6
ch130
25.7
14.8
9.4
rat99
21.8
14.1
12.4
pr299
31.4
18.2
111889
23.7
21.1
fI417
32.4
22.7
19.2
u1817
16.6
d657
29.7
16.3
16.0
d1655
23.9
18.7
17.5
kroA150
26.1
15.6
11.6
bicr127
23.3
15.6
10.8
fi1577
25.0
17.6
12.1
lin3 18
25.8
14.3
16.6
u724
28.5
15.5
16.9
eilS1
32.0
10.2
pr264
17.9
24.0
16.8
15.6
13,4
pr226
24.6
kmB8100
26.3
12.2
pr439
27.4
21.4
19.3
kroC100
25.8
16.2
15.9
Avg. opt. gap
25.4
16.7
14.6
attention scores, which improves generalization of NCO solvers without additional training. However, the expert-designed attention-reshaping can be suboptimal and does not generalize across neural models or problem distributions.
Here we show that ReEvo can automatically and efficiently tailor attention reshaping for specific neural models and problem distributions of interest. We apply attention reshaping designed by experts [85] and ReEvo to two distinct model architectures: POMO with heavy encoder and light decoder [37], and LEHD with light encoder and heavy decoder [51]. On TSP and CVRP, Table compares the original NCO solvers [37, 51], those with expert-designed attention reshaping [85], and those with ReEvo-designet attention reshaping. The results reveal that the ReEvo -eeerreedd heuristics can improve the original models and outperform their expert-designed counterparts. Note that implementing neEvo-generated attention reshaping takes negligible additional time; e.g., solving CVRP1000 with LEHD takes 50.0 seconds with reshaping, compared to 49.8 seconds without.
Evaluating ReEvo
6.1 Fitness landscape analysis
The fitness landscape of searching algorithm depicts the structure and characteristics of its search space F' H + R [59]. This understanding is essential for designing effective HHs. Here introduce this technique to LHHs and evaluate the impact of reflections on the fitness landscape.
Traditionally, the neighborhood of solution is defined set of solutions that can be reached after a single move certain heuristic. However, LHHs feature a probabilistic nature and ended search space, and redefine its neighborhood follows.
Definition 6.1 (Neighborhood). Let LLM denote LHH move, specific prompt, and he the current heuristic. Given LLM and æ, the neighborhood of he is defined as a set N, where each
Method
of shots
Obj.
Puinter-PG [30]
10,000
9.66 0,05
138
AM-PG [60]
10,000
9.63
CNN-DQN [61]
10,000
9.79
12.-
CNN-DDON [100]
10,000
9,63 0.150
Pointer-CRL [30]
Zero Shot
9.59 1oez
AM-CRI. [62]
7ero Shot
9.56 :: c.mi
DevFormer-CSH [31]
Zero Shot
12.88 01e
155
GA
GA-expert [63]
400
12.41 1.00
GA-ReEvo (ours)
400
12.98 0.08
3.5
5.
2.2
10:3
12.5
15.8
175
Ikeosbuss
Comparison DevFormer [31], the expert-designed GA [63] our ReEvo-designed GA on DPP. The evolution curves plot the best objective value over generations; the horizontal line indicates the reward of end-to-end solutions generated by DevFormer. Right: Evaluation results of DPP solvers. We report the number of solution generations and the average objective value of 100 test problems.
Figure 3:

---

Table 3: Evaluation results for NCO solvers with and without different attention-reshaping heuristics.
200
500
1000
Method
Obj-
Opt. gap (9)
Ohj.
Opt. gap (%)
Ohj.
Opt. gap (%)
POMO [37]
11.16
4.40
22.21
34.43
35.19
52.11
POMO + DAR [85]
11.12
3.98
21.63
30.95
33.32
44,05
TSP
POMO + ReEvo [75]
11.12
4.02
20.54
24.32
29.86
29.08
LEHD [51]
10.79
0.87
16.78
1.55
23.87
3.17
LEHD DAR [85]
10.79
0.89
79
1.62
23.87
3.19
ReEvo
10.77
0.74
16.78
23.82
POMO [37]
22.39
10.93
33.76
145.40
289,48
POMO DAR [85]
22.36
10.78
50.23
34.05
144.24
286.37
CVRP
POMO ReEvo
22.30
10.48
47.10
25.70
118.80
218.22
LEHD [51]
20.92
3.68
38.61
3.03
39.12
4.79
LEHD DAR [85]
21.13
4.67
39.16
4.49
39.70
6.35
LEHD ReEvo
20.85
3,30
38.57
2.94
39.11
4.76
element E N represents a heuristic that LLM can mutate he into, in response to a:
Nhhh)) {h LLM (h/)e, E)-
(1)
Here, (h 2) denotes the probability of generating h after prompting with he and x, and & is small threshold value. In practice, the neighborhood can be approximated by sampling from the distribution (LM(-]he, x) for large number of times.
We extend the concept of autocorrelation to LHHS under our definition of neighborhood. Autocorre- lation reflects the ruggedness of a landscape, indicating the difficulty of a COP [59, 22].
Definition 6.2 (Autocorrelation). Autocorrelation measures the correlation structure of a fitness landscape. It is derived from the autocorrelation function of time series of fitness values, which are generated by a random walk on the landscape via neighboring points:
ΣX- (J= - D(++ii
where f is the mean fitness of the points visited, T is the size of the random walk, and is the time lag between points in the walk.
Based on the autocorrelation function, correlation length is defined below [86].
Definition 6.3 (Correlation Length). Given an autocorrelation function r, the correlation length / is formulated as / = 1 In ([rrl) for F O. It reflects the ruggedness of landscape, and smaller values indicate a more rugged landscape.
To perform autocorrelation analysis for ReEvo, we conduct random walks based on the neighborhood established with our crossover prompt either with or without short-term reflections. practice, we set the population size to I and skip invalid heuristies; the selection always picks the current and last heuristics for short-term reflection and crossover, and we do not implement mutation. Table 4 presents the correlation length and the av- erage objective value of the random walks, where
Table 4: Autocorrelation analysis of ReEvo.
we generate ACO heuristics for TSP50. The cor-
relation length is averaged over 3 runs each with 40 random walk steps, while the objective value averaged over all x 40 heuristics. The results verify that implementing reflection leads to less rugged landscape and better search results. As discussed in $ reflections can function as verbal gradients that lead to better neighborhood structures.
Correlation length
Objective +
w/o reflection w/ reflection
0.28 + 0.07
12.08 + 7.15
1.28 + 0.62
6.53 + 0.60
6.2 Ablation studies
In this section, we investigate the effects the proposed components ReEvo with both white and black-box prompting.

---

Black-box prompting. do not reveal any information related to the COPs and prompt LHHs in general forms (e.g., edge_att? attr in place of distance matrix). Black-box settings allow reliable evaluations of LHHss in designing effective heuristics for novel and complex problems, rather than merely retrieving code tailored for prominent COPs from their parameterized knowledge.
We evaluate sampling LLM generations without evolution (LLM) and ReEvo without long-term re- flections, short-term reflections, crossover, or mu- tation on generating ACO heuristics for TSP100. Table shows that ReEvo enhances sample effi- ciency, and all its components positively contribute to its performance, both in white-box and black-box prompting.
Table 5: Ablation study of ReEvo components with both white and black-box prompting.
Method
White box
Black hox
LLM
8.64 2.13
9.74 = 0.5
long long-term term reflections
8.61 1
w/o short-term reflections
8.46 6-0
9.05
w/o crossover
8.45 e.2
9.47 = 1.40
mutation
8.83 0.09
9.34 0.96
6.3 Comparative evaluations
ReEvo
8.40 0.0
8.96 0.82
This section compares ReEvo with EoH [47], a recent SOTA LHH that more sample-efficient than FunSearch [68]. We adhere to the original code and (hyper)parameters of EoH. Our experiments apply both LHHs to generate ACO heuristics for TSP, CVRP, OP, MKP, and BPP, using black-bos box prompting and three LLMs: GPT-3.5 Turbo, GPT-4 Turbo, and Llama 3 (70B).
Fig. compares EoH and ReEvo, and shows that ReEvo demonstrates superior sample efficiency. Besides the better neighborhood structure ($ 6.1), reflections facilitate explicit verbal inference of underlying black-box COP structures; we depict an example in Fig. 1 (b). The enhanced sample efficiency and inference capabilities of ReEvo particularly useful for complex real-world problems, where the objective function is usually black-box and expensive to evaluate.
evara:
MKM10
4
LHH evolution results using different LLMs.
115/50
CVKPS30
O150
MIC1100
270
20
See
10
10
300
20 occectaations
ovcilsationss
#ol LrsiLIi
SeTevalaaionn
(b) LHH evolution curves using GPT-3.5 Turbo.
Figure 4: Comparisons between EoH [47] and ReEvo on five COPs with black-box prompting and using different LLMs. We perform three runs for each setting.
Discussions and limitations
When to use ReEvo as LHH. Our experiments limit the number of heuristic evaluations to 100 shots and the results do not necessarily scale up. ReEvo designed for scenarios where sample efficiency is erucial, such real-world applications where heuristic evaluation can be costly. Allowing a large number of heuristic evaluations could obscure the impact of reflection or other prompting techniques, reported by Zhang et al. [101].
When to use ReEvo as an (alternative to) NCOMIAACO method. LHH can categorized NCO/MLACO method. However, to facilitate discussion, we differentiate LHHs from

---

"traditional" NCO methods that usually train NN parameteriized heuristics via parameter adjustment. In $ 5. we demonstrate that ReEvo can either outperform or enhance NCO methods. Below, we explore the complementary nature of LHH and NCO methods.
Rule-based v.s. NN-parameterized policies. LHHs generate interpretable and rulc-based heuris- ties (code snippets), while NCO generates black-box NN-paaameteriiedd policies. Interpretable heuristics offer insights for human designers and can be more reliable in practice when faced with dynamic environments, limited data, distributional shifts, or adversarial attacks. However, they may not be as expressive as neural networks and may underfit in complex environments.
Evolution and training. LHHS require only less than 100 heuristic evaluations and about 5 minutes to evolve a strong heuristic, while many NCO methods usually require millions of samples and days of training. LHHS are more practical when solution evaluation is expensive.
Inference. LHHs generate heuristics that are less demanding in terms computational resources, they do not require GPU during deployment. NCO methods require GPU for training and deployment, but they can also leverage the parallelism GPU to potentially speed up inference.
Engineering efforts and inductive biases. LHHs only need some text-based (and even black- box) explanations to guide the search. NCO requires the development of NN architectures, hyperparameters, and training strategies, where informed inductive biases and manual tuning are crucial to guarantee performance.
The choice of LLMs for ReEvo. Reflection more effective when using capable LLMs, such as GPT-3.5 Turbo and its successors, discussed by Shinn et al. [70]. Currently, many open-source LLMs are not capable enough to guarantee statistically significant improvement of reflections [101]. However, as LLM capabilities improve, only expect this paradigm to get better over time [70].
One can refer to [101] for extended evaluations based on more LLMs and problem settings.
Benchmarking LHHS based heuristic evaluations. We argue that benchmarking LHHs should prioritize the number of heuristic evaluations rather than LLM query budgets [101] due to the following reasons.
Prioritizing scenarios where heuristic evaluations are costly leads to meaningful comparisons between LHHs. The performance of different LHH methods becomes nearly indistinguishable when a large number of heuristic evaluations are allowed [101].
The overhead of LLM queries is negligible compared to real-world heuristic evaluations. LLM inference- whethhr via local models commercial APIs is highly cost-effective nowadays, with expenses averaging around $0.0003 per call in ReEvo using GPT-3.5-turbo and response times of under second on average for asynchronous API calls batched inference. These costs are negligible compared to real-world heuristic evaluations, which, taking the toy EDA problem in this paper as example, exceeds 20 minutes per evaluation.
Benchmarking LHHs based on LLM inference costs presents additional challenges. Costs and processing time are driven by token usage rather than the number of queries, complicating the benchmarking process. For instance, EoH [47] requires heuristic descriptions before code generation, resulting in higher token usage. In contrast, although ReEvo involves more queries for reflections, it is more token-efficient when generating heuristics.
8 Conclusion
This paper presents Language Hyper-Heuristics (LHHs), a rising variant of HHs, alongside Reflective Evolution (ReEvo), an evolutionary framework elicit the power of LHHs. Applying ReEvo across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, yield state-of-the-arr and competitive meta-heuristies, evolutionary algorithms. heuristics, and neural solvers. Comparing against SOTA LHH [47]. ReEvo demonstrates superior sample efficiency. The development of LHHs is still at its emerging stage. is promising to explore their broader applications, better dual-level optimization architectures, and thcoretical foundations. We also expect ReEvo to enrich the landscape of evolutionary computation, by showing that genetic cues can be interpreted and verbalized using L.MSs.
10

---

Acknowledgments and disclosure of funding
We are very grateful to Yuan Jiang, Yining Ma, Yifan Yang, AI4CO community, anonymous re- viewers, and the area chair for valuable discussions and feedback. This work supported by the National Natural Science Foundation of China (Grant No. 62276006); Wuhan East Lake High-Tech Development Zone National Comprchensive Experimental Base for Governance of Intelligent Soci- ety; the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2022-033 Korea government (MSIT) (No. RS-2024-0041 10000020));));;; the Institute of Information & Communica- tions Technology Planning & Evaluation (InTP)-Inovvative Human Resource Development for Local Intellectualization program grant funded by the Korea government (MSIT) (IITP-204-RS-200) 00436765).
the National Research Foundation of Korea (NRF) grant funded by the
References
[1] F. Aroll and K. Sörensen. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32-46, 2019.
[2] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
[3] F. Berto, C. Hua, J. Park, M. Kim, H. Kim, J. Son, H. Kim, J. Kim, and J. Park. RIACO: unified reinforcement learning for combinatorial optimization library. In NeurIPS 2023 Workshop: New Frontiers in Graph Learming, 2023.
[4] E. Brooks, L, A. Walls, R. Lewis, and S. Singh. Large language models can implement policy iteration. In seventh Conference Neural Information Processing Systems, 2023,
[5] F. Bu, H. Jo, S. Y. Lee, S. Ahn, and K. Shin. Tackling prevalent conditions in unsupervised combinatorial optimization: Cardinality, minimum, covering, and more. arXiv preprint arXiv:2405. 240444440..08444, 2024.
[6] J. Cai, P. Wang. S. Sun, and H. Dong. A dynamic space reduction ant colony optimization for capacitated vehicle routing problem. Soft Computing, 26(17):8745-877 2022.
[7] W. Chao, J. Zhao, L. Jiao, L. Li. F. Liu, and S. Yang. A match made in consistency heaven: when large language models meet evolutionary algorithms, 2024.
[8] A. Chen, D. M. Dohan, and D. R. So. Evoprompting: Language models for code-level neural architecture search. arXiv preprint arXiv:2302.14883. 2023.
[9] J. Chen, Wang, Zhang, Z. Cao, Ye, and Siyuan. Efficient meta neural heuristic for multi-objective combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[10] X. Chen, M. Lin, N. Schärli, and D. Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05125, 2023.
[11] F. de Paulis, R. Cecchetti, C. Olivieri, and M. Buecker. Genetic algorithm pdn optimization based on minimum number of decoupling capacitors applied to arbitrary target impedance. 2020 IEEE International Symposium on Electromagnetic Compatibility & Signal/Power Integrity (EMCSI), pages 428-433 IEEE, 2020.
[12] T. Dernedde, D. Thyssens, S. Dittrich, M. Stubbemann, and L. Schmidt-Thieme, Moco: A learnable meta optimizer for combinatorial optimization. arXiv preprint arXiv:2402.08 2024.
[13] J. H. Drake, A. Kheiri, E. Özean, and F. K. Burke. Recent advances in selection hyper- heuristics. European Journal of Operational Research, 285(2):405-425 2020.
11

---

[14] D. Drakulic, S. Michel, F. Mai, A. Sors, and J.-M. Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[15] G. Duflo, E. Kieffer, M. R. Brust, G. Danoy, and P. Bouvry. A gp hyper-heuristic approach for generating tsp heuristics. In 2019 JEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 521-529. IEEE, 2019.
[16] I. Erdin and R. Achar. Multi-objective optimization of decoupling capacitors for placement and component value. IEEE Transactions on Components, Packaging and Manufacturing Technology, 9(10):1966 1983, 2019.
[17] S. Fidanova. Hybrid ant colony optimization algorithm for multiple knapsack problem. In 2020 5th IEEE International Conference on Recent Advances and Innovations in Engineering (ICRAIE), pages 1-5, IEEE, 2020.
[18] C. Gao, H. Shang, K. Xue, D. Li, and C. Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv preprini arXiv:2308. 14104, 2023.
[19] F. Guerriero and F. P. Saccomanno. A hierarchical hyper-heuristic for the bin packing problem. Soft Computing, 12977-111997 2023.
[20] Q. Guo, R. Wang. J. Guo, B. Li, K. Song. X. Tan, G. Liu, J. Bian, and Y. Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint w3Xiv22309008532 2023.
[21] E. Hemberg, S. Moskal, and U.-M. O'Reilly. Evolving code with large language model, 2024.
[22] W. Hordijk. measure of landscapes. Evolutionary computation, 4(4):335-360, 1996.
[23] J. Hromkovië. Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. Springer Science & Business Media, 2013.
[24] B. Hudson, Q. Li, M. Malencia, and A. Prorok. Graph neural network guided local search for the traveling salesperson problem. International Conference on Learning Representations, 2022.
[25] J. Ji, T. Qiu, B. Chen, B. Zhang, H. Lou, K. Wang, Y. Duan, Z. He, J. Zhou, Z. Zhang, et al. Ai alignment: A comprehensive survey, arXiv preprint arXiv:2310.190 19855, 2023.
[26] L. Jiang, I.. Zhang, S. Tan, D. Li, C. Hwang, J. Fan, and E.PP. Li. A novel physics-assisted genetic algorithm for decoupling capacitor optimization. JEEE Transactions on Microwave Theory and Techniques, 2024.
[27] Y. Jiang, Z. Cao, Y. Wu, W. Wong, and J. Zhang. Ensemble-based deep reinforcement learning for vehicle routing problems under distribution shift. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[28] Jin, Y. Ding, X. Pan, K. He, L. Zhao, T. Qin, L. Song, and J. Bian. Pointerformer: Deep reinforced multi-pointe transformer for the traveling salesman problem. arXiv preprint arXiv:2304.0m 09407, 2023.
[29] C. K. Joshi, Q Cappart, L.-M. Rousseau, and T. Laurent. Learning the travelling salesperson problem requires rethinking generalization. arXiv preprint arXiv:2006.0705. 2020.
[30] H. Kim, H. Park, M. Kim, S. Choi, J. Kim, J. Park, S. Kim, Kim, and Kim. Deep reinforcement learning framework for optimal decoupling capacitor placement on general pdn with an arbitrary probing port. In 2021 IEEE 30th Conference on Electrical Performance of Electronic Packaging and Systems (EPEPS), pages 1-3. IEEE, 2021.
[31] H. Kim, M. Kim, F. Berto, J. Kim, and J. Park. Devformer: A symmetric transformer for context-aware device placement. International Conference on Machine Learning, pages 16541-16566. PMLR, 2023.
12

---

[32] M. Kim, J. Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 14:104 2021.
[33] M. Kim, J. Park, and J. Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances Neurul Information Processing Systems, 35:1936-1944 2022.
[34] M. Kim, T. Yun, E. Bengio, D. Zhang, Y. Bengio, S. Ahn, and J. Park. Local search gflownets. arXiv preprint arXiv:2310.02710, 2023.
[35] M. Kim, S. Choi, J. Son, H. Kim, J. Park, and Y. Bengio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.0704,, 2024.
[36] W. Kool, H. van Hoof, and M. Welling. Attention, learn solve routing problems! In International Conference on Learning Representations, 2019.
[37] Y.-D. Kwon, J. Choo. B. Kim, I. Yoon, Y. Gwon, and Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 1811188-11999 198, 2020.
[38] J. Lehman, J. Gordon, S. Jain, K. Ndousse, C. Yeh, and K. O. Stanley. Evolution through large models. Handbook of Evolutionary Machine Learning, pages 331-366. Springer, 2023.
[39] J. Levine and F. Ducatelle. Ant colony optimization and local search for bin packing and cutting stock problems. Journal of the Operational Research society, 55(7):705-716, 2004.
[40] P. Li. J. Hao, H. Tang, X. Fu, Y. Zheng, and K. Tang. Bridging evolutionary algorithms and reinforcement learning: comprehensive survey, 2024.
[41] Y. Li, D. Choi, J. Chung, N. Kushman, J. Schrittwieser, R. Leblond, T. Eccles, J. Keeling, F. Gimeno, A. Dal Lago, et al. Competition-level code generation with alphacode. Science, 2022.
(18(6624):1092-111
[42] Y. Li, J. Guo, R. Wang, and J. Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances Neural Information Processing Systems, 2023.
[43] J. Liang, W. Huang, Xia, Xu, Hausman, Ichter, Florence, and A. Zeng. Code policies: Language model programs for embodied control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 9493 9500. IEEE, 2023.
[44] K. C. W. Lim, L.-P. Wong, and J. F. Chin. Simulated-anncaling--asss hyppe--huristic for flexible job-shop scheduling. Engineering Optimization, 55(10):1635-1655, 2023.
[45] F. Liu, X. Lin, Z. Wang, S. Yao, X. Tong, M. Yuan, and Q. Zhang. Large language model for multi-objective evolutionary optimization. arXiv preprint arXivv2310.12541, 2023.
[46] F. Liu, X. Tong, M. Yuan, and Q Zhang. Algorithm evolution using large language model. arXiv preprint arXiv:2311.15244 2023.
[47] F. Liu, X. Tong, M. Yuan, X. Lin, Luo, Z. Wang, Z. Lu, and Q. Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language mode. In ICML, 2024. URL https: / //tr////vvvv//////////eeeeeaaaaa wwwpvoog//aaoo aa////bs/2/00 2//0//40...00 .22511.
[48] S. Liu, C. Chen, X. Qu, K. Tang, and Y.-S. Ong. Large language models as evolutionary optimizers. arXiv preprint arXiv:2310. 19046, 2023.
[49] V. Liventsev, A. Grishina, A. Härmä, and L. Moonen. Fully autonomous programming with large language models. arXiv preprint arXiv:2304. 10423, 2023.
[50] Y. Lu, X. Liu, Z. Du, Y. Gao, and G. Wang. Medkpl: heterogeneous knowledge enhanced prompt learning framework for transferable diagnosis. Journal of Biomedical Informatics, page 104417, 2023.
13

---

[51] F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Thirty- Conference on Neural Information Processing Systems, 2023.
[52] Y. Ma, Z. Cao, and Y. M. Chee. Learning search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Processing Systems, 2023.
[53] Y. Ma, W. Liang, G. Wang, D.-A. Huang, O. Bastani, D. Jayaraman, Y. Zhu, L. Fan, and A. Anandkumar. Eureka: Human-level reward design via coding large language models. arXiv preprint arXiv:2310. 12931, 2023.
[54] Z. Ma, H. Guo, J. Chen, Z. Li, G. Peng, Y.J. Gong, Y. Ma, and Z. Cao. Metabox: A benchmark platform for meta-black-bol optimization with reinforcement learning. In Advances in Neural Information Processing Systems, volume 36, 2023.
[55] A. Madaan, A. Shypula, U. Alon, M. Hashemi, P. Ranganathan, Y. Yang. G. Neubig, and A. Yazdanbakhsh. Learning performance-improving code edits. arXiv preprint arXiv:2302.0703 2023.
[56] A. Madaan, N. Tandon, Gupta, S. Hallinan, Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303. 17651, 2023.
[57] E. Meyerson, M. J. Nelson, H. Bradley, A. Gaier, A. Moradi, A. K. Hoover, and J. Lehman. Language model crossover: Variation through few-shot prompting. arXiv preprint 12X1::2302.12170.0 2023.
[58] B. Mohammad Hasani Zade, N. Mansouri, and M. M. Javidi. A new hyper-heuristic based on ant lion optimizer and tabu search algorithm for replica management cloud environment. Artificial Intelligence Review, 56(9):9837-99) 9947, 2023.
[59] G. Ochoa, R. Qu, and E. K. Burke. Analyzing the landscape of graph based hyper-heuristic for timetabling problems. Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 341- 1-84,, 2009.
[60] H. Park, M. Kim, Kim, S. Jeong, S. Kim, H. Kang, K. Kim, K. Son, G. Park, K. Son, et al. Policy gradient reinforcement learning-basse based optimal decoupling capacitor design method for 2.5-d/3-d ies using transformer network. In 2020 IEEE Electrical Design of Advanced Packaging and Systems (EDAPS), pages 1-3. IEEE, 2020.
[61] H. Park, J. Park, S. Kim, K. Cho, D. Lho, S. Jeong, S. Park, G. Park, B. Sim, S. Kim, et al. Deep reinforcement learning-bast bassd optimal decoupling capacitor design method for silicon enterposer-basedd 2.5-d/3-d ics. IEEE Transactions on Components, Packaging and Manufacturing Technology, 10(3):467-478, 2020.
[62] H. Park, M. Kim, S. Kim, K. Kim, H. Kim, T. Shin, K. Son, B. Sim, S. Kim, S. Jeong, et al. Transformer network-bart based reinforcement learning method for power distribution network (pdn) optimization of high bandwidth memory (hbm). IEEE Transactions on Microwave Theory and Techniques, 70(1 70(11):4722-478 2022.
[63] H. Park, H. Kim, H. Kim, J. Park, S. Choi, Kim, K. Son, H. Suh, T. Kim, J. Ahn, et al. Versatile genetic iggorithm-bayeiinn optimization (ga-bo) bi-level optimization for decoupling capacitor placement. In 2023 IEEE 32nd Conference on Electrical Performance of Electronic Packaging and Systems (EPEPS), pages 1-3. IEBE, 2023.
[64] N. Pillay and R. Qu. Hyper-heuristics: theory and applications. Springer, 2018.
[65] M. Popovich, A. Mezhiba, and F. G. Friedman. Power distribution networks with on-chip decoupling capacitors. Springer Science & Business Media, 2007.
[66] R. Pryzant, D. Iter, J. Li, Y. Lee, C. 7hu, and M. Zeng. Automatic prompt optimization with" gradient descent" and beam search. arXiv preprint 20Xv:2205.034955 2023.
14

---

[67] G. Reinelt. Tsplib traveling salesman problem library. ORSA journal on computing. 3(4):
376-384, 1991.
[68] B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, pages 1-3, 2023.
[69] K. Shibasaka, K. Kanazawa, and M. Yasunaga. Decoupling-capaciin allocation problem solved by genetic algorithm. In 2013 IEEE Electrical Design of Advanced Packaging Systems Symposium (EDAPS), pages 225-228. IEEE, 2013.
[70] N. Shinn, F. Cassano, A. Gopinath, K. R. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[71] R. Skinderowicz. Improving ant colony optimization efficiency for solving large tsp instances. Applied Soft Computing, 120: 108653, 2022.
[72] S. Sohrabi, K. Ziarati, and M. Keshtkaran. Acs-ophs: Ant colony system for the orienteering problem with hotel selection. EURO Journal Transportation and Logistics, 10:100036, 2021.
[73] J. Son, M. Kim, S. Choi, and J. Park. Solving np-hard min max routing problems as sequential generation with equity context. arXiv preprint arXiv:2306.0223 02669, 2023.
[74] Song, Y. Tian, foundational models for black-box optimization: Benefits, challenges, and future directions. arXiv preprint arXiv:2405. 03547, 2024.
Lange. C. Lee, Y. Tang, and Y. Chen. Position paper: Leveraging
[75] J. Sui, S. Ding, B. Xia, R. Liu, and D. Bu. Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Computing and Applications, pages 1-20, 2023.
[76] Z. Sun and Y. Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[77] Tang, F. Berto, Z. Ma, C. Hua, K. Ahn, and Park. Himap: Learning heuristics-ifforeed policies for large-scale multi-agent pathfinding. arXiv preprint arXiv:2402. / /5546, 2024.
[78] C. Voudouris and E. Tsang. Guided local search and its application to the traveling salesman problem. European Journal of Operational Research, 113(2):469-499 Mar. 1999. ISSN 03772217. doi: 10.1016/50377 (20033777--2217880000999999
[79] C. Wang, Z. Yu, S. McAleer, T. Yu, and Y. Yang. Asp: Learn universal neural solver! IEEE Transactions on Patlern Analysis and Machine Intelligence, 2024.
[80] H. Wang, S. Feng, T. He, Z. Tan, X. Han, and Y. Tsvetkov. Can language models solve graph problems in natural language? arXiv preprint arXiv:2305.10037 2023.
[81] L. Wang, Y. Ling, Z. Yuan, M. Shridhar, C. Bao, Qin, B. Wang, H. Xu, and X. Wang. Gensim: Generating robotic simulation tasks via large language models. arXiv preprint arXiv:2310.01361, 2023.
[82] L. Wang, C. Ma, X. Feng, Z. Zhang, H. Yang, J. Zhang, Z. Chen, J. Tang, X. Chen, Y. Lin, et al. A survey large language model based autonomous agents. arXiv preprint arXiv:2308. 1432, 2023.
[83] X. Wang, C. Li, Z. Wang, F. Bai, H. Luo. J. Zhang, N. Jojic, E. P. Xing, and Z. Hu. Promptagent: Strategic planning with language models enables expert-level prompt optimization. arXiv preprint arXiv:2310.16427. 2023.
[84] Y. Wang, Z. Liu, J. Zhang, W. Yao, S. Heinecke, and P. S. Yu. Drdt: Dynamic reflection with divergent thinking for based sequential recommendation. arXiv preprint arXiv:2312.13333 2023.
15

---

[85] Y. Wang. Y. Jia, W.-N. Chen, and Y. Mei. Distance-awar attention reshaping; Enhance generalization of neural solver for large-scale vehicle routing problems. arXiv preprint arXiv:2401.06979 2024.
[86] E. Weinberger. Correlated and uncorrelated fitness landscapes and how tell the difference. Biological cyberneticy, 63(5):325-3 323333,, 1990.
[87] X. Wu, S. hao Wu, J. Wu, L. Feng, and K. C. Tan. Evolutionary computation in the era of large language model: Survey and roadmap. 2024.
[88] Z. Xi, W. Chen, X. Guo, W. He, Y. Ding, B. Hong, M. Zhang, J. Wang, S. Jin, E. Zhou, et al. The rise and potential of large language model based agents: survey, arXiv preprint arXiv:2309, S04.023,9,,7864, 2023.
[89] Y. Xiao, D. Wang. H. Chen, B. Li, W. Pang, X. Wu, H. Li, D. Xu, Y. Liang, and Y. Zhou. Reinforcement learning- based non-autoregressive solver for traveling salesman problems. 2023.
arXiv preprint
[90] Y. Xiao, D. Wang. B. Li, M. Wang, X. Wu, C. Zhou, and Y. Zhou. Distilling autoregressive models to obtain nigh-performance non-autoregressive solvers for vehicle routing problems with faster inference speed. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[91] C. Yang. X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen. Large language models as optimizers. arXiv preprint Stti::2309.030000 2023.
[92] J. Yang, A. Prabhakar, K. Narasimhan, and S. Yao. Intercode: Standardizing and benchmarking interactive coding with execution feedback. arXiv preprint arXiv:2306.. /4898, 2023.
[93] Y. Yang and A. Whinston. A survey on reinforcement learning for combinatorial optimization. In 2023 IEEE World Conference on Applied Intelligence and Computing (AIC), pages 131-136. IEEE, 2023.
[94] H. Ye, J. Wang, Z. Cao, H. Liang, and Y. Li. Deepaco: Neural-enhanced ant systems for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[95] H. Ye, J. Wang. H. Liang. Z. Cao, Y. Li, and F. Li. Glop: construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
Learning global partition and local
[96] D. Gutterre, J. Cruz-Duarte, and H. Castañeda. Automatic hyper-heuristic to generate heuristic-basee adaptive sliding mode controller tuners for buck-boost converters. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1482-1489, 2023.
[97] R. S. Zebulum, M. A. Pacheco, and M. M. B. Vellasco. Evolutionary electronics: automatic design of electronic circuits and systems by genetic algorithms. CRC press, 2018
[98] F. Zelikman, F. Lorch, L. Mackey, and A. T. Kalai. Self-taught optimizer (stop): Recursively self self-improving code generation. arXiv preprint arXiv:2310.02304, 2023.
[99] C. Zhang, K. Yang, S. Hu, Z. Wang, G. Li, Y. Sun, C. Zhang. Z. Zhang, A. Liu, S.-C. Zhu, et al. Proagent: Building proactive cooperative with la rge language models. arXiv preprint arXiv:2308. 11399, 2023.
[100] L. Zhang, W. Huang, J. Juang, H. Lin, B.-C. Tseng, and C. Hwang. An enhanced deep reinforcement learning algorithm for decoupling capacitor selection in power distribution network design. In 2020 IEEF International Symposium Electromagnetic Compatibility & Signal/Power Integrity (EMCSI), pages 245-250. IEFE, 2020.
[101] R. Zhang, F. Liu, X. Lin, Z. Wang, Z. Lu, and Q Zhang. Understanding the importance of evolutionary search automated heuristic design with large language models. In International Conference on Parallel Problem Solving from Nature, pages 185-202. Springer, 2024.
16

---

[102] S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan. Planning with large language models for code generation. The Eleventh International Conference on Learning Representations, 2022.
[103] Z.-Q. Zhang, F.-. Wu, B. Qian, R. Hu, L. Wang, and H.-P. Jin. A q-learning-based hyper- heuristic evolutionary algorithm for the distributed flexible job-shop scheduling problem with crane transportation. Expert Systems with Applications, 234:121050, 2023.
[104] Q. Zhao, Q. Duan, B. Yan, S. Cheng, and Y. Shi. A survey automated design of metaheuristic algorithms. arXiv preprint arXiv:2303.0663
2023.
[105] W. X. Zhao, K. Zhou, J. Li, T. Tang. X. Wang. Y. Hou, Y. Min, B. Zhang, J. Zhang, Z. Dong, al. survey of large language models. arXiv preprint arXiv:2303.1822 182233 2023.
[106] T. Zhong, 7. Liu, Pan, Zhang, Zhou, Liang, Wu, Y. Lyu, P. Shu, Yu, al. Evaluation of openai ol: Opportunities and challenges of agi. arXiv preprint arXiv:2409, 18486, 2024.
[107] J. Zhou, Wu, Z. Cao, W. Song. J. Zhang, and Z. Chen. Learning large neighborhood search for vehicle routing in airport ground handling. IEEE Transactions on Knowledge and Data Engineering, 2023.
[108] Y. Zhou, A. I. Muresanu, Z. Han, K. Paster, S. Pitis, H. Chan, and J. Ba. Large language models are human-level prompt engineers. arXiv preprint 1.X11:2211.01910, 2022.
[109] L. Zhu, Y. Zhou, Sun, and Q. Su. Surgical cases assignment problem using an efficient genetic programming hyper-heuristic. Computers & Industrial Engineering, 178:109102 2023.
17

---

A Extended discussions
A.1 Comparisons with EoH
Our work is developed concurrently with Evolution of Heuristics (EoH) [47], which establishes the groundwork for this emerging field. Nonetheless, our work extends the boundaries of LHH through three primary lenses: (1) the search algorithm, (2) the downstream CO applications, and (3) the evaluation methodologies.
Search Algorithm: We introduce the Reflective Evolution, demonstrating its superior sample efficiency.
Applications: Our work broadens the scope by applying LHH to five heterogeneous algorithmic types and six different COPs, advancing the state-of-the in GLS, EDA, ACO, and NCO.
Evaluation Methodologies: We employ fitness landscape analysis to explore the underlying mechanisms of proposed method; establish black-box experimental settings ensure reliable comparisons and practical relevance to real-world applications.
A.2 Extended applications
ReEvo is generally applicable to other string-based optimization scenarios [57] as long reflecting the relative performance of strings meaningful. Preliminary experiments on prompt tuning verify the advantage of ReEvo random search and vanilla genetic programming. Furthermore, identify in caasoning-capablee LLM approaches released after ReEvo such as OpenAl ol [106] an interesting avenue of future works and experimentation that could yield even better sample efficiency and performance.
B
Prompts
We gather prompts used for ReEvo in this section. Our prompt structure is flexible and extensible. To adapt ReEvo to new problem setting, one only needs to define its problem description, function description, and function signature.
B.1 Common prompts
The prompt formats are given below. They are used for all COP settings.
expert of heuristics. Your Your response ouipuis Pytbon code and nothing else. Format your code as a Python code sting: *" pythhn
heuristics effectively optimization problems.
Prompt I: System prompt for generator LLM.
You expert domain of
heuristies..
Your
hime
design
better
heuristics
Prompt 2: System prompt for reflector LLM.
Write [finction, name) fanction for mrnkblem_deerrppinn Faaction,desstti dessriioddsccttiionn
Prompt 3: Task description.
Itsk, deseription
funccion
Formst trivial design above. Re very crestive and give '[fine name] v2". Cuipot code only your Python code block: pytthon
Jong rellection
18

---

Prompt 4: User prompt for population initialization.
Below are two (fanction_name functions for liinction description
Linciion_descritioon
provided
version performs one.
Wause code]
(wons_code)
Better code] (better_code) }
respand some designing
beuristics
two using
Prompt 5: User prompt for short-term reflection.
The user prompt used for short-term reflection in black-box COPs is slightly different from the one used for white-box COPs. We explicitly ask the reflector LLM to infer the problem settings and to give hints about how the node and edge attributes correlate with the black-hox objective value.
(fanctioon tame) functions pprbblem description
Fuaction, Tuaction_desciiption
provided
below, sccoed
better
Wanse code]
(Wone, code]
[Btter cade] (better code
infor problem settings compuring and give designing houristics may give hints about odge sode
artributes conelate
objestive value. less words.
Prompt 6: User prompt for short-term reflection black-box COPs.
[Wime code]
function function_sigmaturo) signatureO
(wome_code code]
Better code]
signaturel better__ooee
Reflection sbort_temm_rffee//ee refeeeellctiio
[Emproved codo] Please
function "ffunction_amme__u L22', according
reflection
Output code and enelose your Python code
pythun
Prompt 7: User prompt for crossover.
The function signature variables here used to adjust function names with their versions, which similar to the design in [68]. For example, when designing "heuristics", the worse code is named "heuristics v0" while the better code "heuristics_vi" v1". In Prompt 9, the elitist code is named "heuristic_vil
Below your prior loug term reflection designing heuristies for (problem_ destriptmddssiiiinnnoo prior_Jogg- reficction
Below are somn newly gained insights...
(new short- reflections
constractive designing howisties,
prlor
reflections
new insights
using less
Prompt 8: User prompt for long term reflection.
19

---

lisk, desoription
PPior reflection
(Jong- term reflection
[Code]
signsturel
elitisr
(Inproved code]
function "[function samee/_..mmm___ according
reflection
Outgut code only your Python
block:
pyythm
Prompt 9: User prompt for elitist mutation.
B.2
Proclem-specific prompt components
Soblem--peccfic prompt components are given below.
Problem descriptions of all COP settings given in Table 6.
The function descriptions of all COP settings are presented in Table 7. The descriptions crafted for black-box settings avoid disclosing any information that could link to the original COP.
The function signatures are gathered in Prompt 10.
The seed functions are shown Prompt II. The seed function used for _SP_constructive drawn from [46]. The seed functions used for black-box ACO settings are expert-designed heuristics [71, 6, 72, 17, 39], while those used for while-box ACO settings are trivial all-ones matrices.
The initial long-term reflections for some COP settings are presented in Prompt 12, while are left empty for the others.
7SP
henristicx(dlaasnce, peariie tarch. Twssor) torch.TTnaore
t CVPP JCD def www.iiediiieeeeeeeecccoeo tarch,
Terch.Temaor) tarch.
* DPP_GA coocoooe
def croxsover (perents: up.ndarray, int) sp.ndarray:
aPP_GA__utation
def mutation (populatio: up.ndarray, probe: int, prohibit: sp.ndurray, aize; int=100) +> sp.ndarray:
beuriaticccdlaannos.ancci sp.ndarray) np.ndarray:
* TSP AAD def www.riitiiddittnsappooo sp.ndarryy) np.sdarray:
4 CVRP_ACD
del heuriat (dwattteeddtttteeeeccrro sp.ndarray, conriistte:: up.ndarray, demanda: up.ndurray, capucity: int) > adurrayy
def beuriaticx(peizes ap.ndarryy, distance: up.udarray, sacies: float) -2 ud.ndaryy::
heuriatica(prize: up.ndurray, wight: sp.ndurray) - up.sdurray:
* BPP_ACO
heurtetsce<demand: up adardarray, capacity: up ndarray::
4 TSP_ACD (black-bos))
det bruristicosedlgeattte ndarray)
CVRP_ACO (black-box)
det henrietico(edge. (etietttcc(dgeeattt:: attr: up ndarray, node_athr: up adarray) >> np ndarray: it Por simplicity, se onst 'coordinater! and capacity! after using capacity sormliza derands, ande_attr
* 0P-ACD (black-box)
def hmuriaticxnnnle ponriatticcmdd_attrr attr: up up.ndarray, eigeLattr: sp.ndarray, soda cod_constrain:: float) >> rp.ndarray:
wtw.iaaticc(iitatttrrtr ap.ndarray, iten_attr9: sp.ndarray) +> np.ndarray:
XPP_ACO (black-box)
np. adarray, cod_ccotrraitt:: ins) up adarray:
20

---

def select_cest, mode (currwns_ ins, iesiiiiiio_nddee ink, unvisi wewiaited_ndeee set, aacetasoe_satiiie up.ndarray) >> int:
Prompt 10: Function signatures used in ReEvo.
TSSP_MD JCD
def ceurietico(dictang
torch, Tensor) torch. Tenzor:
cistance_matriklee (ttpoe/mtrriitttttteeeceeeo
x 100
I Caxpute top nearest neighbore (enallest distances)
values, indices torch, www.tceeetcccceecnooom
larget-iaaee,, dim=1)
ddistance natrix, close()
Create zack vhere topk indices are True and othere are Falre
topk torch-zeron zeron, (tteedteeaanceemnne
topk_rank torch
despettorcb.bon))
indices, Trus) ápply 11og(d_13) only
top-k
hm[ttopr_maek] -torch- htt.aa/eaannemtttttoo......em return bea
NCC
def hearietico(dietanc _attri: torch. Tensor, derands: terch. torch. Tensor) torch, Tensor: return torch, zeroe, 1ake (distance, ratriz)
PPP__A__rrosee crossovee
det croncover up ndarray, n.pop: int) up adarray...:
p.pazents, dedecap parests. shape
Split laft_halves parental;, :8_decup
halves
right, halves pareats [:, a_decap // 2:]
Create parent pairs
parenta_ids up.stack ([ap. randos.
(a.prrrtt)))) replace-False) for popp)) pareata_lott left (parenta, idx(: 0]] parente_right: right, feggtthhalveee hal hagpthhaareeppprrttee..com
1]]
Create offapzing
offopring np.comratematel (parents_ parhtts_right), axis=1) offapring
8 DPP su.utttio
def sutation (populaaioo: up.ndareay,
prohibis: sp.ndarzay,
sp.adazay:
n.pop, a_decap populatios. for 1 in (a.po) ind population[i]
actiees pp..uiiquapppuuatiioll.
San(uniquu_aationn) n_decaps
Find the indices vhersin the action in taken the aecond Line dup. Idx
Ja action unumerata if action in action_set: dup, idk. actioe add(action)
Nutate the duplicated actions infeasible, actious up.concatentt [probe), (nique_ectioss))
sf.eetdiif1ddnn araegegeee Infmaaibll_enttimn)) axsert dadepu len(uniqu actiiussscttni) idd( now actions up.. ap.casses. and melppp_ddrr) idr] nev_.actions population
actions, (ddp) roplace=False)
TSP_ALS _GL del
mucrii: sp.ndarray) up.adarray:
$ TSP AAD
def beuriataca mnttrii: sp.ndarray) np.ndarray:
dissencm_netrix
* CVRP_ACO
def couriattie(diaateeeat mecriie sp.ndarray, coordisatas: up.ndarray, decanda: up.ndarray, capecity: int) nderrnyy dierance_matrik
& OP. ACD
det bouristacs(prize:
distance: ndarrayy zaxies: float) ndartay: inp.nezzin
* MSP_ACO
def heuriatiie(prrize sp.ndarray, weight: sp.ndarray) + np.ndarray: retorn prize np. np.ommiveight, axte=1)
* RPP_ACD
def beurietacs(deennet up deeandddddeeddddmmmmmm O. sbape[0),
adarray::
t TSP AAC (black boxt)
def smuristtceeedde
ndarray)
ap. ones Lodge_atte chape
21

---

CERP_ACO (black-bos)
def leuriatica attr: up ug.aaarray, node_attr: up.adaczuy) + up up.udarray: return pppoonss, (ee(eggeeee
(black-box)
def (arristtcccaoeeatteee. up sd.aadrra,, eáge_attzi up adarraa edge_constrain:: float) -> up adaraay.
return www..
MEC_ACD (black-box)
del heuriatica (iter: up.ndarray, itenattir2: sp.ndarray) + up, ad.adaryy::
1tem, att12.saaps
up. (p.onna(s.)
8 EPP ACD (black-box)
def (onriatticannddentttet op.ndarray, noda_cmetrainnt: int) up.ndarray:
shapa(0) [0]
return up. ((na((a,
* TSP "er__oonaatee tructivo
wwleec__estt_mmdelce (cr.nodeecarreet..node int, Gestimation_ndee int, mniiateed_moees dietamce_ratriiz mp.ndarray)
thrwshold
ct, c2, c3, c4 0.4, 0.3, 0.2, 0.1
unviaited_nncee.
all_ddatances belitanoo.nuttizleee
[i]
usvisited,
node]
average.diataess to, unvissted = ep sp-nman(all (all [ann(al__iettncce _dietancee)
std_dev_dd "eee__dattanse... to_uiiiittedd sxlatd didattneattnnes
distance paaanceeaatttteurreeeeee
[node]
averago.dtetance. tt.icettttovvitted
pad_ddv_diiaarce cetroe_tt_uvvviiieeee
aettanceraerrisdeeeee mnddeetooooneeee____eee [noce]
scores [nnda] score
next_node (scores, keymecoren.ooo get)
Prompt 11: Seed heuristics used for ReEvo.
White-ot COP ACO
Try combining various factors determine how promising select solution cumponent. spunsfying
by setting unpeomising
TSP constructive
Try look-shed mechanisms.
Prompt 12: Initial long-term reflections
Table 7: Function descriptions used in prompts.
Problem
Function description
TSP_NCO
The 'heuristics' function takes input distance matrix and returns prior indicators how bad of the same shape as the input. The heuristics should contain negative values for undesirable edges and positive values for promising ones. Use efficient vectorized implementations.
include each edge a solution. The return is
CVRP_NCO
The 'heuristics' function takes input distance matrix (shape: by n) and of customer demands (shape: n), where the depot node is indexed by the customer demands are normalized by the total vehicle capacity. returns prior indicators of how promising it to include each edge in a solution. The return is of the same shape as the distance matrix. The heuristics should contain negative values for undesirable edges and positive values for promising Use efficient vectorized implementations.
DPP GA.
The 'crossover' function takes input a 2D NumPy array parents and integer n_ n_pop. The function performs a genetic crossover operation on parents to generate n __popp offspring. Use vectorized implementation if possible.
Continued on next page
22

---

Table 7 continued from previous page
Problem
Function description
DPP_ GA mutation
The 'mutation' function modifies a given 2D population array to ensure explo- ration the genetic algorithm. You may also take into account the feasibility of each individual. An individual is considered feasible if all its elements are unique and none are listed in the prohibited array or match the probe value. Use vectorized implementation if possible.
The function takes as input the below arguments:
population (np. ndarray): Population individuals; shape: (P, n_ p_decap)). probe (int): Probe value; each clement in the population should not be equal to this value.
prohibit (np.ndarray): Prohibit values; each element in the population should not this set. size (int): Size of the PDN; each element in the population should be in the range I0, size).
TSP_GLS
The 'heuristics' function takes as input a distance matrix, and returns prior indicators of how bad it is to include each edge in solution. The return is of the same shape as the input.
TSP_ACO
The 'heuristics' function takes input distance matrix, and returns prior indicators of how promising it is to include each edge in solution. The return is of the same shape as the input.
TSP_ACT black-box
The 'heuristics' function takes as input a matrix edge attributes with shape '(n edges, n attributes)', where 'n attributes=1 in this case. It computes prior indicators of how promising it is to include each edge in solution. The return is of the shape of '(n_egges)).
CVRP_ACO
The "heuristics' function takes as input distance matrix (shape: n by n), Eu- clidean coordinates of nodes (shape: by 2), vector of customer demands (shape: n), and the integer capacity of vehicle capacity. returns prior indicators of how promising it is to include each edge in solution. The return of the same shape as the distance matrix. The depot node is indexed by 0.
CVRP_ACO_black black-box
The 'heuristics' function takes as input a matrix of edge attributes (shape: n by n) and vector of node attributes (shape: n). A special node is indexed by 0. "heuristics" returns prior indicators of how promising it to include each edge in a solution. The return is of same shape as the input matrix of edge attributes.
OP_ACO
Suppose 'n' represents the number of nodes in the problem, with the depot being the first node. The 'heuristics' function takes as input a 'prize' array of shape (n.), a 'distance' matrix of shape (n,n), and 'max_len float which is the constraint to total travel distance, and it returns 'heuristics' of shape (n, n). where "heuristics(illi"" indicates the promise of including the edge from node fii to node tij in the solution.
(CCO_black-bbl
The 'heuristies' function takes as input vector of node attributes (shape: n), matrix of edge attributes (shape: n by n), and a constraint imposed on the sum of edge attributes. A special node is indexed by 0. 'heuristics" returns prior indicators of how promising it is to include each edge in solution. The return is of the same shape as the input matrix of edge attributes.
MKP_ACO
Suppose 'n' indicates the scale of the problem, and 'm' is the dimension of weights each item has. The constraint of each dimension is fixed 1. The "heuristics' function takes as input a 'prize" of shape (n.), a 'weight' of shape (n, m), and returns 'heuristics' of shape (n.). 'heuristics(il" indicates how promising it is to include item i in the solution.
ACO black-box
Suppose 'n' indicates the scale of the problem, and 'm' is the dimension of some attributes each involved item has. The "heuristics' function takes as input 'item_attr1 of shape (n.), an fiem_aatr2 of shape m), and returns 'heuristies' of shape (n.). "heuristicsil"" indicates how promising it is to include item in the solution.
Continued on next page
23

---

Table 7 continued from previous page
Problem
Function description
BPP_ACO
Suppose 'n' represents the number of items in the problem. The heuristics func- tion takes as input a 'demand" array of shape (n,) and an integer as the capacity of every bin, and it returns a 'heuristics' array of shape (n.n). "heuristicsiillj"" indicates how promising it is to put item and item in the same bin.
BPP_ACO_blacke
Suppose 'n' represents the scale of the problem. The heuristics function takes imput an 'item_athe _aatrrt'' array of shape (n.) and an integer as certain constraint imposed on the item attributes. The hcuristies function returns 'heuristics' array of shape (n, n). "heuristics(ilji" indicates how promising is to group item i and item
_
The seleet_next_noxe function takes as input the current node, the destination node, set of unvisited nodes, and a distance matrix, and returns the next node to visit.
C Detailed experimental setup
Hyperparameters for ReEvo. Unless otherwise stated, we adopt the parameters in Table for ReEvo runs. During initialization, the LLM temperature is added by 0.3 diversify the initial population.
Heuristic generation pipeline. We perform ReEvo for each COP setting. Unless otherwise stated, the heuristic with the best validation performance selected for final lesting on 64 held-out instances.
Cost and hardware. When the hardware permits, heuristics from the same generation are generated, reflected upon, and evaluated in parallel. The duration of a single ReEvo run can range from approximately two minutes to hours, depending on the evaluation runtime and the hardware used. Each run costs about S0.06 when using GPT3.5 Turbo. When conducting runtime comparisons, we employ single of AMD EPYC 7742 CPU and an NVIDIA GeForce RTX 3090 GPU.
C.1 Penalty heuristics for Guided Local Search
Guided Local Search (GLS) explores solution space through local search operations under the guidance of heuristics. We
use ReEvo find the most effective heuristics to enhance GLS. In our experimental setup, we employed a variation of the classical GLS algorithm [78] that incorporated perturbation phases [1], wherein edges with higher heuristic values will be prioritized for penalization. In the training phase, we evaluate cach heuristic with TSP200 using 1200 GLS iterations. For generating results in Table 1, we the parameters in Table The iterations stop when reaching the predefined threshold or when the optimality gap reduced to zero.
C.2 Heuristic measures for Ant Colony Optimization
Ant Colony Optimization is an evolutionary algorithm that interleaves solution samplings with the update of pheromone trails. Stochastic solution samplings are biased toward more promising solution space by heuristics, and ReEvo searches for the best of such heuristics. For more details, please refer to [94].
Table 10 presents the ACO parameters used for heuristic evaluations during LHH evolution. They are adjusted to maximize ACO performance while ensuring efficient evaluations. Instance generations and ACO implemen- tations follow Ye et al. [94]. To conduct tests in Fig. 2, increase the number of iterations ensure full convergence.
C.3 Genetic operators for Electronic Design Automation
Here briefly introduce the expert-design GA for DPP. Further details be found in [31, Appendix B).
The GA designed by Kim et al. [31] is utilized expert policy collect expert guiding labels for imitation learning. The GA is widely used search heuristic method for the Decoupling Capacitor Placement Problem (DPP), which aims to find the optimal placement of a given number of decoupling capacitors (decaps) on a Power Distribution Network (PDN) with probing port and 0-15 keep-out regions to best suppress the impedance of the probing port.
Key aspects of the designed GA include:
24

---

Table 6: Problem descriptions used in prompts.
Problem
Problem description
TSP_NCO
Assisting in solving the Traveling Salesman Problem (TSP) with some prior heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
CVRP_NCO
Assisting in solving Capacitated Vehicle Routing Problem (CVRP) with some prior heuristics. CVRP requires finding the shortest path that visits all given nodes and returns to the starting node. Each node has a demand and each vehicle has capacity. The total demand of the nodes visited by vehicle cannot exceed the vehiele capacity. When the total demand exceeds the vehicle capacity, the vehicle must return to the starting node.
DPP_GA
Assisting in solving black-hox decap placement problem with genetic algorithm. The problem requires finding the optimal placement of decaps in given power grid.
TSP_GLS
Solving Traveling Salesman Problem (TSP) via guided local search. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
TSP ACO
Solving Traveling Salesman Problem (TSP) via stochastic solution sampling following "heuristics". TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
SUP_AACoblacck-aa
Solving black-bos box graph combinatorial optimization problem via stochastic solution sampling following "heuristics".
CVRP_ACO
Solving Capacitated Vehicle Routing Problem (CVRP) via stochastic solution sampling. CVRP requires finding the shortest path that visits all given nodes and returns to the starting node. Each node has a demand and each vehicle has capacity. The total demand of the nodes visited by vehicle cannot exceed the vehicle capacity. When the total demand exceeds the vehicle capacity, the vehicle must return to the starting node.
CVRP_ bC___ black-box
Solving a black- graph combinatorial optimization problem via stochastic solution sampling following "heuristics".
OP_ACO
Solving Orientecring Problem (OP) via stochastic solution sampling following "heuristics". OP is an optimization problem where the goal is to find the most rewarding route, starting from a depot, visiting subset of nodes with associated prizes, and returning the depot within specified travel distance.
OP_ACO_blacde blo
Solving black-box graph combinatorial optimization problem via stochastic solution sampling following "heuristies".
MKP_AGT
Solving Multiple Knapsack Problems (MKP) through stochastic solution sam- pling based on "heuristics". MKP involves selecting subset items to max- imize the total prize collected, subject to multi-dimensional maximum weight constraints.
MKP_ACO
MKP__ACO_blackbbox black-box
Solving a black-box combinatorial optimization problem via stochastic solution sampling following "heuristics".
BPP_ACO
Solving Bin Packing Problem (BPP). BPP requires packing set of items of various sizes into the smallest number of fixed-sized bins.
BPP_ACO_blace blockklak-boxx
Solving a black-box combinatorial optimization problem via stochastic solution sampling following "heuristics".
cSP_stostrective
Solving Traveling Salesman Problem (TSP) with constructive heuristies. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
25

---

Table 8: Parameters of ReEvo.
Parameter
Value
LLM (generator and reflector)
gpt-3.5 gpt-3.5-turbo
LLM temperature (generator and reflector)
Population size
10
Number of initial generation
30
Maximum number of evaluations
100
Crossover rate
Mutation rate
0.5
Table 9: GLS parameters used for the evaluations in Table
Problem
Perturbation moves
Number of iterations
Scale parameter
TSP20
73
TSP50
0.1
TSP100
40
1800
TSP200
40
800
Encoding and initialization. The GA generates initial population randomly, and each solution
consists of set numbers representing decap locations on the PDN. The population size is 20, and each solution is evaluated and sorted based on its objective value.
Elitism. After the initial population is formulated, the top- performing solutions (clite population)
kept for the next generation. The size the clite population is predefined as 4.
Selection. The hetter half of the population is selected for crossover.
Crossover. This process generates new population candidates by dividing each solution from the selected population half performing random crossover.
Mutation. After crossover, solutions with overlapping numbers are replaced with random numbers while avoiding locations of the probing port and keep-out regions.
this work, we sequentially optimize crossover and mutation operators using ReEvo. When optimizing crossover, all other components of the GA pipeline remain identical to the expert-designed one. When optimizing mutation, we additionally set the crossover operator to the best one previously generated by ReEvo.
During training, we evaluate F on three training instances randomly generated following [31, Appendix A.5]. The evaluation on each instance runs 10 GA iterations and returns the objective value of the best-performing solution. For the final test in Fig. we utilize the
dataset as in [31].
C.4 Attention reshaping for Neural Combinatorial Optimization
For autoregressive NCO solvers, e.g. POMO [37] and LEHD [S1]. the last decoder layer outputs the logits of the next node to visit. Then, the ditention-reshaplie heuristic values added to the logits before masking, logit clipping, and softmax operation.
For the autoregressive NCO models with heavy encoder and light decoder, the last decoder layer computes logits using [36]
q
C
Lanh
if me
VL <L
W(c))
Vd
(3)
otherwise.
Table 10: ACO parameters used for heuristic evaluations during training.
Problem
Population size
Number of iterations
TSP
30
100
CVRP
30
100
OP
20
50
MKP
10
50
BPP
20
15
26

---

Here, "(c) is the compatibility between current context and node j. C' constant for logit clipping, 4(c) the query embedding of the current context, k, the key embedding of node and de the query/key dimensionality. For each node j already visited, i.e j = me, i, u(e]s masked.
We reshape the attention scores by using
C tanh
Tio tyh V4
Ve <t
(e)
(4)
otherwise.
h(c) is computed via attention attention-reshaping heuristics. In practice, for TSP and CVRP, h(e) = He., where the hcuristic matrix and c is simplified to the current node.
For the autoregressive NCO models with light encoder and heavy decoder [51], or only decoder [14], the last decoder layer computes logits using:
u; W.h.,
(5)
where W. is a learnable matrix at the output layer and node i is among the available nodes. We reshape the logits with
W4 Woh; + H
(6)
where node e is the current node.
For evaluations in Table 3, we generalize the models trained on TSPI00 and CVRPI00 to larger instances with 200, 500, and 1000 nodes. For TSP, apply the same ReEvo-generated heuristic across all sizes, whereas for the CVRP, distinct heuristics for each size due the observed variations in desirable heuristics.
D Benchmark problems
D.1 Traveling Salesman Problem
Definition. The Traveling Salesman Problem (TSP) is a classic optimization challenge that seeks the shortest possible route for a salesman to visit each city in a list exactly once and return to the origin city.
Instance generation. Nodes sampled uniformly from [o, 1J2 unit for the synthetic datasets.
D.2 Capacitated Vehicle Routing Problem
The Capacitated Vehicle Routing Problem (CVRP) extends the TSP by adding constraints on vehicle capacity. Each vehicle can carry limited load, and the objective minimize the total distance traveled while delivering goods various locations.
Definition.
Instance generation. For $ 5.2, We follow DeepACO [94]. Customer locations are sampled uniformly in the unit square; customer demands are sampled from the discrete set {1, ....... 9); the capacity of cach vehicle is set to 50; the depot is located the center of the unit square. For $ 5.5, use the test instances provided by LEHD [51].
D.3 Orienteering Problem
Definition. In the Orienteering Problem (OP), the goal is to maximize the total score collected by visiting nodes while subject to maximum tour length constraint.
Instance generation. The generation synthetic datasets aligns with DeepACO [94]. We uniformly sample the nodes, including the depot node, from the unit [0, 1/2. We use a challenging prize distribution [36]
dos (1+ 99 max²_1 day 1/100, where du. is the distance between the depot and node i. The maximum length constraint also designed be challenging. suggested by Kool et al. [36], we set to 3, 4, 5, 8, and 12 for OP50, OP100. OP200. OP500, and OP1000, respectively.
D.4 Multiple Knapsack Problem
The Multiple Knapsack Problem (MKP) involves distributing set of items, each with given weight and value, among multiple knapsacks to maximize the total value without exceeding the capacity of any knapsack.
Definition.
27

---

Instance generation. Instance generation follows DeepACO [94]. The values and weights are uniformly sampled from [0, 1]. To make all instances well-stated, uniformly sample e; from (max wijs 2 wsy)-
D.5 Bin Packing Problem
The Bin Packing Problem requires packing objects of different volumes into finite number of bins containers of fixed volume way that minimizes the numher of hins used. It is widely applicable in manufacturing, shipping, and storage optimization.
Definition.
Instance generation. Following Levine and Ducatelle [39], we set bin capacity to 150, and item sizes are uniformly sampled between 20 and 100.
D.6 Decap Placement Problem
The Decap Placement Problem (DPP) is critical hardware design optimization issue that involves finding the optimal placement decoupling capacitors (decap) within power distribution network (PDN) to enhance power integrity (PT) [65, 69, 16, 63]. Decoupling capacitors are hardware components that help reduce power noise and ensure stable supply of power to the operating integrated circuits within hardware devices such CPUs, GPUs, and AI accelerators [65]. The DPP is formulated problem, where the goal is to determine objective is contextualized by the target hardware's feature vectors, with the constraint a limited number of decaps. Interested readers can refer to [31] for more details.
Definition.
black-box contextual optimization objective. This
best positions for a set decaps to maximize
Instance generation. 10 x 10 PDN instances are used. We generate training and validation instances following Kim et al. [31]. The test instances are directly drawn from [31].
E
Generated heuristics
This section presents the best heuristics generated by ReEvo for all problem settings.
def heurietics (distance matrix: torch, Tensor) >> torch, Tenzor:
(disttnceeetaaa
1e5
gazza 0.5
reciprocal
cestaance_aatiii
log_valses
(ddsttdaneeeeenoooooooooooo xatrii)
local_boc log. values
(reciprocal noaddirrl kropdix--ruo)) reciprocal)
global, nean distance_ratee zatris.neant)
global hea ggzna corch. log(occc abs xatrix global_ncan)) heu local_heu global_beu
Heuristic 1: The best ReEvo-generated heuristic for TSP_NCO_POM POMO.
def houriaticaddistaace _aatrix: torch. Tensor) torch.Tensor:
diatance, Bettaanc__aariz..ittti wwwtrii..iz.((
Calculate the average distance for each mode with syussrical adjustaents
aug distaacee
natrix, dipsi, keopdin/Trus) worddh.uunddsttacco_eecc... dias0, koepdiasTzue) anaguaezee()) difference
torcb.ding(dlattnn
1))
Calculate houristics
average distances vith axphazia
centric avarages
beuriatics 2 (Gistancs_natrix dig_anna))) 6.5 (distanno__aerix barch.ewan(iittess.aerrrii dinet, keepdin
Norral hearistice to have a mean standard deviation
hauriatica (heuriatiica torch. (aturiatic)) (orchi.)le((mnrrtstiica))) sorch.atd (tdraaattdd(ee)itttii))
retuzn Learistica
Hcuristic 2: The best ReEvo-generated heuristic for TSP_NCO_LEHII
* For CVRP200
def heuriation couriatiex(dii ceiiiccdiee (diattnce aettrii: tarch. Tenzor, demands: tarch. Perchr) tarch. Pensor:
distance aatrii.
Csleulate the normal find desand-eecatty for each adge den.ndd
deaands, ries(a, (distance_natrie
Bornslszing factor
Set penaltien adgex arceading capacity
hauristicx
heurictics norn, www.ddddddeddeeeed heuristice (torch, mer (derands.. view(n, 1), derands.viedt n))
28

---

Bearistics
$ For CVRP500 and CVRP1000
def souziattcaadissaancc patrix: torch. Tensor, derands: tozch. torch.Tensor)
torch. Tensor:
panalty torch. borch..nxiiunnaaennnee
deranda,,
retuzn (distance_aatrra 1u-6)
wacezo, Secceaa,_dmandd.co penanddaaaaatt
Hcuristic 3: The best ReBvo-generated hcuristics for CVRP_NCO_POMO.
For CVRE200
heurietics (ttccccceeaaceecsse maatre. Iensor,
total demand demande. nun()
normalized, dezand dexands total_ denand
balanced, penalty tozch. (deaadd (1) over wttp:ccapcccyaaeeeeccc heuristics balazced_ hetpl_ddcc____ppgpeee poights boraalizoddeeaate vies( 1, 1). norral 2tover pepper.spacctyy.cmaake return bearistice
(distance.
1e-8)
uuquuezze maxe0)
det hearietacosdterase matrix: torch, Tensor, derands: torch, Teneor) torch. l'ensor:
total, demand torch, cdrauuddddddddde diaro)
vehicle capaciiyyy total_denan[[1])
exceed cxpeei_ capacisy.ppually wazer, donarddd penalty (vehicle, capacity total, dexand) clamp (miar0) cobicil_capacity
(msqueesu()) vehiclo,capacity) .flaa(()
prozieiness
(dietance_aatres matrii 1)) (1 0.5 exceed sapacitt_pennattte 0.5 unset, canand_eeaalty))
promiiinss
t For CYRP1000
def beuristica (erilattcadiisaasesee pntriii torch. Tensor, derands: tozch. Conch.Tensor)
torch. Tensor:
total, desamt_sors demanda total_
denands.
edge_sariag saviage distance natrix decasd Jone] Gemand_ncxm return odgo savings
Heuristic 4: The best ReEvo-generated heuristics for CVRP CERP_NCO_LEHIE
Crossover
def cramacver(parent up ap.nnarray, n_pop: int) +2 sp.ndarray:
n_decap parents. parente_idr up.randox.chooeec. crossover_paintt www.rnoo...ndnnnn nudecap, n.pop)
(t_pop,
mask up tilefap arangela_decapp. (n.pop, 1))
offepring chere crossover_potnss reshape(-1,
parents (parente idxl; 0),
prrettopprente_aarr 1], :])
reborn offepring
Mitabtion repairing step
feacibilaty the population)
def mutatsoon (population: np- addrdaray, probe: ins, probibit: sp.ndarray, size: int 100) up ad.adarray:
n_decap population. shape
(ppalllpoolatiiio prr_prooibieed up ap.all(ap ioin(populaciinn, prohibit, Invert-Truo), axiav1)
axte=1)
15, feasibbb ic_cot_proot & 1s_not_probibite
mutation_mack up ro..ranonn rand(p, n_decap) < 0.1
autation, sp.randon. randiat sizen(p, a_decap))
mutated, populatioo np. (muratios_nssd) is_feastble(; Houc], autation, voluce, population)
return populatiio
Heuristic The ReEvo-generated heuristic GA.
Calculate average for mp.ndarray: average_diatenn distance mp-rean (aa detasssentttrss axis=1)
Manriaticxddixxteee sp.ndarray)
ranking for
dtstanca ranking up ap.argoort (dietance_mstriss azte=1)
Calculate of closest distances for each sode
claset_mennddiaaeee up. in..mmndiisaaacoommm Cog.raaaaaaaccaaaaaeeeeeeeeeeee axis-1)
distance,rankingii
Initialize the indicator natrix and caloulate ratin of dixtance distance indicators distance xatrix average_dtstancee distancee, ap.nevarie]
Set diagonal alanmta to in-inf filffil..d dill..iagooalllieeco (indicatore, inf)
Adjust indicatar ratris uxing staciatios) zeazоra
indicators ** wewpsst_rannddittncc.c. nevxx1s] ap..cnndietttcc.mmrtttt matrix, axte-1)(;, nevaxis)

---

Heuristic The best -eEvo-genecaaed heuristic for TSP_GLS.
Hcuristic 7 presents the best heuristic found for TSP_ACO, which is generated when viewing TSP as a black-box COP. "edge_attr' _atrr' represents the distance matrix.
import nuzgy
aklears. propeoccsesspe isport StandardSosle:
def heurietics(edge attr: up ndarray) xp. ad.anarr.y:: nus, vdgea udge_attr. shape (0)
attributes odgo_attz. shape
heuristic up. 2eroa Like (edgeedge
Apply eeginerring transformed asir u.. www.ooppeep.aaaeeeee..
attributea
Taking logaritha
actribates
# Norral iow adge attributea StandardBealer()
wige_attr_nore acaler. trraanformmrrmmaoomdee...
# Calculate corzelation confficients
corralation up.corrcant (elge_attr_nommm]]
Calculato heuristic value for each edge actribute
for in (nun, edgus):
in ronge(aus (angeeaus_attiiiieee iitr:ieee)):
if aign_attr_noree valuiat [5] sp.axp(-8 (i) correhatiimm.ttriis(1....
Heuristic 7: The best ReEvo -ennerate heuristic for TCO_ACO.
heuristica
up ap.adarray, coordisates: ap.adarray, domands: up ap.adarray, capacity: iat) ap adarray: nux nodes dietance_satrre pateeisattttt.....a [0)pe
Calculate
distance
Inowrse_diatane www.dddittanttttrrdeeee sp.divida(1, distamca_matrik, vheree (diaatannnnnnnrtti 6))
# Calculate total demand and average denand denand (deaannd) average_denunl total_ deraind nun_sodes
# Calculate the distance from euch node the starting dapat. depos distandistances Sastance_aatrist..
calculate the rensining capacity of the vehicle for each node remsining. capacity derands
hauriatic heuristic_netrie ap.cero. 1ike (daldddtance_saaa
Calculate denand and total_derand
factor
desand factor distance antris / mp.rae(disttmee_ne matrix) norsal distaace distance factor dipot_diatance / dormllgpe distance app.fiafo((lott).pa)
Tearata over each node for in range (oduas)dea):
based bouriatic inverse, wwt.://sttttteeueeiileee.. (1. (norxalized, [istance[]] 20)
Calculate
capacity
Adjust the baaristic valusa based the rensining capacity pouristie_valuee np. (reeeerennnnnncco ceperrrrrceestssscooooct
decandeli) [i], beurtetic.roluee
Adjust the bauriatic valuss based on the desand factor pouristic.valos values denandd_accto[s]] average__esane
based heuristic, valuse valuse =- distance, factor[s] sorristie.vve valuwe
Adjust bauristic
factor
Exclude the depot: mode
Adjust the beurietic valuen based on the capacity utilization uesl cowtionnfacteee factar up vhera www.sernnsiiiinnggge..n.nnn.nnne (wwnsining..cppennee capasitty >- demonda(t], capacity [s]a,ds[s], 0)
heuristic, values utilization factor
hauriatic for current
hauristic
catrristt__zatri/ittt bourtstic, values
30

---

Hcuristic 8: The best geneo--eedertedd heuristic for CVRP_ACO
def beuriaticx(prize sp.ndarray, distance: up.ndarray, flosi) up, addaaaary::: prize chapp(()
hauriaties "p. (aronk(n m))
Calculate grize-to-diatane ratio power transformation prize,diatten wtt.i//iittnneerattee up- np-pover power(prize (priza distance,
Find the indi of valid bazed the distance constraint (diatance
velid_aigen
Ansign the prize-to-diatance ratio to the valid edges bouriaticx [vwlldd wdges bttise_ditttnoerrae wttp:eearaooloolddeeoo..
reburn bearlatica
Heuristic The best beBvo-genernan heuristic OP_ACO
Heuristic 10 presents the best heuristic found for MKP_ACO, which is generated when viewing MKP as black-box COP. ftem_attrl' and qeem_att22' represent the prizes and multi-dimensional weights of items, respectively.
der heuristica(tten, attr:: up ad.adarray, Iten_atie2: ap.ndazray) >> up adarray:
itea, acwa_attr..ccmm shape
Normaline attrr itea_attu2
itez, attrl norm attrl up.nia(ites, attri)) (ap.nax(1ten attri) ap.ain(itcan attzl))
stem attr2 (itex_attr2 (it(tte_.attr)) (op.max(tte__attr)) aptaa
average
arganited
normslized attribute each awx_tttr2 up (ites, axis-1)
Calculate
# Galculate the of nornalized attribute 2 for each itea axises)
up.oun(ites_atre
Calculata the atandard deviation of normalixed attribute for each itan atd_attr2 ap.atd(ttas pore, axis-1)
Calculata beuriatics
coshination nermalized
and
while considering the average, sun, and scandard deviation of nomalized attesiuce heuristics (tten_attri_uan) zaz attr2) attoa_attzi_aan arg_attri) attri sta_attr)) (1
Norral isw the hecristica to a range [o, 1] bouriatica (bwuriatics (berrii(tte)))ccce))
(up.maa((wuraatio) (p.nia((ouriticca)
return
Heuristic The best ReBvo-generated heuristic for MKP_ACO.
dof cruriatics(desande up pdnndarryy, capacity: lns) up addarra::.: demand. shap=(0)
dexand, pormalized dexand desand. max((
sy up. (capacity dasand(: Jone] demand) capacity)
overlap panalty (desand[: (:,, Mone] domand) capacity
heuristica derand, denand_ moedalisedd:: Nose] Henand__orrsalsse same bww.bin..ematty cmarlap.pemally
threshold up. peepprentieellerrieeee 90)
heuriatica (bsuriatica threshold)
bearistics
Heuristic 11: The best MeEvo-geneerate heuristic for BPP_ACO.
Heuristic 12 gives the best-ReEvo generated constructive heuristic for TSP. We used the best heuristic found in
AEL [46] as the seed for ReEvo. As a result, our heuristic closely mirrors the one in AEL,, scoring each node mostly using weighted combination of the four factors.
select_poxt poxt,
1nt, destination, 2ode: ist, unvicited set, distance zatrix: up ndarray)
31

---

('distance,
"average.divtanne : 0.25,
dev. dered_deeddiaaaeeee distance, to unvis 0.25,
'distance, to, destimationss 0.1)
for unviaitel_undea:
Iuturo futuro_distascee distances [distance, wat.icoo__ttiiiiiieeeeee (node, 1] foz in wavinlted,nodea 1. node]
if future, future_diaten distanous:
distancs_tee st_.mc...._niiiited
Len(Cutur_ddistance
std_ddy__daatanee www.stnce.t.oonvittteetee..
(nun((s average, to_mvvaittee)
in future_ distancee))))) /
futurw, Iuture_distann (istannema) 0.5
elae:
average.diaten dinrageddittanee.
scorw (wuightal d'dia to, current Siattnnc_matriiie (eutrii(errrntttnoe node, mode]
veightal averaage distance tt, to..tviiiiiiieeeeooo ited average. distance, toanvisiied
weighta atddd distance, toroeetttuuurrree tnjunviaitan itad!] sed__dy__dddttadee tou
seighta ('diatasce, destinttinn) distence (deat inttiiiiiionnndde noda])
scorwa [nnde]
naxt_noče win (scoras, key=acarea.ge
relazn seat__ode
Hcuristic 12: The best
heuristic for _Sn_ctnstr
F Licenses for used assets
Table 11 the used assets their licenses. Our code licensed under License.
Table 11: Used assets and their licenses.
Type
Asset
License
Usage
NeuOpt [52]
MIT License
Evaluation
GNNGLS [24]
MIT License
Evaluation
EoH [47]
MIT License
Evaluation
Code
DeepACO [94]
MIT License
Evaluation
DevFormer [3]]
Apache-2.0 license
Evaluation
POMO [37]
MIT License
Evaluation
LEHD [51]
MIT License
Evaluation
TSPLIB [67]
Available for any non-commercial use 2p0 license
Testing
Dataset
DPP PDNs [63]
Testing
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims include SOTA heuristics generated by ReEvo and SOTA sample efficiency of ReEvo. They accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be pereeived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation long it is clear that these goals attained by the paper.
2. Limitations
Question: Does paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See 7.
Guidelines:
The answer NA means that paper has no limitation while answer means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust results are violations these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
grounds for rejection,
Theory Assumptions and Proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: This paper does include thcoretical results.
Guidelincs:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
33

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Full experimental details and results are provided in S, $ 6, Appendix B, Appendix C, and Appendix D. Our code is also available.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example. if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g.. a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g.- with open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, which case authors are welcome to describe the particular way they provide for reprodueibility. In the case of closed-source source models, it may be that access to the model is limited in some way (c.g.. registered users), but it should be possible for other rescarchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code. with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Our code is available, with sufficient instructions to faithfully reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
wwwpanisssioooPooiooooo for more details.
While we encourage release of code and data, we understand that this might not possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g.. for a new open-soure benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /// //nips...//////////// cc/public/ Seaiddes/Coce@uumisssiooom/
for more details.
34

---

The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommeneed, but including URLs to data and code is permitted.
6. Experimental Setting/Detann Details
Question: Does the paper specify all the training and test details (c.g,, data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See 5, 6, Appendix B, Appendix C, and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Fig. 3, Table 4, Fig. 4, Table 5, ctc.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should given (e-g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error than state that they not verified.
CL, if the hypothesis of Normality of errors
asymmetric distributions, authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). crror bars are reported tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, docs the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
See Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
35

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, every respect, with NeurIPS Code of Ethics
cc/ htt.eu.pp.../pp..iiaaaaaaoo.o...
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Hcuristic design automation is a long-standing pursuit. Our contributions towards discussed in and $
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative socictal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance). fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example. is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (c.g., gated relcase of models, providing defenses in addition to attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example hy requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
36

---

We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Appendix F.
Guidelines:
The answer means that the paper does not use existing assets.
authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (e.g.. g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g.. website), the copyright and terms of service of that source should he provided.
If assets released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new
Guidelines:
The NA means that the paper does release
Researchers should communicate the details of the dataset/code/model part of their sub- missions structured templates. This includes details about training. license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
answer means that paper does not involve crowdsoureing nor research with human subjects.
Including this information in supplemental material is fine, but main contribution of paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Beard (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants. whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
37

---

Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
38


Reviews:
[{"review_id": "myl1atCBvO", "reviewer": "Reviewer_v9WQ", "summary": "The paper's contributions consist of multiple sections, which could be orthogonal:\n1. The paper proposes a new ReEvo algorithm within the class of string-mutation evolutionary search methods. The core idea is to add a \"Reflection LLM\" which observes patterns over the history of trials, and proposes a new generation instruction for the regular Generator LLM.\n2. This algorithm is applied on the area of combinatorial optimization, to mutate the code specifying a search heuristic.\n\nExperiments are conducted to:\n1. Show better heuristic search over a variety problems and situations like Travelling Salesman (TSP), Ant Colony Optimization, Electronic Design Automation, and Neural Combinatorial Optimization\n2. Ablate the importance of using the \"Reflection LLM\" especially over longer terms, and outperformance over other string-mutation methods like EoH.", "questions": "Please address my weaknesses above.", "limitations": "Yes, in Section 7 (Conclusion).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* This paper is very well written and structured. It demonstrates a strong understanding of the current literature and the nuanced differences against previous works, and their strengths/weaknesses.\n* The paper supports itself well with numerous experiments among multiple dimensions (e.g. varying combinatorial optimization applications, ablation studies on its own components, comparisons against other string-mutation baselines).\n* Overall, the paper does not have any glaring weaknesses and should be a solid accept.", "weaknesses": "* The current writing style is a bit too strong on the evolutionary side (e.g. targeted towards an audience like GECCO), which makes parts of the paper unmotivated to readers who are not deep into the evolutionary literature. It becomes too easy to view the paper as a incremental improvement in the class of evolutionary string-mutation methods, which in itself is a good contribution, but not groundbreaking given previous works (PromptBreeder, FunSearch, and other works that the paper itself has cited). \n  * There are possibly better ways to phrase the paper to make the method more natural. For example, I believe the Reflection LLM with its short-term + long-term variants, is effectively a technique to load in-context samples without incurring memory-blowups.\n* It is unclear whether ReEvo can be applied to any other string-based optimization scenarios (e.g. Prompt optimization, generic code search). Currently the Reflection LLM is very targeted towards summarizing combinatorial heuristics. If so, this would be nice to touch upon, or if not, this should be listed in the limitations section.\n  * Following up on the above comment, this could imply that ReEvo is over-engineered at the moment; is there a more general and simpler variant of it, applicable to any string problems?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in reviewing our work, the insightful questions and suggestions you raised, and your recognition of our contributions. We respond to your comments below.\n\n> W1: The paper's evolutionary focus may be limiting its appeal and perceived novelty to a broader audience, and rephrasing it to emphasize the method's natural approach could be beneficial.\n\nThank you for providing a fresh perspective on the technical presentation. We will adopt your suggestion to generalize the description of the reflection technique. As you suggest, this approach loads in-context knowledge without causing memory blowups. We believe this could broaden its appeal to a wider audience.\n\n\n> W2: The paper should clarify ReEvo's applicability to other string-based optimization scenarios and consider discussing a more generalized version of the method.\n\nThank you for this valuable suggestion. ReEvo is generally applicable to other string-based optimization scenarios as long as the reflecting over the relative performance of strings is meaningful. We exemplify its generality by applying it to prompt learning. We evolve prompts for formal logic reasoning task from MMLU, using random search, vanilla GA, and ReEvo, respectively. The results below present the classification accuracy against the number of prompt evaluations, where ReEvo demonstrates superior sample efficiency.\n  \n\\# prompt evaluations | 4 | 8 | 12 | 16 | 20\n--- | --- | --- | --- | --- | ---\nRandom Search | 10  $\\pm$ 0 % | 10  $\\pm$ 0 % | 10  $\\pm$ 0 % | 10  $\\pm$ 0 % | 10  $\\pm$ 0 %\nVanilla GA | 10  $\\pm$ 0 % | 22 $\\pm$ 8 %| 25 $\\pm$ 12 %| 37 $\\pm$ 8 %| 38 $\\pm$ 9%\nReEvo | 10  $\\pm$ 0 % | 37 $\\pm$ 5 %| 43 $\\pm$ 2 %| 45 $\\pm$ 0 %| 45 $\\pm$ 0%", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eERjVosABM", "reviewer": "Reviewer_zrFg", "summary": "This article proposes a large language model (LLM) assisted evolutionary computation (EC)-based method, to solve combinatorial optimization problems. It incorporates a reflection mechanism to enhance performance in black-box settings.", "questions": "1. As an EC-based method, what is the primary distinction or improvement compared to EoH, FunSearch, and other similar methods [1,2,3]? The reflection technique was developed early and is widely used in prompt engineering and code generation(Shown in Weakness1). To what extent do you think designing more complex reflection and prompt engineering strategies contributes to optimization [4]?\n2. In the ablation experiments, Please include ReEvo based on more open-source LLMs (such as DeepSeek and Gemini).\n3. Testing on the online bin packing problem is recommended [5].\n4. In Table 1, the result of EoH is drawn from the literature, testing it with the released code would be beneficial.\n5. ReEvo requires three LLM calls to complete a single iteration, while other compared EC+LLM methods (such as EoH) only need one LLM call per iteration. Considering the comparison in the degree of LLM calls would be beneficial.\n\n[1] Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arxiv preprint arxiv:2309.08532 (2023).\n[2] Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization. arxiv preprint arxiv:2405.05767 (2024).\n[3] Large language models as evolutionary optimizers.\" arxiv preprint arxiv:2310.19046 (2023).\n[4] Are Large Language Models Good Prompt Optimizers?. arxiv preprint arxiv:2402.02101 (2024).\n[5] Mathematical discoveries from program search with large language models. Nature 625.7995 (2024): 468-475.", "limitations": "N/A", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "1. The method shows an impressive performance on several CO problems with a black-box setting. \n2. The article is well-written.", "weaknesses": "1. The reflection technique has been well-developed and widely used in prompt engineering and code generation [1,2].\n2. Evolution methods based on LLM have been adopted in EOH [3] and Funsearch [4], limiting the contribution to the framework.\n\n[1] Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems 36 (2024).\n[2] Promptbreeder: Self-referential self-improvement via prompt evolution. arxiv preprint arxiv:2309.16797 (2023).\n[3] Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model. Forty-first International Conference on Machine Learning. 2024.\n[4] Mathematical discoveries from program search with large language models. Nature 625.7995 (2024): 468-475.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in reviewing our work, as well as the insightful comments and questions you raised.\n\n> W1: The reflection technique has been well-developed and widely used in prompt engineering and code generation.\n\nThank you for raising this point. Our work introduces a novel integration of reflection with evolutionary search. As noted by Reviewer v9WQ, this integration is effectively a novel technique to load in-context knowledge without incurring memory blowups.\n\nWe respectfully draw your attention to the fact that the reflection techniques, which were initially proposed at NeurIPS 2023 [1, 2], are still under active development. Adapting reflection for a downstream application itself constitutes a valuable contribution; recent examples include its application to translation tasks [3, 4].\n\n\n> W2: Evolution methods based on LLM have been adopted in EoH and Funsearch, limiting the contribution to the framework.\n\nThank you for highlighting the work done in EoH and FunSearch, which we extensively cite and acknowledge in our paper. These groundbreaking studies indeed lay the foundation for our work. We draw significant inspiration from them and aim to extend their contributions in meaningful ways.\n\nWe believe that the combination of LLMs with EA for CO can be explored through three primary lenses: (1) the search algorithm, (2) the downstream CO applications (the search space), and (3) the evaluation methodologies (ways to evaluate how well we search). We believe our work contributes to all three aspects:\n\n- **Search Algorithm**: We introduce the Reflective Evolution method, demonstrating its superior sample efficiency.\n- **Applications**: Our work broadens the scope by applying this paradigm to five heterogeneous algorithmic types and six different combinatorial optimization problems, advancing the state of the art in GLS, EDA, ACO, and NCO methods.\n- **Evaluation Methodologies**: We employ fitness landscape analysis to explore the underlying mechanisms of our proposed method; we establish black-box experimental settings to ensure reliable comparisons and practical relevance to real-world applications.\n\nWe believe that building upon and extending the foundations laid by EoH and FunSearch, as we have done, constitutes solid contributions.\n\n\n> Q1-1: The primary distinction or improvement over prior methods.\n\nPlease refer to our response to W1 and W2.\n\n> Q1-2: The contributions of designing reflections and prompt engineering.\n\nWe verify its contributions in Section 6. They are important for better sample efficiency (e.g. using less than 100 evaluations for designing strong heuristics). Sample efficiency is crucial for real-world applications where heuristic evaluation could be expensive.\n\nReflection is more effective when using capable LLMs, such as GPT-3.5 Turbo and its successors, as discussed in prior works [1]. Allowing a large number of heuristic evaluations, or implementing weak open-source LLMs, could obscure the impact of reflection or other prompting techniques, as reported in [5].\n\n> Q2: Implement ReEvo based on more open-source LLMs for ablation.\n\nAccording to Shinn et al. [1], \"self-reflection relies on the power of the LLM’s self-evaluation capabilities and not having a formal guarantee for success.\" Currently, many open-source LLMs are not capable enough to guarantee the statistically significant improvement of reflections. However, as LLM capabilities improve, we only expect this paradigm to get better over time [1].\n\n> Q3: Testing on the online bin packing problem.\n\nBelow we present the comparative results on online BPP (weibull 5k), which are averaged over 3 runs.\n\n| EoH iteration         | 0      | 1      | 2      | 3      |\n| ----------------- | ------ | ------ | ------ | ------ |\n| total evaluations |        |        |        | 135    |\n| best obj. (mean)  | 4.2844 | 4.2844 | 4.2744 | 4.2511 |\n| best obj. (std)   | 0.0000 | 0.0000 | 0.0141 | 0.0286 |\n| best obj. (min)   | 4.2844 | 4.2844 | 4.2545 | 4.2145 |\n\n| ReEvo iteration | 1 | 2 | 3 | 4 | 5 | 6  | 7 | 8 | 9 | 10 | 11 |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| total evaluations | 30 | 40  | 45 | 55 | 60 | 70 | 75 | 85 | 90 | 100 | 105 |\n| best obj. (mean)  | 4.2844 | 4.2844 | 4.2844 | 4.2844 | 4.2844 | 3.1026 | 3.0560 | 3.0560 | 3.0560 | 1.6379 | 1.6379 |\n| best obj. (std)   | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 1.6713 | 1.6394 | 1.6394 | 1.6394 | 1.1943 | 1.1943 |\n| best obj. (min)   | 4.2844 | 4.2844 | 4.2844 | 4.2844 | 4.2844 | 0.7390 | 0.7390 | 0.7390 | 0.7390 | 0.7390 | 0.7390 |\n\n> Q4: Testing EoH with the released code\n\nWe will test EoH with its released code and update the results.\n\n> Q5: Comparisons based on LLM calls.\n\nReEvo doubles LLM calls when performing crossover. However, we believe LLM inference can be easily sped up by scaling up hardware, and is rapidly technically evolving on both algorithmic and hardware fronts. In contrast, evaluating the generated heuristics can be costly in real-world applications. Therefore, we believe that comparisons based on heuristic evaluations are more practical and meaningful.\n\n**References**:\n\n[1] Shinn et al., Reflexion: language agents with verbal reinforcement learning, NeurIPS 2023\n\n[2] Madaan et al., Self-Refine: Iterative Refinement with Self-Feedback, NeurIPS 2023\n\n[3] Wang et al., TASTE: Teaching Large Language Models to Translate through Self-Reflection, ACL 2024\n\n[4] Chen et al., DUAL-REFLECT: Enhancing Large Language Models for Reflective Translation through Dual Learning Feedback Mechanisms, ACL 2024\n\n[5] Zhang et al., Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WUHaywGFBj", "reviewer": "Reviewer_qdUQ", "summary": "The paper presents a LLM-enhanced evolutionary algorithm to solve diverse combinatorial optimization problems. The method is evaludated on various COPs and heuristics, however, the advantage of proposed method compared to recent ML4CO methods that does not use LLM requires more specification.", "questions": "1. What result does figure 4(B) shows, the obejective value or the gap towards the optimal? Without specifying the evaluation metric, it is difficult to interpret the results.\n2. How does the proposed method compared to recent ML4CO method on TSP [1,2], or probably other methods on VRP? From my experience, hyper-heuristic methods may not perform well as these methods on solution quality or solving time. What is the advantage of LLM-enhanced heuristics in these COPs?", "limitations": "The paper discuss some limitations, but the method may be limited by cost of LLM inference and problem scale.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposed a LLM-enhanced hyper-heuristic model to solve various combinatorial optimization problems.\n2. Extensive experiments show the efficacy of the proposed method on five different COPs and multiple heuristics.", "weaknesses": "1. Some details of model is not fully specified from the text, including the meaning, output of \"short-term reflection\" and \"long-term reflection\". It is unclear how the process is done and how this process completes the \"reflection\"？\n2. Though the proposed method has demonstrated the advances compared with heuristics, on specific problems (take TSP as example), there might be some recent models undiscussed in this paper that does not use heuristic but still achieve competitive results, such as [1,2] that conducts TSP experiments on 1000 and 10000. \n3. The paper does not specify the costs of using LLM APIs, which could be real challenges when readers want to follow and reproduce the results in this paper.\n\n[1] Qiu R, Sun Z, Yang Y. Dimes: A differentiable meta solver for combinatorial optimization problems[J]. Advances in Neural Information Processing Systems, 2022, 35: 25531-25546.\n[2] Li Y, Guo J, Wang R, et al. From distribution learning in training to gradient search in testing for combinatorial optimization[J]. Advances in Neural Information Processing Systems, 2024, 36", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in reviewing our work, as well as the insightful comments and questions you raised.\n\n> W1: Details of reflections.\n\nWe will revise the writing for better clarity according to your suggestions. An example of both short- and long-term reflection is illustrated in Figure 1(b). The process prompts LLM to reflect upon the relative performance of two heuristics (short-term), and accumulate such knowledge over iterations (long-term). The inputs and outputs of the reflection process are all texts.\n\n**Short-term reflection.**\n- Inputs: Two heuristics to crossover and indicators of their relative performance.\n- Outputs: Text-based reflections upon the performance of the two heuristics, i.e. why the better heuristic is better, and how the worse heuristic can be improved. It is analogous to a verbal gradient derived from the performance comparison.\n- How it is utilized: ReEvo incorporates the short-term reflections into the crossover prompt, leading to more informed offspring.\n- Meaning: LLM reflects upon the performance of the two heuristics, providing insights for better heuristic design. It only targets the two heuristics for the current crossover, and does not consider the historical performance of the population.\n\n**Long-term reflection.**\n- Inputs: prior long-term reflections and short-term reflections of the current iteration.\n- Outputs: Text-based reflections upon the overall performance of the population, and strategic hints for better heuristic design.\n- How it is utilized: ReEvo incorporates the long-term reflections into the mutation prompt, leading to more strategic exploration.\n- Meaning: LLM accumulates knowledge over iterations, combining past experiences with new insights to offer long-term strategic hints.\n\n> W2: Undiscussed recent baselines.\n\nWe comprehensively compare against 25 baselines across 6 COPs and 5 algorithmic types, under both black-box and white-box settings, and in terms of both LHH and generated heuristics. 8 of these baselines were published after 2023. We show that LHH can enhance ML4CO solvers in Section 5.5, involving TSP/CVRP with 1000 nodes. \n\nHere, we compare against the suggested SOTA baselines, on TSP500 and TSP1000 each with 128 test instances. Below we report the optimality gap and running time for solving all instances. They indicate the competitive performance of GLS-ReEvo. Please note that T2TCO requires optimal solutions for training, which may not be available for many problems, while ReEvo only requires heuristic evaluations.\n\nMethod | TSP500 (gap; time) | TSP1000 (gap; time)\n--- | --- | ---\nDIMES | 1.76% (2.2h) | 2.46% (4.6h)\nT2TCO | 0.37% (16m) | 0.78% (55m)\nGLS (16 CPU cores) | 0.39% (12m) | 0.80 (2.6h)\nGLS-ReEvo (16 CPU cores) | 0.25% (12m) | 0.72% (2.6h)\n\n\nWe respectfully bring to your attention that LHH and ML4CO [1] are complementary, each with its unique strengths and limitations. Some advantages of LHHs over ML4CO are:\n\n- LHHs generate interpretable heuristics (code snippets), while ML4CO usually generates black-box parameterized policies. Interpretable heuristics offer insights for human designers and can be more reliable in practice when faced with dynamic environments, limited data, distribution shifts, or adversarial attacks.\n- LHHs generate heuristics that are more efficient in terms of computational resources, as they do not require GPU during deployment.\n- LHHs require only less than 100 heuristic evaluations and about 5 minutes to evolve a strong heuristic, while many ML4CO methods require millions of samples and days of training. When the solution evaluation is expensive, LHHs are more practical.\n- LHHs only need some text-based (and even black-box) explanations to guide the search. ML4CO requires the development of NN architectures, hyperparameters, and training strategies, where informed inductive biases and manual tuning are crucial to guarantee performance.\n\n[1] https://github.com/Thinklab-SJTU/awesome-ml4co\n\n> W3: The cost of using LLM APIs\n\nAs reported in Appendix B (line 858), each run costs about $0.06 when using GPT3.5 Turbo.\n\n> Q1: The y-axis of Figure 4(B).\n\nAs indicated by the y-axis label, Figure 4(B) shows the objective value of the best generated heuristic, against the number of heuristic evaluations for an LHH.\n\n> Q2-1: Comparisons with recent ML4CO method on TSP and VRP.\n\nPlease refer to our response to W2.\n\n> Q2-2: Advantage of LLM-enhanced heuristics over ML4CO methods.\n\nPlease refer to our response to W2.\n\n> Potential limitations regarding LLM inference cost and problem scale\n\nPlease also refer to our response to W2 and W3.\n\n**Inference cost.** Please note that we don't need LLM inference once the heuristic is generated, and the generated heuristics are efficient in terms of computational resources. For LHH search, deploying local LLMs is also feasible, as verified in our work with Llama 3.\n\n**Problem scale.** We have tested our method on large-scale problems, such as TSP1000 and CVRP1000. LHHs are currently most effective when integrated with existing algorithms. As long as the algorithm is scalable, its LHH-enhanced version is scalable as well.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5tysPhsZwe", "reviewer": "Reviewer_2Tkz", "summary": "This paper studies how to search for the best heuristics for combinatorial optimization problems (COPs) with large language models (LLM). The key idea is to use genetic programming (GP) to dynamically update the heuristics with LLM. Short-term reflection and long-term reflection are also incorporated in the GP algorithm as the guidance. The proposed methods are demonstrated on five different COPs and compared against other heuristic solvers and neural solvers.", "questions": "I would appreciate the authors' response on my main concerns listed above.", "limitations": "I have no concerns regarding the impact of the manuscript.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Applying LLM to generate heuristics for COPs is novel.\n\n2. The experiements are extensive and in detail.\n\n3. The paper is well-written and the idea is easy to understand, except that the details of the GP algorithm are a bit vague.", "weaknesses": "1. The proposed ReEvo seems to rely on existing heuristic or neural solvers. Can ReEvo discover new heuristics independently? Incorporating LLM to generate heuristics for COPs is interesting, but it seems trivial if LLM can only be used as a post-processing to improve the existing methods.\n\n2. The experiments are not conducted with state-of-the-art (SOTA) methods. For example, on TSP problem, can ReEvo improve the LKH-3 [1] solver? Can ReEvo improve the non-autoregressive neural solvers such as DIFUSCO [2], T2TCO [3]? \n\n3. The writing in Sec. 4 needs improvement. For example, how the short-term and long-term reflection is utilized to improve heuristic design? how to guarantee the generated code is executable? \n\n[1] Helsgaun, Keld. \"An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems.\" Roskilde: Roskilde University 12 (2017): 966-980.\n\n[2] Sun, Zhiqing, and Yiming Yang. \"Difusco: Graph-based diffusion solvers for combinatorial optimization.\" Advances in Neural Information Processing Systems 36 (2023): 3706-3731.\n\n[3] Li, Yang, et al. \"From distribution learning in training to gradient search in testing for combinatorial optimization.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in reviewing our work, and the insightful questions and suggestions you raised. We respond to your comments below.\n\n\n> W1: Reliance on existing heuristic or neural solvers.\n\nReEvo can discover new heuristics independently but integration currently leads to better performance. In Section 5.4, we show that ReEvo can independently discover new constructive heuristics for TSP, which outperform the algorithm designed by traditional hyper-heuristics. \n\nReEvo improves the key algorithmic components of existing methods, such as the perturbation in GLS, the crossover and mutation in GA for EDA, the heuristics in ACO, and the attention in NCO. We leave it to future work to further explore its potential to independently discover new complicated heuristics. Under an agentic framework, by first designing a skeleton of the program and then each individual function, we may be able to generate high-performing long programs using LLMs.\n\n\n> W2: Experiments with SOTA methods, such as T2TCO, DIFUSCO, and LKH-3.\n\nLHH is complementary to your suggested SOTA methods. \n\n- LKH-3 is a specialized solver for the TSP, which has been heavily optimized for the VRP over decades. LHHs, on the other hand, are more general and can be applied to any COP. They are especially suitable for cases where expert knowledge is lacking or the problem is treated as a black box.\n\n- DIFUSCO and T2TCO require optimal solutions for training, which may not be available for many problems. LHHs, on the other hand, only require heuristic evaluations. We compare against T2TCO on TSP500 and TSP1000, each with 128 test instances. Below we report the optimality gap and running time for solving all instances. They indicate the competitive performance of GLS-ReEvo.\n\nMethod | TSP500 (gap; time) | TSP1000 (gap; time)\n--- | --- | ---\nT2TCO | 0.37% (16m) | 0.78% (55m)\nGLS (16 CPU cores) | 0.39% (12m) | 0.80 (2.6h)\nGLS-ReEvo (16 CPU cores) | 0.25% (12m) | 0.72% (2.6h)\n\n- LHH and general ML4CO [1] are complementary, each with its unique strengths and limitations. Some advantages of LHHs over ML4CO are:\n\n  - LHHs generate interpretable heuristics (code snippets), while ML4CO generates black-box parameterized policies. Interpretable heuristics offer insights for human designers and can be more reliable in practice when faced with dynamic environments, limited data, distribution shifts, or adversarial attacks.\n  - LHHs generate heuristics that are more efficient in terms of computational resources, as they do not require GPU during deployment.\n  - LHHs require only less than 100 heuristic evaluations and about 5 minutes to evolve a strong heuristic, while many ML4CO methods require millions of samples and days of training. When the solution evaluation is expensive, LHHs are more practical.\n  - LHHs only need some text-based (and even black-box) explanations to guide the search. ML4CO requires the development of NN architectures, hyperparameters, and training strategies, where informed inductive biases and manual tuning are crucial to guarantee performance.\n\n\n[1] https://github.com/Thinklab-SJTU/awesome-ml4co\n\n\n> W3-1: The writing in Sec. 4 needs improvement. For example, how the short-term and long-term reflection is utilized to improve heuristic design? \n\nWe will improve the writing in Section 4 according to your suggestion.\n\nAn example of both short- and long-term reflection is illustrated in Figure 1(b). The process prompts LLM to reflect upon the relative performance of two heuristics (short-term), and accumulate such knowledge over iterations (long-term). The inputs and outputs of the reflection process are all texts.\n\n**Short-term reflection.**\n- Inputs: Two heuristics to crossover and indicators of their relative performance.\n- Outputs: Text-based reflections upon the performance of the two heuristics, i.e. why the better heuristic is better, and how the worse heuristic can be improved. It is analogous to a verbal gradient derived from the performance comparison.\n- How it is utilized: ReEvo incorporates the short-term reflections into the crossover prompt, leading to more informed offspring.\n\n**Long-term reflection.**\n- Inputs: prior long-term reflections and short-term reflections of the current iteration.\n- Outputs: Text-based reflections upon the overall performance of the population, and strategic hints for better heuristic design.\n- How it is utilized: ReEvo incorporates the long-term reflections into the mutation prompt, leading to more strategic exploration.\n\n\n> W3-2: How to guarantee the generated code is executable?\n\nIf the generated code is not executable, it is discarded.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a novel and general framework that uses LLMs to evolve hyper-heuristics. The framework is built primarily from existing LLM-based components, but coheres well and achieves its goal of an approach that feels like what it's like to design heuristics as a human, leading to interpretable insights in specific results, and allowing the reader to reflect on their own scientific/engineering process through this exercise in formalizing it. The method should be inspiring for many long-term evolutionary improvement approaches.

The main remaining concern about the paper is its similarity to a very recent work EoH, which also frames itself in the lineage of hyper-heuristics. The present work is sufficiently novel to merit its own publication, and the empirical results show strong benefits compared with EoH. However, I suggest the authors clearly state that EoH was developed _concurrently_ to this work, and enumerate the exact differences. To further clarify the paper's place in the literature, it would also be helpful to reference the earliest work using LLMs for mutations [1] and crossover [2] of code. 

Beyond incorporating the changes agreed upon in the discussion with reviewers, I would also encourage a longer dedicated limitations section; since the method appears so general, it would be helpful to clearly identify scenarios where it is not expected to be a good choice.

[1] Lehman et al. "Evolution through Large Models" arXiv:2206.08896 (2023, Handbook of Evolutionary Machine Learning)
[2] Meyerson et al. "Language Model Crossover: Variation through Few-Shot Prompting" arXiv:2302.12170
Decision: Accept (poster)