HEMO: Harness Self-Evolution for Multi-Objective Combinatorial Optimization

Jianghan Zhu; Cong Zhang; Ni Zhang; Yifan Yang; Yew Soon Ong; Zhiguang Cao

cs.NEOct 29, 2026

HEMO: Harness Self-Evolution for Multi-Objective Combinatorial Optimization

Authors: Jianghan Zhu, Cong Zhang, Ni Zhang, Yifan Yang, Yew Soon Ong, Zhiguang Cao

Organizations: School of Computing and Information Systems, Singapore Management University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore · Huawei Noah's Ark Lab · TikTok Singapore ·

Abstract

Automatic operator design (AOD) has increasingly adopted large language models (LLMs) to generate problem-specific search and variation operators for multi-objective combinatorial optimization (MOCO). Yet most methods evolve the operators while leaving the process that discovers them fixed. This limits adaptation as new Pareto trade-offs and operator interactions change where and how the search should proceed. We introduce HEMO, which makes the AOD harness itself a self-evolving optimization target. HEMO maintains a persistent harness state and updates one module at a time, revising the logic that determines which experience to retrieve, which operators to improve, which parents to select, and how to formulate the orchestration of search steps. Downstream solution quality and runtime guide these updates, while a discounted UCB scheduler directs adaptation toward promising modules as their utility changes. A persistent memory filesystem preserves candidate outcomes and diagnostic feedback across harness states, enabling successive states to build on accumulated optimization experience. Experiments across eight MOCO tasks and two structurally distinct evolutionary backbones demonstrate strong performance against conventional evolutionary, neural, and LLM-based AOD baselines, together with effective transfer to related tasks. HEMO extends automatic operator design beyond evolving individual operators to improving the search process that discovers them.

Figures & tables

Fig. 1: Paradigms of LLM-based AOD characterized by agent autonomy and harness adaptivity. Fixed evolutionary AOD (upper left) uses agents as role-specific tools within a predefined evolutionary loop, whereas independent AOD harness search (upper right) evaluates separately sampled but internally fixed harnesses. Agent-autonomic AOD (lower left) allows the agent to control candidate generation and feedback inspection within a fixed outer AOD loop, while stateful AOD harness self-evolution, adopted by HEMO in the lower-right quadrant, evolves the stateful harness itself through persistent module-level transitions, allowing search control and the use of accumulated experience to co-adapt over time under outer-agent guidance.

Fig. 2: Overview of HEMO . Along the outer state transition trajectory, a selected decision module is revised and incorporated into the parent harness to form the child harness for the next evaluation episode, while optimization experience is retained in the memory filesystem.

	Bi-TSP						Bi-CVRP						Bi-KP
Method	$N=20$		$N=50$		$N=100$		$N=20$		$N=50$		$N=100$		$N=50$		$N=100$		$N=200$
	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$
SEMO	0.5878	29.411	0.4612	35.476	0.3674	42.621	0.4840	9.726	0.3380	8.991	0.2987	10.691	0.3543	14.528	0.3917	8.146	0.2912	16.284
NSGA-II	0.5600	1102.171	0.3860	1099.551	0.3120	985.188	0.6025	1178.418	0.5420	1162.623	0.5199	1530.646	0.3581	1045.565	0.4024	551.730	0.3207	529.589
MOEA/D	0.5874	136.718	0.4385	146.027	0.3696	183.499	0.5893	–	0.5288	–	0.5347	–	0.3541	–	0.4040	–	0.3285	–
PFG-MOEA	0.5906	74.886	0.4601	63.210	0.3847	86.956	0.5888	123.347	0.4527	225.457	0.3469	317.618	0.3562	68.912	0.4041	67.459	0.3250	67.129

TABLE I: Average performance of the best-HV candidate selected from the final Pareto front of each of four independent runs on the three source tasks. Time denotes runtime in seconds per instance. The best value in each column is shown in bold ; “–” denotes runs that exceeded the time limit.

	Tri-TSP						Bi-SPDP						Bi-MDKP
Method	$N=20$		$N=50$		$N=100$		$N=20$		$N=50$		$N=100$		$N=50$		$N=100$		$N=200$
	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$
