Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs

# Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs
Source: [https://arxiv.org/html/2608.06808](https://arxiv.org/html/2608.06808)
Shaofeng Zhang, Shengcai Liu, Zhiyuan Wang, and Ke TangShaofeng Zhang is with the Guangdong Provincial Key Laboratory of Brain\-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China, and also with the Zhongguancun Academy, Beijing 100094, China \(e\-mail: 12445025@mail\.sustech\.edu\.cn\)\. Shengcai Liu, Zhiyuan Wang, and Ke Tang are with the Guangdong Provincial Key Laboratory of Brain\-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China \(e\-mail: liusc3@sustech\.edu\.cn; wangzy2020@mail\.sustech\.edu\.cn; tangk3@sustech\.edu\.cn\)\.

###### Abstract

The Automatic Construction of Portfolios via Large Language Models \(LLM\-ACP\) suffers from poor generalization in practical few\-shot scenarios when solving complex combinatorial optimization problems\. Instance and algorithm co\-evolution frameworks address this by expanding the training dataset with generated hard instances on which the current algorithm portfolio underperforms, thereby enhancing generalization\. However, this paradigm faces two critical limitations: evaluating instance hardness relies on high\-quality reference solutions, and single\-mode generation patterns limit instance diversity\. To overcome these limitations, we introduce the Potential\-aware Instance and Algorithm Co\-evolution \(PIAC\) framework\. Our core contribution is twofold\. First, we propose*potential gain*, a novel metric that eliminates the need for reference solutions\. This metric estimates generalization gain by perturbing the generated algorithms and assessing their improvement potential on generated problem instances\. Second, PIAC leverages LLMs to synthesize diverse instance mutators, exploring a broader region of the problem\-instance space and thereby enhancing the portfolio’s generalization capabilities\. Given that perturbation spaces vary across different algorithms, we instantiate our framework on Greedy Constructive, Ant Colony Optimization, and Guided Local Search algorithmic backbones\. Comprehensive evaluations on the Traveling Salesman Problem \(TSP\) and Capacitated Vehicle Routing Problem \(CVRP\) across six distinct data distributions demonstrate that PIAC consistently outperforms state\-of\-the\-art LLM\-ACP baselines, notably achieving a 19\.76% relative improvement for TSP Greedy Constructive portfolios\.

## IIntroduction

Parallel Algorithm Portfolios \(PAPs\) have emerged as a powerful paradigm for solving complex engineering optimization problems\[[11](https://arxiv.org/html/2608.06808#bib.bib3),[8](https://arxiv.org/html/2608.06808#bib.bib5)\]\. Inspired by the No Free Lunch theorem\[[34](https://arxiv.org/html/2608.06808#bib.bib1)\], which posits that different algorithms exhibit varying performance across different problem characteristics, PAPs aim to construct a complementary set of member algorithms to enhance overall performance across the entire problem space\. During inference, a PAP typically runs multiple member algorithms in parallel and returns the best solution found as the final output\. In doing so, PAPs can effectively exploit the complementarity among their members while fully leveraging modern parallel computing resources, such as multi\-core CPUs, to achieve superior overall performance\.

Since manually constructing a high\-quality PAP is non\-trivial, Automated Construction of Portfolios \(ACP\) has been extensively studied\[[38](https://arxiv.org/html/2608.06808#bib.bib8),[15](https://arxiv.org/html/2608.06808#bib.bib9)\]\. To reduce manual effort, mainstream ACP frameworks adopt the data\-driven paradigm\. Given an algorithm search space \(traditionally the parameter configuration space of base solvers\) and a set of training instances, the standard framework iteratively explores this space to evolve candidate algorithms\. Guided by their performance on the training instances, it ultimately returns a portfolio of complementary member algorithms that maximizes overall performance\. Recent advances in the programming capabilities of Large Language Models \(LLMs\) have introduced Automatic Construction of Portfolios via LLMs \(LLM\-ACP\) as a powerful new subfield of ACP\[[18](https://arxiv.org/html/2608.06808#bib.bib14),[43](https://arxiv.org/html/2608.06808#bib.bib15),[16](https://arxiv.org/html/2608.06808#bib.bib23)\]\. The fundamental distinction between LLM\-ACP and ACP lies in the algorithm search space\. LLM\-ACP shifts the paradigm from tuning fixed parameter configurations to exploring an open\-ended programmatic space, such as heuristic code snippets\.

Despite this progress, ACP \(including LLM\-ACP\) frequently encounters the*few\-shot*generalization challenge\. In practice, only a limited number of training instances are available, and they often fail to capture the complex instance distributions encountered in real\-world data\[[26](https://arxiv.org/html/2608.06808#bib.bib30),[29](https://arxiv.org/html/2608.06808#bib.bib31)\]\. Consequently, portfolios constructed on such limited training sets are highly susceptible to overfitting and often fail to generalize to unseen instances\. To overcome this limitation, prior studies \(e\.g\., CEPS\[[28](https://arxiv.org/html/2608.06808#bib.bib6)\]and DACE\[[33](https://arxiv.org/html/2608.06808#bib.bib7)\]\) have leveraged instance\-algorithm co\-evolution to dynamically expand the training dataset\. In this paper, we define thequalityof a problem instance as the improvement in a PAP’s generalization performance achieved by incorporating it into the training dataset\. To obtain such high\-quality instances, existing methods actively generate adversarial or “hard” instances that the current portfolio struggles to solve\. Specifically, these hard instances expose regions of the problem space where current algorithms underperform\. Augmenting the training set with these instances drives the portfolio to improve its performance in these specific regions, thereby enhancing overall generalization\.

However, adapting traditional co\-evolutionary frameworks, such as CEPS and DACE, to the LLM\-ACP paradigm exposes two critical limitations\. First, regardingreliance on high\-quality solutions, existing methods typically depend on near\-optimal reference solutions to evaluate the quality of newly generated instances\[[30](https://arxiv.org/html/2608.06808#bib.bib2),[32](https://arxiv.org/html/2608.06808#bib.bib13),[3](https://arxiv.org/html/2608.06808#bib.bib4)\]\. Specifically, these approaches evaluate an instance’s quality based on its difficulty, termed thehardness metric, and quantify this metric by calculating the performance gap between the current PAP and the reference solutions\. In many practical or newly formulated scenarios, acquiring such high\-quality solutions is a challenging task\. Second, regardingsingle\-mode instance generation patterns, prior instance generation strategies often rely on fixed, predefined operators, such as simple geometric transformations or random perturbations\[[28](https://arxiv.org/html/2608.06808#bib.bib6),[33](https://arxiv.org/html/2608.06808#bib.bib7)\]\. This single\-mode generation paradigm lacks diversity, yielding highly homogeneous instances that restrict the generalization capability of the resulting algorithm portfolio\.

To overcome these limitations, we introduce the Potential\-aware Instance and Algorithm Co\-evolution \(PIAC\) framework\. While building upon the co\-evolution framework, PIAC advances the paradigm through two core innovations tailored to LLM\-ACP\. First, we propose*potential gain*, a novel potential\-aware metric that avoids the need for high\-quality reference solutions\. Rather than relying on the hardness metric to determine an instance’s quality, PIAC shifts the evaluation focus to the algorithm portfolio’s “potential for improvement”\. The potential gain metric operates by perturbing the designed algorithms and quantifying the performance improvement achieved by the perturbed algorithms relative to the original algorithms on newly generated instances\. By directly measuring this empirical gain,*potential gain*provides a surrogate signal for the portfolio’s improvement potential on the given instance\. Second, to enhance the diversity of generated instances, PIAC leverages the code\-generation capabilities of LLMs to synthesize and evolve a population of programmatic instance mutators\. By transitioning from static, predefined operators to diverse mutators, PIAC effectively expands the searchable instance space and further enhances generalization\. Together, potential\-aware evaluation and programmatic instance synthesis augment the training set with valuable instances, guiding portfolio evolution toward greater complementarity and better generalization\. To evaluate the generalization of the algorithm portfolios, we construct the PAPs in the few\-shot setting and measure their performance across six distinct data distributions for both the Traveling Salesman Problem \(TSP\) and the Capacitated Vehicle Routing Problem \(CVRP\)\. The main contributions of this work are summarized as follows:

- •Potential\-Aware Instance Evaluation\.We propose a novelpotential\-awaremetric to evaluate generated instances without reference solutions\. By perturbing the generated algorithms, the metric estimates the performance gains achievable on each instance, thereby identifying high\-quality training instances\.
- •LLM\-Driven Instance Evolution Mechanisms\.We leverage the code\-generation capabilities of LLMs to dynamically synthesize a diverse set of instance mutators, enabling the instance generation process to explore a broader and more diverse instance space\.
- •Instantiation on Multiple Algorithmic Backbones\.We apply our framework to Greedy Constructive, Ant Colony Optimization, and Guided Local Search algorithmic backbones\. Comprehensive evaluations demonstrate that PIAC consistently outperforms state\-of\-the\-art LLM\-ACP baselines, notably achieving a 19\.76% relative improvement for TSP Greedy Constructive portfolios\.

The remainder of this paper is organized as follows\. Section[II](https://arxiv.org/html/2608.06808#S2)formalizes the problem of ACP and reviews relevant prior work\. Section[III](https://arxiv.org/html/2608.06808#S3)introduces the proposed PIAC framework\. Section[IV](https://arxiv.org/html/2608.06808#S4)provides algorithm\-specific instantiations of the framework\. Section[V](https://arxiv.org/html/2608.06808#S5)presents a comprehensive empirical evaluation of our approach\. Finally, Section[VI](https://arxiv.org/html/2608.06808#S6)concludes the article and outlines directions for future research\. Our code is available athttps://anonymous\.4open\.science/r/piac\-BAF3\.

## IIProblem Definition and Related Work

### II\-AProblem Formulation

Assume that the construction of a PAP is defined over the entire problem class\. Letx∈Ωx\\in\\Omegadenote a problem instance, whereΩ\\Omegarepresents the complete instance space\. The backboneBBspecifies a complete solution procedure, such as greedy construction or ant colony optimization\. LetℋB\\mathcal\{H\}\_\{B\}denote the corresponding space of heuristic functions that can be constructed by the LLM\. Given an instancex∈Ωx\\in\\Omegaand a solver statessencountered during solution construction or search, eachH∈ℋBH\\in\\mathcal\{H\}\_\{B\}produces a heuristic matrixM=H​\(x,s\)M=H\(x,s\)that guides the subsequent decision made by the backbone\. Instantiating the fixed backboneBBwithHHyields a complete executable algorithm, denoted byA=B​\[H\]A=B\[H\]\. Accordingly, the complete algorithm space under this backbone is

𝒜=\{B​\[H\]∣H∈ℋB\}\.\\mathcal\{A\}=\\\{B\[H\]\\mid H\\in\\mathcal\{H\}\_\{B\}\\\}\.\(1\)PIAC employs the LLM to construct and evolve the heuristic componentHHwhile keepingBBunchanged\. Throughout this paper, “algorithm” refers to the complete executable algorithmA=B​\[H\]A=B\[H\], rather than the isolated heuristic functionHH\. A PAP is denoted by𝔸=\{A1,…,AK\}\\mathbb\{A\}=\\\{A\_\{1\},\\ldots,A\_\{K\}\\\}, whereAj=B​\[Hj\]∈𝒜A\_\{j\}=B\[H\_\{j\}\]\\in\\mathcal\{A\}and𝔸⊆𝒜\\mathbb\{A\}\\subseteq\\mathcal\{A\}\. Given a problem instancexx, letF​\(A,x\)F\(A,x\)denote the performance of algorithmAAonxx\. Without loss of generality, we assume that smaller values indicate better performance\. Accordingly, the performance of the PAP𝔸\\mathbb\{A\}on instancexxis defined as

F​\(𝔸,x\)=minA∈𝔸⁡F​\(A,x\),F\(\\mathbb\{A\},x\)=\\min\_\{A\\in\\mathbb\{A\}\}F\(A,x\),\(2\)which indicates that the portfolio performance on a given instance is determined by the best\-performing algorithm within the PAP\.

Ideally, the objective of automated PAP construction is to identify an optimal PAP, denoted by𝔸∗\\mathbb\{A\}^\{\\ast\}, that achieves the best generalization performance over the entire problem domain:

𝔸∗=arg⁡min𝔸⊆𝒜,\|𝔸\|=K⁡𝔼x∼p​\(x\)​\[F​\(𝔸,x\)\],\\mathbb\{A\}^\{\\ast\}=\\arg\\min\_\{\\mathbb\{A\}\\subseteq\\mathcal\{A\},\\,\|\\mathbb\{A\}\|=K\}\\mathbb\{E\}\_\{x\\sim p\(x\)\}\\left\[F\(\\mathbb\{A\},x\)\\right\],\(3\)wherep​\(x\)p\(x\)denotes the underlying distribution over the problem instance space\.

However, in practical scenarios, the true distribution over the entire instance space is usually unavailable\. Therefore, existing PAP construction methods commonly optimize the empirical performance of the PAP on a given training dataset𝒟⊂Ω\\mathcal\{D\}\\subset\\Omega:

𝔸^∗=arg⁡min𝔸⊆𝒜,\|𝔸\|=K⁡F​\(𝔸,𝒟\),\\widehat\{\\mathbb\{A\}\}^\{\\ast\}=\\arg\\min\_\{\\mathbb\{A\}\\subseteq\\mathcal\{A\},\\,\|\\mathbb\{A\}\|=K\}F\(\\mathbb\{A\},\\mathcal\{D\}\),\(4\)whereF​\(𝔸,𝒟\)=1\|𝒟\|​∑x∈𝒟F​\(𝔸,x\)F\(\\mathbb\{A\},\\mathcal\{D\}\)=\\frac\{1\}\{\|\\mathcal\{D\}\|\}\\sum\_\{x\\in\\mathcal\{D\}\}F\(\\mathbb\{A\},x\)\.

This empirical objective implicitly assumes that the training dataset𝒟\\mathcal\{D\}is sufficiently representative of the complete problem instance spaceΩ\\Omega\. Nevertheless, in few\-shot scenarios, the available training instances are often scarce and insufficient to capture the diversity and critical structural characteristics of the underlying problem distribution\. As a result, the constructed PAP may suffer from limited generalization ability when applied to unseen problem instances\.

![Refer to caption](https://arxiv.org/html/2608.06808v1/x1.png)Figure 1:PIAC Framework:A co\-evolutionary framework for LLM\-driven portfolio construction\. By alternating between instance synthesis via LLM\-generated mutators and algorithm portfolio optimization, PIAC jointly enhances training data coverage and the generalization performance of the algorithm portfolios\.
### II\-BExisting ACP Framework

The automated construction of algorithm portfolios \(ACP\) has driven significant advancements in solving hard combinatorial problems\[[8](https://arxiv.org/html/2608.06808#bib.bib5),[24](https://arxiv.org/html/2608.06808#bib.bib44),[9](https://arxiv.org/html/2608.06808#bib.bib46)\]\. Existing approaches generally follow two paradigms\. The first constructs a globally complementary set of member algorithms evaluated across the entire instance space, as exemplified by Hydra\[[38](https://arxiv.org/html/2608.06808#bib.bib8)\], GLOBAL\[[15](https://arxiv.org/html/2608.06808#bib.bib9)\], and PARHYDRA\[[15](https://arxiv.org/html/2608.06808#bib.bib9)\]\. In contrast, the second paradigm addresses instance heterogeneity by partitioning the problem space and constructing a tailored component algorithm for each specific cluster, as demonstrated by CLUSTERING\[[13](https://arxiv.org/html/2608.06808#bib.bib10)\]and PCIT\[[21](https://arxiv.org/html/2608.06808#bib.bib11)\]\. By yielding diverse member algorithms, these paradigms inherently facilitate automated algorithm selection \(AS\)\[[37](https://arxiv.org/html/2608.06808#bib.bib36),[35](https://arxiv.org/html/2608.06808#bib.bib41),[25](https://arxiv.org/html/2608.06808#bib.bib45)\]\. However, traditional frameworks typically cast ACP strictly as a parameter configuration problem\. Consequently, they confine the search to the predefined parameter spaces of existing solvers, fundamentally precluding the discovery of structurally novel algorithms\.

To break these structural limits, recent studies leverage LLMs to automatically design heuristics or executable code for discrete optimization\[[36](https://arxiv.org/html/2608.06808#bib.bib16),[12](https://arxiv.org/html/2608.06808#bib.bib39),[20](https://arxiv.org/html/2608.06808#bib.bib42),[39](https://arxiv.org/html/2608.06808#bib.bib43)\]\. These methods generally establish a novel paradigm integrating LLMs with Evolutionary Computation \(EC\)\. In this framework, LLMs act as intelligent variation operators within an evolutionary loop to iteratively generate and refine heuristic code, as demonstrated by methods such as FunSearch\[[27](https://arxiv.org/html/2608.06808#bib.bib17)\], EoH\[[17](https://arxiv.org/html/2608.06808#bib.bib18)\], ReEvo\[[40](https://arxiv.org/html/2608.06808#bib.bib19)\], HSEvo\[[5](https://arxiv.org/html/2608.06808#bib.bib20)\], and MCTS\-AHD\[[44](https://arxiv.org/html/2608.06808#bib.bib21)\]\. This paradigm, formally recognized as LLM\-based Automatic Heuristic Design \(LLM\-AHD\), has been widely applied across diverse domains, including recommender systems\[[19](https://arxiv.org/html/2608.06808#bib.bib37)\]and scientific discovery\[[4](https://arxiv.org/html/2608.06808#bib.bib38)\]\. Building upon this foundation, the research frontier has shifted toward LLM\-ACP to explicitly address instance heterogeneity\. For example, InstSpecHH\[[42](https://arxiv.org/html/2608.06808#bib.bib22)\]partitions the problem space to evolve instance\-specific heuristics for feature\-based subclasses\. Concurrently, EoH\-S\[[16](https://arxiv.org/html/2608.06808#bib.bib23)\]directly targets portfolio synergy by employing a complementary\-aware memetic search to evolve a highly cooperative heuristic set that collectively covers diverse instance distributions\.

While existing LLM\-ACP methods demonstrate strong performance, they predominantly rely on the assumption of abundant training data, inherently struggling with the few\-shot generalization challenge in data\-scarce scenarios\. In traditional ACP, data scarcity is typically mitigated via co\-evolutionary frameworks, such as CEPS\[[28](https://arxiv.org/html/2608.06808#bib.bib6)\], GAST\[[22](https://arxiv.org/html/2608.06808#bib.bib12)\], and DACE\[[33](https://arxiv.org/html/2608.06808#bib.bib7)\]\. These frameworks fundamentally operate through a competitive, two\-step iterative mechanism\. The process begins by evolving a PAP over a given training dataset to maximize overall portfolio performance\. Subsequently, the training set is augmented by generating and incorporating novel instances explicitly designed to minimize the performance of the current PAP\. These two adversarial phases alternate continuously, ultimately yielding a robust parallel algorithm portfolio with strong generalization capabilities\. Extending this adversarial paradigm to deep learning, ASP\[[32](https://arxiv.org/html/2608.06808#bib.bib13)\]formulates distributional exploration as a two\-player zero\-sum meta\-game to train best\-response generators alongside neural solvers\.

Despite the potential of integrating this co\-evolutionary paradigm with LLM\-ACP, current frameworks present two primary limitations\. First, regarding the reliance on high\-quality solutions, existing methods typically depend on near\-optimal reference solutions to evaluate the difficulty of newly generated instances\[[30](https://arxiv.org/html/2608.06808#bib.bib2),[32](https://arxiv.org/html/2608.06808#bib.bib13),[3](https://arxiv.org/html/2608.06808#bib.bib4)\]\. This dependency severely restricts the framework’s applicability, making it challenging to extend to practical or newly formulated problem domains\. Second, regarding single\-mode instance generation, current instance generation strategies often rely on static, predefined generation operators\[[28](https://arxiv.org/html/2608.06808#bib.bib6),[33](https://arxiv.org/html/2608.06808#bib.bib7)\]\. This unimodal generation paradigm fundamentally lacks diversity, yielding highly homogeneous instances that hinder further improvements to the generalization capability of the evolved PAP\.

## IIIThe Proposed PIAC Framework

We extend the adversarial co\-evolution framework\[[28](https://arxiv.org/html/2608.06808#bib.bib6)\]to the LLM\-ACP paradigm\. While our Potential\-aware Instance and Algorithm Co\-evolution \(PIAC\) framework adopts the alternating optimization phases of CEPS to iteratively evolve both the algorithm portfolio and the training instances, its core novelty lies within the instance evolution phase\. Existing co\-evolution frameworks typically equate instance quality with instance hardness, inherently relying on high\-quality reference solutions, and are often restricted to single\-mode generation patterns\. PIAC addresses these limitations by introducing the potential gain metric, which circumvents the need for reference solutions, coupled with an evolutionary search over mutator programs to expand the searchable instance space\.

As illustrated in Algorithm[1](https://arxiv.org/html/2608.06808#alg1), the framework consists of two alternating phases:

1. 1\.LLM\-Driven Instance Generation:The LLM generates executable mutator code to synthesize novel instances\. The primary objective of this process is to maximize the overall quality of the generated instancesmax𝒟t​∑x∈𝒟tV​\(x;𝔸t−1\)\\max\_\{\\mathcal\{D\}\_\{t\}\}\\sum\_\{x\\in\\mathcal\{D\}\_\{t\}\}V\(x;\\mathbb\{A\}\_\{t\-1\}\), whereV​\(x;𝔸t−1\)V\(x;\\mathbb\{A\}\_\{t\-1\}\)denotes the potential gain of generated instancexxwith respect to the current portfolio𝔸t−1\\mathbb\{A\}\_\{t\-1\}\.
2. 2\.LLM\-Driven Algorithm Portfolio Construction:Subsequently, the LLM evolves the heuristic portfolio to address these challenging new instances\. The goal is to identify a portfolio𝔸t\\mathbb\{A\}\_\{t\}of sizeKKthat minimizes the evaluation metricFFover the accumulated training set𝒟t​r​a​i​n\\mathcal\{D\}^\{train\}:min𝔸t:\|𝔸t\|=K⁡F​\(𝔸t,𝒟t​r​a​i​n\)\\min\_\{\\mathbb\{A\}\_\{t\}:\|\\mathbb\{A\}\_\{t\}\|=K\}F\(\\mathbb\{A\}\_\{t\},\\mathcal\{D\}^\{train\}\)\.

To systematically present these contributions, Section[III\-A](https://arxiv.org/html/2608.06808#S3.SS1)details the LLM\-driven instance generation phase, encompassing both the mutator search and the potential\-aware evaluation\. Subsequently, Section[III\-B](https://arxiv.org/html/2608.06808#S3.SS2)outlines the LLM\-based algorithm portfolio construction process\.

Algorithm 1PIAC0:Initial dataset

𝒟0\\mathcal\{D\}\_\{0\}, algorithmic backbone

BB, portfolio size

KK, max iterations

TT, max mutator evaluations

F​EmFE\_\{m\}, max algorithm evaluations

F​EaFE\_\{a\}, number of augmented instances

NaugN\_\{\\mathrm\{aug\}\}, number of executions per mutator

NexecN\_\{\\mathrm\{exec\}\}
0:Final complementary algorithm portfolio

𝔸T\\mathbb\{A\}\_\{T\}
1:/\* Phase 1: Initialization \*/

2:Initialize accumulated training dataset:

𝒟t​r​a​i​n←𝒟0\\mathcal\{D\}^\{train\}\\leftarrow\\mathcal\{D\}\_\{0\}\.

3:Construct initial portfolio

𝔸0\\mathbb\{A\}\_\{0\}of size

KKon

𝒟0\\mathcal\{D\}\_\{0\}via LLM generation and greedy selection\.

4:/\* Phase 2: Co\-Evolution Loop \*/

5:for

t=1,2,…,T−1t=1,2,\\ldots,T\-1do

6:/\* Step 2\.1: LLM\-Driven Data Generation\*/

7:Initialize candidate instance set

𝒳c​a​n​d←∅\\mathcal\{X\}\_\{cand\}\\leftarrow\\emptyset\.

8:Prompt LLM to generate initial mutator set

ℳp​r​e​v\\mathcal\{M\}\_\{prev\}\.

9:

em←0,ea←0\.e\_\{m\}\\leftarrow 0,e\_\{a\}\\leftarrow 0\.
10:while

em<F​Eme\_\{m\}<FE\_\{m\}do

11:Select parent mutators from

ℳp​r​e​v\\mathcal\{M\}\_\{prev\}\.

12:Prompt LLM to generate child mutators

ℳc​h​i​l​d\\mathcal\{M\}\_\{child\}\.

13:foreachchild mutator

m∈ℳc​h​i​l​dm\\in\\mathcal\{M\}\_\{child\}do

14:Execute

mmfor

NexecN\_\{\\mathrm\{exec\}\}times, independently sampling base instances

xb​a​s​e∼𝒟0x\_\{base\}\\sim\\mathcal\{D\}\_\{0\}each time to synthesize

𝒳n​e​w\\mathcal\{X\}\_\{new\}\.

15:Evaluate the potential gain

V​\(x;𝔸t−1\)V\(x;\\mathbb\{A\}\_\{t\-1\}\)for instances in

𝒳n​e​w\\mathcal\{X\}\_\{new\}via Eq\. \([6](https://arxiv.org/html/2608.06808#S3.E6)\)\.

16:Update fitness of

mmvia Eq\. \([7](https://arxiv.org/html/2608.06808#S3.E7)\)\.

17:Add the evaluated instances

𝒳n​e​w\\mathcal\{X\}\_\{new\}to

𝒳c​a​n​d\\mathcal\{X\}\_\{cand\}\.

18:endfor

19:

ℳp​r​e​v←ℳc​h​i​l​d\\mathcal\{M\}\_\{prev\}\\leftarrow\\mathcal\{M\}\_\{child\},

em←em\+\|ℳc​h​i​l​d\|e\_\{m\}\\leftarrow e\_\{m\}\+\|\\mathcal\{M\}\_\{child\}\|\.

20:endwhile

21:Select top\-

NaugN\_\{\\mathrm\{aug\}\}instances from

𝒳c​a​n​d\\mathcal\{X\}\_\{cand\}with maximum

V​\(x;𝔸t−1\)V\(x;\\mathbb\{A\}\_\{t\-1\}\)to form

𝒟t\\mathcal\{D\}\_\{t\}\.

22:

𝒟t​r​a​i​n←𝒟t​r​a​i​n∪𝒟t\\mathcal\{D\}^\{train\}\\leftarrow\\mathcal\{D\}^\{train\}\\cup\\mathcal\{D\}\_\{t\}\.

23:/\* Step 2\.2: LLM\-Driven Algorithm Construction \*/

24:Initialize current portfolio

𝔸t←𝔸t−1\\mathbb\{A\}\_\{t\}\\leftarrow\\mathbb\{A\}\_\{t\-1\}\.

25:while

ea<F​Eae\_\{a\}<FE\_\{a\}do

26:Select parent algorithms from

𝔸t\\mathbb\{A\}\_\{t\}for eitherCrossoverorMutation\.

27:Prompt the LLM to generate a set of child heuristic components

ℋc​h​i​l​d\\mathcal\{H\}\_\{child\}\.

28:Instantiate complete child algorithms

𝒜c​h​i​l​d←\{B​\[H\]∣H∈ℋc​h​i​l​d\}\\mathcal\{A\}\_\{child\}\\leftarrow\\\{B\[H\]\\mid H\\in\\mathcal\{H\}\_\{child\}\\\}\.

29:Evaluate

𝒜c​h​i​l​d\\mathcal\{A\}\_\{child\}on

𝒟t​r​a​i​n\\mathcal\{D\}^\{train\}\.

30:Update

𝔸t\\mathbb\{A\}\_\{t\}using the greedy selection and replacement strategies in Eq\. \([10](https://arxiv.org/html/2608.06808#S3.E10)\) and \([11](https://arxiv.org/html/2608.06808#S3.E11)\)\.

31:

ea←ea\+\|𝒜c​h​i​l​d\|e\_\{a\}\\leftarrow e\_\{a\}\+\|\\mathcal\{A\}\_\{child\}\|\.

32:endwhile

33:endfor

34:returnFinal portfolio

𝔸T\\mathbb\{A\}\_\{T\}

### III\-APotential\-Aware Instance Generation

#### III\-A1Potential\-Aware Instance Evaluation

A critical challenge in the instance generation process is evaluating the quality of newly generated instances\. A straightforward approach would be to incorporate each candidate instance into the training set and re\-evolve the portfolio to measure the resulting performance improvement\. Traditional methods instead approximate instance quality by absolute hardness, typically measured using the optimality gap to a high\-quality reference solution\[[30](https://arxiv.org/html/2608.06808#bib.bib2),[32](https://arxiv.org/html/2608.06808#bib.bib13),[3](https://arxiv.org/html/2608.06808#bib.bib4)\]\. However, obtaining such reference solutions is challenging, and absolute hardness does not necessarily indicate that an instance can guide further portfolio improvement\. For example, an instance may be challenging for every member algorithm in the current PAP yet offer little room for further performance improvement\. PIAC instead uses potential gainV​\(x;𝔸t−1\)V\(x;\\mathbb\{A\}\_\{t\-1\}\)as a surrogate for instance\-quality evaluation\. It measures the current portfolio’s improvement potential under controlled perturbations\. If perturbing the generated algorithms yields a superior solution, the portfolio retains exploitable room for improvement on that instance, indicating higher estimated instance quality for subsequent evolution\.

The operational mechanism of this metric relies on the internal heuristic component of each complete algorithm\. Under the fixed backboneBB, consider a portfolio memberAj=B​\[Hj\]A\_\{j\}=B\[H\_\{j\}\], whereHjH\_\{j\}is the LLM\-constructed heuristic function embedded inBB\. For the instancex∈Ωx\\in\\Omegaand the solver statessencountered during solution construction or search, the heuristic component produces a heuristic matrixMj=Hj​\(x,s\)M\_\{j\}=H\_\{j\}\(x,s\)that guides the subsequent decision\. We introduce aperturbation operatorPξP\_\{\\xi\}that acts only on this heuristic matrix:

M~j\(ξ\)=H~j\(ξ\)​\(x,s\)=Pξ​\(Mj\)=Mj⊙max⁡\(ε​𝟏,𝟏\+E\(ξ\)\),\\widetilde\{M\}\_\{j\}^\{\(\\xi\)\}=\\widetilde\{H\}\_\{j\}^\{\(\\xi\)\}\(x,s\)=P\_\{\\xi\}\(M\_\{j\}\)=M\_\{j\}\\odot\\max\\\!\\left\(\\varepsilon\\mathbf\{1\},\\mathbf\{1\}\+E^\{\(\\xi\)\}\\right\),\(5\)whereξ\\xiindexes an independent realization of the perturbation,E\(ξ\)E^\{\(\\xi\)\}is a random matrix with the same dimensions asMjM\_\{j\}, andEu​v\(ξ\)​∼i\.i\.d\.​𝒩​\(0,σ2\)E\_\{uv\}^\{\(\\xi\)\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\mathcal\{N\}\(0,\\sigma^\{2\}\)\. Here,uuandvvindex the entries ofMjM\_\{j\},⊙\\odotdenotes element\-wise multiplication,𝟏\\mathbf\{1\}is the all\-ones matrix with the same dimensions asMjM\_\{j\}, andε\>0\\varepsilon\>0is a small constant that clips the multiplicative factors away from zero\. Embedding the perturbed heuristic component into the same backbone yields the complete perturbed algorithmA~j\(ξ\)=B​\[H~j\(ξ\)\]\\widetilde\{A\}\_\{j\}^\{\(\\xi\)\}=B\[\\widetilde\{H\}\_\{j\}^\{\(\\xi\)\}\]\.

To illustrate, consider a constructive framework for the Traveling Salesman Problem \(TSP\) where the heuristic outputs a priority vectorMMfor unvisited nodes\. Conventionally, the framework greedily visits the node with the highest priority at each step\. Under our formulation, the priority of each nodeccis perturbed tom~c=mc​max⁡\(ε,1\+ϵc\)\\tilde\{m\}\_\{c\}=m\_\{c\}\\max\(\\varepsilon,1\+\\epsilon\_\{c\}\)withϵc∼𝒩​\(0,σ2\)\\epsilon\_\{c\}\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}\)\. Although the framework strictly retains its standard greedy selection rule \(c~∗=arg⁡maxc∈C⁡m~c\\tilde\{c\}^\{\*\}=\\arg\\max\_\{c\\in C\}\\tilde\{m\}\_\{c\}\), the injected noise shifts the relative priority rankings and directly alters the chosen decision variables at each step\. Consequently, by perturbing the original heuristic strategy, this mechanism effectively simulates a newly constructed prioritization policy that empowers the search process to escape local optima\.

Based on this operator, we define thepotential gain\. LetNpN\_\{p\}denote the total perturbation budget for the current portfolio𝔸=\{A1,…,AK\}\\mathbb\{A\}=\\\{A\_\{1\},\\ldots,A\_\{K\}\\\}\. We distribute this budget as evenly as possible among theKKportfolio members\. Specifically, letq=⌊Np/K⌋q=\\lfloor N\_\{p\}/K\\rfloorandrp=NpmodKr\_\{p\}=N\_\{p\}\\bmod K\. The number of perturbations assigned toAjA\_\{j\}isNp,j=q\+𝕀​\(j≤rp\)N\_\{p,j\}=q\+\\mathbb\{I\}\(j\\leq r\_\{p\}\)\. Thus, the firstrpr\_\{p\}algorithms receiveq\+1q\+1perturbations each, while the remaining algorithms receiveqqperturbations each, ensuring∑j=1KNp,j=Np\\sum\_\{j=1\}^\{K\}N\_\{p,j\}=N\_\{p\}\. For each complete algorithmAj=B​\[Hj\]A\_\{j\}=B\[H\_\{j\}\], we performNp,jN\_\{p,j\}independent applications of the perturbation operatorPξP\_\{\\xi\}to its heuristic componentHjH\_\{j\}\. This produces perturbed heuristic componentsH~j\(1\),…,H~j\(Np,j\)\\widetilde\{H\}\_\{j\}^\{\(1\)\},\\ldots,\\widetilde\{H\}\_\{j\}^\{\(N\_\{p,j\}\)\}and the corresponding complete algorithmsA~j\(ℓ\)=B​\[H~j\(ℓ\)\]\\widetilde\{A\}\_\{j\}^\{\(\\ell\)\}=B\[\\widetilde\{H\}\_\{j\}^\{\(\\ell\)\}\]\. The resulting perturbed algorithm set is𝔸~=\{A~j\(ℓ\)=B​\[H~j\(ℓ\)\]∣j=1,…,K,ℓ=1,…,Np,j\}\\widetilde\{\\mathbb\{A\}\}=\\\{\\widetilde\{A\}\_\{j\}^\{\(\\ell\)\}=B\[\\widetilde\{H\}\_\{j\}^\{\(\\ell\)\}\]\\mid j=1,\\ldots,K,\\;\\ell=1,\\ldots,N\_\{p,j\}\\\}\. The potential gainV​\(x;𝔸\)V\(x;\\mathbb\{A\}\)for an instancexxis defined as the relative improvement achieved by the best\-performing complete perturbed algorithm:

V​\(x;𝔸\)=F​\(𝔸,x\)−F​\(𝔸~,x\)F​\(𝔸~∪𝔸,x\)\.V\(x;\\mathbb\{A\}\)=\\frac\{F\(\\mathbb\{A\},x\)\-F\(\\widetilde\{\\mathbb\{A\}\},x\)\}\{F\(\\widetilde\{\\mathbb\{A\}\}\\cup\\mathbb\{A\},x\)\}\.\(6\)
If applying slight noise to the scoring matrix yields a significantly better solution than the original deterministic algorithm, it indicates that the portfolio’s decision boundary on this instance is suboptimal\. This improvement, quantified as the potential gain, allows us to identify instances that expose latent weaknesses in the portfolio, marking them as high\-value training data\. Because the structure of the scoring matrix and its corresponding perturbation operation depend on the underlying algorithmic architecture, we provide algorithm\-specific instantiations of this perturbation mechanism in Section[IV](https://arxiv.org/html/2608.06808#S4)\.

#### III\-A2Instance Generation via Mutator Evolution

Conventional problem instance generators rely on predefined mutation operators, which often produce homogeneous patterns that fail to adequately expose algorithmic weaknesses\[[28](https://arxiv.org/html/2608.06808#bib.bib6)\]\. To overcome this limitation, we conceptualize instance generation as an evolutionary search over the space of mutator programs\. We maintain a population of mutators, where the fitness of each mutatormmis evaluated by its ability to generate instances with high quality under the current algorithm portfolio𝔸t−1\\mathbb\{A\}\_\{t\-1\}\. To ensure a robust evaluation, the mutatormmis applied toNe​x​e​cN\_\{exec\}base instances independently sampled from the initial data distribution𝒟0\\mathcal\{D\}\_\{0\}, and its overall fitness is defined as the average value across these generated instances:

f​\(m\)\\displaystyle f\(m\)=1Ne​x​e​c​∑r=1Ne​x​e​cV​\(m​\(xb​a​s​e\(r\)\);𝔸t−1\),\\displaystyle=\\frac\{1\}\{N\_\{exec\}\}\\sum\_\{r=1\}^\{N\_\{exec\}\}V\\big\(m\(x\_\{base\}^\{\(r\)\}\);\\mathbb\{A\}\_\{t\-1\}\\big\),\(7\)where​xb​a​s​e\(r\)∼𝒟0,r=1,…,Ne​x​e​c\.\\displaystyle\\quad\\text\{where \}x\_\{base\}^\{\(r\)\}\\sim\\mathcal\{D\}\_\{0\},\\quad r=1,\\ldots,N\_\{exec\}\.We use potential gainV​\(x;𝔸\)V\(x;\\mathbb\{A\}\), defined in Eq\. \([6](https://arxiv.org/html/2608.06808#S3.E6)\), as the surrogate quality score in the mutator fitness function\. A higher fitness indicates that the mutator effectively synthesizes instances with higher surrogate quality scores with respect to the current portfolio\.

During each evolutionary generation, we sample parent mutators from the current populationℳprev\\mathcal\{M\}\_\{\\text\{prev\}\}using rank\-based stochastic selection, where selection probability is proportional to inverse rank, favoring lower\-rank \(better\-performing\) mutators\. The LLM is then prompted to performcrossoverandmutationoperations to construct a new generation of child mutatorsℳc​h​i​l​d\\mathcal\{M\}\_\{child\}\. The crossover operation recombines parent instance mutators to exploit existing high\-quality mutator structures, while the mutation operation enhances exploration by introducing diverse instance mutators \(Algorithm[1](https://arxiv.org/html/2608.06808#alg1), lines[11](https://arxiv.org/html/2608.06808#alg1.l11)–[12](https://arxiv.org/html/2608.06808#alg1.l12)\)\. Full text descriptions of the corresponding prompts can be found in the supplementary material\.

After generatingℳc​h​i​l​d\\mathcal\{M\}\_\{child\}, we collect all valid mutated instances into a candidate set𝒳c​a​n​d\\mathcal\{X\}\_\{cand\}\. To extract the most informative data, we select theNaugN\_\{\\mathrm\{aug\}\}instances that collectively maximize the overall quality:

𝒟t=arg⁡max𝒮⊆𝒳c​a​n​d\|𝒮\|=Naug​∑x∈𝒮V​\(x;𝔸t−1\)\.\\mathcal\{D\}\_\{t\}=\\arg\\max\_\{\\begin\{subarray\}\{c\}\\mathcal\{S\}\\subseteq\\mathcal\{X\}\_\{cand\}\\\\ \|\\mathcal\{S\}\|=N\_\{\\mathrm\{aug\}\}\\end\{subarray\}\}\\sum\_\{x\\in\\mathcal\{S\}\}V\(x;\\mathbb\{A\}\_\{t\-1\}\)\.\(8\)Finally, these selected instances are appended to the training dataset \(𝒟t​r​a​i​n←𝒟t​r​a​i​n∪𝒟t\\mathcal\{D\}^\{train\}\\leftarrow\\mathcal\{D\}^\{train\}\\cup\\mathcal\{D\}\_\{t\}\), driving the co\-evolution of the subsequent algorithm portfolio \(Algorithm[1](https://arxiv.org/html/2608.06808#alg1), lines[21](https://arxiv.org/html/2608.06808#alg1.l21)–[22](https://arxiv.org/html/2608.06808#alg1.l22)\)\.

### III\-BAutomatic Construction of Algorithm Portfolio

Inspired by the EoH\-S framework\[[16](https://arxiv.org/html/2608.06808#bib.bib23)\], we formulate portfolio construction as an evolutionary process, defining the population as the actively maintained algorithm portfolio\. The overarching goal is to evolve an algorithm portfolio with strong generalization performance, whose member algorithms exhibit diverse and mutually compensatory behaviors\. To achieve this, the framework employs two core mechanisms, namely evolutionary operations for generating novel heuristics and a portfolio maintenance strategy for evaluating and updating the population\.

#### III\-B1LLM\-Driven Algorithm Evolutionary Operations

During each iteration, parent algorithms are selected to generate novel child heuristics via two evolutionary operations: the complementary operation and the mutation operation\. The complementary operation executes targeted recombination of two mutually compensatory parent heuristics, aiming to synthesize novel algorithms that overcome individual weaknesses and exhibit synergistic search behaviors\. In parallel, the mutation operation injects structural variations into existing parent heuristics to continuously foster overall algorithmic diversity\.

The execution of the complementary operation begins by pairing mutually complementary parent heuristics\. To facilitate this pairing, we employ a parent selection mechanism executed in two stages\. In the first stage, the first parentAiA\_\{i\}is sampled using rank\-based stochastic selection, where the selection probability is proportional to the inverse of the greedy\-selection rankR​\(A\)R\(A\)defined via Eq\. \([10](https://arxiv.org/html/2608.06808#S3.E10)\)\. In the second stage, the second parentAjA\_\{j\}is selected from the remaining candidates based on a complementary gain criterion\. Specifically, each candidate is ranked according to its complementary gain with respect toAiA\_\{i\}, defined as:

G​\(Ai,Aj\)=min⁡\{F​\(\{Ai\},𝒟t​r​a​i​n\),F​\(\{Aj\},𝒟t​r​a​i​n\)\}−F​\(\{Ai,Aj\},𝒟t​r​a​i​n\),\\begin\{split\}G\(A\_\{i\},A\_\{j\}\)&=\\min\\\{F\(\\\{A\_\{i\}\\\},\\mathcal\{D\}^\{train\}\),F\(\\\{A\_\{j\}\\\},\\mathcal\{D\}^\{train\}\)\\\}\\\\ &\\quad\-F\(\\\{A\_\{i\},A\_\{j\}\\\},\\mathcal\{D\}^\{train\}\),\\end\{split\}\(9\)whereF​\(⋅\)F\(\\cdot\)denotes portfolio\-level performance\. A largerG​\(Ai,Aj\)G\(A\_\{i\},A\_\{j\}\)indicates stronger complementarity\.

Following parent selection, we assign specific roles to the parents for the LLM prompt \(illustrated in Fig\.[2](https://arxiv.org/html/2608.06808#S3.F2)\)\. The parent with relatively poorer individual performance is designated as the Reference Algorithm to expose latent algorithmic weaknesses\. The better\-performing parent serves as the Complementary Algorithm, providing the primary code structure\. The LLM then synthesizes a new heuristic by structurally modifying the Complementary Algorithm while explicitly addressing the deficiencies highlighted by the Reference Algorithm\. This ensures that the generated algorithms are not mere local refinements but genuinely exhibit complementary search behaviors\.

Prompt Template: Algorithm Complementary Operation\{user\_generator\}Below are two complementary functions\. They excel in different scenarios or handle different aspects of the problem\.\[Reference Algorithm Description\]
\{worse\_algorithm\}\[Reference Algorithm Code\]
\{worse\_code\}\[Complement Seed Algorithm Description\]
\{better\_algorithm\}\[Complement Seed Code\]
\{better\_code\}\[Complementarity Reflection\]
\{reflection\}\[Complementary Code\]
Please write a new function ‘\{func\_name\}\_v2’ which serves as a stronger complementary algorithm to the Reference Algorithm, according to the reflection\.Return ‘\[Algorithm Description\]’, and one final Python code block\.Figure 2:Prompt for algorithm complementary operation\.Additionally, the mutation operation targets individual heuristics to increase exploration\. The parent algorithm is sampled with probability inversely proportional to its greedy\-selection rank\. Taking this selected parent as input, the LLM integrates mutation logic into its structural framework to explore new regions within the algorithmic design space\. This process introduces novel algorithmic components and alters existing search trajectories, thereby preventing premature convergence\.

To guide evolutionary search, the framework incorporates the reflection mechanism\. Rather than evaluating parent heuristics in isolation, this mechanism analyzes sampled historical search trajectories and the current parent\. This process generates high\-level conceptual hints for refining candidate heuristic structures\. The exact prompt formulations driving these components are documented in the Supplement\.

#### III\-B2Algorithm Portfolio Construction

During the initialization phase, we prompt the LLM to generate a diverse candidate pool𝒞\\mathcal\{C\}\. The candidates are evaluated on the augmented training dataset𝒟t​r​a​i​n\\mathcal\{D\}^\{train\}\. We then construct the portfolio of sizeKKusing greedy selection\[[16](https://arxiv.org/html/2608.06808#bib.bib23)\]\. The portfolio is initialized with the candidate in𝒞\\mathcal\{C\}that achieves the best individual performance on𝒟t​r​a​i​n\\mathcal\{D\}^\{train\}\. Subsequently, at each steph=1,…,K−1h=1,\\ldots,K\-1, the candidate with the largest marginal gain is added:

Δh​\(A\)\\displaystyle\\Delta\_\{h\}\(A\)=F​\(𝔸\(h\),𝒟t​r​a​i​n\)−F​\(𝔸\(h\)∪\{A\},𝒟t​r​a​i​n\),\\displaystyle=F\\\!\\left\(\\mathbb\{A\}^\{\(h\)\},\\mathcal\{D\}^\{train\}\\right\)\-F\\\!\\left\(\\mathbb\{A\}^\{\(h\)\}\\cup\\\{A\\\},\\mathcal\{D\}^\{train\}\\right\),\(10\)A\(h\+1\)\\displaystyle A^\{\(h\+1\)\}=arg⁡maxA∈𝒞∖𝔸\(h\)⁡Δh​\(A\)\.\\displaystyle=\\arg\\max\_\{A\\in\\mathcal\{C\}\\setminus\\mathbb\{A\}^\{\(h\)\}\}\\Delta\_\{h\}\(A\)\.The selection order defines thegreedy\-selection rankR​\(A\(h\)\)=hR\(A^\{\(h\)\}\)=hforh=1,…,Kh=1,\\ldots,K, where a lower rank indicates a larger marginal contribution\. During parent selection, portfolio members are sampled with probabilities proportional to1/R​\(A\)1/R\(A\), thereby favoring algorithms with larger marginal contributions\.

To manage the integration of newly generated algorithms while strictly maintaining a fixed portfolio capacityKK, a greedy replacement strategy is implemented\. The replacement gain of substituting an existing algorithmAiA\_\{i\}with a novel candidateAnewA\_\{\\mathrm\{new\}\}is formulated as:

Δrep​\(i;Anew\)=F​\(𝔸t,𝒟t​r​a​i​n\)−F​\(\(𝔸t∖\{Ai\}\)∪\{Anew\},𝒟t​r​a​i​n\)\.\\begin\{split\}\\Delta\_\{\\mathrm\{rep\}\}\(i;A\_\{\\mathrm\{new\}\}\)&=F\(\\mathbb\{A\}\_\{t\},\\mathcal\{D\}^\{train\}\)\\\\ &\\quad\-F\(\(\\mathbb\{A\}\_\{t\}\\setminus\\\{A\_\{i\}\\\}\)\\cup\\\{A\_\{\\mathrm\{new\}\}\\\},\\mathcal\{D\}^\{train\}\)\.\\end\{split\}\(11\)The new candidate replaces the incumbent algorithm that yields the largest replacement gain\. The replacement is performed only when this gain is positive, after which the greedy\-selection ranksR​\(A\)R\(A\)are recomputed; otherwise, the portfolio remains unchanged\. If multiple incumbents yield the same gain, the one with poorer individual performance, measured by a higher mean objective value, is replaced\. This update maintains the fixed portfolio size while progressively improving portfolio\-level performance and complementarity \(Algorithm[1](https://arxiv.org/html/2608.06808#alg1), Step 2\.2\)\.

## IVAlgorithm\-Specific Instantiations of Perturbation

The perturbation operatorPξP\_\{\\xi\}in Eq\. \([5](https://arxiv.org/html/2608.06808#S3.E5)\) acts on the heuristic matrixM=H​\(x,s\)M=H\(x,s\), which guides the decisions of the complete algorithmA=B​\[H\]A=B\[H\]\. We instantiate this mechanism for three representative backbones: Greedy Constructive, Ant Colony Optimization \(ACO\), and Guided Local Search \(GLS\)\. For each solver setting, the backboneBBremains fixed and defines the overall solution procedure, whereas the LLM constructs and evolves only the heuristic componentHH\. PerturbingMMtherefore changes the heuristic guidance used at each solver state without modifying the underlying construction or search process\. The following subsections specifyMMand its role for each backbone\.

### IV\-AGreedy Constructive Algorithms

Greedy algorithms iteratively build solutions by selecting candidatesc∈Ctc\\in C\_\{t\}based on a heuristic priority matrixMtM\_\{t\}\. Rather than altering the underlying greedy selection rule, our matrix\-level perturbation structurally modulates these relative priorities\. The perturbed selection becomes:

c~∗=argmaxc∈Ct\[Pξ\(Mt\)\]c\\widetilde\{c\}^\{\*\}=\\arg\\max\_\{c\\in C\_\{t\}\}\\big\[P\_\{\\xi\}\(M\_\{t\}\)\\big\]\_\{c\}\(12\)If this perturbation yields a significantly superior final solution, it implies the instance is highly sensitive to the heuristic’s local scoring logic\. Such instances are highly valuable for evaluation, as they explicitly expose critical vulnerabilities in standard greedy decision\-making\.

### IV\-BAnt Colony Optimization \(ACO\)

In ACO\[[41](https://arxiv.org/html/2608.06808#bib.bib24)\], the search is guided by both dynamic pheromone trailsτi​j\\tau\_\{ij\}and a static heuristic information matrixMM\. Under our framework, pheromone updates proceed conventionally based on search history, but the heuristic matrix is replaced by its perturbed counterpartPξ​\(M\)P\_\{\\xi\}\(M\)\. The perturbed candidate\-edge weight is computed as:

W~i​j=τi​jα​\[Pξ​\(M\)\]i​jβ\\widetilde\{W\}\_\{ij\}=\\tau\_\{ij\}^\{\\alpha\}\[P\_\{\\xi\}\(M\)\]\_\{ij\}^\{\\beta\}\(13\)whereα\\alphaandβ\\betabalance the pheromone and heuristic influences\. By altering the ants’ sampling distribution, we can evaluate the instance’s underlying difficulty\. If the perturbed matrix enables ACO to escape local optima and find better solutions, the instance serves as a valuable stress test, revealing cases where the original heuristic inappropriately biased the search trajectory\.

### IV\-CGuided Local Search \(GLS\)

In GLS\[[1](https://arxiv.org/html/2608.06808#bib.bib25)\], the matrixMMgoverns edge\-level penalty selection to help the search escape local minima\. ApplyingPξP\_\{\\xi\}directly reshapes the utility landscape dictating this penalization\. The target edge\(i∗,j∗\)\(i^\{\*\},j^\{\*\}\)in the current solutionSSis selected via:

\(i∗,j∗\)=arg⁡max\(i,j\)∈E​\(S\)⁡\[Pξ​\(M\)\]i​j1\+pi​j\(i^\{\*\},j^\{\*\}\)=\\arg\\max\_\{\(i,j\)\\in E\(S\)\}\\frac\{\[P\_\{\\xi\}\(M\)\]\_\{ij\}\}\{1\+p\_\{ij\}\}\(14\)wherepi​jp\_\{ij\}is the accumulated penalty\. Following this selection, GLS updates the penalty\-adjusted cost matrix \(i\.e\.,Wi​j=ci​j\+kG​L​S​pi​jW\_\{ij\}=c\_\{ij\}\+k\_\{GLS\}p\_\{ij\}\) conventionally\.

A high potential gain from this perturbation reveals thatMMoriginally formed a “utility trap” by overvaluing suboptimal edges for this specific instance\. Incorporating these highly sensitive, vulnerable instances into training forces the evolutionary search to circumvent such traps, ultimately driving the evolution of a more generalizable search policy\.

## VExperiments

TABLE I:Hyperparameter settings of PIAC\.ParameterSymbolValueFrameworkMax iterationsTT4Algorithm evolutionPortfolio sizeKK5\# Algorithm evals/iterF​EaFE\_\{a\}100Data evolutionInitial dataset size\|𝒟0\|\|\\mathcal\{D\}\_\{0\}\|8\# Mutator evals/iterF​EmFE\_\{m\}30\# Executions per mutatorNexecN\_\{\\mathrm\{exec\}\}4\# Augmented instances/iterNaugN\_\{\\mathrm\{aug\}\}8\# Noise perturbationsNpN\_\{p\}64Noise strengthσ\\sigma0\.01We conduct extensive experiments to evaluate the proposed method on two representative combinatorial optimization problems: the Traveling Salesman Problem \(TSP\) and the Capacitated Vehicle Routing Problem \(CVRP\)\. Our experiments are designed to answer four research questions \(*RQs*\):

- *RQ1*:Does the proposed framework construct an algorithm portfolio that generalizes across different data distributions?
- *RQ2*:Do the two proposed components effectively contribute to the overall performance of the framework?
- *RQ3*:What is the relationship between the potential gain and the optimality gap?
- *RQ4*:Do the newly generated valuable instances continuously improve the performance of the algorithm portfolio?

### V\-AExperimental Setup

TABLE II:Performance of various methods on constructive heuristic design for synthetic TSP and CVRP across six instance distributions\. Values on the left and right under each distribution represent the objective value \(Obj\) and optimality gap \(Gap\), respectively \(lower is better\)\. Bold values indicate the best result and any results not significantly different from it \(paired Wilcoxon signed\-rank test with Holm correction,α=0\.05\\alpha=0\.05\)\.TSP Constructive HeuristicMethodRueExplosionImplosionExpansionClusterGridAvgFunSearch12\.9120\.75%10\.2722\.44%10\.8324\.49%10\.5921\.99%9\.7123\.15%13\.1118\.14%21\.83%EoH12\.4916\.84%10\.0519\.83%10\.5020\.78%10\.2618\.26%9\.4720\.08%12\.7514\.83%18\.44%ReEvo12\.7319\.05%10\.1521\.04%10\.6322\.19%10\.4119\.92%9\.4920\.21%12\.9816\.97%19\.90%MCTS\-AHD12\.9721\.31%10\.4324\.38%10\.8124\.27%10\.6022\.12%9\.7623\.71%13\.2119\.05%22\.47%EoH\-S12\.2514\.54%9\.7316\.00%10\.0915\.99%9\.9714\.93%9\.0714\.88%12\.5112\.69%14\.83%PIAC \(RND\)12\.0512\.69%9\.6715\.32%9\.9214\.07%9\.8513\.48%8\.9813\.82%12\.3711\.45%13\.47%PIAC \(GAP\)12\.0112\.30%9\.6615\.16%9\.9013\.82%9\.8012\.99%8\.9413\.29%12\.3411\.14%13\.12%PIAC11\.9311\.54%9\.4913\.23%9\.8012\.68%9\.7011\.84%8\.8512\.23%12\.209\.90%11\.90%CVRP Constructive HeuristicMethodRueExplosionImplosionExpansionClusterGridAvgFunSearch34\.2024\.45%32\.6022\.41%31\.4823\.62%30\.5421\.87%31\.4519\.89%34\.3125\.74%23\.00%EoH34\.3725\.00%32\.4721\.94%31\.1522\.38%30\.6322\.23%31\.2018\.92%34\.5426\.53%22\.83%ReEvo34\.5725\.77%33\.0524\.21%31\.6624\.33%31\.1424\.30%31\.6520\.59%34\.4726\.20%24\.23%MCTS\-AHD34\.7726\.54%33\.0624\.44%31\.7824\.96%31\.1824\.53%31\.8421\.52%34\.6727\.08%24\.85%EoH\-S33\.6722\.55%31\.9420\.22%30\.6020\.32%30\.2420\.74%30\.5816\.69%33\.5823\.06%20\.60%PIAC \(RND\)33\.3421\.24%31\.4317\.99%30\.2318\.78%29\.6918\.47%30\.4916\.17%33\.3322\.09%19\.12%PIAC \(GAP\)33\.1920\.78%31\.2117\.16%30\.0518\.07%29\.5217\.79%30\.3615\.72%33\.2521\.81%18\.56%PIAC33\.0720\.36%31\.1016\.77%29\.9717\.79%29\.4617\.59%30\.3015\.48%33\.2321\.76%18\.29%

Datasets\.For each problem class, the training instances are generated under the random\-distribution setting adopted in ReEvo\. The test instances follow Bossek et al\.\[[2](https://arxiv.org/html/2608.06808#bib.bib28),[45](https://arxiv.org/html/2608.06808#bib.bib29)\], where structured locations are generated from random uniform Euclidean \(Rue\) point clouds by simulating five spatial patterns: explosion, implosion, cluster, expansion, and grid\. The same location distributions are used for both TSP and CVRP\. For all synthetic instances, the problem size is fixed ton=200n=200\. In this work, we use 8 training instances for each problem class and generate 100 test instances for each spatial pattern\.

Evaluation Metric\.We report the optimality gap to evaluate the solution quality of each method\. For each instancexx, the gap is computed with respect to a reference objective value\. Specifically, we use LKH\[[10](https://arxiv.org/html/2608.06808#bib.bib26)\]for TSP instances and HGS\[[31](https://arxiv.org/html/2608.06808#bib.bib27)\]for CVRP instances to obtain the reference objective value\. Given the objective valueF​\(𝔸,x\)F\(\\mathbb\{A\},x\)obtained by the algorithm portfolio𝔸\\mathbb\{A\}on instancexxand the reference objective valuefref​\(x\)f\_\{\\mathrm\{ref\}\}\(x\), the optimality gap is defined as:

Gap​\(𝔸,x\)=F​\(𝔸,x\)−fref​\(x\)fref​\(x\)×100%\.\\mathrm\{Gap\}\(\\mathbb\{A\},x\)=\\frac\{F\(\\mathbb\{A\},x\)\-f\_\{\\mathrm\{ref\}\}\(x\)\}\{f\_\{\\mathrm\{ref\}\}\(x\)\}\\times 100\\%\.\(15\)Lower gap values indicate better performance\.

Compared Methods\.We compare the proposed method with representative LLM\-based baselines, specifically FunSearch\[[27](https://arxiv.org/html/2608.06808#bib.bib17)\], EoH\[[17](https://arxiv.org/html/2608.06808#bib.bib18)\], ReEvo\[[40](https://arxiv.org/html/2608.06808#bib.bib19)\], MCTS\-AHD\[[44](https://arxiv.org/html/2608.06808#bib.bib21)\], and EoH\-S\[[16](https://arxiv.org/html/2608.06808#bib.bib23)\]\. Direct comparison with traditional frameworks like CEPS remains infeasible because they optimize continuous parameter spaces rather than discrete heuristics\. To indirectly evaluate our instance evolution against CEPS strategies, we introduce two strong baselines within the algorithm space, as detailed below:

- •PIAC \(RND\):This variant replaces the LLM\-based mutator with a fixed random \(RND\) perturbation operator, while retaining potential gain as the instance evaluation metric\.
- •PIAC \(GAP\):This variant retains the LLM\-based mutator but replaces potential gain with theOptimality Gap\(evaluated via strong solvers\) as the instance evaluation metric\.

Since the base training dataset remains identical during the initial 100 evaluations, we directly reuse the algorithm portfolio evolved by the full PIAC atF​Ea=100FE\_\{a\}=100to ensure an identical starting point for all comparisons\.

Implementation Details\.Unless otherwise specified, we employ DeepSeek\-V3\.2\[[6](https://arxiv.org/html/2608.06808#bib.bib32)\]as the backbone LLM for both algorithm and generator queries\. For the algorithm evolution process, the total number of algorithm evaluations is configured toT⋅F​Ea=400T\\cdot FE\_\{a\}=400\. Specifically, after everyF​Ea=100FE\_\{a\}=100algorithm evaluations, the data evolution process conducts 30 instance mutator evaluations\. From these generated candidates, 8 newly constructed problem instances are selected and incorporated into the training set for algorithm evaluation\. The primary hyperparameters utilized in our framework are summarized in Table[I](https://arxiv.org/html/2608.06808#S5.T1)\. To ensure a fair comparison, these same hyperparameter settings are applied across all the baseline methods introduced above\. Each experiment is independently repeated 3 times, and we report the average performance across these runs\.

### V\-BOverall Results

TABLE III:Performance comparison of different methods for designing heuristics within two TSP backbones: ACO and GLS, across six instance distributions\. Values on the left and right under each distribution represent the objective value \(Obj\) and optimality gap \(Gap\), respectively \(lower is better\)\. Bold values indicate the best result and any results not significantly different from it \(paired Wilcoxon signed\-rank test with Holm correction,α=0\.05\\alpha=0\.05\)\.ACOMethodRueExplosionImplosionExpansionClusterGridAvgFunSearch11\.8811\.06%9\.4512\.55%9\.6310\.68%9\.6611\.29%8\.7110\.28%12\.2410\.26%11\.02%EoH11\.9611\.81%9\.4913\.12%9\.7111\.61%9\.6911\.71%8\.7711\.11%12\.3010\.81%11\.70%ReEvo12\.2014\.06%9\.7015\.64%10\.0015\.01%9\.8914\.07%9\.0715\.04%12\.5012\.66%14\.41%MCTS\-AHD11\.9812\.02%9\.5213\.39%9\.7512\.10%9\.7111\.97%8\.7811\.24%12\.3311\.06%11\.96%EoH\-S11\.7810\.16%9\.3611\.49%9\.5810\.12%9\.5810\.40%8\.649\.49%12\.169\.51%10\.20%PIAC \(RND\)11\.608\.49%9\.199\.53%9\.458\.61%9\.428\.61%8\.568\.52%11\.977\.89%8\.61%PIAC \(GAP\)11\.669\.01%9\.229\.93%9\.478\.90%9\.469\.05%8\.558\.35%12\.018\.23%8\.91%PIAC11\.568\.06%9\.169\.11%9\.377\.67%9\.408\.32%8\.467\.22%11\.947\.61%8\.00%GLSMethodRueExplosionImplosionExpansionClusterGridAvgFunSearch10\.7140\.175%8\.4020\.090%8\.7140\.173%8\.6980\.247%7\.8990\.128%11\.1240\.209%0\.170%EoH10\.7150\.183%8\.4050\.120%8\.7160\.202%8\.7000\.266%7\.9030\.172%11\.1280\.241%0\.197%ReEvo10\.7160\.194%8\.4050\.124%8\.7140\.182%8\.6990\.261%7\.9020\.170%11\.1230\.196%0\.187%MCTS\-AHD10\.7150\.185%8\.4040\.114%8\.7120\.157%8\.6960\.228%7\.9030\.178%11\.1260\.224%0\.181%EoH\-S10\.7010\.057%8\.3970\.024%8\.7030\.055%8\.6830\.074%7\.8930\.051%11\.1100\.077%0\.056%PIAC \(RND\)10\.6990\.041%8\.3970\.026%8\.7030\.049%8\.6830\.072%7\.8930\.054%11\.1070\.055%0\.050%PIAC \(GAP\)10\.6990\.042%8\.3960\.022%8\.7020\.043%8\.6820\.065%7\.8910\.029%11\.1080\.060%0\.044%PIAC10\.6990\.040%8\.3960\.018%8\.7020\.047%8\.6850\.098%7\.8920\.036%11\.1080\.063%0\.050%

#### V\-B1Performance on Diverse Problem Distributions

Table[II](https://arxiv.org/html/2608.06808#S5.T2)reports the performance of all evaluated methods using the Greedy Construction backbone on synthetic TSP and CVRP instances\. To evaluate generalization capabilities, all methods are trained exclusively on the rue training dataset and subsequently tested across six distinct distributions, comprising the in\-distribution rue instances and five additional unseen distributions\. For constructive heuristics, PIAC consistently achieves the lowest optimality gaps, demonstrating strong generalization well beyond the training set\. Notably, PIAC significantly outperforms single\-algorithm baselines, including EoH, ReEvo, and MCTS\. For instance, on the constructive TSP, PIAC achieves an average gap of11\.90%11\.90\\%, substantially lower than those of EoH \(18\.44%18\.44\\%\), ReEvo \(19\.90%19\.90\\%\), and MCTS \(22\.47%22\.47\\%\)\. This confirms that a complementary portfolio of heuristics is inherently more effective than discovering a single best algorithm\. Furthermore, compared to EoH\-S, PIAC achieves a19\.76%19\.76\\%relative reduction in the average gap on TSP \(from14\.83%14\.83\\%to11\.90%11\.90\\%\) and an11\.21%11\.21\\%relative reduction on CVRP \(from20\.60%20\.60\\%to18\.29%18\.29\\%\)\. While EoH\-S also constructs an algorithm portfolio using fixed instances, PIAC dynamically co\-evolves the complementary algorithms alongside valuable synthesized data\. These outcomes directly answer*RQ1*by demonstrating that our co\-evolutionary framework constructs an algorithm portfolio capable of robustly generalizing across diverse data distributions, rather than simply overfitting to the initial rue training set\.

This robust generalization extends across diverse algorithms, as shown in Table[III](https://arxiv.org/html/2608.06808#S5.T3)\. On TSP ACO, PIAC reduces the average gap from10\.20%10\.20\\%\(EoH\-S\) to8\.00%8\.00\\%\. For TSP GLS, where baseline methods already achieve near\-zero gaps and inherently limit further improvements, PIAC continues to outperform EoH\-S, successfully reducing the average gap from0\.056%0\.056\\%to0\.050%0\.050\\%\.

To further validate generalization capabilities, we benchmark the portfolios on standard public datasets, specifically TSPLib\[[26](https://arxiv.org/html/2608.06808#bib.bib30)\]for TSP and CVRPLib\[[29](https://arxiv.org/html/2608.06808#bib.bib31)\]for CVRP\. As shown in Table[IV](https://arxiv.org/html/2608.06808#S5.T4), PIAC attains the lowest optimality gap on TSPLib, decreasing it from13\.67%13\.67\\%\(EoH\-S\) to11\.79%11\.79\\%\. On CVRP, PIAC secures the top rank across 8 of the 10 CVRPLib subsets and places second on the remaining two, dropping the overall average gap to24\.53%24\.53\\%compared to the29\.88%29\.88\\%achieved by EoH\-S\. Collectively, these findings directly answer*RQ1*by demonstrating that the proposed co\-evolutionary framework successfully constructs algorithm portfolios capable of robust generalization across diverse data distributions\.

TABLE IV:Performance on public benchmark instances\. Lower values are better\. Bold values indicate the best result and any results not significantly different from it \(paired Wilcoxon signed\-rank test with Holm correction,α=0\.05\\alpha=0\.05\)\.BenchmarksReEvoEoH\-SPIAC\(RND\)PIAC\(GAP\)PIACTSPLib19\.59%13\.67%13\.28%12\.92%11\.79%CVRPLib A29\.60%25\.74%25\.36%24\.02%22\.97%CVRPLib B32\.37%24\.75%17\.90%18\.10%16\.97%CVRPLib CMT39\.17%33\.34%34\.65%32\.15%32\.95%CVRPLib F50\.70%44\.43%44\.35%36\.85%33\.97%CVRPLib Golden26\.82%22\.86%22\.22%22\.69%20\.58%CVRPLib Li27\.89%25\.49%21\.42%20\.73%18\.26%CVRPLib M38\.65%36\.17%34\.31%33\.21%33\.75%CVRPLib P25\.21%21\.77%21\.39%20\.71%20\.22%CVRPLib tai51\.52%43\.64%33\.57%30\.93%28\.53%CVRPLib X24\.05%20\.65%18\.04%17\.76%17\.12%

#### V\-B2Effectiveness of the Proposed Components

To answer*RQ2*, we conduct an ablation study to validate the core mechanisms of PIAC\. To isolate the contributions of our co\-evolutionary design, we evaluate the full framework against two strong internal variants\.

First, we assess the impact of the LLM\-driven instance generation by introducing PIAC \(RND\)\. This variant replaces the LLM\-constructed mutator with a fixed random perturbation operator while retaining the proposed potential gain for instance evaluation\. The evaluation reveals that the full PIAC outperforms the PIAC \(RND\) baseline, reducing the average optimality gap from13\.47%13\.47\\%to11\.90%11\.90\\%on the constructive TSP and from19\.12%19\.12\\%to18\.29%18\.29\\%on the constructive CVRP\. This robust improvement demonstrates that LLM\-evolved mutators successfully explore a broader data space to effectively enhance generalization\.

Second, we evaluate the effectiveness of the instance evaluation metric by comparing our full framework against PIAC \(GAP\)\. This variant retains the LLM mutator but relies on the traditional optimality gap evaluated via strong external solvers to assess generated instances\. The full framework improves the average gap from13\.12%13\.12\\%to11\.90%11\.90\\%on the TSP Constructive Heuristic and from8\.91%8\.91\\%to8\.00%8\.00\\%on TSP ACO without requiring reference solvers\. This advantage arises because potential gain exposes suboptimal decision boundaries, precisely targeting high\-value instances that reveal latent algorithmic weaknesses rather than simply selecting universally hard problems\.

Collectively, these findings directly answer*RQ2*by confirming that both the LLM\-driven mutator evolution and the potential\-aware metric contribute to constructing robust algorithm portfolios\.

#### V\-B3Time Cost Analysis

To evaluate the computational efficiency of the proposed metric, we compare the time cost of potential gain against the traditional Opt Gap\. We evaluate 120 Rue problem instances using a reference algorithm portfolio constructed after 100 function evaluations\. The optimal objectives for Opt Gap are computed using default configurations of LKH for TSP and HGS for CVRP\. Both metrics are computed using 64 parallel processes\.

Table[V](https://arxiv.org/html/2608.06808#S5.T5)details the evaluation results\. Regarding the time cost, the potential gain demonstrates highly competitive efficiency\. With the sole exception of TSP Constructive, where Opt Gap holds a minor computational edge, the proposed metric matches or significantly accelerates the evaluation process across all other paradigms\. Most notably on CVRP Constructive instances, potential gain requires only 9\.46 seconds, which is substantially faster than the 46\.35 seconds consumed by Opt Gap\. For both TSP ACO and TSP GLS, the execution times of the two metrics are strictly competitive and closely matched\.

Unlike Opt Gap, whose computational overhead fluctuates with external reference solvers, potential gain avoids these dependencies\. By relying on controlled perturbations, its evaluation time is bounded by the execution time of the algorithm itself\. Empirical results show that the evaluation cost ofpotential gainremains relatively stable\.

TABLE V:Cost analysis of Potential Gain vs Opt Gap\. The reported values are computational time in seconds\.ProblemPotential Gain / sOpt Gap / sTSP Constructive8\.913\.59CVRP Constructive9\.4646\.35TSP ACO16\.6317\.46TSP GLS8\.286\.37![Refer to caption](https://arxiv.org/html/2608.06808v1/x2.png)

\(a\)TSP

![Refer to caption](https://arxiv.org/html/2608.06808v1/x3.png)

\(b\)CVRP

Figure 3:Relationship between the potential gain and the optimality gap on generated instances\.

### V\-CRelationship Between Potential Gain and Optimality Gap

To address*RQ3*, we investigate whether the proposed potential gain positively correlates with the hardness metric\. To ensure a fair evaluation, we freeze the algorithm portfolio \(PAP\) afterF​Ea=100FE\_\{a\}=100evaluations for each problem domain \(TSP constructive and CVRP constructive heuristics\)\. We then use this static PAP to evaluate all problem instances generated by the LLM\-evolved mutators\. This setup ensures that instance hardness is measured against a consistent algorithmic baseline, isolating the evaluation from the dynamics of a continuously evolving portfolio\.

For each training instanceii, letviv\_\{i\}denote its potential gain andgig\_\{i\}denote its optimality gap, both measured using the static PAP\. We quantify their statistical relationship via the Pearson correlation coefficient:

ρv,g=∑i=1N\(vi−v¯\)​\(gi−g¯\)∑i=1N\(vi−v¯\)2​∑i=1N\(gi−g¯\)2,\\rho\_\{v,g\}=\\frac\{\\sum\_\{i=1\}^\{N\}\(v\_\{i\}\-\\bar\{v\}\)\(g\_\{i\}\-\\bar\{g\}\)\}\{\\sqrt\{\\sum\_\{i=1\}^\{N\}\(v\_\{i\}\-\\bar\{v\}\)^\{2\}\}\\sqrt\{\\sum\_\{i=1\}^\{N\}\(g\_\{i\}\-\\bar\{g\}\)^\{2\}\}\},\(16\)whereNNis the total number of evaluated instances, andv¯\\bar\{v\}andg¯\\bar\{g\}are the sample means of the potential gains and optimality gaps, respectively\.

As illustrated in Figure[3](https://arxiv.org/html/2608.06808#S5.F3), potential gain is positively associated with the optimality gap\. The Pearson correlation coefficients are0\.74450\.7445for TSP and0\.52300\.5230for CVRP, indicating strong and moderate positive correlations, respectively\. These results suggest that harder instances tend to exhibit greater improvement potential\. However, some hard instances show only limited improvement after perturbation\. The potential gain metric therefore favors instances with greater potential for improvement, rather than simply those with large optimality gaps\. As a result, many selected instances have both high potential gains and large optimality gaps, without requiring reference solutions during instance evaluation\. These results answer*RQ3*by showing that potential gain is positively correlated with instance hardness while capturing a distinct, improvement\-oriented signal rather than merely reproducing the optimality gap\.

![Refer to caption](https://arxiv.org/html/2608.06808v1/x4.png)

\(a\) TSP\-Rue

![Refer to caption](https://arxiv.org/html/2608.06808v1/x5.png)

\(b\) TSP\-Cluster

![Refer to caption](https://arxiv.org/html/2608.06808v1/x6.png)

\(c\) CVRP\-Rue

![Refer to caption](https://arxiv.org/html/2608.06808v1/x7.png)

\(d\) CVRP\-Cluster

Figure 4:Performance curves under different numbers of algorithm evaluations\. Lower objective values indicate better performance\.
### V\-DPerformance Dynamics of the Algorithm Portfolio

To answer*RQ4*regarding whether the introduction of newly generated valuable instances can continuously improve performance, we track the performance dynamics of the algorithm portfolios throughout the evolution process for the TSP constructive and CVRP constructive heuristics\. In our experimental setup, the portfolio is initially trained on the initial dataset of 8 instances\. Subsequently, PIAC dynamically expands the training dataset by introducing 8 newly synthesized problem instances every 100 algorithm evaluations \(F​EFE\)\. Figure[4](https://arxiv.org/html/2608.06808#S5.F4)illustrates the performance of the algorithm portfolios across different test data distributions, including TSP\-Rue, TSP\-Cluster, CVRP\-Rue, and CVRP\-Cluster\.

On the TSP test datasets \(TSP\-Rue and TSP\-Cluster\), a clear divergence in search dynamics emerges\. During the initial 100 algorithm evaluations, EoH\-S and PIAC achieve highly comparable performance, as both methods rapidly reduce the objective values\. However, the improvement of EoH\-S slows down significantly thereafter, reaching a performance plateau after 200 evaluations with limited further gains\. In contrast, PIAC sustains a continuous downward trend throughout the entire evaluation process\. By dynamically introducing valuable training data, PIAC effectively avoids early convergence and consistently refines the algorithm portfolio\. Transitioning to the CVRP test datasets, although both EoH\-S and PIAC achieve substantial performance gains on CVRP\-Rue, PIAC maintains a higher rate of improvement\. Furthermore, a distinct divergence occurs in the later stages across different distributions\. While EoH\-S continues to achieve considerable gains on CVRP\-Rue after 200 evaluations, its improvement on the CVRP\-Cluster distribution becomes severely limited\. A similar stagnation is observed for PIAC \(RND\) on CVRP\-Cluster\. This limitation arises because PIAC \(RND\) introduces instances from a fixed random distribution, failing to adequately cover the structural properties of the Cluster distribution\. In contrast, by leveraging LLMs to construct diverse instance mutators, both PIAC \(GAP\) and the full PIAC ensure that the generated training data covers a significantly broader problem space, enabling them to continuously enhance performance on the Cluster distribution\. In summary, the evaluation dynamics explicitly answer*RQ4*and confirm that continuously introducing newly generated valuable instances successfully drives the sustained performance improvement of the algorithm portfolio\.

### V\-EFoundation Model Analysis

To analyze PIAC’s performance across different LLMs, we evaluate PIAC using DeepSeek\-V3\.2\[[6](https://arxiv.org/html/2608.06808#bib.bib32)\], DeepSeek\-V4\[[7](https://arxiv.org/html/2608.06808#bib.bib35)\], Kimi\-K2\.6\[[14](https://arxiv.org/html/2608.06808#bib.bib33)\], and GPT\-4\.1 mini\[[23](https://arxiv.org/html/2608.06808#bib.bib34)\]\. As shown in Table[VI](https://arxiv.org/html/2608.06808#S5.T6), the quality of the constructed algorithm portfolios consistently improves as the capability of the underlying model increases\. DeepSeek\-V4 achieves the best overall performance, reducing the optimality gaps to 10\.08 and 10\.31 on the Rue and Cluster instances, respectively\.

TABLE VI:Performance comparison of different LLMs on Rue and Cluster instances using PIAC\.LLMRueClusterDeepSeek\-V3\.2\[[6](https://arxiv.org/html/2608.06808#bib.bib32)\]11\.54%12\.23%DeepSeek\-V4\[[7](https://arxiv.org/html/2608.06808#bib.bib35)\]10\.08%10\.31%Kimi\-K2\.6\[[14](https://arxiv.org/html/2608.06808#bib.bib33)\]17\.72%17\.68%GPT\-4\.1 mini\[[23](https://arxiv.org/html/2608.06808#bib.bib34)\]13\.63%16\.09%TABLE VII:Ablation study on complementary operation\. Lower values are better\. Values in parentheses indicate the performance degradation compared with PIAC\.MethodRueClusterEoH\-S18\.71%19\.07%PIACw/ random17\.52%\(\+1\.63%\)18\.52%\(\+2\.25%\)PIACw/ distance16\.47%\(\+0\.58%\)17\.04%\(\+0\.77%\)PIAC15\.89%16\.27%
### V\-FAblation Study: Complementary Operation

We conduct an ablation study to evaluate the effectiveness of the proposed Complementary Operation in guiding the evolutionary PAP algorithm\. The experiments are performed on a fixed training dataset with 100 algorithm evaluations per portfolio\. We compare three strategies: \(i\)random crossover operation, where parent algorithms are randomly paired from the current algorithm pool; \(ii\)distance\-based crossover operation, where parent pairing is guided by score\-list distance; and \(iii\) the PIAC method with the proposed complementary crossover operation, which integrates two\-stage parent selection and complementary LLM prompting\.

As shown in Table[VII](https://arxiv.org/html/2608.06808#S5.T7), the PIAC variant using random crossover operation exhibits a clear performance degradation compared with the original PIAC, with Rue increasing from 15\.89% to 17\.52% and Cluster from 16\.27% to 18\.52%\. The distance\-based crossover operation improves over the random variant but still underperforms the original PIAC, indicating that score\-list distance only captures partial diversity and fails to fully exploit complementary strengths\. The original PIAC, leveraging the proposed complementary crossover operation with two\-stage parent pairing and complementary LLM prompting, consistently achieves the best results\. This demonstrates that explicitly guiding LLM\-based crossover with complementary parent algorithms produces more diverse and synergistic heuristic rules, leading to superior algorithm portfolios\.

## VIConclusion

This work introduced PIAC, a potential\-aware co\-evolutionary framework for automated algorithm portfolio construction\. PIAC advances both problem\-instance evaluation and generation through the potential gain metric and diverse LLM\-evolved instance mutators, respectively\. Specifically, by perturbing generated algorithms, potential gain quantifies achievable performance gains to identify instances with high quality, thereby bolstering portfolio generalization without relying on high\-quality reference solutions\. Simultaneously, the framework leverages LLMs to synthesize diverse instance mutators, expanding coverage across the problem space beyond hand\-crafted operators\. Together, these components guide the co\-evolution of training instances and complementary portfolio members\. Extensive experiments on the TSP and CVRP across six data distributions demonstrate that PIAC consistently outperforms state\-of\-the\-art LLM\-based portfolio construction methods\. Ultimately, PIAC successfully extends the co\-evolutionary paradigm into the domain of LLM\-driven automated algorithm portfolio construction\. While the current perturbation strategy assumes heuristic algorithms produce matrix\-structured outputs, future research will design more universal perturbation schemes to accommodate arbitrary decision representations\.

## References

- \[1\]\(2019\)Knowledge\-guided local search for the vehicle routing problem\.Computers & Operations Research105,pp\. 32–46\.External Links:ISSN 0305\-0548Cited by:[§IV\-C](https://arxiv.org/html/2608.06808#S4.SS3.p1.4)\.
- \[2\]J\. Bossek, P\. Kerschke, A\. Neumann, M\. Wagner, F\. Neumann, and H\. Trautmann\(2019\)Evolving diverse tsp instances by means of novel and creative mutation operators\.InProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,FOGA ’19,pp\. 58–71\.External Links:ISBN 9781450362542Cited by:[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p1.1)\.
- \[3\]J\. Branke and C\. W\. Pickardt\(2011\)Evolutionary search for difficult problem instances to support the design of job shop dispatching rules\.European Journal of Operational Research212\(1\),pp\. 22–32\.External Links:ISSN 0377\-2217Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p4.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p4.1),[§III\-A1](https://arxiv.org/html/2608.06808#S3.SS1.SSS1.p1.1)\.
- \[4\]C\. Chen, H\. Hong, W\. Lin, and K\. C\. Tan\(2025\)A physics\-informed evolutionary transfer optimization framework for material design\.InProceedings of CEC,Vol\.,pp\. 1–9\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[5\]P\. V\. T\. Dat, L\. Doan, and H\. T\. T\. Binh\(2025\)HSEvo: elevating automatic heuristic design with diversity\-driven harmony search and genetic algorithm using llms\.InProceedings of the Thirty\-Ninth AAAI Conference on Artificial Intelligence and Thirty\-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence,AAAI’25/IAAI’25/EAAI’25\.External Links:ISBN 978\-1\-57735\-897\-8Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[6\]DeepSeek\-AI, A\. Liu, B\. Feng, B\. Xue,et al\.\(2024\)DeepSeek\-V3 Technical Report\.arXiv e\-prints,pp\. arXiv:2412\.19437\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2412.19437),2412\.19437Cited by:[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p4.2),[§V\-E](https://arxiv.org/html/2608.06808#S5.SS5.p1.1),[TABLE VI](https://arxiv.org/html/2608.06808#S5.T6.1.2.1)\.
- \[7\]DeepSeek\-AI\(2026\)DeepSeek\-V4: Towards Highly Efficient Million\-Token Context Intelligence\.Note:Technical reportAccessed: 2026\-05\-31External Links:[Link](https://huggingface.co/deepseek-ai/DeepSeek-V4-Pro/blob/main/DeepSeek_V4.pdf)Cited by:[§V\-E](https://arxiv.org/html/2608.06808#S5.SS5.p1.1),[TABLE VI](https://arxiv.org/html/2608.06808#S5.T6.1.3.1)\.
- \[8\]C\. P\. Gomes and B\. Selman\(2001\)Algorithm portfolios\.Artificial Intelligence126\(1\-2\),pp\. 43–62\.External Links:ISSN 0004\-3702Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p1.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[9\]T\. Guo, Y\. Mei, M\. Zhang, H\. Ding, and W\. Du\(2026\)Multitree genetic programming with behavioral semantics for large\-scale dynamic air traffic flow management\.IEEE Transactions on Evolutionary Computation,pp\. 1–1\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[10\]K\. Helsgaun\(2000\)An effective implementation of the lin–kernighan traveling salesman heuristic\.European Journal of Operational Research126\(1\),pp\. 106–130\.External Links:ISSN 0377\-2217Cited by:[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p2.5)\.
- \[11\]B\. A\. Huberman, R\. M\. Lukose, and T\. Hogg\(1997\)An economics approach to hard computational problems\.Science275\(5296\),pp\. 51–54\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p1.1)\.
- \[12\]C\. Jiang, X\. Shu, H\. Qian, X\. Lu, J\. Zhou, A\. Zhou, and Y\. Yu\(2025\)LLMOPT: learning to define and solve general optimization problems from scratch\.InProceedings of ICLR,Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[13\]S\. Kadioglu, Y\. Malitsky, M\. Sellmann, and K\. Tierney\(2010\)ISAC–instance\-specific algorithm configuration\.InProceedings of ECAI,pp\. 751–756\.External Links:ISBN 9781607506058Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[14\]Kimi Team, Y\. Bai, Y\. Bao,et al\.\(2025\)Kimi K2: Open Agentic Intelligence\.arXiv e\-prints,pp\. arXiv:2507\.20534\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2507.20534),2507\.20534Cited by:[§V\-E](https://arxiv.org/html/2608.06808#S5.SS5.p1.1),[TABLE VI](https://arxiv.org/html/2608.06808#S5.T6.1.4.1)\.
- \[15\]M\. Lindauer, H\. Hoos, K\. Leyton\-Brown, and T\. Schaub\(2017\)Automatic construction of parallel portfolios via algorithm configuration\.Artificial Intelligence244,pp\. 272–290\.External Links:ISSN 0004\-3702Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p2.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[16\]F\. Liu, Y\. Liu, Q\. Zhang, T\. Xialiang, and M\. Yuan\(2026\)EoH\-s: evolution of heuristic set using llms for automated heuristic design\.Proceedings of AAAI40\(43\),pp\. 37090–37098\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p2.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1),[§III\-B2](https://arxiv.org/html/2608.06808#S3.SS2.SSS2.p1.6),[§III\-B](https://arxiv.org/html/2608.06808#S3.SS2.p1.1),[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p3.2)\.
- \[17\]F\. Liu, X\. Tong, M\. Yuan, X\. Lin, F\. Luo, Z\. Wang, Z\. Lu, and Q\. Zhang\(2024\)Evolution of heuristics: towards efficient automatic algorithm design using large language model\.InProceedings of ICML,ICML’24\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1),[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p3.2)\.
- \[18\]F\. Liu, Y\. Yao, P\. Guo, Z\. Yang, X\. Lin, Z\. Zhao, X\. Tong, K\. Mao, Z\. Lu, Z\. Wang, M\. Yuan, and Q\. Zhang\(2026\)A systematic survey on large language models for algorithm design\.ACM Comput\. Surv\.58\(8\)\.External Links:ISSN 0360\-0300Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p2.1)\.
- \[19\]J\. Liu, Z\. Sun, S\. Feng, C\. Chen, and Y\. Ong\(2025\)Language model evolutionary algorithms for recommender systems: benchmarks and algorithm comparisons\.IEEE Transactions on Evolutionary Computation\(\),pp\. 1–1\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[20\]S\. Liu, C\. Chen, X\. Qu, K\. Tang, and Y\. Ong\(2024\)Large language models as evolutionary optimizers\.InIEEE Congress on Evolutionary Computation \(CEC\),pp\. 1–8\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[21\]S\. Liu, K\. Tang, and X\. Yao\(2019\)Automatic construction of parallel portfolios via explicit instance grouping\.Proceedings of AAAI33\(01\),pp\. 1560–1567\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[22\]S\. Liu, K\. Tang, and X\. Yao\(2022\)Generative adversarial construction of parallel portfolios\.IEEE Transactions on Cybernetics52\(2\),pp\. 784–795\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p3.1)\.
- \[23\]OpenAI, J\. Achiam, S\. Adler,et al\.\(2023\)GPT\-4 Technical Report\.arXiv e\-prints,pp\. arXiv:2303\.08774\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2303.08774),2303\.08774Cited by:[§V\-E](https://arxiv.org/html/2608.06808#S5.SS5.p1.1),[TABLE VI](https://arxiv.org/html/2608.06808#S5.T6.1.5.1)\.
- \[24\]J\. Pang, Y\. Mei, and M\. Zhang\(2026\)Balancing effectiveness and structural complexities in scheduling heuristics via multi/many\-objective multiform genetic programming\.IEEE Transactions on Evolutionary Computation\(\),pp\. 1–1\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[25\]J\. Pei, Y\. Mei, J\. Liu, M\. Zhang, and X\. Yao\(2025\)Adaptive operator selection for meta\-heuristics: a survey\.IEEE Transactions on Artificial Intelligence6\(8\),pp\. 1991–2012\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[26\]G\. Reinelt\(1991\)TSPLIB–a traveling salesman problem library\.ORSA Journal on Computing3\(4\),pp\. 376–384\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p3.1),[§V\-B1](https://arxiv.org/html/2608.06808#S5.SS2.SSS1.p3.4)\.
- \[27\]B\. Romera\-Paredes, M\. Barekatain, A\. Novikov, M\. Balog, M\. P\. Kumar, E\. Dupont, F\. J\. R\. Ruiz, J\. S\. Ellenberg, P\. Wang, O\. Fawzi, P\. Kohli, and A\. Fawzi\(2024\)Mathematical discoveries from program search with large language models\.Nature625\(7995\),pp\. 468–475\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1),[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p3.2)\.
- \[28\]K\. Tang, S\. Liu, P\. Yang, and X\. Yao\(2021\)Few\-shots parallel algorithm portfolio construction via co\-evolution\.IEEE Transactions on Evolutionary Computation25\(3\),pp\. 595–607\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p3.1),[§I](https://arxiv.org/html/2608.06808#S1.p4.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p3.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p4.1),[§III\-A2](https://arxiv.org/html/2608.06808#S3.SS1.SSS2.p1.5),[§III](https://arxiv.org/html/2608.06808#S3.p1.1)\.
- \[29\]E\. Uchoa, D\. Pecin, A\. Pessoa, M\. Poggi, T\. Vidal, and A\. Subramanian\(2017\)New benchmark instances for the capacitated vehicle routing problem\.European Journal of Operational Research257\(3\),pp\. 845–858\.External Links:ISSN 0377\-2217Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p3.1),[§V\-B1](https://arxiv.org/html/2608.06808#S5.SS2.SSS1.p3.4)\.
- \[30\]J\. I\. van Hemert\(2006\)Evolving combinatorial problem instances that are difficult to solve\.Evolutionary Computation14\(4\),pp\. 433–462\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p4.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p4.1),[§III\-A1](https://arxiv.org/html/2608.06808#S3.SS1.SSS1.p1.1)\.
- \[31\]T\. Vidal\(2022\)Hybrid genetic search for the cvrp: open\-source implementation and swap\* neighborhood\.Computers & Operations Research140,pp\. 105643\.External Links:ISSN 0305\-0548Cited by:[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p2.5)\.
- \[32\]C\. Wang, Z\. Yu, S\. McAleer, T\. Yu, and Y\. Yang\(2024\)ASP: learn a universal neural solver\!\.IEEE Transactions on Pattern Analysis and Machine Intelligence46\(6\),pp\. 4102–4114\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p4.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p3.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p4.1),[§III\-A1](https://arxiv.org/html/2608.06808#S3.SS1.SSS1.p1.1)\.
- \[33\]Z\. Wang, S\. Liu, P\. Yang, and K\. Tang\(2025\)Evolving generalizable parallel algorithm portfolios for binary optimization problems via domain\-agnostic instance generation\.IEEE Transactions on Evolutionary Computation\(\),pp\. 1–1\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p3.1),[§I](https://arxiv.org/html/2608.06808#S1.p4.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p3.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p4.1)\.
- \[34\]D\.H\. Wolpert and W\.G\. Macready\(1997\)No free lunch theorems for optimization\.IEEE Transactions on Evolutionary Computation1\(1\),pp\. 67–82\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p1.1)\.
- \[35\]X\. Wu, J\. Wu, Y\. Zhou, L\. Feng, and K\. Tan\(2025\)Towards robustness and explainability of automatic algorithm selection\.InICML,Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[36\]X\. Wu, S\. Wu, J\. Wu, L\. Feng, and K\. C\. Tan\(2025\)Evolutionary computation in the era of large language model: survey and roadmap\.IEEE Transactions on Evolutionary Computation29\(2\),pp\. 534–554\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[37\]X\. Wu, Y\. Zhong, J\. Wu, B\. Jiang, and K\. C\. Tan\(2024\)Large language model\-enhanced algorithm selection: towards comprehensive algorithm representation\.InProceedings of IJCAI,IJCAI’24\.External Links:ISBN 978\-1\-956792\-04\-1Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[38\]L\. Xu, H\. Hoos, and K\. Leyton\-Brown\(2010\)Hydra: automatically configuring algorithms for portfolio\-based selection\.Proceedings of AAAI24\(1\),pp\. 210–216\.Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p2.1),[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p1.1)\.
- \[39\]M\. Xu, J\. Liu, and Y\. S\. Ong\(2026\)EvoSpeak: large language models for interpretable genetic programming\-evolved heuristics\.IEEE Transactions on Evolutionary Computation\(\),pp\. 1–1\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[40\]H\. Ye, J\. Wang, Z\. Cao, F\. Berto, C\. Hua, H\. Kim, J\. Park, and G\. Song\(2024\)ReEvo: large language models as hyper\-heuristics with reflective evolution\.InAdvances in NeurIPS,Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1),[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p3.2)\.
- \[41\]H\. Ye, J\. Wang, Z\. Cao, H\. Liang, and Y\. Li\(2023\)DeepACO: neural\-enhanced ant systems for combinatorial optimization\.InAdvances in NeurIPS,Cited by:[§IV\-B](https://arxiv.org/html/2608.06808#S4.SS2.p1.3)\.
- \[42\]S\. Zhang, S\. Liu, N\. Lu, J\. Wu, J\. Liu, Y\. Ong, and K\. Tang\(2026\)LLM\-driven instance\-specific heuristic generation and selection\.External Links:2506\.00490,[Link](https://arxiv.org/abs/2506.00490)Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1)\.
- \[43\]Y\. Zhang, R\. Cheng, G\. Yi, and K\. C\. Tan\(2026\)A systematic survey on large language models for evolutionary optimization: from modeling to solving\.External Links:2509\.08269,[Link](https://arxiv.org/abs/2509.08269)Cited by:[§I](https://arxiv.org/html/2608.06808#S1.p2.1)\.
- \[44\]Z\. Zheng, Z\. Xie, Z\. Wang, and B\. Hooi\(2025\)Monte carlo tree search for comprehensive exploration in llm\-based automatic heuristic design\.InProceedings of ICML,ICML’25\.Cited by:[§II\-B](https://arxiv.org/html/2608.06808#S2.SS2.p2.1),[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p3.2)\.
- \[45\]F\. Zhou, A\. Lischka, B\. Kulcsár, J\. Wu, M\. H\. Chehreghani, and G\. Laporte\(2025\)Learning for routing: a guided review of recent developments and future directions\.Transportation Research Part E: Logistics and Transportation Review202,pp\. 104278\.External Links:ISSN 1366\-5545Cited by:[§V\-A](https://arxiv.org/html/2608.06808#S5.SS1.p1.1)\.