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

MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design
Jul 31, 2026Oguzhan Gungordu, Siheng Xiong, Faramarz FekriAlgorithm Selection Automated Heuristic Design
Georgia Institute of Technology
Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery
May 21, 2026Halil Alperen Gozeten, Xuechen Zhang, Emrullah Ildiz +3Evolutionary Optimization Large Language Model-Guided Optimization
University of Michigan - Ann Arbor · University of California San Diego
MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design
Jun 12, 2026Zishang Qiu, Xinan Chen, Rong Qu +1Automated Heuristic Design Evolutionary Optimization
School of Computer Science, University of Nottingham Ningbo China, Ningbo, China · School of Computer Science, University of Nottingham, Nottingham, UK

Jul 31, 2026, cs.NEJ/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery

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