EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design

Oguzhan Gungordu; Ayse Tursucular; Siheng Xiong; Faramarz Fekri

cs.AIOct 12, 2026

EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design

Authors: Oguzhan Gungordu, Ayse Tursucular, Siheng Xiong, Faramarz Fekri

Organizations: Georgia Institute of Technology

Abstract

LLM-based automated heuristic design (AHD) discovers heuristics for combinatorial optimization problems (COPs), where an LLM generates candidates in an evolutionary search. Existing frameworks freeze the generator or fine-tune it on a scalar fitness signal hiding which instances each heuristic covers. Reflection-based frameworks improve heuristics with natural-language feedback, but it stays in the prompt and never reaches the generator's weights. We propose EPOCH, which makes instance coverage the objective of the evolutionary search and fine-tunes the generator to internalize reflection. Parent selection, operator allocation, and stagnation recovery all optimize how well the heuristics jointly cover the training instances, so the search returns a complementary heuristic ensemble. The generator learns from its own search by experiential preference optimization. A teacher LLM returns a natural-language insight on the generated heuristics, and the generator produces new heuristics with this insight. These improvements join the preference pairs for direct preference optimization (DPO). Since DPO only teaches the generator to rank these improvements, a reflective self-distillation (RSD) term makes it more likely to generate them on its own, and the gains accumulate over the long horizon of the search. Across COPs and open-source LLM backbones, EPOCH's heuristic ensembles outperform inference-only and fine-tuned baselines and generalize across problem scales.

Figures & tables

Figure 1: Overview of EPOCH , illustrating one training iteration. (1) Heuristics are represented by per-instance gap vectors, whose minima define expert heuristics and the coverage gap $\rho(\mathcal{P})$ . (2) These drive parent selection, operator allocation, and coverage-aware population management. (3) The policy $\pi_{\theta}$ samples rollouts from the operator prompt $q$ , the teacher $\pi_{\mathrm{T}}$ returns an insight $z$ on the best and worst valid ones, and $\pi_{\theta}$ regenerates from $q\oplus z$ . (4) Responses form within-batch and cross-round preference pairs; periodic DPO bursts add an RSD term internalizing the hint-guided improvement into the unhinted policy.

Classical heuristics
Method		TSP-20	TSP-50	TSP-100	TSP-200
Nearest Neighbor		17.64	21.96	24.58	26.10
LLM-based AHD: GPT-4o-mini (closed-source)
ReEvo	Top-1	10.55 $\pm 3.58$	13.89 $\pm 4.48$	15.43 $\pm 4.77$	16.64 $\pm 5.00$
	Top-3	9.18 $\pm 2.55$	12.12 $\pm 2.66$	13.66 $\pm 3.29$	17.01 $\pm 4.28$
	Top-10	8.49 $\pm 2.52$	10.92 $\pm 2.29$	12.48 $\pm 2.70$	14.29 $\pm 2.98$

Table 1: TSP optimality gap (%) to LKH-3 optima; each cell is the mean over runs with standard deviation, lower is better. Size

n{=}50

is ID (underlined);

n\in\{20,100,200\}

are OOD. Within each backbone block the best method per metric and test set is shaded ; each test set’s overall best result is shown in bold .

Method		1k_100	1k_500	5k_100	5k_500	10k_100	10k_500	Avg.
Classical heuristics
First-Fit		5.02	0.25	4.65	0.55	4.36	0.50	2.55
Best-Fit		4.77	0.25	4.31	0.55	4.05	0.47	2.40
LLM-based AHD: GPT-4o-mini (closed-source)
ReEvo	Top-1	3.74 $\pm 0.94$	0.40 $\pm 0.30$	3.09 $\pm 1.12$	0.69 $\pm 0.30$	2.84 $\pm 1.11$	0.53 $\pm 0.12$	1.88 $\pm 0.46$
ReEvo	Top-4	3.61 $\pm 1.01$	0.40 $\pm 0.30$	2.98 $\pm 1.21$	0.56 $\pm 0.13$	2.74 $\pm 1.22$	0.44 $\pm 0.03$	1.79 $\pm 0.53$