SEMO	0.4055	11.166	0.1880	22.008	0.1041	43.133	0.7510	1.973	0.8343	3.645	0.8461	7.005	0.2536	2.875	0.2460	2.994	0.4866	3.144
NSGA-II	0.4020	814.270	0.2050	1004.854	0.1310	1207.876	0.7531	568.591	0.8081	537.841	0.8137	563.270	0.2596	1050.822	0.2662	553.071	0.5469	558.297
MOEA/D	0.4098	489.636	0.2230	1104.641	0.1534	2577.410	0.7579	61.224	0.8219	107.852	0.8317	140.504	0.2589	–	0.2729	–	0.5774	–
PFG-MOEA	0.4520	265.914	0.2810	765.435	0.2125	963.652	0.7465	13.927	0.8029	31.840	0.8117	58.505	0.2535	76.271	0.2587	74.336	0.5420	70.115

TABLE II: Performance averaged over the best-HV candidate of each of four independent runs on the three intra-family transfer tasks. The best available value in each column is shown in bold .

	Expert		E2OC		HEMO
Setting	HV $\uparrow$	IGD $\downarrow$	HV $\uparrow$	IGD $\downarrow$	HV $\uparrow$	IGD $\downarrow$
Traveling Salesman Problems
Bi-TSP 20	0.5476	0.0579	0.6174	0.0081	0.6103	0.0093
Bi-TSP 50	0.3613	0.1330	0.4897	0.0437	0.4948	0.0215
Bi-TSP 100	0.2835	0.1021	0.3631	0.0367	0.3763	0.0214
Tri-TSP 20	0.3661	0.0660	0.4132	0.0206	0.4305	0.0160

TABLE III: NSGA-II results on TSP (averaged over 50 instances per size) and FJSP (ID: Mk15; OOD: Mk01–Mk14).

	HV $\uparrow$		IGD $\downarrow$
Setting	PMOCO	HEMO -SEMO	PMOCO	HEMO -SEMO
Bi-TSP 20	0.6260	0.6269	0.005281	0.000781
Bi-TSP 50	0.6350	0.6348	0.006773	0.001295
Bi-TSP 100	0.6977	0.6853	0.004168	0.006003
Bi-TSP 150	0.6958	0.7142	0.020435	0.003545
Bi-TSP 200	0.7151	0.7276	0.019029	0.006109

TABLE IV: Solution-quality comparison with PMOCO without instance augmentation. Results are averaged over 50 instances per setting. The better value for each metric within each setting is shown in bold . Winning HEMO -SEMO values are additionally shaded in blue.

Fig. 3: Search dynamics and final heuristic fronts across four tasks. (a) Mean heuristic-front HV with

\pm

std shading. (b) Aggregated final heuristic Pareto fronts obtained by nondominated filtering.

	Bi-TSP20		Tri-TSP20
Variant	HV $\uparrow$	IGD $\downarrow$	HV $\uparrow$	IGD $\downarrow$
HEMO	0.9583	0.0046	0.9330	0.0084
w/o harness evolution	0.6133	0.0364	0.5754	0.0462
w/o discounted UCB	0.8766	0.0097	0.8318	0.0153
w/o global memory	0.7879	0.0122	0.7942	0.0168
w/o retrieved context	0.6842	0.0176	0.6366	0.0286

TABLE V: Ablation study of HEMO on Bi-TSP20 and Tri-TSP20, averaged over four independent runs. HV and IGD for each variant are computed from the aggregated non-dominated solution fronts of all heuristics in the final heuristic Pareto front.


Bi-CVRP

Model	Token (M) $\downarrow$	Cost ( $)$ \downarrow$	Wall-clock (h) $\downarrow$	HV $\uparrow$	IGD $\downarrow$

GPT-5-nano	49.00	7.46	44.54	0.6173	0.0082
GPT-4.1-nano	29.80	3.82	13.95	0.5832	0.0355

TABLE VI: Cost and performance of HEMO under different LLM backbones on Bi-CVRP and Bi-SPDP with

N=20

. Performance is evaluated separately on 50 test instances for each task.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Problem	Size	Reference point $\mathbf{r}$	Ideal point $\mathbf{z}$
Bi-KP	50	$(-5,-5)$	$(-30,-30)$
	100	$(-20,-20)$	$(-50,-50)$
	200	$(-30,-30)$	$(-75,-75)$
