Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

Zhuoliang Xie; Changliang Zhou; Genghui Li; Zhenkun Wang

cs.AIOct 2, 2026

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

Authors: Zhuoliang Xie, Changliang Zhou, Genghui Li, Zhenkun Wang

Organizations: School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China · College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, China

Abstract

Designing effective heuristics for diverse combinatorial optimization problems requires substantial expertise and repeated search. Large language models (LLMs) automate heuristic generation and refinement, but heuristic search typically depends on evaluation feedback from the problem being optimized. Generalizing to new problem definitions using only source-task feedback therefore remains a central challenge. We introduce MECo, an LLM-driven multi-task evolutionary framework for zero-shot cross-problem generalization. MECo maintains task-conditioned heuristic populations and uses a transfer gap based on cross-task population performance to guide their interactions. These interactions enable the transfer and recombination of heuristics. A complementary selection criterion then constructs a compact heuristic set by rewarding each member's additional coverage of source combinations. The selected set is applied to target problems without further search or adaptation. Experiments on 32 problem variants across vehicle routing (VRP) and flexible job-shop scheduling (FJSP) show that MECo achieves the lowest mean costs compared with eight automated heuristic design (AHD) baselines under the same budgets. On out-of-domain problems, it outperforms the strongest baseline in each family. Moreover, integrating the framework of MECo with different AHD methods improves their ID and OOD performance in both families, supporting its effectiveness across different methods.

Figures & tables

Figure 1: Comparison of heuristic design paradigms. Unlike existing methods, MECo evolves a heuristic set for zero-shot cross-problem generalization.

Figure 2: A case of generalization to combined VRP variants under separate and joint source training. Curves show the mean cost of the best heuristic in each population.

Figure 3: MECo couples transfer-guided task interactions with heuristic evolution. Each node represents a task-conditioned population. Source datasets $D_{T_{j}}$ guide training and final set selection. The selected heuristics are frozen before zero-shot target evaluation.

Split	Variants	Instances	Size
Training	4	10	50
ID test	4	1,000	100
OOD test	12	1,000	100

Table 1: Data per family. Instances are counted per variant.

(a) VRP distance $\downarrow$
Method	All (#16)	ID (#4)	OOD (#12)	Rank (#16)	Gap (%) (#16)
Nearest-feasible	$23.53$ $\pm$	$23.04$ $\pm$	$23.69$ $\pm$	$7.66$	$7.74$
Savings-priority	$24.51$ $\pm$	$22.48$ $\pm$	$25.19$ $\pm$	$7.75$	$14.64$
EoH	$23.16$ $\pm$ $0.80$	$22.14$ $\pm$ $0.08$	$23.49$ $\pm$ $1.04$	$7.12$	$7.52$
ReEvo	$23.20$ $\pm$ $0.55$	$22.41$ $\pm$ $0.46$	$23.46$ $\pm$ $0.60$	$8.78$	$7.58$
MCTS-AHD	$22.54$ $\pm$ $0.17$	$22.10$ $\pm$ $0.05$	$22.69$ $\pm$ $0.21$	$5.81$	$4.76$

Table 2: Performance comparison across the two problem families.

Figure 4: OOD mean cost relative to MECo, computed as

100(\bar{f}/\bar{f}_{\mathrm{MECo}}-1)

	VRP distance $\downarrow$			FJSP makespan $\downarrow$
Method	All (#16)	ID (#4)	OOD (#12)	All (#16)	ID (#4)	OOD (#12)
EoH	$23.16$ $\pm$ $0.80$	$22.14$ $\pm$ $0.08$	$23.49$ $\pm$ $1.04$	$1466.8$ $\pm$ $33.5$	$1247.0$ $\pm$ $37.6$	$1540.1$ $\pm$ $32.2$
EoH-MECo	$\mathbf{21.99}$ $\pm$ $0.66$	$\mathbf{21.66}$ $\pm$ $0.83$	$\mathbf{22.10}$ $\pm$ $0.61$	$\mathbf{1432.0}$ $\pm$ $6.5$	$\mathbf{1211.1}$ $\pm$ $13.3$	$\mathbf{1505.7}$ $\pm$ $4.9$
ReEvo	$23.20$ $\pm$ $0.55$	$22.41$ $\pm$ $0.46$	$23.46$ $\pm$ $0.60$	$1446.0$ $\pm$ $29.7$	$1229.2$ $\pm$ $12.0$	$1518.2$ $\pm$ $35.8$
ReEvo-MECo	$\mathbf{22.86}$ $\pm$ $1.75$	$\mathbf{21.17}$ $\pm$ $0.70$	$\mathbf{23.43}$ $\pm$ $2.41$	$\mathbf{1415.9}$ $\pm$ $28.4$	$\mathbf{1207.3}$ $\pm$ $18.0$	$\mathbf{1485.4}$ $\pm$ $32.2$
HSEvo	$22.47$ $\pm$ $0.27$	$22.12$ $\pm$ $0.11$	$22.58$ $\pm$ $0.33$	$1443.3$ $\pm$ $23.3$	$1225.2$ $\pm$ $5.1$	$1516.0$ $\pm$ $29.5$

Table 3: Baseline engines with and without MECo.

Figure 5: Performance on FJSP for ten runs.

	VRP distance $\downarrow$			FJSP makespan $\downarrow$
Condition	All (#16)	ID (#4)	OOD (#12)	All (#16)	ID (#4)	OOD (#12)
w/o transfer gap	$22.35$ $\pm$ $0.05$	$22.16$ $\pm$ $0.05$	$22.41$ $\pm$ $0.05$	$\underline{1410.2}$ $\pm$ $7.8$	$\underline{1214.6}$ $\pm$ $11.5$	$\underline{1475.3}$ $\pm$ $6.6$
w/o $\mathrm{c}_{1}$	$22.28$ $\pm$ $0.16$	$22.11$ $\pm$ $0.11$	$\underline{22.34}$ $\pm$ $0.17$	$1418.4$ $\pm$ $11.3$	$1226.7$ $\pm$ $13.9$	$1482.3$ $\pm$ $10.7$
w/o $\mathrm{c}_{2}$	$\underline{22.19}$ $\pm$ $0.09$	$\underline{21.73}$ $\pm$ $0.31$	$\underline{22.34}$ $\pm$ $0.06$	$1411.9$ $\pm$ $8.7$	$1216.7$ $\pm$ $13.2$	$1477.0$ $\pm$ $7.3$
w/o $\mathrm{c}_{3}$	$22.32$ $\pm$ $0.11$	$21.89$ $\pm$ $0.31$	$22.46$ $\pm$ $0.16$	$1424.0$ $\pm$ $24.7$	$1224.0$ $\pm$ $18.5$	$1490.7$ $\pm$ $26.7$
w/o $\mathrm{m}_{1}$	$22.37$ $\pm$ $0.09$	$22.08$ $\pm$ $0.05$	$22.47$ $\pm$ $0.10$	$1411.4$ $\pm$ $4.9$	$1215.2$ $\pm$ $3.9$	$1476.8$ $\pm$ $5.2$

Table 4: Component ablations with full MECo.

	VRP distance $\downarrow$			FJSP makespan $\downarrow$
Model	All (#16)	ID (#4)	OOD (#12)	All (#16)	ID (#4)	OOD (#12)
gpt-4o-mini	$\underline{21.98}$ $\pm$ $0.50$	$\underline{21.60}$ $\pm$ $0.70$	$\underline{22.11}$ $\pm$ $0.43$	$1408.7$ $\pm$ $1.1$	$1211.3$ $\pm$ $3.5$	$1474.4$ $\pm$ $1.1$
gpt-5.4-nano	$22.29$ $\pm$ $0.46$	$21.72$ $\pm$ $0.43$	$22.48$ $\pm$ $0.48$	$\underline{1405.8}$ $\pm$ $1.7$	$\underline{1205.1}$ $\pm$ $3.4$	$\underline{1472.7}$ $\pm$ $1.9$
gemini-3.1-flash-lite	$\mathbf{21.72}$ $\pm$ $0.36$	$\mathbf{21.36}$ $\pm$ $0.28$	$\mathbf{21.84}$ $\pm$ $0.38$	$\mathbf{1367.6}$ $\pm$ $22.3$	$\mathbf{1163.2}$ $\pm$ $13.6$	$\mathbf{1435.8}$ $\pm$ $25.1$

Table 5: MECo performance with different generation models.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

VRP							FJSP
Variant	O	B	TW	L	Depth	Split	Variant	R	A	S	T	Depth	Split
Base					0	OOD	Base					0	OOD
B		$\checkmark$			1	ID	A		$\checkmark$			1	ID
L				$\checkmark$	1	ID	R	$\checkmark$				1	ID
TW			$\checkmark$		1	ID	S			$\checkmark$		1	ID
O	$\checkmark$				1	ID	T				$\checkmark$	1	ID

Appendix

Table 6: Benchmark variants and active constraints. ID and OOD denote source and held-out task types.

Setting	VRP	FJSP
Training tasks $\times$ instances	$4\times 10$	$4\times 10$
Training size	50 customers and a depot	50 operations, 10 jobs, 5 machines
Test tasks $\times$ instances	$16\times 1{,}000$	$16\times 1{,}000$
Test size	100 customers and a depot	100 operations, 10 or 20 jobs
Test machines	–	5, 10, 11, 12, or 13
Coordinates / processing data	Uniform coordinates in $[0,1]^{2}$	Public processing times and eligibility sets

Appendix

Table 7: Dataset sizes and base parameters.

Family	Attribute	Setting
VRP	O	Routes end at the last customer without returning to the depot
	B	Pickups comprise $20\%$ of customers, chosen uniformly
	L	Route-distance bound of $3$
	TW	Speed $1$ , service duration $s=0.2$ , depot horizon $[0,3]$
		Window center $\mathcal{U}(d_{i},3-d_{i}-s)$ and half-width $\mathcal{U}(s/2,1)$ , where $d_{i}$ is depot distance
FJSP	R	Release dates from $0$ to $0.80H$ , with the first job released at zero

Appendix

Table 8: Constraint generation parameters.

Common setting		Value
Generation model		GPT-4o-mini
New solver proposals per search		At most 2,000
Independent searches / final set size		3 / 4
Method	Population	Principal parameters
EoH	20	Initial allowance 40, two crossover parents
ReEvo	20	Mutation rate $0.5$ , short- and long-term reflection

Appendix

Table 9: Common search settings and method parameters.

Problem	Rule	All (#16)	ID (#4)	OOD (#12)
VRP	Nearest-feasible	$\mathbf{23.53}$	$23.04$	$\mathbf{23.69}$
VRP	Savings-priority	$24.51$	$\mathbf{22.48}$	$25.19$
FJSP	ECT	$\mathbf{1486.8}$	$\mathbf{1301.4}$	$\mathbf{1548.6}$
FJSP	MWKR(min)-ECT	$1751.7$	$1436.3$	$1856.9$

Appendix

Table 10: Classical heuristic costs. Lower is better.

Method Base B L TW Nearest-feasible

20.85

\pm

21.98

\pm

20.91

\pm

35.61

\pm

Savings-priority

\mathbf{19.80}

\pm

\mathbf{20.33}

\pm

\mathbf{19.79}

\pm

33.90

\pm

EoH

20.85

\pm

0.00

22.00

\pm

0.04

21.13

\pm

0.24

\underline{31.77}

\pm

0.07

ReEvo

20.89

\pm

0.15

22.05

\pm

0.10

20.95

\pm

0.22

32.84

\pm

1.43

MCTS-AHD

20.86

\pm

0.00

21.99

\pm

0.03

20.95

\pm

0.06

\mathbf{31.76}

\pm

0.10

EoH-S

20.69

\pm

0.07

22.10

\pm

0.14

20.82

\pm

0.11

32.09

\pm

0.54

MEoH

20.86

\pm

0.01

21.98

\pm

0.01

20.94

\pm

0.02

33.53

\pm

0.72

HSEvo

20.85

\pm

0.00

21.91

\pm

0.23

20.91

\pm

0.00

32.00

\pm

0.28

EMO-STA

20.37

\pm

0.84

21.08

\pm

1.55

20.50

\pm

0.70

35.05

\pm

0.97

MoH

\underline{20.25}

\pm

0.76

\underline{21.01}

\pm

1.50

20.39

\pm

0.63

33.19

\pm

0.61

MECo

20.37

\pm

0.84

21.08

\pm

1.55

\underline{20.32}

\pm

0.61

31.80

\pm

0.15

Method O BL BTW LTW Nearest-feasible

13.68

\pm

21.43

\pm

38.92

\pm

35.62

\pm

Savings-priority

15.88

\pm

\mathbf{19.44}

\pm

37.06

\pm

33.85

\pm

EoH

13.68

\pm

0.00

22.27

\pm

0.74

34.80

\pm

0.28

34.00

\pm

2.76

ReEvo

13.77

\pm

0.13

21.82

\pm

0.48

35.78

\pm

1.00

33.00

\pm

1.16

MCTS-AHD

13.68

\pm

0.00

21.50

\pm

0.12

34.87

\pm

0.43

\underline{31.77}

\pm

0.12

EoH-S

13.71

\pm

0.05

21.56

\pm

0.19

35.08

\pm

0.32

32.10

\pm

0.53

MEoH

13.68

\pm

0.01

21.46

\pm

0.02

36.20

\pm

0.75

34.27

\pm

0.54

HSEvo

13.66

\pm

0.03

21.33

\pm

0.33

\underline{34.78}

\pm

0.90

31.97

\pm

0.16

EMO-STA

\underline{13.21}

\pm

0.81

20.72

\pm

1.22

38.29

\pm

1.10

35.08

\pm

0.94

MoH

\mathbf{12.94}

\pm

0.70

\underline{20.55}

\pm

1.10

35.74

\pm

0.55

33.16

\pm

0.61

MECo

\underline{13.21}

\pm

0.81

20.58

\pm

1.09

\mathbf{34.54}

\pm

0.15

\mathbf{31.74}

\pm

0.10

Method OB OL OTW BLTW Nearest-feasible

15.62

\pm

13.68

\pm

20.14

\pm

38.89

\pm

Savings-priority

17.82

\pm

15.80

\pm

25.10

\pm

36.92

\pm

EoH

15.62

\pm

0.00

14.65

\pm

1.14

\mathbf{19.65}

\pm

0.37

37.77

\pm

3.01

ReEvo

15.78

\pm

0.11

13.83

\pm

0.14

21.24

\pm

1.30

35.92

\pm

0.83

MCTS-AHD

15.61

\pm

0.01

13.71

\pm

0.05

20.00

\pm

0.03

34.85

\pm

0.60

EoH-S

15.84

\pm

0.41

13.66

\pm

0.03

20.25

\pm

0.42

35.46

\pm

0.99

MEoH

15.63

\pm

0.01

13.70

\pm

0.01

\underline{19.83}

\pm

0.13

36.95

\pm

0.59

HSEvo

15.57

\pm

0.04

13.67

\pm

0.02

20.02

\pm

0.28

\underline{34.68}

\pm

0.83

EMO-STA

\underline{14.64}

\pm

1.69

13.20

\pm

0.83

20.00

\pm

0.25

38.26

\pm

1.08

MoH

\mathbf{14.35}

\pm

1.50

\underline{12.91}

\pm

0.73

20.13

\pm

0.02

35.60

\pm

0.61

MECo

\underline{14.64}

\pm

1.69

\mathbf{12.62}

\pm

0.76

19.94

\pm

0.14

\mathbf{34.41}

\pm

0.16

Method OBL OBTW OLTW OBLTW Nearest-feasible

15.40

\pm

21.89

\pm

20.13

\pm

21.76

\pm

Savings-priority

17.15

\pm

27.25

\pm

25.03

\pm

27.00

\pm

EoH

16.50

\pm

0.95

\mathbf{21.42}

\pm

0.54

21.04

\pm

1.86

23.36

\pm

1.90

ReEvo

15.78

\pm

0.38

23.10

\pm

1.01

21.27

\pm

1.17

23.13

\pm

0.90

MCTS-AHD

15.49

\pm

0.16

21.84

\pm

0.34

19.88

\pm

0.06

21.92

\pm

0.70

EoH-S

15.61

\pm

0.28

22.40

\pm

0.26

20.02

\pm

0.57

22.62

\pm

0.50

MEoH

15.44

\pm

0.06

\underline{21.45}

\pm

0.10

\underline{19.78}

\pm

0.15

\underline{21.37}

\pm

0.11

HSEvo

15.35

\pm

0.08

21.66

\pm

0.91

\mathbf{19.74}

\pm

0.18

\mathbf{21.35}

\pm

0.75

EMO-STA

14.49

\pm

1.58

21.73

\pm

0.28

19.96

\pm

0.31

21.61

\pm

0.25

MoH

\underline{14.18}

\pm

1.39

21.89

\pm

0.00

20.13

\pm

0.00

21.76

\pm

0.00

MECo

\mathbf{13.62}

\pm

0.83

21.59

\pm

0.12

19.83

\pm

0.15

21.45

\pm

0.10

Appendix

Table 11: VRP results on all variants. Lower is better.

Method Base A R S ECT

1146.7

\pm

1324.9

\pm

1299.8

\pm

1291.8

\pm

MWKR-ECT

1152.3

\pm

1528.9

\pm

1500.5

\pm

1366.4

\pm

EoH

1061.8

\pm

28.3

1300.4

\pm

34.4

\underline{1216.5}

\pm

37.0

1243.0

\pm

57.6

ReEvo

1044.4

\pm

12.1

1264.1

\pm

17.5

1245.1

\pm

38.0

1200.1

\pm

23.7

MCTS-AHD

1049.4

\pm

43.3

1269.6

\pm

10.2

1247.5

\pm

87.7

1214.2

\pm

30.5

EoH-S

1049.7

\pm

40.7

1258.9

\pm

6.4

1243.9

\pm

76.2

1245.8

\pm

37.1

MEoH

1049.2

\pm

32.1

\underline{1258.2}

\pm

8.5

1239.5

\pm

27.1

1231.9

\pm

51.9

HSEvo

\underline{1036.2}

\pm

9.6

1268.0

\pm

8.9

1218.3

\pm

11.0

1215.0

\pm

11.2

EMO-STA

1091.7

\pm

56.0

1279.8

\pm

37.5

1259.3

\pm

34.1

1232.5

\pm

51.5

MoH

1049.4

\pm

2.0

1264.6

\pm

12.0

1233.0

\pm

11.5

\underline{1199.6}

\pm

17.5

MECo

\mathbf{1035.2}

\pm

5.6

\mathbf{1251.8}

\pm

0.7

\mathbf{1211.6}

\pm

0.8

\mathbf{1181.3}

\pm

2.6

Method T AS AT RA ECT

1289.2

\pm

1462.2

\pm

1604.7

\pm

1464.6

\pm

MWKR-ECT

1349.2

\pm

1725.0

\pm

1922.7

\pm

1875.3

\pm

EoH

1228.3

\pm

23.1

1464.0

\pm

58.9

1649.2

\pm

27.8

1428.7

\pm

30.1

ReEvo

1207.5

\pm

23.2

1415.2

\pm

26.8

1589.9

\pm

52.7

1446.2

\pm

48.2

MCTS-AHD

1227.3

\pm

77.7

1418.7

\pm

32.9

1617.5

\pm

50.5

1416.8

\pm

37.7

EoH-S

1218.0

\pm

64.1

1439.8

\pm

4.7

1616.1

\pm

54.1

\underline{1405.2}

\pm

23.6

MEoH

1219.2

\pm

27.1

1421.5

\pm

28.1

1617.0

\pm

40.6

1428.9

\pm

55.8

HSEvo

\underline{1199.4}

\pm

14.2

1434.3

\pm

6.1

1599.4

\pm

43.9

1431.0

\pm

36.0

EMO-STA

1251.3

\pm

47.2

1418.8

\pm

34.2

1580.3

\pm

20.4

1429.2

\pm

30.4

MoH

\mathbf{1196.9}

\pm

17.9

\underline{1393.8}

\pm

10.2

\underline{1568.9}

\pm

9.4

1412.5

\pm

11.9

MECo

1200.8

\pm

11.7

\mathbf{1388.8}

\pm

1.6

\mathbf{1561.9}

\pm

1.0

\mathbf{1402.5}

\pm

0.5

Method RS RT ST AST ECT

1429.0

\pm

1469.4

\pm

1441.4

\pm

1744.5

\pm

MWKR-ECT

1689.4

\pm

1687.8

\pm

1540.6

\pm

2104.8

\pm

EoH

1365.3

\pm

43.8

1423.6

\pm

28.9

1418.4

\pm

39.5

1810.1

\pm

44.1

ReEvo

1376.0

\pm

43.9

1427.4

\pm

27.5

1358.5

\pm

32.3

1740.1

\pm

57.0

MCTS-AHD

1385.4

\pm

71.0

1484.5

\pm

163.7

1387.3

\pm

67.9

1755.2

\pm

49.0

EoH-S

1397.5

\pm

65.6

1464.5

\pm

122.1

1399.4

\pm

56.7

1773.5

\pm

34.1

MEoH

1378.2

\pm

43.3

1441.0

\pm

40.8

1384.5

\pm

45.3

1751.5

\pm

51.6

HSEvo

1358.0

\pm

12.9

\underline{1415.6}

\pm

31.6

1365.9

\pm

10.9

1755.8

\pm

29.4

EMO-STA

1372.7

\pm

48.1

1441.9

\pm

18.7

1388.2

\pm

45.6

1722.1

\pm

23.9

MoH

\underline{1345.4}

\pm

14.6

1417.7

\pm

12.7

\underline{1349.0}

\pm

23.7

\underline{1699.2}

\pm

12.4

MECo

\mathbf{1326.9}

\pm

1.0

\mathbf{1393.9}

\pm

1.6

\mathbf{1334.6}

\pm

1.2

\mathbf{1692.2}

\pm

5.7

Method RAS RAT RST RAST ECT

1582.7

\pm

1768.3

\pm

1589.6

\pm

1880.7

\pm

MWKR-ECT

2047.9

\pm

2256.9

\pm

1859.2

\pm

2420.8

\pm

EoH

1561.4

\pm

40.8

1799.7

\pm

22.7

1570.6

\pm

27.0

1927.8

\pm

23.2

ReEvo

1574.4

\pm

53.3

1782.3

\pm

58.8

1554.0

\pm

43.2

1910.3

\pm

69.1

MCTS-AHD

1541.1

\pm

35.8

1786.0

\pm

69.0

1612.6

\pm

147.8

1896.3

\pm

53.6

EoH-S

1556.9

\pm

25.9

1786.0

\pm

71.5

1600.4

\pm

108.6

1908.2

\pm

49.3

MEoH

1555.5

\pm

58.9

1801.2

\pm

76.2

1562.2

\pm

54.8

1909.0

\pm

80.6

HSEvo

1561.8

\pm

32.1

1781.4

\pm

83.6

1545.9

\pm

22.6

1907.2

\pm

68.6

EMO-STA

1543.2

\pm

36.0

1743.6

\pm

21.2

1549.6

\pm

41.5

1856.6

\pm

24.6

MoH

\underline{1523.2}

\pm

11.3

\underline{1729.2}

\pm

14.6

\underline{1521.4}

\pm

19.3

\underline{1838.3}

\pm

15.1

MECo

\mathbf{1511.9}

\pm

2.5

\mathbf{1717.9}

\pm

1.4

\mathbf{1500.4}

\pm

2.0

\mathbf{1827.1}

\pm

3.0

Appendix

Table 12: FJSP results on all variants. Lower is better.

Figure 6: Relative gaps across all variants. Lower is better. MECo is red.

Figure 7: Costs by composition depth, with sample standard deviations.

	VRP			FJSP
Method	Depth 2	Depth 3	Depth 4	Depth 2	Depth 3	Depth 4
Nearest-feasible (VRP) ECT (FJSP)	$24.23$	$24.08$	$21.76$	$1478.5$	$1671.3$	$1880.7$
Savings-priority (VRP) MWKR-ECT (FJSP)	$24.85$	$26.59$	$27.00$	$1740.1$	$2067.2$	$2420.8$
EoH	$23.50$ $\pm 0.80$	$24.18$ $\pm 1.47$	$23.36$ $\pm 1.90$	$1458.2$ $\pm 35.7$	$1685.5$ $\pm 30.2$	$1927.8$ $\pm 23.2$
ReEvo	$23.57$ $\pm 0.55$	$24.02$ $\pm 0.74$	$23.13$ $\pm 0.90$	$1435.5$ $\pm 29.4$	$1662.7$ $\pm 47.3$	$1910.3$ $\pm 69.1$
MCTS-AHD	$22.91$ $\pm 0.12$	$23.01$ $\pm 0.29$	$21.92$ $\pm 0.70$	$1451.7$ $\pm 53.6$	$1673.7$ $\pm 51.3$	$1896.3$ $\pm 53.6$

Appendix

Table 13: Costs by composition depth. Lower is better.

Method	Total proposals	OB $\downarrow$	BLTW $\downarrow$	Avg. rank $\downarrow$
EoH	$500+500$	$15.7304$ $\pm 0.1173$	$34.1699$ $\pm 0.4925$	$5.00$
EoH-S	$500+500$	$15.5708$ $\pm 0.1741$	$34.1896$ $\pm 0.4038$	$4.50$
ReEvo	$500+500$	$15.7903$ $\pm 0.0376$	$\mathbf{33.8441}$ $\pm 0.0562$	$4.00$
MEoH	$500+500$	$15.7702$ $\pm 0.0267$	$34.1351$ $\pm 0.5875$	$5.00$
MCTS-AHD	$500+500$	$15.8940$ $\pm 0.4708$	$34.5688$ $\pm 0.0305$	$8.00$
HSEvo	$500+500$	$15.9109$ $\pm 0.1988$	$34.1125$ $\pm 0.4006$	$6.00$

Appendix

Table 15: VRP target adaptation. Costs are mean

\pm

sample SD over three searches.

Method	All (#16)	ID (#4)	OOD (#12)
MTN	$148.67$	$115.16$	$159.85$
MTN 8aug	$137.05$	$109.33$	$146.29$
MECo	$\mathbf{106.60}\pm 2.54$	$\mathbf{88.75}\pm 2.40$	$\mathbf{112.55}\pm 2.62$

Appendix

Table 16: Frozen evaluation on 1,000-customer VRP instances. Lower is better.

Task	Size	EMO-STA	MoH	MECo
3 tasks
TSP	50	$6.99$ $\pm 0.00$	$6.46$ $\pm 0.19$	$\mathbf{6.34}$ $\pm 0.07$
	100	$9.69$ $\pm 0.00$	$9.04$ $\pm 0.32$	$\mathbf{8.83}$ $\pm 0.11$
VRP	50	$13.53$ $\pm 0.00$	$13.41$ $\pm 0.63$	$\mathbf{12.97}$ $\pm 0.51$
	100	$23.35$ $\pm 0.00$	$23.03$ $\pm 1.16$	$\mathbf{22.31}$ $\pm 1.02$
FJSP	50	$132.87$ $\pm 7.03$	$\mathbf{115.02}$ $\pm 0.30$	$123.00$ $\pm 9.15$

Appendix

Table 17: Joint design across three tasks. Mean

\pm

sample SD.

VRP
Method	Train (h)	Test (h)	Input (M)	Output (M)	Tokens (M)
EoH	$0.77$ $\pm 0.26$	$1.26$ $\pm 0.13$	$2.16$ $\pm 0.09$	$0.84$ $\pm 0.03$	$3.00$ $\pm 0.11$
ReEvo	$1.04$ $\pm 0.08$	$0.87$ $\pm 0.17$	$4.97$ $\pm 0.17$	$1.26$ $\pm 0.07$	$6.23$ $\pm 0.23$
MCTS-AHD	$5.64$ $\pm 0.07$	$0.94$ $\pm 0.16$	$8.17$ $\pm 0.55$	$1.18$ $\pm 0.02$	$9.35$ $\pm 0.56$
EoH-S	$0.99$ $\pm 0.32$	$1.25$ $\pm 0.18$	$2.54$ $\pm 0.06$	$1.03$ $\pm 0.04$	$3.57$ $\pm 0.11$
MEoH	$0.92$ $\pm 0.29$	$1.25$ $\pm 0.09$	$2.21$ $\pm 0.18$	$0.88$ $\pm 0.05$	$3.09$ $\pm 0.22$

Appendix

Table 18: Resource use per search, with sample standard deviations.

Method	License	URL
EoH	BSD 2-Clause	https://github.com/Optima-CityU/LLM4AD
ReEvo	BSD 2-Clause	https://github.com/ai4co/reevo
MCTS-AHD	BSD 2-Clause	https://github.com/Optima-CityU/LLM4AD
EoH-S	MIT	https://github.com/FeiLiu36/EoH-S
MEoH	BSD 2-Clause	https://github.com/Optima-CityU/LLM4AD
HSEvo	MIT	https://github.com/datphamvn/HSEvo

Appendix

Table 19: Licenses and URLs of the baseline implementations used in this work.

Explore similar work

Jul 31, 2026cs.NE

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

May 21, 2026cs.LG

Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery

Recent LLM-guided evolutionary search methods have shown that iterative program mutation can discover strong algorithms, but they typically optimize each task independently, even when related tasks share reusable structure. We introduce Evolutionary Multi-Task Optimization (EMO) for LLM-guided program discovery, and propose EMO-STA (Shared-Then-Adapt), a two-stage framework that first evolves a shared archive of executable programs across a task family and then adapts selected shared candidates to each target task. Within EMO-STA, we explore multiple adaptation strategies, including warm-starting from the shared archive, adapting the best average shared program, and adapting the shared program that performs best on each target task. Across eight task families spanning continuous optimization, geometric construction, modeling, and algorithmic optimization, EMO-STA improves over matched-compute single-task evolution in most settings, with STA Best-Local providing the strongest in-distribution adaptation and STA Best-Shared yielding robust transfer to unseen tasks. Compute-allocation experiments show that allocating a substantial fraction of the family-level budget to shared evolution is consistently beneficial, with roughly balanced shared and adaptation budgets often being optimal. Beyond compute efficiency, we show that shared evolution can mitigate overfitting in low-evidence settings (e.g. few training data), including ARC tasks and time-series feature engineering, by favoring programs that generalize across all tasks rather than exploiting task-specific brittle artifacts.

Halil Alperen Gozeten, Xuechen Zhang, Emrullah Ildiz +3

University of Michigan - Ann Arbor · University of California San Diego

Evolutionary Optimization Large Language Model-Guided Optimization LLM-Based Program Synthesis Transfer Learning

Ask PDF

Jun 12, 2026cs.NE

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