Table 2: OBP optimality gap (%) to the

L_{1}

lower bound on the six held-out Weibull test sets; each cell is the mean over runs with standard deviation, lower is better. Columns are

(\text{items},\text{capacity})

, e.g. 1k_100 is

1{,}000

items at capacity

100

; Avg. is the mean over the six. Item scales

1\mathrm{k},5\mathrm{k}

are ID (underlined);

10\mathrm{k}

is OOD. Within each backbone block the best Avg. per metric is shaded ; each test set’s overall best result is shown in bold .

Figure 2: Motivation for RSD, on TSP with Llama-3.1-8B (top) and Qwen2.5-7B (bottom): (a) reflective cross-round pairs are a minority of the preference buffer; (b) plain DPO at

\lambda{=}0

satisfies the reflective pairs’ margin by lowering the implicit reward of the rejected response, not raising the winner’s; (c) increasing the RSD weight

\lambda

raises the unhinted policy’s per-token log-likelihood of the reflective winners.

Figure 3: Internalization over training, on TSP with Llama-3.1-8B (left) and Qwen2.5-7B (right). The unhinted policy’s per-token log-likelihood of the reflective winners rises across DPO bursts for

\lambda>0

and stays flat at

\lambda{=}0

Reflective learning
	TSP	OBP
EPOCH (full)	6.79 $\pm 0.19$	0.64 $\pm 0.07$
w/o RSD	7.17 $\pm 0.27$	0.79 $\pm 0.06$
w/o cross-round pairs	6.92 $\pm 0.16$	0.75 $\pm 0.10$
w/o instance-grounded insight	6.90 $\pm 0.21$	0.68 $\pm 0.07$
w/o teacher reflection	6.99 $\pm 0.14$	0.83 $\pm 0.16$

Table 3: Component ablations on the Llama-3.1-8B backbone, reported as the ensemble optimality gap (%), lower is better. The full method is in bold .

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

	Train		Test
Problem	Scale	#Inst.	Scale	#Inst.
TSP	$n{=}\underline{50}$	64	$n\in\{20,\underline{50},100,200\}$	300
OBP	$\{\underline{1\mathrm{k}},\underline{5\mathrm{k}}\}$ , $C{=}100$	4	$\{\underline{1\mathrm{k}},\underline{5\mathrm{k}},10\mathrm{k}\}{\times}\{100,500\}$	5
KP	$n{=}\underline{100}$	64	$n\in\{50,\underline{100},200\}$	1,000

Appendix

Table 4: Training and test datasets. ID scales are underlined; the rest are OOD. #Inst. is per size (TSP, KP) or per

(\text{items},\text{capacity})

set (OBP). TSP gaps are to LKH-3 optima, OBP gaps to the

L_{1}

lower bound, and KP gaps to the optimum.

Method	TSP-20	TSP-50	TSP-100	TSP-200
Classical heuristics
Nearest Neighbor	17.64	21.96	24.58	26.10
Greedy Edge	11.96	17.41	18.69	17.89
Nearest Insertion	13.14	19.38	21.55	23.69
Christofides	8.82	11.17	11.95	12.41
LLM-based AHD: GPT-4o-mini (closed-source)

Appendix

Table 5: Complete version of Table 1 . TSP optimality gap (%) to LKH-3 optima; each cell is the mean over runs with standard deviation, lower is better. Size

n{=}50

is ID (underlined);

n\in\{20,100,200\}

are OOD. Within each backbone block the best method per metric and test set is shaded ; each test set’s overall best result is shown in bold .