Bi-MDKP	50	$(-5,-5)$	$(-30,-30)$
	100	$(-20,-20)$	$(-50,-50)$
	200	$(-30,-30)$	$(-85,-85)$

Appendix

TABLE VII: Reference points and ideal points for the MOCOP benchmarks.

Family	Problem	Objectives	Final test instances
Knapsack	Bi-KP	two collected profits	$n\in\{50,100,200\}$
Knapsack	Bi-MDKP	two collected profits	$n\in\{50,100,200\}$
Routing	Bi-CVRP	total distance; longest route	$n\in\{20,50,100\}$
Routing	Bi-SPDP	total distance; required vehicle capacity	$n\in\{20,50,100\}$
TSP	Bi-TSP	two tour lengths	$n\in\{20,50,100\}$
TSP	Tri-TSP	three tour lengths	$n\in\{20,50,100\}$

Appendix

TABLE VIII: Overview of the MOCOP benchmarks used in our experiments. Each synthetic problem size contains

50

fixed test instances. For FJSP, Mk15 is used during operator design for NSGA-II, while all 15 Brandimarte instances are used for final evaluation.

Problem	Design init.	Design steps	Test init.	Test steps
Bi-KP	100	2,000	100	10,000
Bi-MDKP	100	2,000	100	10,000
Bi-CVRP	100	2,000	100	10,000
Bi-SPDP	100	2,000	100	20,000
Bi-TSP	100	2,000	100	20,000
Tri-TSP	100	2,000	100	20,000

Appendix

TABLE IX: SEMO initialization and iteration budgets. “Design” denotes evaluation of candidates during harness self-evolution and inference of HEMO , whereas “test” denotes final evaluation of the selected candidates.

Task	Chromosome representation	Design targets in execution order
Bi-TSP	City permutation	tsp_oropt $\rightarrow$ tsp_2opt $\rightarrow$ tsp_3opt
Tri-TSP	City permutation	tsp_oropt $\rightarrow$ tsp_2opt $\rightarrow$ tsp_3opt
Bi-CVRP	Customer permutation (giant tour)	vrp_oropt $\rightarrow$ vrp_swap $\rightarrow$ vrp_2opt
Bi-SPDP	Signed node permutation	vrp_oropt $\rightarrow$ vrp_swap $\rightarrow$ vrp_2opt
Bi-KP	Binary item-selection vector	kp_bitflip $\rightarrow$ kp_crossover $\rightarrow$ kp_repair_mutation
Bi-MDKP	Binary item-selection vector	kp_bitflip $\rightarrow$ kp_crossover $\rightarrow$ kp_repair_mutation

Appendix

TABLE X: NSGA-II operator design targets and default execution order across the eight tasks. Every named operator is a design target. Arrows indicate sequential calls on the offspring population, not alternative operator choices.

Operator name	Operation and design scope
tsp_oropt	Relocate a contiguous tour segment by selecting its length, original location, and reinsertion position while preserving the order of nodes within the segment. The reference operator moves one to three consecutive nodes.
tsp_2opt	Reverse a contiguous tour segment to change its boundary connections and internal traversal direction. The design controls segment selection and reordering while preserving a valid city permutation.
tsp_3opt	Modify multiple tour segments through cut selection and reconnection. The reference operator reverses two segments defined by three cuts.
vrp_oropt	Relocate a contiguous customer or node segment, choosing which segment to move and where to insert it. The reference operators move one to three nodes.
vrp_swap	Exchange two customer or node positions to modify visit order while preserving node identifiers. The seed operator uses route-quality sampling for CVRP and swaps signed entries for SPDP.
vrp_2opt	Reverse a contiguous segment to modify route ordering and neighboring connections. The seed operator acts within one capacity-decoded route for CVRP and on the signed node permutation for SPDP.

Appendix

TABLE XI: Operator interfaces and their intended roles. Descriptions summarize the operation and its design scope, and task-specific feasibility safeguards are described below.

