Evolving Parallel Algorithm Portfolios via
Potential-Aware Instance Generation with LLMs
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.
Keywords: Parallel algorithm portfolios, large language model, automatic algorithm design, co-evolutionary algorithm.
1Introduction
Parallel Algorithm Portfolios (PAPs) have emerged as a powerful paradigm for solving complex engineering optimization problems [1],[2]. Inspired by the No Free Lunch theorem [3], 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 [4],[5]. 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 [6]-[8]. 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 [9],[10]. 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 [11] and DACE [12]) have leveraged instance-algorithm co-evolution to dynamically expand the training dataset. In this paper, we define the quality of 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, regarding reliance on high-quality solutions, existing methods typically depend on near-optimal reference solutions to evaluate the quality of newly generated instances [13]-[15]. Specifically, these approaches evaluate an instance's quality based on its difficulty, termed the hardness 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, regarding single-mode instance generation patterns, prior instance generation strategies often rely on fixed, predefined operators, such as simple geometric transformations or random perturbations [11],[12]. 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 novel potential-aware metric 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 2 formalizes the problem of ACP and reviews relevant prior work. Section 3 introduces the proposed PIAC framework. Section 4 provides algorithm-specific instantiations of the framework. Section 5 presents a comprehensive empirical evaluation of our approach. Finally, Section 6 concludes the article and outlines directions for future research. Our code is available at https://anonymous.4open.science/r/piac-BAF3.
2Problem Definition and Related Work
2.1Problem Formulation
Assume that the construction of a PAP is defined over the entire problem class. Let \(x \in \Omega\) denote a problem instance, where \(\Omega\) represents the complete instance space. The backbone \(B\) specifies a complete solution procedure, such as greedy construction or ant colony optimization. Let \(\mathcal{H}_B\) denote the corresponding space of heuristic functions that can be constructed by the LLM. Given an instance \(x\in\Omega\) and a solver state \(s\) encountered during solution construction or search, each \(H\in\mathcal{H}_B\) produces a heuristic matrix \(M=H(x,s)\) that guides the subsequent decision made by the backbone. Instantiating the fixed backbone \(B\) with \(H\) yields a complete executable algorithm, denoted by \(A=B[H]\). Accordingly, the complete algorithm space under this backbone is
PIAC employs the LLM to construct and evolve the heuristic component \(H\) while keeping \(B\) unchanged. Throughout this paper, "algorithm" refers to the complete executable algorithm \(A=B[H]\), rather than the isolated heuristic function \(H\). A PAP is denoted by \(\mathbb{A} = \{A_1, \ldots, A_K\}\), where \(A_j=B[H_j]\in\mathcal{A}\) and \(\mathbb{A} \subseteq \mathcal{A}\). Given a problem instance \(x\), let \(F(A,x)\) denote the performance of algorithm \(A\) on \(x\). Without loss of generality, we assume that smaller values indicate better performance. Accordingly, the performance of the PAP \(\mathbb{A}\) on instance \(x\) is defined as
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:
where \(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\):
where \(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.
2.2Existing ACP Framework
The automated construction of algorithm portfolios (ACP) has driven significant advancements in solving hard combinatorial problems [2],[16],[17]. 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 [4], GLOBAL [5], and PARHYDRA [5]. 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 [18] and PCIT [19]. By yielding diverse member algorithms, these paradigms inherently facilitate automated algorithm selection (AS) [20]-[22]. 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 [23]-[26]. 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], EoH [28], ReEvo [29], HSEvo [30], and MCTS-AHD [31]. This paradigm, formally recognized as LLM-based Automatic Heuristic Design (LLM-AHD), has been widely applied across diverse domains, including recommender systems [32] and scientific discovery [33]. Building upon this foundation, the research frontier has shifted toward LLM-ACP to explicitly address instance heterogeneity. For example, InstSpecHH [34] partitions the problem space to evolve instance-specific heuristics for feature-based subclasses. Concurrently, EoH-S [8] 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 [11], GAST [35], and DACE [12]. 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 [14] 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 [13]-[15]. 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 [11],[12]. This unimodal generation paradigm fundamentally lacks diversity, yielding highly homogeneous instances that hinder further improvements to the generalization capability of the evolved PAP.
3The Proposed PIAC Framework
We extend the adversarial co-evolution framework [11] 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, the framework consists of two alternating phases:
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 instances \(\max_{\mathcal{D}_t} \sum_{x \in \mathcal{D}_t} V(x; \mathbb{A}_{t-1})\), where \(V(x;\mathbb{A}_{t-1})\) denotes the potential gain of generated instance \(x\) with respect to the current portfolio \(\mathbb{A}_{t-1}\).
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 \(\mathbb{A}_t\) of size \(K\) that minimizes the evaluation metric \(F\) over the accumulated training set \(\mathcal{D}^{train}\): \(\min_{\mathbb{A}_t : |\mathbb{A}_t|=K} F(\mathbb{A}_t, \mathcal{D}^{train})\).
To systematically present these contributions, Section 3.1 details the LLM-driven instance generation phase, encompassing both the mutator search and the potential-aware evaluation. Subsequently, Section 3.2 outlines the LLM-based algorithm portfolio construction process.
3.1Potential-Aware Instance Generation
3.1.1Potential-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 [13]-[15]. 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 gain \(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 backbone \(B\), consider a portfolio member \(A_j=B[H_j]\), where \(H_j\) is the LLM-constructed heuristic function embedded in \(B\). For the instance \(x\in\Omega\) and the solver state \(s\) encountered during solution construction or search, the heuristic component produces a heuristic matrix \(M_j=H_j(x,s)\) that guides the subsequent decision. We introduce a perturbation operator \(P_{\xi}\) that acts only on this heuristic matrix:
where \(\xi\) indexes an independent realization of the perturbation, \(E^{(\xi)}\) is a random matrix with the same dimensions as \(M_j\), and \(E_{uv}^{(\xi)}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\sigma^2)\). Here, \(u\) and \(v\) index the entries of \(M_j\), \(\odot\) denotes element-wise multiplication, \(\mathbf{1}\) is the all-ones matrix with the same dimensions as \(M_j\), and \(\varepsilon>0\) is a small constant that clips the multiplicative factors away from zero. Embedding the perturbed heuristic component into the same backbone yields the complete perturbed algorithm \(\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 vector \(M\) for unvisited nodes. Conventionally, the framework greedily visits the node with the highest priority at each step. Under our formulation, the priority of each node \(c\) is perturbed to \(\tilde{m}_c = m_c\max(\varepsilon,1+\epsilon_c)\) with \(\epsilon_c \sim \mathcal{N}(0, \sigma^2)\). Although the framework strictly retains its standard greedy selection rule (\(\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 the potential gain. Let \(N_p\) denote the total perturbation budget for the current portfolio \(\mathbb A=\{A_1,\ldots,A_K\}\). We distribute this budget as evenly as possible among the \(K\) portfolio members. Specifically, let \(q=\lfloor N_p/K\rfloor\) and \(r_p=N_p\bmod K\). The number of perturbations assigned to \(A_j\) is \(N_{p,j}=q+\mathbb I(j\le r_p)\). Thus, the first \(r_p\) algorithms receive \(q+1\) perturbations each, while the remaining algorithms receive \(q\) perturbations each, ensuring \(\sum_{j=1}^{K}N_{p,j}=N_p\). For each complete algorithm \(A_j=B[H_j]\), we perform \(N_{p,j}\) independent applications of the perturbation operator \(P_{\xi}\) to its heuristic component \(H_j\). This produces perturbed heuristic components \(\widetilde{H}_j^{(1)},\ldots,\widetilde{H}_j^{(N_{p,j})}\) and the corresponding complete algorithms \(\widetilde{A}_j^{(\ell)}=B[\widetilde{H}_j^{(\ell)}]\). The resulting perturbed algorithm set is \(\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 gain \(V(x; \mathbb{A})\) for an instance \(x\) is defined as the relative improvement achieved by the best-performing complete perturbed algorithm:
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 4.
3.1.2Instance 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 [11]. 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 mutator \(m\) is evaluated by its ability to generate instances with high quality under the current algorithm portfolio \(\mathbb{A}_{t-1}\). To ensure a robust evaluation, the mutator \(m\) is applied to \(N_{exec}\) base instances independently sampled from the initial data distribution \(\mathcal{D}_0\), and its overall fitness is defined as the average value across these generated instances:
We use potential gain \(V(x;\mathbb{A})\), defined in Eq. (6), 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 \(\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 perform crossover and mutation operations to construct a new generation of child mutators \(\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, lines 11-12). Full text descriptions of the corresponding prompts can be found in the supplementary material.
After generating \(\mathcal{M}_{child}\), we collect all valid mutated instances into a candidate set \(\mathcal{X}_{cand}\). To extract the most informative data, we select the \(N_{\mathrm{aug}}\) instances that collectively maximize the overall quality:
Finally, these selected instances are appended to the training dataset (\(\mathcal{D}^{train} \leftarrow \mathcal{D}^{train} \cup \mathcal{D}_t\)), driving the co-evolution of the subsequent algorithm portfolio (Algorithm 1, lines 21-22).
3.2Automatic Construction of Algorithm Portfolio
Inspired by the EoH-S framework [8], 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.
3.2.1LLM-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 parent \(A_i\) is sampled using rank-based stochastic selection, where the selection probability is proportional to the inverse of the greedy-selection rank \(R(A)\) defined via Eq. (10). In the second stage, the second parent \(A_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 to \(A_i\), defined as:
where \(F(\cdot)\) denotes portfolio-level performance. A larger \(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). 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.
InterePrompt Template: Algorithm Complementary Operationsets
{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.
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.
3.2.2Algorithm 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 \(\mathcal{D}^{train}\). We then construct the portfolio of size \(K\) using greedy selection [8]. The portfolio is initialized with the candidate in \(\mathcal{C}\) that achieves the best individual performance on \(\mathcal{D}^{train}\). Subsequently, at each step \(h=1, \ldots, K-1\), the candidate with the largest marginal gain is added:
The selection order defines the greedy-selection rank \(R(A^{(h)})=h\) for \(h=1,\ldots,K\), where a lower rank indicates a larger marginal contribution. During parent selection, portfolio members are sampled with probabilities proportional to \(1/R(A)\), thereby favoring algorithms with larger marginal contributions.
To manage the integration of newly generated algorithms while strictly maintaining a fixed portfolio capacity \(K\), a greedy replacement strategy is implemented. The replacement gain of substituting an existing algorithm \(A_i\) with a novel candidate \(A_{\mathrm{new}}\) is formulated as:
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 ranks \(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, Step 2.2).
4Algorithm-Specific Instantiations of Perturbation
The perturbation operator \(P_{\xi}\) in Eq. (5) acts on the heuristic matrix \(M=H(x,s)\), which guides the decisions of the complete algorithm \(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 backbone \(B\) remains fixed and defines the overall solution procedure, whereas the LLM constructs and evolves only the heuristic component \(H\). Perturbing \(M\) therefore changes the heuristic guidance used at each solver state without modifying the underlying construction or search process. The following subsections specify \(M\) and its role for each backbone.
4.1Greedy Constructive Algorithms
Greedy algorithms iteratively build solutions by selecting candidates \(c \in C_t\) based on a heuristic priority matrix \(M_t\). Rather than altering the underlying greedy selection rule, our matrix-level perturbation structurally modulates these relative priorities. The perturbed selection becomes:
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.
4.2Ant Colony Optimization (ACO)
In ACO [36], the search is guided by both dynamic pheromone trails \(\tau_{ij}\) and a static heuristic information matrix \(M\). Under our framework, pheromone updates proceed conventionally based on search history, but the heuristic matrix is replaced by its perturbed counterpart \(P_{\xi}(M)\). The perturbed candidate-edge weight is computed as:
where \(\alpha\) and \(\beta\) balance 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.
4.3Guided Local Search (GLS)
In GLS [37], the matrix \(M\) governs edge-level penalty selection to help the search escape local minima. Applying \(P_{\xi}\) directly reshapes the utility landscape dictating this penalization. The target edge \((i^*,j^*)\) in the current solution \(S\) is selected via:
where \(p_{ij}\) is the accumulated penalty. Following this selection, GLS updates the penalty-adjusted cost matrix (i.e., \(W_{ij} = c_{ij} + k_{GLS} p_{ij}\)) conventionally.
A high potential gain from this perturbation reveals that \(M\) originally 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.
5Experiments
We 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?
5.1Experimental Setup
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. [38],[39], 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 to \(n=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 instance \(x\), the gap is computed with respect to a reference objective value. Specifically, we use LKH [40] for TSP instances and HGS [41] for CVRP instances to obtain the reference objective value. Given the objective value \(F(\mathbb A,x)\) obtained by the algorithm portfolio \(\mathbb A\) on instance \(x\) and the reference objective value \(f_{\mathrm{ref}}(x)\), the optimality gap is defined as:
Lower gap values indicate better performance.
Compared Methods. We compare the proposed method with representative LLM-based baselines, specifically FunSearch [27], EoH [28], ReEvo [29], MCTS-AHD [31], and EoH-S [8]. 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 the Optimality 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 at \(FE_a = 100\) to ensure an identical starting point for all comparisons.
Implementation Details. Unless otherwise specified, we employ DeepSeek-V3.2 [42] as the backbone LLM for both algorithm and generator queries. For the algorithm evolution process, the total number of algorithm evaluations is configured to \(T \cdot FE_a = 400\). Specifically, after every \(FE_a = 100\) algorithm 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 1. 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.
5.2Overall Results
5.2.1Performance on Diverse Problem Distributions
Table 2 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 of \(11.90\%\), substantially lower than those of EoH (\(18.44\%\)), ReEvo (\(19.90\%\)), and MCTS (\(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 a \(19.76\%\) relative reduction in the average gap on TSP (from \(14.83\%\) to \(11.90\%\)) and an \(11.21\%\) relative reduction on CVRP (from \(20.60\%\) to \(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 3. On TSP ACO, PIAC reduces the average gap from \(10.20\%\) (EoH-S) to \(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 from \(0.056\%\) to \(0.050\%\).
To further validate generalization capabilities, we benchmark the portfolios on standard public datasets, specifically TSPLib [9] for TSP and CVRPLib [10] for CVRP. As shown in Table 4, PIAC attains the lowest optimality gap on TSPLib, decreasing it from \(13.67\%\) (EoH-S) to \(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 to \(24.53\%\) compared to the \(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.
5.2.2Effectiveness 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 from \(13.47\%\) to \(11.90\%\) on the constructive TSP and from \(19.12\%\) to \(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 from \(13.12\%\) to \(11.90\%\) on the TSP Constructive Heuristic and from \(8.91\%\) to \(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.
5.2.3Time 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 5 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 of potential gain remains relatively stable.
(a) TSP
(b) CVRP
5.3Relationship 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) after \(FE_a = 100\) evaluations 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 instance \(i\), let \(v_i\) denote its potential gain and \(g_i\) denote its optimality gap, both measured using the static PAP. We quantify their statistical relationship via the Pearson correlation coefficient:
where \(N\) is the total number of evaluated instances, and \(\bar{v}\) and \(\bar{g}\) are the sample means of the potential gains and optimality gaps, respectively.
As illustrated in Figure 3, potential gain is positively associated with the optimality gap. The Pearson correlation coefficients are \(0.7445\) for TSP and \(0.5230\) for 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.
(a) TSP-Rue
(b) TSP-Cluster
(c) CVRP-Rue
(d) CVRP-Cluster
5.4Performance 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 (\(FE\)). Figure 4 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.
5.5Foundation Model Analysis
To analyze PIAC's performance across different LLMs, we evaluate PIAC using DeepSeek-V3.2 [42], DeepSeek-V4 [43], Kimi-K2.6 [44], and GPT-4.1 mini [45]. As shown in Table 6, 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.
5.6Ablation 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 7, 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.
6Conclusion
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
- B. A. Huberman, R. M. Lukose, T. Hogg, "An Economics Approach to Hard Computational Problems", Science, vol. 275, no. 5296, pp. 51-54, 1997.
- C. P. Gomes, B. Selman, "Algorithm portfolios", Artificial Intelligence, vol. 126, no. 1-2, pp. 43-62, 2001.
- D. Wolpert, W. Macready, "No free lunch theorems for optimization", IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67-82, 1997.
- L. Xu, H. Hoos, K. Leyton-Brown, "Hydra: Automatically Configuring Algorithms for Portfolio-Based Selection", Proceedings of AAAI, vol. 24, no. 1, pp. 210–216, 2010.
- M. Lindauer, H. Hoos, K. Leyton-Brown, T. Schaub, "Automatic construction of parallel portfolios via algorithm configuration", Artificial Intelligence, vol. 244, pp. 272-290, 2017.
- F. Liu, Y. Yao, P. Guo, Z. Yang, X. Lin, Z. Zhao, X. Tong, K. Mao, Z. Lu, Z. Wang, M. Yuan, Q. Zhang, "A Systematic Survey on Large Language Models for Algorithm Design", ACM Comput. Surv., vol. 58, no. 8, 2026.
- Y. Zhang, R. Cheng, G. Yi, K. C. Tan, "A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving", 2026.
- F. Liu, Y. Liu, Q. Zhang, T. Xialiang, M. Yuan, "EoH-S: Evolution of Heuristic Set Using LLMs for Automated Heuristic Design", Proceedings of AAAI, vol. 40, no. 43, pp. 37090-37098, 2026.
- G. Reinelt, "TSPLIB--A Traveling Salesman Problem Library", ORSA Journal on Computing, vol. 3, no. 4, pp. 376-384, 1991.
- E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, A. Subramanian, "New benchmark instances for the Capacitated Vehicle Routing Problem", European Journal of Operational Research, vol. 257, no. 3, pp. 845-858, 2017.
- K. Tang, S. Liu, P. Yang, X. Yao, "Few-Shots Parallel Algorithm Portfolio Construction via Co-Evolution", IEEE Transactions on Evolutionary Computation, vol. 25, no. 3, pp. 595-607, 2021.
- Z. Wang, S. Liu, P. Yang, K. Tang, "Evolving Generalizable Parallel Algorithm Portfolios for Binary Optimization Problems via Domain-Agnostic Instance Generation", IEEE Transactions on Evolutionary Computation, pp. 1-1, 2025.
- J. I. van Hemert, "Evolving Combinatorial Problem Instances That Are Difficult to Solve", Evolutionary Computation, vol. 14, no. 4, pp. 433-462, 2006.
- C. Wang, Z. Yu, S. McAleer, T. Yu, Y. Yang, "ASP: Learn a Universal Neural Solver!", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 6, pp. 4102-4114, 2024.
- J. Branke, C. W. Pickardt, "Evolutionary search for difficult problem instances to support the design of job shop dispatching rules", European Journal of Operational Research, vol. 212, no. 1, pp. 22-32, 2011.
- J. Pang, Y. Mei, M. Zhang, "Balancing Effectiveness and Structural Complexities in Scheduling Heuristics via Multi/Many-objective Multiform Genetic Programming", IEEE Transactions on Evolutionary Computation, pp. 1-1, 2026.
- T. Guo, Y. Mei, M. Zhang, H. Ding, W. Du, "Multitree Genetic Programming with Behavioral Semantics for Large-Scale Dynamic Air Traffic Flow Management", IEEE Transactions on Evolutionary Computation, pp. 1-1, 2026.
- S. Kadioglu, Y. Malitsky, M. Sellmann, K. Tierney, "ISAC--Instance-Specific Algorithm Configuration", in Proceedings of ECAI, pp. 751-756, 2010.
- S. Liu, K. Tang, X. Yao, "Automatic Construction of Parallel Portfolios via Explicit Instance Grouping", Proceedings of AAAI, vol. 33, no. 01, pp. 1560–1567, 2019.
- X. Wu, Y. Zhong, J. Wu, B. Jiang, K. C. Tan, "Large language model-enhanced algorithm selection: towards comprehensive algorithm representation", in Proceedings of IJCAI, 2024.
- X. Wu, J. Wu, Y. Zhou, L. Feng, K. Tan, "Towards Robustness and Explainability of Automatic Algorithm Selection", in ICML, 2025.
- J. Pei, Y. Mei, J. Liu, M. Zhang, X. Yao, "Adaptive Operator Selection for Meta-Heuristics: A Survey", IEEE Transactions on Artificial Intelligence, vol. 6, no. 8, pp. 1991-2012, 2025.
- X. Wu, S. Wu, J. Wu, L. Feng, K. C. Tan, "Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap", IEEE Transactions on Evolutionary Computation, vol. 29, no. 2, pp. 534-554, 2025.
- C. Jiang, X. Shu, H. Qian, X. Lu, J. Zhou, A. Zhou, Y. Yu, "LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch", in Proceedings of ICLR, 2025.
- S. Liu, C. Chen, X. Qu, K. Tang, Y. Ong, "Large Language Models as Evolutionary Optimizers", in IEEE Congress on Evolutionary Computation (CEC), pp. 1-8, 2024.
- M. Xu, J. Liu, Y. S. Ong, "EvoSpeak: Large Language Models for Interpretable Genetic Programming-Evolved Heuristics", IEEE Transactions on Evolutionary Computation, pp. 1-1, 2026.
- 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, A. Fawzi, "Mathematical discoveries from program search with large language models", Nature, vol. 625, no. 7995, pp. 468-475, 2024.
- F. Liu, X. Tong, M. Yuan, X. Lin, F. Luo, Z. Wang, Z. Lu, Q. Zhang, "Evolution of heuristics: towards efficient automatic algorithm design using large language model", in Proceedings of ICML, 2024.
- H. Ye, J. Wang, Z. Cao, F. Berto, C. Hua, H. Kim, J. Park, G. Song, "ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution", in Advances in NeurIPS, 2024.
- P. V. T. Dat, L. Doan, H. T. T. Binh, "HSEvo: elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using LLMs", in Proceedings 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, 2025.
- Z. Zheng, Z. Xie, Z. Wang, B. Hooi, "Monte Carlo tree search for comprehensive exploration in LLM-based automatic heuristic design", in Proceedings of ICML, 2025.
- J. Liu, Z. Sun, S. Feng, C. Chen, Y. Ong, "Language Model Evolutionary Algorithms for Recommender Systems: Benchmarks and Algorithm Comparisons", IEEE Transactions on Evolutionary Computation, pp. 1-1, 2025.
- C. Chen, H. Hong, W. Lin, K. C. Tan, "A Physics-Informed Evolutionary Transfer Optimization Framework for Material Design", in Proceedings of CEC, pp. 1-9, 2025.
- S. Zhang, S. Liu, N. Lu, J. Wu, J. Liu, Y. Ong, K. Tang, "LLM-Driven Instance-Specific Heuristic Generation and Selection", 2026.
- S. Liu, K. Tang, X. Yao, "Generative Adversarial Construction of Parallel Portfolios", IEEE Transactions on Cybernetics, vol. 52, no. 2, pp. 784-795, 2022.
- H. Ye, J. Wang, Z. Cao, H. Liang, Y. Li, "DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization", in Advances in NeurIPS, 2023.
- F. Arnold, K. Sörensen, "Knowledge-guided local search for the vehicle routing problem", Computers \& Operations Research, vol. 105, pp. 32-46, 2019.
- J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, H. Trautmann, "Evolving diverse TSP instances by means of novel and creative mutation operators", in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pp. 58-71, 2019.
- F. Zhou, A. Lischka, B. Kulcsár, J. Wu, M. H. Chehreghani, G. Laporte, "Learning for routing: A guided review of recent developments and future directions", Transportation Research Part E: Logistics and Transportation Review, vol. 202, pp. 104278, 2025.
- K. Helsgaun, "An effective implementation of the Lin--Kernighan traveling salesman heuristic", European Journal of Operational Research, vol. 126, no. 1, pp. 106-130, 2000.
- T. Vidal, "Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood", Computers \& Operations Research, vol. 140, pp. 105643, 2022.
- DeepSeek-AI, A. Liu, B. Feng, B. Xue, others, "DeepSeek-V3 Technical Report", arXiv e-prints, pp. arXiv:2412.19437, 2024.
- DeepSeek-AI, "DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence", 2026.
- K. Team, Y. Bai, Y. Bao, others, "Kimi K2: Open Agentic Intelligence", arXiv e-prints, pp. arXiv:2507.20534, 2025.
- OpenAI, J. Achiam, S. Adler, others, "GPT-4 Technical Report", arXiv e-prints, pp. arXiv:2303.08774, 2023.
Supplementary Material for "Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs"
App. APrompt Design for Instance and Algorithm Generation
App. A.1Instance Mutator Prompts
To generate heterogeneous evaluation instances, we design two prompt types to evolve mutators through genetic operations.
Mutator Crossover Operation. As shown in Figure 5, this prompt synthesizes an improved instance mutator by integrating the logic of a worse-performing mutator and a better-performing mutator, guided by a targeted reflection on their differences.
Mutator Mutation Operation. As shown in Figure 6, this prompt generates a novel mutator variant by applying structural perturbations to a single elite mutator based on a prior reflection.
App. A.2Algorithm Evolution Prompts
We design four prompt types to support iterative heuristic evolution, including crossover, mutation, and two levels of reflection.
Algorithm Complementary Operation. As shown in Figure 2, this prompt constructs a complementary algorithm by combining the strengths of two heuristics.
Algorithm Mutation Operation. As shown in Figure 7, this prompt generates diverse variants by perturbing heuristic structures and decision rules.
Algorithm Complementary Analysis. As shown in Figure 8, this prompt analyzes a reference algorithm and a seed algorithm to extract complementary behaviors.
Algorithm Long-term Reflection. As shown in Figure 9, this prompt aggregates historical reflections and new insights to guide future heuristic design.
App. BVisualization of Problem Instances
This section presents a visual analysis of the generated problem instances to demonstrate the structural diversity and complexity of our benchmark datasets. Visualizing these geometries provides intuitive insights into the spatial characteristics and topological variations. We first examine the overall coordinate distributions that form the foundation of our testbed, followed by a detailed visual breakdown of the specific transformations induced by the LLM-based mutators for both the TSP and CVRP.
Prompt Template: Mutator Crossover Operation
{user_generator}
[Worse Algorithm Description]
{worse_algorithm}
[Worse Code]
{func_signature0}
{worse_code}
[Better Algorithm Description]
{better_algorithm}
[Better Code]
{func_signature1}
{better_code}
[Reflection]
{reflection}
[Improved Code]
Return [Algorithm Description], and one final Python code block. Please write an improved function {func_name}_v2, according to the reflection.
Prompt Template: Mutator Mutation Operation
{user_generator}
[Prior Reflection]
{reflection}
[Algorithm Description]
{elitist_algorithm}
[Code]
{func_signature1}
{elitist_code}
[Mutated Code]
Please write a mutated instance mutation function {func_name}_v2, according to the reflection.
Return [Algorithm Description], and one final Python code block.
App. B.1Visualization of Benchmark Distributions
The benchmark coordinate datasets for the TSP and CVRP are derived from random uniform Euclidean (Rue) point clouds subjected to structured transformations. This approach produces five quintessential spatial paradigms: explosion, implosion, expansion, cluster, and grid. As demonstrated in Fig. 10, these distributions cover a comprehensive range of topologies, providing a rigorously controlled testbed for evaluating algorithmic robustness across diverse spatial conditions.
App. B.2LLM-based TSP Instance Mutators
The instances depicted in Fig. 11 are generated by an ensemble of LLM-based mutators. The figure shows their spatial coordinate projections. A key advantage of utilizing LLMs for mutator construction is their capacity to cover a significantly broader problem instance space. While conventional single-method schemes typically yield structurally homogeneous topologies, the LLM ensemble dynamically combines diverse spatial transformations. As demonstrated by the representative implementation in Fig. 13, these mutators can generate highly heterogeneous instances.
These transformations exhibit higher-order spatial regularities compared to purely random perturbations, ensuring that the resulting instances feature non-trivial structural shifts. Fig. 13 shows a representative code snippet of just one such mutator, illustrating how cluster construction, node assignment, and geometric transformations are defined in practice.
App. B.3LLM-based CVRP Instance Mutators
The instances depicted in Fig. 12 are generated by an ensemble of LLM-based mutators. The figure shows their spatial coordinate projections. These visualizations effectively capture a diverse spectrum of geometric structures, ranging from dense multi-cluster arrangements to dispersed ring layouts. Beyond these macroscopic spatial topologies, the mutators further manipulate customer demands to cover a significantly broader space of problem instances. This concurrent mutation approach ensures that the generated datasets challenge evaluation algorithms across multiple structural dimensions rather than just pure spatial variations.
As illustrated by the representative implementation in Fig. 15, the underlying generation logic explicitly couples geometric transformations with heterogeneous demand reshaping. The mutator dynamically assigns high-variance demands to specific nodes within a cluster and strategically inserts inter-cluster bridge customers with moderate requirement profiles. These multi-dimensional features significantly heighten the overall routing complexity. Consequently, the structured instances force algorithms to balance spatial proximity with varying demands, leading to challenging cross-region vehicle allocation decisions under strict capacity constraints.
Prompt Template: Algorithm Mutation Operation
{user_generator}
[Prior Reflection]
{reflection}
[Algorithm Description]
{algorithm}
[Algorithm Code]
{code}
[Reflection]
{reflection}
[Improved code]
Please write a mutated function `{func_name}_v2' according to the reflection.
Return [Algorithm Description] and one final Python code block.
Prompt Template: Complementary Analysis
Below are two complementary {func_name} functions for {problem_desc}. They excel in different scenarios or handle different aspects of the problem.
[Function Description]
{func_desc}
[Reference Algorithm Description]
{worse_algorithm}
[Reference Code]
{worse_code}
[Complement Seed Algorithm Description]
{better_algorithm}
[Complement Seed Code]
{better_code}
[Task]
Analyze the unique strengths of each version. Provide a hint for constructing a complementary algorithm scheme to the Reference Algorithm. Use fewer than 20 words.
Prompt Template: Long-Term Reflection
Below is your prior long-term reflection on designing heuristics for {problem_desc}.
{prior_reflection}
Below are some newly gained insights.
{new_reflection}
Task
Write constructive hints for designing better heuristics, based on prior reflections and new insights. Use fewer than 50 words.
(a) Rue
(b) Explosion
(c) Implosion
(d) Expansion
(e) Cluster
(f) Grid
| 1 | import numpy as np |
| 2 | |
| 3 | def mutate_v2(instance: dict) -> dict: |
| 4 | locations = np.asarray(instance["locations"], dtype=float).copy() |
| 5 | problem_size = len(locations) |
| 6 | |
| 7 | # Calculate bounding box and center |
| 8 | x_min, x_max = np.min(locations[:, 0]), np.max(locations[:, 1]) |
| 9 | y_min, y_max = np.min(locations[:, 1]), np.max(locations[:, 1]) |
| 10 | x_center, y_center = (x_min + x_max) / 2, (y_min + y_max) / 2 |
| 11 | |
| 12 | # 1. Create 2-4 overlapping clusters (deceptive structure) |
| 13 | n_clusters = np.random.randint(2, min(5, problem_size // 4 + 2)) |
| 14 | # ... [Initialize cluster_centers omitted] ... |
| 15 | |
| 16 | # 2. Assign nodes: 60% to clusters, 40% as outliers |
| 17 | cluster_probs = [0.4] + [0.6 / n_clusters] * n_clusters |
| 18 | assignments = np.random.choice(n_clusters + 1, size=problem_size, p=cluster_probs) |
| 19 | |
| 20 | # 3. Spatial placement |
| 21 | for i in range(problem_size): |
| 22 | if assignments[i] == 0: # Outlier |
| 23 | # ... [Strategic outlier placement omitted] ... |
| 24 | pass |
| 25 | else: # Cluster node |
| 26 | cx, cy = cluster_centers[assignments[i] - 1] |
| 27 | # ... [Radius calculation omitted] ... |
| 28 | angle = np.random.uniform(0, 2*np.pi) |
| 29 | orig_bias = np.random.uniform(0, 0.3) |
| 30 | locations[i, 0] = (1-orig_bias)*(cx + radius*np.cos(angle)) + orig_bias*locations[i, 0] |
| 31 | locations[i, 1] = (1-orig_bias)*(cy + radius*np.sin(angle)) + orig_bias*locations[i, 1] |
| 32 | |
| 33 | # 4. Apply non-uniform scaling |
| 34 | scale_x = np.random.uniform(0.6, 1.4) |
| 35 | scale_y = np.random.uniform(0.6, 1.4) |
| 36 | locations[:, 0] = x_center + (locations[:, 0] - x_center) * scale_x |
| 37 | locations[:, 1] = y_center + (locations[:, 1] - y_center) * scale_y |
| 38 | |
| 39 | # 5. Apply random rotation (15-45 degrees) |
| 40 | angle = np.random.uniform(15, 45) * np.pi / 180 |
| 41 | cos_a, sin_a = np.cos(angle), np.sin(angle) |
| 42 | rotated_x = x_center + (locations[:, 0] - x_center) * cos_a - (locations[:, 1] - y_center) * sin_a |
| 43 | rotated_y = y_center + (locations[:, 0] - x_center) * sin_a + (locations[:, 1] - y_center) * cos_a |
| 44 | locations[:, 0], locations[:, 1] = rotated_x, rotated_y |
| 45 | |
| 46 | # ... [Ensure no exact duplicates] ... |
| 47 | |
| 48 | return {"problem_size": problem_size, "locations": locations.tolist()} |
| 1 | import numpy as np |
| 2 | from typing import List |
| 3 | |
| 4 | def priority_v2(current_node: int, unvisited_nodes: List[int], distance_matrix: np.ndarray) -> List[float]: |
| 5 | """ |
| 6 | Priority function for TSP constructive heuristic emphasizing cluster linking and frontier expansion. |
| 7 | |
| 8 | Args: |
| 9 | current_node: Index of current node |
| 10 | unvisited_nodes: List of indices of unvisited nodes |
| 11 | distance_matrix: Square matrix of pairwise distances |
| 12 | |
| 13 | Returns: |
| 14 | List of priority scores for each unvisited node (higher = better) |
| 15 | """ |
| 16 | priorities = [] |
| 17 | k = 3 # Number of nearest neighbors to consider for local density |
| 18 | |
| 19 | for candidate in unvisited_nodes: |
| 20 | # 1. Immediate cost (inverse) |
| 21 | direct_cost = distance_matrix[current_node][candidate] |
| 22 | |
| 23 | # 2. Local density: average distance to k nearest unvisited neighbors |
| 24 | other_nodes = [n for n in unvisited_nodes if n != candidate] |
| 25 | if other_nodes: |
| 26 | dists_to_others = [distance_matrix[candidate][n] for n in other_nodes] |
| 27 | nearest_dists = sorted(dists_to_others)[:k] |
| 28 | local_density = np.mean(nearest_dists) if nearest_dists else 0 |
| 29 | else: |
| 30 | local_density = 0 |
| 31 | |
| 32 | # 3. Frontier expansion: maximum distance to any unvisited node |
| 33 | # Favors nodes that expand reach into sparse regions |
| 34 | if other_nodes: |
| 35 | frontier_expansion = max(dists_to_others) |
| 36 | else: |
| 37 | frontier_expansion = 0 |
| 38 | |
| 39 | # 4. Isolation penalty: penalize nodes far from all others |
| 40 | if other_nodes: |
| 41 | avg_dist_all = np.mean(dists_to_others) |
| 42 | isolation_penalty = -np.std(dists_to_others) if len(dists_to_others) > 1 else 0 |
| 43 | else: |
| 44 | avg_dist_all = 0 |
| 45 | isolation_penalty = 0 |
| 46 | |
| 47 | # Combined priority with weights |
| 48 | w1, w2, w3, w4 = 0.4, 0.25, 0.2, 0.15 |
| 49 | priority = ( |
| 50 | -w1 * direct_cost + |
| 51 | w2 * local_density + |
| 52 | w3 * frontier_expansion + |
| 53 | w4 * isolation_penalty |
| 54 | ) |
| 55 | priorities.append(priority) |
| 56 | |
| 57 | return priorities |
| 1 | import numpy as np |
| 2 | |
| 3 | def mutate_v2(instance: dict) -> dict: |
| 4 | locations = np.asarray(instance["locations"], dtype=float).copy() |
| 5 | demands = np.asarray(instance["demands"], dtype=float).copy() |
| 6 | problem_size = int(instance.get("problem_size", locations.shape[0])) |
| 7 | vehicle_capacity = float(instance["vehicle_capacity"]) |
| 8 | |
| 9 | # 1. Create 2-4 distant cluster centers (placed in opposing corners/edges) |
| 10 | n_clusters = rng.integers(2, min(5, len(customer_idx))) |
| 11 | # ... [Generate cluster_centers in a ring with radius 0.7 * span] ... |
| 12 | |
| 13 | cluster_probs = rng.dirichlet(np.ones(n_clusters) * 2.0) |
| 14 | cluster_assign = rng.choice(n_clusters, size=len(customer_idx), p=cluster_probs) |
| 15 | |
| 16 | # 2. Spatial mutation: Pull locations toward cluster centers |
| 17 | for i, idx in enumerate(customer_idx): |
| 18 | center = cluster_centers[cluster_assign[i]] |
| 19 | pull_strength = rng.uniform(0.7, 0.95) # Strong pull towards center |
| 20 | |
| 21 | # Linear interpolation + noise for subtle dispersion |
| 22 | locations[idx] = pull_strength * center + (1 - pull_strength) * customer_locations[i] |
| 23 | locations[idx] += rng.normal(0, rng.uniform(0.05, 0.15) * span, size=2) |
| 24 | |
| 25 | # 3. Demand mutation: Create high variance within each cluster |
| 26 | for c in range(n_clusters): |
| 27 | cluster_cust = customer_idx[cluster_assign == c] |
| 28 | # 30-50% of cluster nodes become high-demand |
| 29 | n_high = max(1, int(len(cluster_cust) * rng.uniform(0.3, 0.5))) |
| 30 | high_idx = rng.choice(cluster_cust, size=min(n_high, len(cluster_cust)), replace=False) |
| 31 | |
| 32 | for idx in cluster_cust: |
| 33 | if idx in high_idx: |
| 34 | demands[idx] = rng.uniform(0.7, 0.95) * vehicle_capacity # Saturating |
| 35 | else: |
| 36 | demands[idx] = d_min + rng.uniform(0.05, 0.3) * d_range # Trivial |
| 37 | |
| 38 | # 4. Strategic trap: Add bridge customers between clusters |
| 39 | n_bridge = max(1, int(len(customer_idx) * 0.1)) # 10% bridge nodes |
| 40 | bridge_indices = rng.choice(customer_idx, size=n_bridge, replace=False) |
| 41 | |
| 42 | for idx in bridge_indices: |
| 43 | c1, c2 = rng.choice(n_clusters, size=2, replace=False) |
| 44 | midpoint = (cluster_centers[c1] + cluster_centers[c2]) / 2 |
| 45 | |
| 46 | # Place at midpoint with slight offset and moderate demand |
| 47 | locations[idx] = midpoint + rng.normal(0, 0.1 * span, size=2) |
| 48 | demands[idx] = min(d_min + rng.uniform(0.4, 0.6) * d_range, vehicle_capacity) |
| 49 | |
| 50 | # ... [Bounds checking, depot logic, and collision resolution omitted] ... |
| 51 | |
| 52 | return { |
| 53 | "problem_size": problem_size, |
| 54 | "vehicle_capacity": vehicle_capacity, |
| 55 | "locations": locations.tolist(), |
| 56 | "demands": demands.tolist(), |
| 57 | } |
| 1 | import numpy as np |
| 2 | |
| 3 | def priority_v2(current_node: int, depot: int, unvisited_nodes: np.ndarray, rest_capacity: float, demands: np.ndarray, distance_matrix: np.ndarray) -> np.ndarray: |
| 4 | """ |
| 5 | Priority function combining angular alignment and radial grouping with capacity-aware decay, |
| 6 | selecting nodes that align spatially with the route direction while efficiently using capacity |
| 7 | through a dynamic distance penalty system. |
| 8 | """ |
| 9 | if len(unvisited_nodes) == 0: |
| 10 | return np.array([]) |
| 11 | |
| 12 | num_nodes = len(unvisited_nodes) |
| 13 | priorities = np.full(num_nodes, -np.inf) |
| 14 | |
| 15 | # Precompute distances |
| 16 | depot_dists = distance_matrix[depot, unvisited_nodes] |
| 17 | current_to_depot = distance_matrix[current_node, depot] |
| 18 | current_to_nodes = distance_matrix[current_node, unvisited_nodes] |
| 19 | |
| 20 | # Capacity utilization factor |
| 21 | max_demand = np.max(demands[unvisited_nodes]) if len(unvisited_nodes) > 0 else 1.0 |
| 22 | capacity_ratio = rest_capacity / max_demand |
| 23 | |
| 24 | # Dynamic decay factor: sigmoid transition around 35% capacity ratio |
| 25 | decay_factor = 1.0 / (1.0 + np.exp(-7.0 * (capacity_ratio - 0.35))) |
| 26 | |
| 27 | # Radial grouping similarity |
| 28 | radial_similarity = 1.0 / (1.0 + np.abs(depot_dists - current_to_depot) / (depot_dists + 1e-6)) |
| 29 | |
| 30 | # Angular alignment component |
| 31 | alignment_scores = np.zeros(num_nodes) |
| 32 | for i in range(num_nodes): |
| 33 | d_cn = current_to_nodes[i] |
| 34 | d_nd = depot_dists[i] |
| 35 | if d_cn > 0 and d_nd > 0 and current_to_depot > 0: |
| 36 | cos_theta = (d_cn**2 + d_nd**2 - current_to_depot**2) / (2 * d_cn * d_nd + 1e-6) |
| 37 | alignment_scores[i] = (cos_theta + 1.0) / 2.0 # normalized to [0,1] |
| 38 | else: |
| 39 | alignment_scores[i] = 0.5 |
| 40 | |
| 41 | for i in range(num_nodes): |
| 42 | node = unvisited_nodes[i] |
| 43 | demand = demands[node] |
| 44 | |
| 45 | if demand > rest_capacity: |
| 46 | continue |
| 47 | |
| 48 | d_cn = current_to_nodes[i] |
| 49 | d_nd = depot_dists[i] |
| 50 | |
| 51 | # Proximity with alignment weighting |
| 52 | proximity = 1.0 / (d_cn + 1e-6) * (1.0 + 0.4 * alignment_scores[i]) |
| 53 | # Capacity efficiency component |
| 54 | capacity_efficiency = demand / (rest_capacity + 1e-6) |
| 55 | # Distance decay penalty |
| 56 | distance_penalty = d_nd * (1.0 - decay_factor) |
| 57 | # Spatial coherence score combining alignment and radial similarity |
| 58 | spatial_coherence = 0.6 * alignment_scores[i] + 0.4 * radial_similarity[i] |
| 59 | # Savings component (modified Clarke-Wright) |
| 60 | savings = depot_dists[i] + current_to_depot - d_cn |
| 61 | savings_boost = savings * (0.7 + 0.3 * capacity_ratio) * spatial_coherence |
| 62 | # Combined priority score |
| 63 | priority_score = (savings_boost + 0.6 * proximity + 0.5 * capacity_efficiency + |
| 64 | 0.4 * spatial_coherence - 0.3 * distance_penalty) |
| 65 | priorities[i] = priority_score |
| 66 | |
| 67 | return priorities |