Method		1k_100	1k_500	5k_100	5k_500	10k_100	10k_500	Avg.
Classical heuristics
First-Fit		5.02	0.25	4.65	0.55	4.36	0.50	2.55
Best-Fit		4.77	0.25	4.31	0.55	4.05	0.47	2.40
LLM-based AHD: GPT-4o-mini (closed-source)
ReEvo	Top-1	3.74 $\pm 0.94$	0.40 $\pm 0.30$	3.09 $\pm 1.12$	0.69 $\pm 0.30$	2.84 $\pm 1.11$	0.53 $\pm 0.12$	1.88 $\pm 0.46$
ReEvo	Top-4	3.61 $\pm 1.01$	0.40 $\pm 0.30$	2.98 $\pm 1.21$	0.56 $\pm 0.13$	2.74 $\pm 1.22$	0.44 $\pm 0.03$	1.79 $\pm 0.53$

Appendix

Table 6: Complete version of Table 2 . OBP optimality gap (%) to the

L_{1}

lower bound on the six held-out Weibull test sets; each cell is the mean over runs with standard deviation, lower is better. Columns are

(\text{items},\text{capacity})

, e.g. 1k_100 is

1{,}000

items at capacity

100

; Avg. is the mean over the six. Item scales

1\mathrm{k},5\mathrm{k}

are ID (underlined);

10\mathrm{k}

is OOD. Within each backbone block the best Avg. per metric is shaded ; each test set’s overall best result is shown in bold .

Classical heuristics
Method		KP-50	KP-100	KP-200
First-Fit (seed)		32.856	34.836	53.153
LLM-based AHD: Llama-3.1-8B
ReEvo	Top-1	0.224 $\pm 0.031$	0.099 $\pm 0.016$	0.107 $\pm 0.025$
	Top-3	0.198 $\pm 0.018$	0.081 $\pm 0.006$	0.089 $\pm 0.023$
	Top-10	0.170 $\pm 0.022$	0.066 $\pm 0.005$	0.071 $\pm 0.018$

Appendix

Table 7: KP optimality gap (%) to the optimum with the Llama-3.1-8B backbone; each cell is the mean over runs with standard deviation, lower is better. Size

n{=}100

is ID (underlined);

n\in\{50,200\}

are OOD. The best method per metric and test set is shaded ; each test set’s overall best result is shown in bold .

Method		TSP-20	TSP-50	TSP-100	TSP-200
LLM-based AHD: Qwen2.5-7B
CALM	Top-1	12.08 $\pm 3.56$	16.70 $\pm 3.89$	19.38 $\pm 4.21$	21.39 $\pm 3.56$
	Top-3	12.08 $\pm 3.57$	16.65 $\pm 3.89$	19.32 $\pm 4.21$	21.21 $\pm 3.56$
	Top-10	11.49 $\pm 3.56$	16.10 $\pm 3.72$	18.60 $\pm 3.93$	20.48 $\pm 3.23$
EPOCH (Ours)	Top-1	7.97 $\pm 2.39$	10.85 $\pm 1.45$	12.82 $\pm 1.30$	14.64 $\pm 1.28$
	Top-3	5.55 $\pm 2.01$	8.61 $\pm 1.59$	11.08 $\pm 1.71$	13.22 $\pm 1.53$

Appendix

Table 8: TSP optimality gap (%) to LKH-3 optima when the two methods that fine-tune the generator start from the weak seed; each cell is the mean over runs with standard deviation, lower is better. Size

n{=}50

is ID (underlined);

n\in\{20,100,200\}

are OOD. Within each backbone block the best method per metric and test set is shaded ; each test set’s overall best result is shown in bold .

Panel of Figure 4 — Figure 4: Evolution curves on TSP from the weak seed for (a) Llama-3.1-8B and (b) Qwen2.5-7B. Each curve is the mean over runs with its standard deviation as the shaded band; EPOCH is drawn as its top-1, top-3, and top-10 ensembles.

	Manual & GP heuristics				LLM-based AHD