Problem	Evolution pop.	Evolution gen.	Test pop.	Test gen.
Bi-KP	50	15	200	200
Bi-MDKP	50	15	200	200
Bi-CVRP	30	15	200	100
Bi-SPDP	50	15	200	200
Bi-TSP	50	15	200	200
Tri-TSP	50	15	200	100

Appendix

TABLE XII: NSGA-II population sizes and generation budgets. “Evolution” denotes candidate evaluation during harness self-evolution. Inference with the selected harness doubles both evolution budgets, whereas “test” denotes final evaluation of the selected operator combinations.

Role	Memory field	Meaning and type
Retrieval scope	task_id	Task associated with the record ( str ), used to restrict retrieval to the current task or related scope.
	family , representation	Problem family and solution representation ( Optional[str] ), used for matching related search experience.
	objective_dims	Objective dimensionalities represented by the record ( List[str] , List[int] ).
	timestamp	Record creation time ( float ), providing a weak recency preference during retrieval.
Evaluation context	score	Observed candidate score vector ( Any , normally a numeric list), typically containing negative HV and per-instance runtime.
	valid , error	Evaluation validity and failure information ( Optional[bool] , Optional[str] ).

Appendix

TABLE XIII: Memory fields most relevant to experience retrieval and subsequent search decisions.

		SEMO		NSGA-II
Family	Task	Design size	Instances	Design size	Instances
TSP	Bi-TSP	20 cities	10	20 cities	10
	Tri-TSP	20 cities	10	20 cities	10
Routing	Bi-CVRP	50 customers	10	50 customers	10
	Bi-SPDP	20 nodes incl. depot	20	20 nodes incl. depot	20
Knapsack	Bi-KP	50 items	10	50 items	10

Appendix

TABLE XIV: Problem sizes and numbers of instances used for heuristic or operator design.

	$N=20$		$N=50$		$N=100$		Overall
Method	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	Mean HV $\uparrow$	Speedup $\uparrow$
NSGA-II + 2-opt	0.6241	257.486	0.4607	249.499	0.3549	251.704	0.4799	1.531 $\times$
NSGA-II + 3-opt	0.6152	260.655	0.4607	253.314	0.3549	249.597	0.4769	1.521 $\times$
NSGA-II + Or-opt	0.6150	266.671	0.3647	262.096	0.2832	272.126	0.4210	1.450 $\times$
NSGA-II + 2opt-3opt-oropt	0.5469	257.407	0.3612	252.412	0.2836	244.447	0.3972	1.540 $\times$
NSGA-II + 3opt-2opt-oropt	0.5474	175.315	0.3605	166.707	0.2782	205.978	0.3954	2.120 $\times$

Appendix

TABLE XV: Comparison of HEMO-NSGA-II with expert-designed TSP operators and operator combinations. HV and runtime are reported for 50 test instances at each problem size. Mean HV averages the three problem sizes. Speedup is computed from the mean runtime across the three sizes, using the slowest method as

1\times

. Best values in each column are shown in bold .

	Bi-FJSP						Tri-FJSP
	ID		OOD		All		ID		OOD		All
Method	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$	HV $\uparrow$	Time $\downarrow$
SEMO	0.7430	1.482	0.7789	14.672	0.7610	8.077	0.5434	5.014	0.3210	12.117	0.4322	8.566
NSGA-II	0.7166	1339.077	0.5915	1295.714	0.6540	1317.396	0.3066	1293.551	0.1784	1183.967	0.2425	1238.759
MOEA/D	0.8738	–	0.7801	–	0.8269	–	0.5516	–	0.3293	–	0.4404	–
PFG-MOEA	0.8565	287.431	0.7535	401.254	0.8050	344.343	0.5447	589.162	0.3218	879.100	0.4333	734.131

Appendix

TABLE XVI: Additional FJSP results with the SEMO backbone. ID comprises 15 synthetic instances and OOD comprises 15 Brandimarte instances. Time is in seconds per instance. Best displayed values are shown in bold , including ties, and “–” denotes runs exceeding the time limit.

	Expert			E2OC			HEMO