Instance	Greedy	Near-ins.	Near-gr.	GPHH	ReEvo	HSEvo	MCTS-AHD	EoH-S	CALM	EPOCH
ts225	5.38	19.93	16.82	7.71	7.36	6.18	3.56	3.69	5.78	5.68
rat99	22.30	21.05	21.79	14.09	17.39	17.72	16.88	18.50	14.05	9.87
bier127	19.50	23.05	23.25	15.64	20.94	17.26	17.53	11.24	12.18	6.33
lin318	18.75	24.44	25.78	14.30	15.47	16.21	14.48	14.48	12.73	11.97
eil51	13.03	16.14	31.96	10.20	6.65	8.42	7.26	7.56	7.53	6.83

Appendix

Table 9: Generalization to real-world TSPLIB instances Reinelt (1991) , reported as the per-instance optimality gap (%) to the known optimum, lower is better. The LLM-based methods use the Llama-3.1-8B backbone, and the manual and GP reference columns are single heuristics taken from Duflo et al. (2019) . Per instance, the best LLM-based method is shaded and the overall best is in bold .

	Qwen2.5-7B				Llama-3.1-8B
Method	TSP-20	TSP-50	TSP-100	TSP-200	TSP-20	TSP-50	TSP-100	TSP-200
ReEvo	$0.003$	$0.002$	$0.003$	$0.026$	$2.7{\times}10^{-6}$	$8.5{\times}10^{-4}$	$7.1{\times}10^{-4}$	$1.8{\times}10^{-4}$
HSEvo	$0.003$	$0.003$	$0.002$	$0.020$	$2.9{\times}10^{-4}$	$5.6{\times}10^{-4}$	$0.003$	$0.009$
MCTS-AHD	$0.005$	$0.001$	$0.001$	$0.003$	$2.4{\times}10^{-5}$	$1.2{\times}10^{-5}$	$9.5{\times}10^{-5}$	$3.7{\times}10^{-4}$
EoH-S	$0.060$	$0.004$	$0.005$	$0.016$	$0.001$	$6.2{\times}10^{-5}$	$1.9{\times}10^{-5}$	$1.4{\times}10^{-5}$
CALM	$4.0{\times}10^{-5}$	$6.2{\times}10^{-6}$	$1.3{\times}10^{-6}$	$1.8{\times}10^{-5}$	$4.2{\times}10^{-5}$	$3.7{\times}10^{-4}$	$3.3{\times}10^{-4}$	$0.002$

Appendix

Table 10: Across-run significance on TSP. One-sided Welch

t

-test

p

-values for the EPOCH top-10 ensemble gap against each baseline, per test size and backbone;

p<0.05

is shown in bold .

Method	Qwen2.5-7B	Llama-3.1-8B
ReEvo	$0.005$	$0.009$
HSEvo	$1.9{\times}10^{-11}$	$0.023$
EoH-S	$0.033$	$0.007$
CALM	$0.013$	$0.005$

Appendix

Table 11: Across-run significance on OBP. One-sided Welch

t

-test

p

-values for the EPOCH top-4 ensemble gap, averaged over the six Weibull test sets, against the baselines;

p<0.05

is shown in bold .

		Qwen2.5-7B				Llama-3.1-8B
Method	$n$	Wilcoxon $p$	Win	Tie	Loss	Wilcoxon $p$	Win	Tie	Loss
ReEvo	20	$1.8{\times}10^{-47}$	278	0	22	$7.9{\times}10^{-50}$	292	0	8
	50	$3.9{\times}10^{-50}$	289	0	11	$6.1{\times}10^{-51}$	300	0	0
	100	$9.3{\times}10^{-51}$	296	0	4	$6.1{\times}10^{-51}$	300	0	0
	200	$1.9{\times}10^{-50}$	289	0	11	$6.1{\times}10^{-51}$	300	0	0
HSEvo	20	$3.7{\times}10^{-50}$	295	0	5	$2.3{\times}10^{-50}$	292	0	8

Appendix

Table 12: Cross-instance uncertainty quantification on TSP for the deployed top-10 ensemble. Each entry is the Wilcoxon signed-rank

p

-value on the paired per-instance gap differences, with the Win/Tie/Loss counts of EPOCH against the baseline.

Method	$n$	Wilcoxon $p$	Win	Tie	Loss
ReEvo	50	$2.3{\times}10^{-126}$	522	440	38
	100	$1.8{\times}10^{-121}$	657	273	70
	200	$4.4{\times}10^{-131}$	825	66	109
MCTS-AHD	50	$2.9{\times}10^{-77}$	453	493	54
	100	$3.6{\times}10^{-78}$	544	367	89
	200	$1.8{\times}10^{-36}$	515	309	176

Appendix

Table 13: Cross-instance uncertainty quantification on KP for the deployed top-10 ensemble with the Llama-3.1-8B backbone. Each entry is the Wilcoxon signed-rank

p

-value on the paired per-instance gap differences over the

1{,}000

instances per size, with the Win/Tie/Loss counts of EPOCH against the baseline.

Ablation	Removed	Replacement
Reflective learning
w/o RSD	the RSD distillation term	plain DPO on the same pairs ( $\lambda{=}0$ )
w/o cross-round pairs	the certified cross-round matching, a valid hinted Round-2 winner over a strictly worse valid Round-1 heuristic	each valid Round-2 heuristic paired with a randomly chosen valid Round-1 heuristic, reward-ordered ( $\lambda{=}0$ )
w/o instance-grounded insight	the gap-vector instance-split sentence in the teacher prompt	a generic critique from code and scalar gaps only
w/o teacher reflection	the insight channel	Round 2 regenerates unhinted ( $\lambda{=}0$ )
w/o preference optimization	all DPO bursts	a frozen generator, search and reflection only

Appendix

Table 14: Component ablations: what each row removes and the simpler alternative that replaces it, grouped as in Table 3 .

RSD weight $\lambda$
	TSP	OBP
$\lambda{=}0$ (no RSD)	7.17 $\pm 0.27$	0.79 $\pm 0.06$
$\lambda{=}0.1$ $\star$	6.79 $\pm 0.19$	0.64 $\pm 0.07$
$\lambda{=}0.15$	6.84 $\pm 0.35$	0.73 $\pm 0.12$
$\lambda{=}0.2$	6.96 $\pm 0.09$	0.76 $\pm 0.09$
RSD scope

Appendix

Table 15: Hyperparameter ablation on the Llama-3.1-8B backbone, reported as the ensemble optimality gap (%), lower is better;

\star

marks the full-method default.

Method		TSP-20	TSP-50	TSP-100	TSP-200
LLM-based AHD: Qwen2.5-7B
EoH-S	Top-1	8.64 $\pm 1.03$	12.25 $\pm 1.26$	14.44 $\pm 1.84$	16.73 $\pm 2.50$
	Top-3	5.43 $\pm 1.14$	9.12 $\pm 1.05$	11.76 $\pm 1.45$	14.43 $\pm 2.37$
	Top-10	3.46 $\pm 0.66$	7.08 $\pm 0.76$	9.97 $\pm 1.01$	12.69 $\pm 1.34$
CALM	Top-1	6.75 $\pm 0.08$	9.99 $\pm 0.22$	11.96 $\pm 0.20$	13.96 $\pm 0.20$
	Top-3	6.70 $\pm 0.14$	9.92 $\pm 0.23$	11.90 $\pm 0.21$	13.91 $\pm 0.27$

Appendix

Table 16: Teacher LLM ablation on TSP. Optimality gap (%) to LKH-3 optima for EPOCH with three teachers, named in parentheses, with the EoH-S and CALM rows of Table 5 for reference; each cell is the mean over runs with standard deviation, lower is better. Size

n{=}50

is ID (underlined);

n\in\{20,100,200\}

are OOD. Within each backbone block the best method per metric and test set is shaded ; each test set’s overall best result is shown in bold .

Method		1k_100	1k_500	5k_100	5k_500	10k_100	10k_500	Avg.
LLM-based AHD: Qwen2.5-7B
EoH-S	Top-1	3.70 $\pm 1.10$	0.49 $\pm 0.29$	2.89 $\pm 1.21$	0.52 $\pm 0.12$	2.71 $\pm 1.21$	0.44 $\pm 0.12$	1.79 $\pm 0.57$
EoH-S	Top-4	3.37 $\pm 1.10$	0.25 $\pm 0.25$	2.31 $\pm 1.35$	0.39 $\pm 0.12$	2.04 $\pm 1.43$	0.39 $\pm 0.12$	1.46 $\pm 0.64$
CALM	Top-1	4.17 $\pm 0.54$	0.35 $\pm 0.12$	2.89 $\pm 1.18$	0.45 $\pm 0.15$	2.55 $\pm 1.33$	0.35 $\pm 0.15$	1.79 $\pm 0.51$
CALM	Top-4	4.09 $\pm 0.55$	0.30 $\pm 0.10$	2.82 $\pm 1.28$	0.45 $\pm 0.15$	2.50 $\pm 1.41$	0.35 $\pm 0.16$	1.75 $\pm 0.56$
EPOCH (GPT-5-nano)	Top-1	3.91 $\pm 0.66$	0.25 $\pm 0.22$	1.54 $\pm 0.46$	0.17 $\pm 0.09$	1.27 $\pm 0.66$	0.19 $\pm 0.14$	1.22 $\pm 0.20$

Appendix

Table 17: Teacher LLM ablation on OBP. Optimality gap (%) to the

L_{1}

lower bound on the six held-out Weibull test sets for EPOCH with three teachers, named in parentheses, with the EoH-S and CALM rows of Table 6 for reference; each cell is the mean over runs with standard deviation, lower is better. Columns are

(\text{items},\text{capacity})

and Avg. is the mean over the six. Item scales

1\mathrm{k},5\mathrm{k}

are ID (underlined);

10\mathrm{k}

is OOD. Within each backbone block the best Avg. per metric is shaded ; each test set’s overall best result is shown in bold .

LLM-based AHD: GPT-4o-mini (closed-source)
	TSP	OBP
ReEvo	0.60	0.52
HSEvo	0.38	0.29
MCTS-AHD	0.42	0.36
EoH-S	0.53	0.29
LLM-based AHD: GPT-5-nano (closed-source)

Appendix

Table 18: API cost per run in US dollars at list prices, grouped by the model that generates the heuristics. With an open backbone, the cost is that of the auxiliary LLM calls, averaged over the two backbones.

Component	Setting
Iterations / heuristic generations	$125$ / $1{,}000$
Generations per iteration	$4+4$ (Round 1 $+$ Round 2)
Sampling	temperature $0.8$ , top- $p$ $0.95$
Population size $N_{p}$	$10$
LoRA rank	$32$ (4-bit base)
DPO every / $\beta$ / lr	$20$ iterations / $0.1$ / $5\times 10^{-6}$

Appendix

Table 19: EPOCH hyperparameters (shared across problems and backbones unless noted).

Operator	Instruction sentence
Exploitative crossover	Please generate a new algorithm that is motivated by the following algorithms but performs better on any same instance.
Complementary crossover	The two algorithms below each perform well on different problem instances. Please generate a new algorithm that unites their strengths so that it performs well across all the instances that either of them already handles well.
Simplification	Please create a simplified and more elegant version of an algorithm by distilling and refining the core ideas from the following.
Injection	Inject a novel, meaningful component into the following algorithm. The component may be self-devised or inspired by ideas from other domains or problems.
Replacement	For the following algorithm, identify a fragment that assigns equal or near-equal credits to multiple elements and rewrite it to a fragment where credits are deterministically and reasonably differentiated.
Refine	Identify the single most important weakness or failure mode of the following algorithm, then write an improved version that fixes specifically that weakness while preserving the parts that already work well.

Appendix

Table 20: Operator instruction sentences. Each is placed before the parent heuristics and fills the {operator_instruction} field of the Round-1 user prompt.

Problem	Description and efficiency note
TSP	Takes the current node, the destination node, the unordered set of unvisited nodes, and a distance matrix where distance_matrix[i][j] is the distance from node $i$ to $j$ ; returns the next node, which must be unvisited. Efficiency: called once per step, so avoid nested loops and recomputation.
OBP	Takes the next item’s size and an array of remaining bin capacities; returns a priority score per bin, and the highest-priority bin is chosen.
KP	Takes the remaining capacity and two aligned arrays with the weights and values of the items not yet packed; returns the index of the next item to pack, which must fit. Efficiency: called once per packed item, so score all remaining items with array operations rather than loops over items.

Appendix

Table 21: Per-problem function description used in the operator prompts; it fills the {function_spec} field together with the signature from Appendix B .

Critique	{candidate_intro}	{task_direction}
Contrastive	Below are the best and worst valid algorithms it produced for that request, ordered from best to worst:	Identify which design choices appear to have helped reduce the optimality gap, and give a concrete change of direction that would lead to an even better next attempt.
Repair	Below are two algorithms it produced for that request: one valid algorithm that ran successfully, and one invalid algorithm that failed to run (its “Why it failed” line explains the reason).	One candidate ran to completion and one failed at runtime. Identify the design choices that supported successful execution and the code-level pitfalls that caused the failure, then give a concrete next-attempt direction that combines both lessons.
Diagnostic	Below are two algorithms it produced for that request. Both of them are invalid - neither ran successfully. Each one’s “Why it failed” line explains why it was rejected.	Both candidates failed to run, so there is no working example: diagnose the shared failure modes and give a concrete next-attempt direction that produces a runnable function.

Appendix

Table 22: Critique-mode fields of the teacher user prompt. Each row fills {candidate_intro} and {task_direction} ; the contrastive critique additionally receives the {instance_split} sentence.

Automated Heuristic Design

Automated heuristic design creates or adapts problem-solving rules for optimization, planning, scheduling, and related search tasks.

See all 84 papers

Jul 31, 2026

MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

Automated heuristic design (AHD) with large language models (LLMs) has produced strong heuristics for combinatorial optimization problems (COPs). Yet existing frameworks optimize for average performance on a small fixed dataset and steer the search with "verbal gradients" distilled from scalar better/worse feedback. No single heuristic dominates across instance distributions, and scalar feedback tells the LLM whether a heuristic improved, but not where in the instance space or why. We propose MOSAIC, a grid-based framework that adversarially co-evolves problem instances and specialist heuristics inside a Quality-Diversity (QD) archive indexed by structural instance features. Instances evolve to expose weaknesses of the current heuristics, and heuristics evolve to eliminate them by specializing to the newly exposed regions. Each archive cell keeps a specialist heuristic, representative instances, and insights explaining what works in its region, forming a persistent memory that accumulates over the evolutionary search. For each heuristic pair sampled from distant grid regions, an LLM-guided evolutionary loop generates discriminative instances, and a decision tree identifies the feature-space regions where each heuristic wins. A reflection LLM then contrasts the two heuristics to produce multi-directional insights that persist in those regions and guide crossover and mutation. The archive is simultaneously a co-evolved benchmark of discriminative instances and a pool of region specialist heuristics, from which greedy selection extracts a compact complementary portfolio. Across COPs, test sizes, and LLM backbones, the portfolio consistently outperforms state-of-the-art LLM-based AHD methods, and the co-evolved instances attain higher feature-space coverage and stronger heuristic discrimination than evolutionary instance-generation baselines.

Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

Georgia Institute of Technology

Algorithm Selection Automated Heuristic Design Large Language Model-Guided Optimization Combinatorial Optimization Quality-Diversity Optimization

Ask PDF

Jun 12, 2026

MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design

Large Language Models (LLMs) have advanced Automatic Heuristic Design (AHD) by enabling heuristic generation through reasoning and code synthesis. In LLM-based AHD, the LLM reasons about algorithm design and generates executable heuristic code. Existing architectures adopt two main paradigms: Natural Evolution applies crossover and mutation to this code to explore diverse strategies, but discards the reasoning traces behind the design decisions, weakening knowledge retention; Metacognitive Evolution retains these reasoning traces and refines them through reflection, but lacks population-level recombination, limiting exploration. These limitations reduce search efficiency, stability, and solution quality on complex problems. To address this gap, we propose MeEvo, an AHD framework that cyclically couples Natural Evolution and Metacognitive Evolution with operator balance that shifts from exploration to exploitation. Natural Evolution explores heuristic code while recording LLM-generated reasoning traces, fitness values, errors and best heuristic into a shared history; Metacognitive Evolution then reflects on this history to generate improved heuristics that feed into the next Natural Evolution cycle. This design enables population-driven exploration and reflection-driven refinement to reinforce each other. Experiments on five optimization problems show that MeEvo achieves stronger performance and lower variance than tested LLM-based AHD architectures, especially on complex constrained tasks.

Zishang Qiu, Xinan Chen, Rong Qu +1

School of Computer Science, University of Nottingham Ningbo China, Ningbo, China · School of Computer Science, University of Nottingham, Nottingham, UK

Automated Heuristic Design Evolutionary Optimization Large Language Model-Guided Optimization Metacognition in Language Models

Ask PDF

Sep 29, 2026

SimpleEvol: An Agent-Loop Framework for LLM-Driven Automated Heuristic Design with Minimal Human Priors

Large language models (LLMs) have emerged as powerful tools for automated heuristic design (AHD), enabling iterative generation and refinement of heuristics. However, the dominant paradigm embeds LLMs as narrow, fixed components, such as crossover or mutation, within heavily hand-engineered evolutionary frameworks. We argue this misapprehends LLMs. It treats them as specialized tools rather than general reasoners, constrains them to low-level operations, and underutilizes their autonomy. Moreover, the extensive human priors in these frameworks violate the bitter lesson principle that general methods scaling with computation surpass hand-crafted solutions. This raises a key question: which AHD framework designs best convert stronger LLM capabilities into better heuristics? To address this, we propose metrics for LLM-driven AHD framework handcraftedness (AHI) and intelligence conversion efficiency (ICE). Evaluating ten LLMs across three challenging combinatorial optimization problems, we obtain a notable finding that frameworks with fewer human priors consistently yield higher ICE. Based on this finding, we propose SimpleEvol, an agent-loop framework for AHD which removes nearly all human priors and allows the LLM to operate autonomously. SimpleEvol consistently achieves the highest ICE, often by a large margin. Our results challenge the trend toward complex AHD pipelines and point to a lighter and more model-centric alternative, suggesting that reducing human priors is a more effective strategy to scale up with model intelligence. The source code is available at https://github.com/HenryZhu1029/SimpleEvol-Master.

Jianghan Zhu, Cong Zhang, Rongjie Zhu +2

School of Computing and Information Systems, Singapore Management University, Singapore · Independent Researcher · School of Teacher Education, Nanjing University of Information Science and Technology, China +1

Automated Heuristic Design Large Language Model-Guided Optimization Combinatorial Optimization LLM Agents

Ask PDF

Abstract

Automated Heuristic Design

Explore similar work

MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design

SimpleEvol: An Agent-Loop Framework for LLM-Driven Automated Heuristic Design with Minimal Human Priors