Setting	HV $\uparrow$	IGD $\downarrow$	Time $\downarrow$	HV $\uparrow$	IGD $\downarrow$	Time $\downarrow$	HV $\uparrow$	IGD $\downarrow$	Time $\downarrow$
Bi-CVRP 20	0.6001	0.011265	173.681	0.5953	0.012716	139.499	0.6011	0.011267	119.408
Bi-CVRP 50	0.5232	0.031433	243.641	0.5179	0.039418	279.866	0.5467	0.012060	292.293
Bi-CVRP 100	0.4579	0.095994	235.605	0.5138	0.043941	1651.226	0.5457	0.014028	1361.897
Bi-SPDP 20	0.7447	0.036631	154.625	0.7671	0.012824	158.575	0.7670	0.011057	162.802
Bi-SPDP 50	0.7951	0.041620	165.747	0.8185	0.020679	163.603	0.8268	0.015460	167.782

Appendix

TABLE XVII: Additional NSGA-II-based results, averaged over 50 test instances per setting. Time is in seconds per instance. Best displayed values are shown in bold and HEMO columns are shaded.

Fig. 4: Final solution archives of HEMO -SEMO and expert-designed baselines across 50 test instances per setting. Rows correspond to Bi-KP, Bi-MDKP, Bi-TSP, and Tri-TSP. Columns correspond to increasing problem sizes. Knapsack objectives are shown as positive profits (higher is better), and TSP objectives as distances (lower is better). All saved final archive points are retained.

Fig. 5: Final solution archives of operator combinations designed by HEMO and expert-designed operator combinations under NSGA-II, using matched population and generation budgets. Each panel includes 50 test instances. Rows correspond to Bi-KP, Bi-MDKP, Bi-TSP, and Tri-TSP. Columns correspond to increasing problem sizes. Knapsack profits are divided by the total available profit of the corresponding objective (higher is better). TSP objectives are distances (lower is better). All saved final archive points are retained.

Automated Heuristic Design

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

See all 85 papers

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization
May 8, 2026Yuping Yan, Jirui Han, Fei Ming +2Multi-Agent LLM Systems Multi-Agent System Optimization
School of Engineering Westlake University
RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience
Jul 13, 2026Yang Wu, Junran Pan, Yifan Zhang +3Automated Heuristic Design Evolutionary Optimization
C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing · University of Chinese Academy of Sciences, Nanjing +1
LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization
May 30, 2026Mingen Kuang, Xudong Deng, Xi Lin +3Automated Heuristic Design Evolutionary Optimization
Xi’an Jiao Tong University · Northwestern Polytechnical University

May 8, 2026J/K move · Enter open · S save

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

Yuping Yan, Jirui Han, Fei Ming, Yuanshuai Li+1

School of Engineering Westlake University

Multi-Agent LLM Systems Multi-Agent System Optimization Automated Heuristic Design Evolutionary Optimization Large Language Model-Guided Optimization Combinatorial Optimization+1

Open paper AskPDF arXiv

Large Language Models have recently emerged as a promising paradigm for automated heuristic design for NP-hard combinatorial optimization problems. Despite this progress, existing LLM-based methods typically rely on monolithic workflows constrained by rigid templates, thereby restricting memory-guided exploration and triggering premature convergence to local optima. To design an autonomous and collaborative architecture, we introduce HMACE, a Heterogeneous Multi-Agent Collaborative Evolution framework that reconceptualizes heuristic search as an organizational design problem. HMACE decomposes each evolutionary generation into an autonomous, role-specialized loop with four coordinated agents: a Proposer for strategy exploration, a Generator for executable heuristic synthesis, an Evaluator for empirical assessment, and a Reflector for archive-backed memory update. By coupling behavior-aware retrieval, lightweight candidate filtering, and fitness-grounded archive updates, HMACE guides the search toward diverse and promising heuristic behaviors while avoiding redundant evaluations. Extensive evaluations on representative COPs, including TSP, Online BPP, MKP, and PFSP, show that HMACE achieves a favorable quality-efficiency trade-off compared to state-of-the-art single-agent and multi-agent baselines. In the matched LLM-driven reference comparison, HMACE achieves the lowest average gaps on TSP and Online BPP (0.464% and 0.223%, respectively), while requiring only 0.13M and 0.42M tokens for the two tasks, substantially fewer than the compared baselines.

Abstract

Automated Heuristic Design

Explore similar work

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience

LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization