MEGO: Learning Mixture-of-Experts for General-Purpose Binary Optimization
1Introduction
Abstract
Discrete optimization is ubiquitous in science and engineering. The vast array of existing discrete optimization problems, coupled with the continuous emergence of new ones, necessitates off-the-shelf optimizers capable of generating high-quality solutions for a large variety of optimization problems. This article introduces MEGO, a novel general-purpose neural optimizer for binary optimization under the black-box setting, intended for broad applicability across diverse binary optimization problem classes with minimal problem-specific customization. MEGO comprises a mixture-of-experts trained without domain knowledge. When presented with a new problem instance to solve, it employs a routing policy to dynamically activate the most relevant expert models to generate high-quality solutions. The strong generalization capability of MEGO is demonstrated on six problem classes from different disciplines, including classic problems and real-world applications. Trained solely on classic problems, MEGO effectively generalizes to unseen and complex real-world problem classes, significantly outperforming widely-used general-purpose optimizers in both solution quality and efficiency. Furthermore, MEGO provides a computational approach for quantifying similarity between optimization problems and classifying them, which is fundamentally different from the conventional analysis-based problem classification.
Keywords: Discrete Optimization, Binary Optimization, Neural Optimizer, Learn to Optimize
2Introduction
Discrete optimization, an important branch of applied mathematics and computer science, focuses on solving optimization problems with discrete decision variables. This type of problems represents a foundational challenge that spans across scientific and engineering disciplines, such as in synthetic biology [1], urban planning [2], social network analysis [3],[4], camera imaging [5],[6], and compiler configuration [7]. Traditionally, these problems are addressed through a problem-specific approach, where the inherent structures of the specific problem class are analyzed, and tailored optimizers are designed to exploit these characteristics. For example, for the Influence Maximization Problem (IMP) on social network [3], the submodularity and monotonicity of the problem have been leveraged to achieve theoretically optimal approximation ratios. On the other hand, although such problem-specific approach can achieve excellent performance, it requires substantial domain expertise and human effort for each problem class [8]. The significant time and resources required to develop each specialized optimizer create a critical bottleneck. Consequently, this problem-specific approach struggles to keep pace with the vast and rapidly expanding landscape of optimization problems [9], particularly for optimization problems where domain knowledge is not yet available or is difficult to acquire [10].
Given the above challenge, there is a pressing need for high-performing general-purpose optimizers that can serve as off-the-shelf tools for a large variety of optimization problems. We focus on problems that arise in practical contexts rather than completely arbitrary random binary functions. Even when treated as black-box problems, such practical problems often exhibit non-arbitrary regularities in their solution-quality landscapes, for example in variable interactions or the relative importance of variables [11]-[13]. Such regularities may make the transfer of solving experience across instances, and potentially across problem classes, more plausible. Detailed discussions on the non-arbitrary regularities can be found in the supplementary material. Specifically, such optimizers should deliver high-quality (if not optimal) solutions across diverse problem classes without requiring problem-specific adjustments. Actually, the pursuit of general-purpose optimizers dates back several decades, gradually giving rise to optimizers including Evolutionary Algorithms (EAs) [14], Simulated Annealing (SA) [15], Estimation of Distribution Algorithms (EDAs) [16], and Bayesian optimization (BO) [17]. However, the performance of these optimizers often falls short of satisfactory levels without problem-specific customization, such as meticulous parameter tuning [18] or the selection of specialized search operators and kernel [19]. This dependency on expert-driven, often time-consuming customization presents a significant barrier to their practical utility. Consequently, a critical gap persists in the availability of high-performing, general-purpose optimizers that can be readily deployed.
This article aims to bridge the above gap in the realm of discrete optimization with binary decision variables (hereafter referred to as binary optimization). Such problems are widespread in practice, e.g., appearing in machine learning [20] and certain graph problems [21]. In this work, we study these problems under the black-box setting, where the optimizer accesses a problem instance only through function evaluations. This setting fits naturally our goal of minimizing problem-specific customization, since it avoids reliance on handcrafted structures, explicit formulations, or other domain knowledge. Moreover, the black-box setting is also practically relevant, since in many real-world problems [7] such information is unavailable or difficult to exploit effectively. Accordingly, our use of "general-purpose" refers to broad applicability across diverse binary problem classes with minimal problem-specific customization, rather than a universal performance guarantee for all binary optimization problems. Specifically, we develop a novel general-purpose neural optimizer for binary optimization under this black-box setting through the learning-to-optimize (L2O) paradigm [22]. The core principle of L2O involves training optimizers to effectively handle unseen problem instances by drawing upon experiences from solving training problem instances. A prominent approach within this paradigm is to train neural networks (called neural optimizers) to solve optimization problems. However, prior research in this area has predominantly relied on domain knowledge to train neural optimizers for particular problem classes [8],[23]-[27]. In contrast, this work introduces a domain-agnostic neural optimizer that is trained using only sampled solutions and their corresponding objective values.
The resulting neural optimizer, named Mixture-of-Experts as General-Purpose Optimizers (MEGO), can be viewed as a foundation model for binary optimization. Fig. 1 presents an overview of MEGO. At its core, MEGO comprises a collection of distinct neural networks, with each network acting as an "expert" model. The architecture is inspired by the classical concept of Mixture-of-Experts (MoEs) [28], which refers to a collaborative architecture that adaptively activates specific experts for a given input. Unlike many contemporary MoEs frameworks [29] where the router is typically a module jointly and end-to-end trained with the experts within a unified neural network, MEGO is designed as an ensemble of neural networks (expert models) governed by a dedicated routing policy. These expert models are trained on experiences (i.e., sampled solutions and their objective values) gathered from solving a set of training problem instances (Figs.1a-1b). When applied to new, unseen problem instances (Figs. 1c-1e), the routing policy automatically activates relevant expert(s) to generate high-quality solutions. The entire process, from training to application, operates without the need for domain knowledge or human intervention. This domain-agnostic design allows MEGO to effectively address diverse problem classes.
The strong generalization capability of MEGO across different problem classes is demonstrated through extensive experiments, highlighting two significant findings. First, to the best of our knowledge, MEGO represents the first neural optimizer trained on a specific set of binary optimization problem classes that successfully generalizes to entirely different and unseen binary optimization problem classes. We validate this across six problem classes from diverse disciplines, including three classic problem classes and three challenging problem classes arising from real-world applications. Experimental results in our testbed show that MEGO, trained solely on the three classic problem classes, consistently outperforms widely-used general-purpose optimizers such as GA [14], Hill Climbing with random restart (HC) [30], and BO [31] across all six problem classes in both solution quality and efficiency. Specifically, these competitors require at least 3.6 times the number of function evaluations (#FEs) to match MEGO's solution quality, with MEGO's advantage holding across the tested problem dimensions. Furthermore, when used as an initial solution generator, MEGO can significantly enhance the solution quality of existing general-purpose optimizers. Indeed, on certain problem classes, this enhancement enables a general-purpose optimizer to surpass the performance of specialized optimizers.
Second, MEGO introduces a new perspective on the relationships between binary optimization problems through its vector-based representation of problem instances. Such representation facilitates the measurement of similarity between problem instances, leading to an intriguing problem clustering (classification) that diverges from conventional, analysis-based classification. This data-driven perspective may offer new insights into the landscape of optimization problems.
The contributions of this article are summarized below.
A novel general-purpose neural optimizer, MEGO, is proposed to address diverse binary optimization problem classes under the black-box setting.
Extensive experiments demonstrate that MEGO effectively generalizes to unseen and complex real-world problem classes in our testbed, significantly outperforming widely-adopted general-purpose optimizers in both solution quality and efficiency. Moreover, as an initial solution generator, MEGO can also boost the performance of existing optimizers.
MEGO provides a computational approach to classify optimization problems based on the vector-based representations, offering a new, data-driven perspective on the relationships between different problem classes.
The remainder of this article is organized as follows. Section 3 presents the preliminaries and reviews the related work. Section 4 details the architecture of MEGO, along with its training and application procedures. Experiments are presented in Section 5. Section 6 concludes the article with discussions.
4MoEs as General-Purpose Optimizers (MEGO)
This section details our proposed neural optimizer, MEGO. We first introduce its architecture, and then describe how to train MEGO and apply it to solve new problem instances. Finally, different modes in which MEGO can be utilized are also discussed.
4.1Model Architecture and Training Procedure
We aim to learn a general-purpose neural optimizer for a wide range of binary optimization problem classes. To train such an optimizer, a training set \(T\) is constructed by collecting experiences from solving \(n\) training problem instances \(I_j\left(1\leq j\leq n\right)\) from different problem classes. The experience for each \(I_j\) is a dataset \(E_j=\left\{\left(\mathbf{x}_i,y_i \right)\right\}_{i=1}\), where \(\mathbf{x}_i\in\left\{0,1\right\}^{d_j}\) (\(d_j\) is the problem dimension of \(I_j\)) is a sampled solution and \(y_i\in\mathbb{R}\) is its objective value. Note that \(E_j\) does not contain any explicit knowledge of \(I_j\), such as the formulation of its objective function. Based on the training set \(T=\left\{E_j|1\leq j\leq n\right\}\), the goal is to train an optimizer that generalizes well to an unseen test set \(T^*\) comprising problem instances from diverse problem classes and with dimensions that may differ from those in \(T\).
Our neural optimizer, MEGO, is a MoEs (an ensemble of expert models) where each expert \(M_j\) is trained on an experience set \(E_j\). As a whole, the MoEs collectively captures diverse structural patterns in the training data, adhering to the categorical modularization paradigm [60] where different expert models specialize in solving different problems. To obtain \(M_j\), classical machine learning methods can be used here, e.g., training a neural network based on \(E_j\) to model \(I_j\) 's unknown objective function \(F:\left\{0,1\right\}^{d_j}\rightarrow \mathbb{R}\). However, there are two main limitations to this approach. First, small changes in the discrete input, e.g., flipping several bits, can lead to substantial changes in the objective value, potentially causing \(M_j\) to overfit to local data points and hindering its ability to capture overall structural characteristics. Second, this approach poses challenges when adapting \(M_j\) to new problem instances, as it is difficult to balance leveraging prior experience with incorporating new information.
To address these limitations, we propose a decoupled architecture for the expert model based on variational autoencoder (VAE) [61]. The VAE maps a discrete solution into a compact, continuous latent representation. By predicting objective values from within this regularized latent space, the model is compelled to learn the problem instance's global structural patterns, thereby mitigating overfitting to local patterns in the discrete domain. Furthermore, the model's encoder-decoder architecture facilitates fine-tuning on new instances to solve them, as detailed in Sec. 4.2. The model's architecture and training procedure are illustrated in Figs. 1a-1b, and are detailed below.
Specifically, each expert model \(M_j\) consists of an encoder \(f_\theta\), a decoder \(g_\phi\), and a latent score predictor \(h_\omega\), where \(\theta\), \(\phi\), and \(\omega\) are trainable parameters. The encoder-decoder is implemented as a VAE that explicitly regularizes the latent space to be smooth and compact. Given an input solution \(\mathbf{x}_i\in\left\{0,1\right\}^{d_j}\), the encoder \(f_{\theta}\) predicts means \(\boldsymbol{\mu}\in\mathbb{R}^{d_z}\) and standard deviations \(\boldsymbol{\sigma}\in\mathbb{R}^{d_z}\) of a \(d_z\) -dimensional multivariate Gaussian distribution \(\mathcal{N}\left(\boldsymbol{\mu},\boldsymbol{\sigma}^2\boldsymbol{I}\right)\), from which a vector \(\boldsymbol{z} \in \mathbb{R}^{d_z}\) is sampled. Based on \(\boldsymbol{z}\), The decoder \(g_\phi\left(\mathbf{z}\right)=\mathbf{x}_i^\prime\) reconstructs the input, while the score predictor \(h_\omega\left(\mathbf{z}\right)=y_i^\prime\) estimates the objective value. Conceptually, \(M_j\) is a VAE augmented with a predictor \(h_\omega\) that introduces semantic meaning (i.e., the supervision signal from the objective values) into the latent space. Once well trained, this latent space becomes a smooth and compact transformation of \(I_j\) 's original discrete solution space that also aligns well with its objective function.
The training procedure of MEGO is outlined in Alg. 1. The encoder \(f_\theta\), decoder \(g_\phi\), and score predictor \(h_\omega\) are all neural networks and are jointly trained using normalized samples in \(E_j\) (lines 2-4 in Alg.1). The overall training objective of \(M_j\) is to minimize a composite loss function:
where \(\boldsymbol{\mu},\boldsymbol{\sigma}=f_\theta\left(\mathbf{x}_i\right)\), \(\mathbf{z}\sim\mathcal{N}\left(\boldsymbol{\mu},\boldsymbol{\sigma^2I}\right)\) , \(\mathbf{x}_i^\prime=g_\phi\left(\mathbf{z}\right)\), and \(y^\prime=h_{\omega}\left(\mathbf{z}\right)\). Overall, Eq. (1) consists of three parts: 1) a reconstruction loss measured by square error between \(\mathbf{x}_i\) and \(\mathbf{x}_i^\prime\), encouraging the VAE to capture the essential information of the discrete input; 2) a score prediction loss measured by square error between \(y_i\) and \(y_i^\prime\), encouraging the score predictor to be accurate; and 3) a regularization loss measured by the Kullback-Leibler (KL) divergence between the learned probability distribution \(\mathcal{N}\left(\boldsymbol{\mu},\boldsymbol{\sigma^2I}\right)\) over the latent space and a predefined prior distribution (the standard normal distribution \(\mathcal{N}\left(\boldsymbol{0},\boldsymbol{I}\right)\)), which promotes a smooth and compact latent space. Here, \(\lambda\) and \(\gamma\) are two weighting hyper-parameters.
4.2Employing MEGO to Solve a New Problem Instance
When presented with a new problem instance \(I_{new}\), MEGO follows a three-step procedure: 1) identifying relevant experts, 2) fine-tuning them, and 3) generating solutions. This select-adapt-generate process is designed to efficiently utilize knowledge from previously solved training problem instances for \(I_{new}\), requiring only a small budget of function evaluations (#FEs) on \(I_{new}\). The application procedure of MEGO is shown in Figs. 1c-1e, with the pseudo-code outlined in Alg. 2. For a concrete illustration, Fig. 2 also details these steps as MEGO solves a test instance of the compiler argument optimization problem from our experiments.
4.2.1Relevant Expert Identification
This step aims to identify experts whose learned structural patterns correlate strongly with \(I_{new}\), ensuring that only the most suitable knowledge is utilized. It is governed by MEGO's routing policy (Fig 1c), a rule-based mechanism that quantifies the correlation between \(M_j\) and \(I_{new}\), measured by the alignment between the objective values of the sampled solutions on \(I_{new}\) and the objective values predicted by \(M_j\). Specifically, a small set of \(s\) solutions, \(\left\{\left(\hat{\mathbf{x}}_i, \hat{y}_i\right)\right\}^s_{i=1}\), is obtained by sampling uniformly at random and evaluating on the objective function of \(I_{new}\) (Fig. 2a and line 1 in Alg. 2). Each expert model \(M_j\) is then applied to \(\left\{\hat{\mathbf{x}}_i\right\}^s_{i=1}\) to predict their objective values. The results are denoted as \(\left\{\left(\hat{\mathbf{x}}_i, \hat{y}_i^\prime\right)\right\}^s_{i=1}\), where \(\hat{y}_i^\prime=h_\omega\left(f_\theta\left(\hat{\mathbf{x}}_i\right) \right)\) is the predicted score. If the dimension of \(I_{new}\) is smaller than an expert's input dimension, the sampled target-instance solutions are padded with zeros during relevant expert identification; if it is larger, truncation is used instead. These two sets of results, \(\left\{\left(\hat{\mathbf{x}}_i, \hat{y}_i\right)\right\}^s_{i=1}\) and \(\left\{\left(\hat{\mathbf{x}}_i, \hat{y}_i^\prime\right)\right\}^s_{i=1}\), are then sorted separately based on their respective \(y\) -values to obtain their corresponding rank sequences, \(\left\{\hat{\pi}_i\right\}^s_{i=1}\) and \(\left\{\hat{\pi}_i^\prime\right\}^s_{i=1}\) (Fig. 2b and lines 4-5 in Alg. 2).
To measure the correlation, two coefficients \(\rho_1\) and \(\rho_2\) are calculated (Fig. 2c and lines 6-7 in Alg. 2). An expert \(M_j\) is considered relevant to \(I_{new}\) if \(\rho_1>0\) and \(\rho_2>0\):
\(\rho_1\): the Pearson correlation between the actual and predicted objective values, i.e., \(\left\{\hat{y}_i\right\}^s_{i=1}\) and \(\left\{\hat{y}_i^\prime\right\}^s_{i=1}\). This captures the linear relationship between the scores.
\(\rho_2\): the Spearman's rank coefficient between the ranks of actual and predicted values, i.e., \(\left\{\hat{\pi}_i\right\}^s_{i=1}\) and \(\left\{\hat{\pi}_i^\prime\right\}^s_{i=1}\). This measures the ordinal relationship, assessing whether the expert can correctly rank the solutions by quality.
4.2.2Expert Fine-Tuning
All relevant models are then efficiently adapted to \(I_{new}\). For each relevant model \(M_j\), only its decoder \(g_\phi\) is fine-tuned while the other parts (encoder and latent score predictor) are kept fixed (Fig. 1d), allowing the model to incorporate new information while preserving the learned knowledge. The goal of fine-tuning is to establish a transformation that aligns the solution spaces of \(I_j\) and \(I_{new}\) (Figs. 2d-2e). This is achieved by training the decoder \(g_{\phi}\) on a specially constructed dataset (lines 9-14 in Alg. 2), \(\left\{\left(\mathbf{x}_i,\hat{\mathbf{x}}_i\right)\right\}_{i=1}\). This dataset pairs solutions from the expert's original experience set, \(\mathbf{x}_i \in E_j\), with the newly sampled solutions, \(\hat{\mathbf{x}}_i\), from \(I_{new}\), enforcing ordinal consistency (i.e., better solutions are mapped to better solutions).
Specifically, to construct such a mapping dataset, we first sort the solutions sampled from \(I_{new}\) according to the objective values, denoted as \(R_1\). Then we sample \(4s\) solutions from the training set \(E_j\) of \(M_j\) and also sort them, denoted as \(R_2\). Within each of \(R_1\) and \(R_2\), there may be solutions with the same objective value. Supposing there are \(m_1\) and \(m_2\) unique objective values within \(R_1\) and \(R_2\), respectively, we partition \(R_1\) and \(R_2\) into two sequences of \(m_1\) and \(m_2\) disjoint subsets and sort them, respectively, where the y-values within the same subset are the same: \(R_1=\cup_{i=1}^{m_1}R_1^i\) and \(R_2=\cup_{i=1}^{m_2}R_2^i\). Finally, from both sequences of subsets, we select the first \(m_{min}=\min\left\{m_1,m_2\right\}\) subsets, constructing \(m_{min}\) pairs \(\left\{\left(R_1^i, R_2^i\right)\right\}_{i=1}^{m_{min}}\). The Cartesian product of each pair will constitute the mapping dataset , where " \(\times\) " denotes Cartesian product. Given the mapping dataset \(R=\cup_{i=1}^{m_{min}}R_1^i\times R_2^i=\left\{\left(\mathbf{x}_i,\hat{\mathbf{x}}_i\right)\right\}_{i=1}\), the loss function for fine-tuning \({M_j}\) is:
where \(\boldsymbol{\mu},\boldsymbol{\sigma}=f_\theta\left(\mathbf{x}_i\right)\), \(\mathbf{z}\sim\mathcal{N}\left(\boldsymbol{\mu},\boldsymbol{\sigma^2I}\right)\), \(\mathbf{x}_i^\prime=g_\phi\left(\mathbf{z}\right)\), and \(\phi\) denotes the trainable parameters of the decoder \(g_\phi\). During fine-tuning, the final layer of the decoder will be adjusted to match the problem dimension of \(I_{new}\).
4.2.3Solution Generation
Each fine-tuned \(M_j\) is used to generate candidate solutions for \(I_{new}\) (Fig. 1e). Since the encoder-decoder of fine-tuned \(M_j\) serves as an effective transformation from the solution space of \(I_j\) to that of \(I_{new}\), high-quality solutions for \(I_j\) can be mapped to generate high-quality solutions for \(I_{new}\). Specifically, a large number of \(p\) solutions are randomly sampled in the input space of the encoder of \(M_j\), and their scores, as predicted by \(M_j\), are obtained.An alternative is to search directly in the latent space of a selected expert. An empirical comparison with latent-space search is provided in Section 5.6.1. These solutions are sorted based on the scores, and the top- \(k\) unique solutions, denoted as \(\left\{\bar{\mathbf{x}}_i\right\}_{i=1}^k\) (line 15 in Alg. 2), are retained, where \(k\) is a hyper-parameter. It is worth noting that these retained solutions are high-quality solutions in the source expert's solution space, rather than in the solution space of \(I_{new}\). The encoder-decoder of \(M_j\) is then applied to map \(\left\{\bar{\mathbf{x}}_i\right\}_{i=1}^k\) to a new set of solutions \(\left\{\bar{\mathbf{x}}^\prime_i\right\}_{i=1}^k\) tailored for \(I_{new}\) (line 16 in Alg. 2). Solutions generated from all fine-tuned models are aggregated, evaluated on \(I_{new}\), and the final top- \(k\) solutions are returned (line 20 in Alg. 2).
The total #FEs used by MEGO to generate solutions for \(I_{new}\) is \(s+k\times m\), where \(m\) is the number of relevant expert models. In the experiments, \(s\) and \(k\) are set to small values (\(s=64\) and \(k=4\)), while \(m\) can vary across different problem instances but is generally of moderate size. Typically, MEGO consumes around 100 FEs in total to solve a problem instance.
4.3Constraint Handling and Application Modes of MEGO
MEGO does not incorporate a built-in mechanism for handling constraints, as constraints in optimization problems are often highly problem-dependent. Integrating problem-specific constraint-handling mechanism into the architecture would compromise the model's generality, conflicting with our primary goal of creating a general-purpose optimizer. To address constrained problems, MEGO uses simple, external constraint-handling techniques that operate as a wrapper around it. During training phase, any sampled solution that violates constraints is first transformed into a feasible one by a repair heuristic. Similarly, when MEGO generates solutions for a constrained problem instance, the same technique is applied to ensure the final outputs are feasible. This straightforward approach allows MEGO to maintain its general-purpose characteristic while effectively solving constrained optimization problems.
MEGO can be employed in two modes:
As a standalone optimizer: MEGO can be used directly to find high-quality solutions for a new problem instance within a small budget of #FEs.
As an initial solution generator: The solutions produced by MEGO can provide a set of high-quality starting points to warm-start other optimizers. As demonstrated in the experiments, MEGO's output can be used to initialize the population of GA, provide effective starting points for HC, or serve as the initial design for BO, thereby boosting their performance.
5Experiments
The experiments mainly aim to answer the following key questions. First, as a general-purpose optimizer that targets at diverse binary problem classes, the most important aspect to evaluate is its generalization ability across problem classes. Specifically, can MEGO effectively solve problem instances from classes and dimensionalities that are not part of its training data (RQ1)? Second, for the problem classes that are included in the training set, how well does MEGO generalize to new instances within those same classes (RQ2)?
Beyond evaluating performance, the experiments also explore a novel application of MEGO. A computational approach to problem classification is developed based on vector representations of problem instances derived from MEGO's fine-tuning procedure (see Sec. 5.7). This approach allows for measuring the similarity between different problem instances, leading to a data-driven problem classification. This gives rise to the third key question: How does this learned classification compare with conventional, analysis-based problem classification, and what new relationships between problems might it reveal (RQ3)?
To address these questions, a comprehensive experimental setup is established across six problem classes from various disciplines. This includes three classic problems--the generalized One-Max Problem (OM) [62], the Knapsack Problem (KP) [33], and the Max-Cut Problem (MC) [63]--as well as three real-world applications: Compiler Arguments Optimization (CA) [7], Complementary Influence Maximization (CIM) on social networks [21], and Anchor Selection (AS) for pose estimation in camera imaging [5].
The training set is composed of 27 instances exclusively from the three classic problem classes (OM, KP, and MC). For each class, three instances are generated for each of the dimensions 30, 35, and 40. To generate the training data, each of these instances is associated with an experience set of 20,000 pairs of (solution, objective value), where solutions are sampled uniformly at random. In contrast, the test set comprises 72 instances from all six problem classes, including the three real-world applications (CA, CIM, and AS) unseen during training. The dimensions of the test instances are also higher--specifically 40, 60, 80, and 100--with three instances per dimension for each class. This experimental setup is motivated by a practical consideration: data for classic problems is often abundant or easy to generate, whereas data for real-world applications can be scarce and expensive to obtain. Therefore, demonstrating that an optimizer trained on accessible classic problems can generalize effectively to challenging real-world applications strongly supports its practical utility. Since the black-box setting is considered here, in the experiments, all the general-purpose optimizers interact with the problem instances solely through function evaluations. The Python code of MEGO, problem instances, baselines, and the scripts for repeating our experiments are open-sourced at https://github.com/MetaronWang/MEGO.
5.1Problem Classes, Instances, and Constraint Handling
During the six problem classes, KP, MC, CIM, and AS involve constraints. As noted in Sec. 4.3, MEGO does not handle constraints directly. Instead, external constraint-handling techniques are applied. Details on each problem class, including their objective functions, constraint-handling techniques, and problem instances, are provided below.
5.1.1One-Max Problem (OM)
The OM problem [62] is a fundamental binary optimization task, often serving as a benchmark for analyzing the theoretical performance of search-based optimizer. This work employs a generalized version of OM to create a diverse set of instances. Specifically, the objective of OM is to find a binary vector \(\mathbf{x}\) that minimizes the Hamming distance to a predefined reference vector \(\hat{\mathbf{x}}\). This is equivalent to maximizing the number of matching bits. The original OM problem is a special case where the reference vector consists of all ones.
For a \(d\) -dimensional OM instance with a reference vector \(\hat{\mathbf{x}} \in \{0,1\}^d\), the objective function is:
In the experiments, OM instances are generated by constructing the refenrece vector \(\hat{\mathbf{x}}\). Each element of \(\hat{\mathbf{x}}\) is sampled independently from a uniform distribution over \(\{0, 1\}\).
5.1.2Knapsack Problem (KP)
The KP [33] is a classic combinatorial optimization problem. The goal is to select a subset of items to maximize their total value, subject to a total weight constraint. For a KP instance with \(d\) items, where each item \(i\) has a value \(v_i\) and a weight \(w_i\), a solution is represented by a binary vector \(\mathbf{x} \in \{0,1\}^d\). Here, \(x_i=1\) indicates that item \(i\) is selected. The objective function is:
where \(w_{\text{max}}\) is the weight capacity.
In the experiments, KP instances are generated as follows. Both the value vector \(\mathbf{v}\) and the weight vector \(\mathbf{w}\) are populated with elements sampled uniformly from \([0, 1]\). To introduce a correlation between values and weights, the two vectors are sorted in tandem, ensuring that a higher value corresponds to a higher weight. The weight capacity \(w_{\text{max}}\) is then set as a fraction of the total possible weight, calculated as \(w_{\text{max}} = r \sum_{i=1}^d w_i\), where \(r\) is sampled uniformly from \([0.2, 0.8]\).
Given a KP instance, infeasible solutions are repaired using a simple heuristic. It processes the solution vector \(\mathbf{x}\) sequentially from index \(i=1\) to \(d\). For each selected item \(i\) (\(x_i=1\)), it checks if adding its weight would cause the solution to be infeasible. If so, the selection is reversed by setting \(x_i\) to 0. This check is performed for all items in order, guaranteeing that the repaired solution is feasible.
5.1.3Max-Cut Problem (MC)
The MC problem [63] aims to partition the vertices of a graph into two disjoint sets to maximize the number of edges connecting the two sets. This work focuses on a constrained variant where one of the two partitions is limited to a maximum size. Given an undirected graph with \(d\) vertices, represented by its adjacency matrix \(A \in \{0, 1\}^{d \times d}\), a partition can be defined by a binary vector \(\mathbf{x} \in \{0,1\}^d\), where \(x_i=1\) assigns vertex \(i\) to the first partition, and \(x_i=0\) assigns it to the second. The objective function is:
where \(b\) is the maximum allowed size of the first partition.
In the experiments, problem instances are generated by creating graph structure and the partition size limit. Undirected graphs with \(d\) vertices are generated using the NetworkX library [64]. The number of edges is set to \(r d^2\), where \(r\) is sampled uniformly from \([0.2, 0.4]\). To ensure a meaningful problem structure, only connected graphs are used; any disconnected graphs are discarded and then regenerated. The maximum size for the first partition, i.e., \(b\), is set to \(\lfloor r' d \rfloor\), with \(r'\) is sampled uniformly from \([0.2, 0.4]\).
A repair heuristic, analogous to the one for KP, handles solutions violating the constraint. The heuristic iterates through the solution vector \(\mathbf{x}\) sequentially from \(i=1\) to \(d\). If it encounters a selected vertex (\(x_i=1\)) after the size of the first partition has already reached the limit \(b\), the selection is reversed (\(x_i\) is set to 0).
5.1.4Compiler Arguments Optimization Problem (CA)
The CA problem [7] seeks to identify the optimal set of compiler arguments for a given source code. The goal is to minimize the size of the generated executable file. This is a practical black-box optimization problem, as the objective function involves an actual compilation process. Given a source code file \(G\) and a set of \(d\) available compiler arguments, a solution \(\mathbf{x} \in \{0, 1\}^d\) represents a compiler configuration where \(x_i=1\) enables the \(i\) -th argument. The objective function is:
In the experiments, CA instances are generated using source files randomly selected from the cbench and polybench-cpu benchmarks [65]. The GCC compiler is used, and \(d\) arguments are randomly selected from its 186 available arguments to generate a \(d\) -dimensional CA instance.
5.1.5Complementary Influence Maximization Problem (CIM)
The CIM problem [21] extends the classic IMP [3] by introducing complementary users. The goal is to select a set of "seed" nodes \(S_B\) for one opinion \(B\) to maximize its spread in a social network, given that a complementary opinion \(A\) is already being propagated from a predefined seed set \(S_A\). Formally, given a social network \(\mathcal{G}\) and \(S_A\), CIM aims to find a node set \(S_B\) from a candidate set of \(d\) nodes to maximize the expected number of nodes activated by opinion \(B\), subject to a constraint \(b\) on the size of \(S_B\):
where \(\mathbf{x} \in \{0,1\}^d\) and \(x_i=1\) indicates the \(i\) -th node is included into \(S_B\). The interaction between opinions \(A\) and \(B\) are governed by parameters \(q_{A|\emptyset}\), \(q_{A|B}\), \(q_{B|\emptyset}\), and \(q_{B|A}\), as detailed in [21].
In the experiments, CIM instances are generated using real-world social networks. Specifically, the social network \(\mathcal{G}\) is randomly chosen from the Wiki [66] and Facebook datasets [67]. The candidate node set and \(S_A\) are formed by randomly selecting nodes from the network. The budget \(b\) is set to \(\lfloor r d \rfloor\), with \(r\) sampled uniformly from \([0.2, 0.4]\). The interaction parameters between opinions are set following [21]: \(q_{A|\emptyset}=0.5\), \(q_{A|B}=0.7\), \(q_{B|\emptyset}=0.5\), and \(q_{B|A}=0.5\).
A repair heuristic similar to the one for KP is employed to handle infeasible solutions. If a solution vector violates the size constraint, it iterates through the solution \(\mathbf{x}\) sequentially from \(i=1\) to \(d\), and excess selections are disabled by setting their corresponding bits to 0.
5.1.6Anchor Selection Problem (AS)
The AS Problem arises in selecting robust initial points for numerical solvers in camera imaging [5]. The goal is to select a small subset of "anchor points" (of size at most \(b\)) from a larger candidate set, such that these anchors collectively "cover" or correctly solve the maximum number of problems from a given problem set. This task can be framed as the Maximum Coverage problem. Let \(M = \{m_1, \dots, m_d\}\) be a candidate set of \(d\) anchor points and \(Q\) be a set of problems. For each point \(m_i \in M\), let \(Q_i \subseteq Q\) be the subset of problems it can solve. A solution is represented by a binary vector \(\mathbf{x} \in \{0, 1\}^d\), where \(x_i\) indicates \(m_i\) is selected. The objective function is:
In the experiments, AS instances are generated by randomly selecting scenes from the ETH3D dataset [68], following [5]. A problem set \(Q\) of size 100,000 is generated from a selected scene. The candidate anchor set \(M\) of size \(d\) is created by sampling points from \(Q\). The size limit \(b\) for the anchor set is set to \(\lfloor r d \rfloor\), where \(r\) is uniformly sampled from \([0.1, 0.6]\).
A repair heuristic same as the one for CIM is employed. If a solution vector violates the size constraint, it iterates through the solution and excess selections are disabled.
5.2Compared Optimizers and Experimental Protocol
MEGO is compared with widely-adopted general-purpose optimizers for binary optimization, including GA [14], Hill Climbing with random restart (HC) [30], and BO [31]. The parameters of these baselines are tuned or set according to their original publications. Specifically, GA employs the elitism mechanism, the single-point crossover operator and random flip mutation operator. Its population size is 32, the number of elites is 1, and the mutation rate is set to \(1/d\), where \(d\) is the problem dimension. HC is based on the bit-flip operator and has no parameters. BO is implemented via the SMAC3 package [31], following the suggested settings in its official documentation suitable for various scales of discrete optimization problems. Specifically, random forest is used as the surrogate model and log expected improvement is adopted as the acquisition function. The initial design is generated using a scrambled Sobol sequence, with the number of initial #FEs limited to 25% of the total budget. Finally, a comparison is also made with SMARTEST [7], a specialized optimizer for the CA problem. The parameters of SMARTEST are set following its original paper [7], using a population size of 100, a crossover rate of 0.8, and an elitism rate of 0.1. We also include a variant of MEGO to examine the effect of target-specific adaptation. Compared with MEGO, the variant removes the decoder fine-tuning step (line 14 in Alg. 2) after expert selection, while keeping the total FE budget the same as in MEGO for a fair comparison.
The hyper-parameter settings for MEGO are summarized in Table 1. Its structural hyper-parameters (e.g., VAE architecture), learning hyper-parameters (e.g., learning rate), and weighting hyper-parameters are manually tuned for stable training. Details of the manual tuning process are also provided in the supplementary material. To ensure MEGO consumes within a small budget (around 100) of #FEs, \(s\) and \(k\) are set to 64 and 4, respectively. In terms of wall-clock time, the fine-tuning step of MEGO uses 20000 epochs and takes about 120-180 seconds, while sampling and scoring \(2\times 10^6\) source-space solutions takes about 3 seconds on our reference machine. As aforementioned in Sec. 4.3, MEGO can be employed in two modes. Both modes are evaluated in the experiments. First, MEGO is assessed as a standalone optimizer and compared directly against the baselines. Second, MEGO is utilized as an initial solution generator to warm-start these optimizers. In the second mode, the combined optimizer is denoted as MEGO+X (e.g., MEGO+GA). For MEGO+GA, the solutions generated by MEGO will be directly inserted into its initial population. For MEGO+HC, the generated solutions will serve as candidates for the starting point at each restart. For MEGO+BO, the generated solutions are used to initialize the surrogate model.
For a comprehensive performance evaluation, the compared optimizers are assessed under two distinct stopping criteria:
A short budget criterion: the optimizers use the same #FEs as MEGO, which typically represents the scenario with high demands for solution efficiency.
A long-budget criterion: the optimizers run for a longer time until a budget of 800 FEs is consumed.
To ensure a fair comparison, the same repair procedure is applied to all compared methods under the same evaluation protocol. Each optimizer is applied 30 times independently on every test instance, and the average results from these runs are compared. For the ease of comparison, all objective values are normalized and reported, with higher values indicating better performance. The detailed solution quality results for all compared optimizers are available in the supplementary. Furthermore, Wilcoxon rank-sum tests with significance level 0.05 are employed to determine the significance of the observed performance differences between the optimizers.
5.3Performance on Entirely Unseen Problem Classes
The most intriguing findings of this work emerge from the performance of MEGO on real-world problem classes beyond the training set. Fig. 3 presents these results. Figs. 3a-3l show the averaged convergence curves across the three test instances for each problem class and dimension. The #FEs consumed by MEGO and the solution quality it achieves are indicated with red lines for easy comparison under the first stopping criterion. Fig. 3m presents the acceleration ratio (detailed results are provided in the supplementary), calculated as the #FEs required by baselines to reach MEGO's solution quality divided by MEGO's #FEs. Finally, on different problem dimensions, statistical results of comparing MEGO with baselines are presented in Figs. 3n-3o, respectively.
There are five primary findings from Fig. 3. First, Figs. 3a-3l show that MEGO generalizes effectively to the unseen problem classes considered here. To the best of our knowledge, this is the first neural optimizer trained on a specific set of binary optimization problem classes generalizes well to entirely unseen binary optimization problem classes. Furthermore, this generalization extends to problem dimensionality. MEGO was trained on instances with dimensions up to 40, yet it performs well on test instances with dimensions up to 100. Second, MEGO surpasses widely-adopted general-purpose optimizers in both solution quality and computational efficiency on the problem classes considered here. Specifically, under the first stopping criterion, MEGO obtains much better solutions than the three baselines when using the same #FEs. As shown in Fig. 3m, GA, HC, and BO require on average 3.7, 4.0, and 4.4 times the #FEs of MEGO, respectively, to match MEGO's solution quality, indicating MEGO is much more efficient than these optimizers. Third, MEGO serves as an effective performance booster for existing optimizers as an initial solution generator. Specifically, on the CA class, the W-D-L (win-draw-loss) counts of MEGO+X vs. X (X: GA, HC, or BO) are 4-8-0, 5-7-0, and 6-6-0 when X is GA, HC, and BO, respectively. On the CIM class, these counts are 9-3-0, 11-1-0, and 12-0-0, respectively, and on the AS class, these counts are 9-3-0, 12-0-0, and 11-1-0, respectively. Fourth, MEGO is consistently better than the No-Finetuning variant, indicating that target-specific adaptation plays an important role in the effectiveness of MEGO. Finally, from Fig. 4n and Fig. 4o, the advantage of MEGO under both stopping criteria does not change significantly as the problem dimension varies from 40 to 100, i.e., it is not sensitive to problem dimension.
In summary, these findings have affirmatively answered RQ1, thus indicating MEGO's potential for practical applications. Particularly, MEGO can be trained on well-studied classic problems and then, without adjustments, applied to unseen, real-world optimization challenges where training data might be scarce or difficult to obtain.
5.4Performance on Problem Classes Seen in the Training Set
On the classic problem classes present in the training set, MEGO's performance advantage is even more pronounced (Figs. 4a-4l). Under the first stopping criterion (Fig. 4m), MEGO achieves average acceleration ratios of 3.6, 5.1, and 4.8 compared to GA, HC, and BO, respectively. With an extended budget of 800 FEs, MEGO+X consistently outperforms the three baselines across all dimensions and problem classes. For example, on the OM class, MEGO+X achieves a perfect 12-0-0 W-D-L record against all three baselines. Finally, from Figs. 4n-4o, once again MEGO's advantage is not sensitive to problem dimension.
These results further confirm MEGO's superior performance over the considered general-purpose optimizers and its ability to enhance them, thus affirmatively answering RQ2 within our testbed. Collectively, Figs. 3 and 4 demonstrate MEGO's promising performance as a general-purpose optimizer applicable to diverse binary optimization problem classes.
5.5Comparison with Specialized Optimizer on CA Problem
Table 2 compares MEGO+BO with the recently published specialized optimizer SMARTEST [7] on the CA problem class. From Table 2, MEGO+BO obtains the best solution quality (in terms of code size of the generated executable file) on all 12 problem instances, far better than any other compared optimizer. Statistical results further show that on any of the problem instances, MEGO+BO is not inferior to SMARTEST, and on five of them, the solution quality obtained by MEGO+BO is significantly better than SMARTEST. The above findings hold even when the #FEs consumed by SMARTEST is doubled to 1600. These results once again demonstrate that MEGO can significantly improve a general-purpose optimizer, in some cases enabling it to substantially surpass the performance of specialized optimizers.
5.6Component Analysis
5.6.1Source-Space Sampling versus Latent-Space Search
Since prior VAE-based optimization methods often perform search directly in the latent space, we further compared the current solution-generation strategy in MEGO with a latent-space search variant. In MEGO, candidate solutions are generated by sampling in the source instance's solution space, where \(p=2000000\) source-space solutions are randomly sampled (see Sec. 4.2.3). In the latent-space variant, 1024 random latent vectors are first initialized, and gradient descent is then applied for 1954 steps to optimize the latent score predictor, resulting in 2000896 evaluated solutions in total.
The comparison results, in terms of aggregated W-D-L counts for each class, are presented in Table 3. Complete per-instance solution-quality and W-D-L results are provided in the supplementary. It can be seen that the current source-space sampling strategy outperforms the latent-space search variant on 53 out of 72 test instances, ties on 16 instances, and loses on only 3 instances. A possible explanation is that the fine-tuning stage in MEGO is designed to establish a mapping from the source solution space to that of the target instance. Under this design, source-space sampling produces genuine source-space candidate solutions, for which the score predictor and the fine-tuned decoder are better aligned. By contrast, direct optimization in the latent space may move to regions that are weakly supported by the source training data, where high predicted scores do not necessarily correspond to truly high-quality source-space solutions. As a result, the decoded target solutions may become less reliable.
5.6.2Padding Strategy
To examine whether zero padding would introduce bias during the expert identification step of MEGO (see Sec. 4.2.1), we compared three padding strategies: zero padding, all-one padding, and random padding. To ensure that padding is indeed required, we used test instances of dimension 20, while the experts were trained on dimensions 30, 35, and 40. Each strategy was executed for 30 independent runs on every problem instance. The test results are presented in Table 4. Across the 18 test instances, zero padding achieves W-D-L counts of 2-15-1 against all-one padding and 2-14-2 against random padding. These results indicate that all the three strategies are broadly comparable to each other, and no clear systematic bias is observed.
5.6.3Source-Target Mapping
To investigate the effect of the source-target mapping step (line 16 in Alg. 2), we further compared the following two configurations of MEGO.
Mapping: The standard MEGO procedure.
No Mapping: A variant of MEGO where the solution mapping step is removed. After experts are selected, new solutions are sampled directly in the source problem instance's solution space. Then, these solutions are ranked by their performance on the expert models and the top- \(k\) solutions are selected, and are finally evaluated on the target problem instance.
Each method was executed for 30 independent runs on every problem instance. The test results, in terms of aggregated W-D-L counts (according to the Wilcoxon rank-sum test at a 0.05 significance level) for each class, are presented in Table 5. Complete per-instance solution-quality and W-D-L results are provided in the supplementary. Overall, these results show that MEGO (with mapping) outperforms the no-mapping variant on 67 out of 72 test instances, ties on 4 instances, and loses on only 1 instance. These results indicate that the mapping step is essential for the effectiveness of MEGO.
5.6.4Relevant Expert Identification
The current implementation of MEGO would normally activate multiple experts rather than only one (MEGO selects about 14 experts on average across the experiments). A natural question is whether activating multiple experts is beneficial, since different experts may contain overlapping knowledge. To examine the effect of this design, we compared MEGO with three expert-selection baselines: (i) random selection of the same number of experts as MEGO (denoted as "SAMPLE"), (ii) the average performance obtained by running each expert individually ("MEAN") that corresponds to randomly selecting only one expert, and (iii) the hindsight best individual expert among all experts ("MAX"). Table 6 reports aggregated W-D-L results (according to the Wilcoxon rank-sum test at a 0.05 significance level) at the problem-class level. Complete results are provided in the supplementary material.
Across all 72 test instances, MEGO achieves W-D-L counts of 19-45-8 against SAMPLE, 71-0-1 against MEAN, and 9-15-48 against MAX. These results suggest that activating multiple experts is indeed beneficial, as MEGO substantially outperforms the MEAN baseline (relying on a single randomly chosen expert), and that the correlation-based routing strategy is more effective than selecting the same number of experts at random. At the same time, it is not surprising that the hindsight best single expert often outperforms MEGO, because that baseline assumes oracle knowledge after exhaustively evaluating all experts. Overall, these results suggest that overlap among experts does not negate the value of multi-expert activation. Rather, what matters is activating a relevant subset of experts for the target instance.
To further examine whether the correlation-based routing policy can identify useful experts, we compared it with random selection in terms of the rates of hitting top- \(k\) relevant experts, where \(k=1,3,5,10\). The results in Figure 5 show that using correlation coefficients generally leads to higher average hit rates than random selection, especially for top-3, top-5, and top-10. This indicates that the routing policy is effective in identifying relevant experts for a target instance.
5.6.5Analysis of the Latent Representation
To further examine whether the latent representations could preserve global structural information, we performed a quantitative analysis of reconstruction fidelity and geometry preservation for the expert models. Specifically, for an expert model trained on a training instance, we randomly generate 10000 binary solutions \(X\), encode them into the latent space, and then decode them to obtain reconstructed solutions \(X'\). These input solutions are generated independently of the training and validation sets. The mean absolute error between \(X\) and \(X'\) is only 0.006, corresponding to a per-dimension reconstruction accuracy of 99.4% for binary vectors. In addition, the exact reconstruction accuracy at the whole-solution level reaches 84%.
We further analyze whether relative relationships among solutions are preserved after passing through the latent representation. Specifically, we compute the pairwise Manhattan distances among solutions in \(X\) and among reconstructed solutions in \(X'\), and then measure the rank correlation between these two distance matrices. The results are illustrated in Fig. 6. The resulting Kendall's Tau and Spearman correlation coefficients are 0.767 and 0.927, respectively.
These results suggest that the latent representations preserve substantial structural information about the original solution space, both at the level of individual solution reconstruction and at the level of geometric relationships among solutions.
5.7A Novel Perspective of Problem Classification
Based on MEGO, a computational approach is developed to classify optimization problems based on their vector-based representations. This approach results in a novel, data-driven perspective that diverges from conventional, analysis-based classification.
Specifically, each test instance \(I_{new}\) is represented as a \(27\) -dimensional vector, with the \(j\) -th component quantifies the similarity between \(I_{new}\) and the \(j\) -th training problem instance (there are 27 training problem instances in total). To obtain this vector, the following procedure is applied. First, each of the 27 expert models in MEGO is adapted to \(I_{new}\), using the fine-tuning procedure described in Sec. 4.2. Once fine-tuned, the encoder-decoder of each expert model is a mapping from the solution space of the corresponding training problem instance to the solution space of \(I_{new}\). Based on each of these mappings, a large number of solutions are randomly sampled and the four solutions with the highest predicted scores are identified, resulting in a candidate pool of 108 solutions. These solutions are then evaluated using the objective function of \(I_{new}\), and the top four unique solutions from this pool are retained. This step validates which expert models are genuinely most effective at generating high-quality solutions for \(I_{new}\).
The above procedure is repeated for 30 times; therefore a final elite set of 120 solutions (4 solutions × 30 repeat) is collected. The vector is then derived from this elite set. A raw 27-dimensional count vector, \(\mathbf{a}'\), is first constructed, where its \(j\) -th component, \(a_j\), is simply the number of solutions in the 120-solution elite set that originated from the \(j\) -th expert model. This count directly measures the contribution, and thus the relevance, of the \(j\) -th training problem instance to solving \(I_{new}\). Finally, to ensure the components are on a consistent scale for comparison and clustering, the raw count vector is L2-normalized to produce the final vector: \(\mathbf{a}=\frac{\mathbf{a}'}{||\mathbf{a}||_2}\).
Fig. 7 illustrates the clustering (using K-means [69]) and 2-dimensional t-SNE visualization [70] of the vectors of all 72 test instances (5 clusters). The resulting classification reveals interesting discrepancies from conventional problem classification. While some consistency exists (e.g., between OM class and cluster 5, AS class and cluster 3), other problem classes show substantial distribution across multiple clusters. For instance, the CA and CIM classes are each spread across 4 clusters. These findings are somewhat counterintuitive. They indicate that from the perspective of a learned optimizer like MEGO, instances from conventionally different problem classes may exhibit greater similarity than instances within the same problem class. This observation also suggests that the behavior of MEGO is not determined solely by the manually defined training problem classes. This insight offers an explanation for MEGO's strong generalization to unseen problem classes. That is, in the cases studied here, MEGO succeeds not by learning the abstract properties of a problem class, but by identifying that a new instance--regardless of its conventional class label--shares sufficiently aligned solution-quality landscape structure with some instances in its experience, thereby enabling the transfer of a relevant optimization strategy.
Overall, MEGO introduces a computational lens for examining the relationships between seemingly disparate optimization problems. This data-driven perspective on problem similarity complements conventional, analysis-based classifications and may offer new insights into the problem landscape.
6Conclusion and Discussion
This work addresses the challenge of building off-the-shelf optimizers for binary optimization. MEGO, a general-purpose neural optimizer, is introduced. With minimal problem-specific customization, MEGO shows strong generalization capabilities across the six problem classes considered in this work, including those not seen during training. Furthermore, MEGO offers a new computational approach for classifying optimization problems, which is fundamentally different from the conventional problem classification approach. At the same time, it is important to note that MEGO should not be understood as a universal optimizer for arbitrary binary optimization problems. Its effectiveness depends on whether the target problem instance shares reusable structure (regularities) with the expert pool. To further examine this point, we conducted an additional experiment in which the target problem instance is an arbitrary random binary function, and compared MEGO with the baselines under the same #FEs over 30 independent runs. The results show that MEGO no longer exhibits a meaningful transfer advantage in that case. This supports the view that when such reusable structure is weak or absent, transfer is no longer meaningful and negative transfer may occur. Detailed discussion of these regularities and the additional experiment is provided in the supplementary material.
There exist many open avenues for future improvement. For instance, the current MEGO architecture is intentionally modular rather than fully end-to-end. Each expert model is trained independently on one training instance, the routing policy is based on sampled evaluations and correlation-based expert selection, and the selected experts are subsequently adapted to the target instance through decoder fine-tuning. As a result, the overall pipeline is better viewed as a select-adapt-generate framework than a conventional end-to-end MoE.
This design has both advantages and limitations. On the one hand, it makes MEGO modular and flexible, allows experts to be learned independently from black-box experience data, and avoids requiring a differentiable routing mechanism tied to a specific problem representation. It also naturally supports target-instance-specific adaptation after expert selection. On the other hand, because the router and the experts are not jointly optimized, they may not be perfectly synchronized. Consequently, the routing rule may fail to activate the most useful experts in some cases, or may activate suboptimal ones.
Developing a more tightly integrated version of MEGO would require a substantially different framework, since the current routing procedure is non-differentiable and the adaptation step depends on target-instance-specific sampled data. Future work may therefore investigate differentiable routing, meta-level adaptation across problem instances, or reinforcement-learning-based routing and training strategies.
Furthermore, MEGO does not directly handle constraints. While it can be paired with simple repair heuristics to solve constrained problems, a notable advancement would be the integration of a built-in, general-purpose constraint-handling mechanism. Beyond that, several other exciting research directions are envisioned:
The evaluation of MEGO can be extended to a wider array of problem classes and dimensions. In particular, scaling MEGO to much larger binary dimensions is an important direction for future work, but will likely require improved expert architectures and more efficient adaptation mechanisms for high-dimensional settings.
Another important direction is to investigate more principled ways of automatically constructing the training problem classes and expert pool, thereby mitigating the potential bias of manual selection.
The current solution-generation step uses random sampling for simplicity and efficiency. A promising direction is to investigate more sophisticated search strategies in the latent space of selected experts, which may further improve solution quality.
A continuous learning framework could be explored. This would allow MEGO to continuously improve by learning from new problem instances encountered after its initial training, but it would also enlarge the expert pool over time. In the current implementation, the storage cost grows linearly with the number of experts, with each expert occupying about 5.9 MB. At inference time, not all experts are activated for every target instance, and fine-tuning and solution generation for different selected experts are naturally parallelizable. The GPU memory usage for one expert is about 750 MB, and on an 8-GPU server with Nvidia MPS or MIG enabled, we can fine-tune and sample from at least 24 experts concurrently with little observed additional latency. A key challenge for future work is therefore to manage the growing expert pool efficiently, for example through dynamic model pruning, so as to maintain a balance between performance and computational cost.
Finally, the problem classification approach enable by MEGO could be explored further. A valuable next step would be to analyze the structural properties of the resulting problem clusters. For instance, by using fitness landscape analysis, one could examine whether the problem instances grouped together share underlying features, such as ruggedness or variable interaction. Such an understanding could then be used to develop more suitable optimization strategy for these problem instances.
7Acknowledgments
This work was supported by National Key Research and Development Program of China under Grant 2022YFA1004102, and in part by the Natural Science Foundation of China under Grants T2495254, 62502192, and 62250710682, and in part by the internal grants of Lingnan University.
References
- G. Naseri, M. A. Koffas, "Application of combinatorial optimization strategies in synthetic biology", Nat. Commun., vol. 11, no. 1, pp. 2446, 2020.
- L. Tang, T. Li, Y. Meng, J. Liu, "Searching in Symmetric Solution Space for Permutation-Related Optimization Problems", IEEE Trans. Pattern Anal. Mach. Intell., vol. 47, no. 8, pp. 7036--7052, 2025.
- D. Kempe, J. Kleinberg, \. Tardos, "Maximizing the spread of influence through a social network", in Proceedings of KDD'2003, 2003.
- J. Yu, T. Xu, Y. Rong, Y. Bian, J. Huang, R. He, "Recognizing Predictive Substructures With Subgraph Information Bottleneck", IEEE Trans. Pattern Anal. Mach. Intell., vol. 46, no. 3, pp. 1650--1663, 2024.
- P. Hruby, T. Duff, A. Leykin, T. Pajdla, "Learning to solve hard minimal problems", in Proceedings of CVPR'2022, New Orleans, LA, 2022.
- C. Wang, Y. Liu, Y. Wang, X. Li, M. Wang, "Efficient and Outlier-Robust Simultaneous Pose and Correspondence Determination by Branch-and-Bound and Transformation Decomposition", IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 10, pp. 6924--6938, 2022.
- H. Jiang, G. Gao, Z. Ren, X. Chen, Z. Zhou, "SMARTEST: a surrogate-assisted memetic algorithm for code size reduction", IEEE Trans. Reliab., vol. 71, no. 1, pp. 190--203, 2021.
- S. Liu, Y. Zhang, K. Tang, X. Yao, "How good is neural combinatorial optimization? A systematic evaluation on the traveling salesman problem", IEEE Comput. Intell. Mag., vol. 18, no. 3, pp. 14--28, 2023.
- J. Pan, P. Hu, V. Sn\'asel, S. Chu, "A survey on binary metaheuristic algorithms and their engineering applications", Artif. Intell. Rev., vol. 56, no. 7, pp. 6101--6167, 2023.
- L. M. Rios, N. V. Sahinidis, "Derivative-free optimization: a review of algorithms and comparison of software implementations", J. Glob. Optim., vol. 56, no. 3, pp. 1247--1293, 2013.
- B. Li, Z. Wei, J. Wu, S. Yu, T. Zhang, C. Zhu, D. Zheng, W. Guo, C. Zhao, J. Zhang, "Machine learning-enabled globally guaranteed evolutionary computation", Nat. Mac. Intell., vol. 5, no. 4, pp. 457--467, 2023.
- A. Schrijver, others, "Combinatorial optimization: polyhedra and efficiency", Springer, 2003.
- Z. Wang, F. Hutter, M. Zoghi, D. Matheson, N. D. Freitas, "Bayesian Optimization in a Billion Dimensions via Random Embeddings", J. Artif. Intell. Res., vol. 55, pp. 361--387, 2016.
- J. H. Holland, "Genetic algorithms", Sci. Am., vol. 267, no. 1, pp. 66--73, 1992.
- S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi, "Optimization by simulated annealing", Science, vol. 220, no. 4598, pp. 671--680, 1983.
- P. Larra\~naga, J. A. Lozano, "Estimation of distribution algorithms: A new tool for evolutionary computation", Springer Science \& Business Media, 2001.
- D. R. Jones, M. Schonlau, W. J. Welch, "Efficient global optimization of expensive black-box functions", J. Glob. Optim., vol. 13, pp. 455--492, 1998.
- M. L\'opez-Ib\'a\~nez, J. Dubois-Lacoste, L. P. C\'aceres, M. Birattari, T. Stutzle, "The irace package: Iterated racing for automatic algorithm configuration", Oper. Res. Perspect., vol. 3, pp. 43--58, 2016.
- G. Malkomes, R. Garnett, "Automating Bayesian optimization with Bayesian optimization", in Proceedings of NeurIPS'2018, 2018.
- T. Elsken, J. H. Metzen, F. Hutter, "Neural Architecture Search: A Survey", J. Mach. Learn. Res., vol. 20, pp. 55:1--55:21, 2019.
- W. Lu, W. Chen, L. V. S. Lakshmanan, "From Competition to Complementarity: Comparative Influence Diffusion and Maximization", Proc. VLDB Endow., vol. 9, no. 2, pp. 60--71, 2015.
- K. Tang, X. Yao, "Learn to optimize—a brief overview", Natl. Sci. Rev., vol. 11, no. 8, pp. nwae132, 2024.
- O. Vinyals, M. Fortunato, N. Jaitly, "Pointer Networks", in Proceedings of NIPS'2015, 2015.
- I. Bello, H. Pham, Q. V. Le, M. Norouzi, S. Bengio, "Neural Combinatorial Optimization with Reinforcement Learning", in Proceedings of ICLR'2017, 2017.
- Y. Bengio, A. Lodi, A. Prouvost, "Machine learning for combinatorial optimization: a methodological tour d’horizon", Eur. J. Oper. Res., vol. 290, no. 2, pp. 405--421, 2021.
- C. Wang, Z. Yu, S. McAleer, T. Yu, Y. Yang, "ASP: Learn a Universal Neural Solver!", IEEE Trans. Pattern Anal. Mach. Intell., vol. 46, no. 6, pp. 4102--4114, 2024.
- T. Kortus, R. Keidel, N. R. Gauger, "Towards Neural Charged Particle Tracking in Digital Tracking Calorimeters With Reinforcement Learning", IEEE Trans. Pattern Anal. Mach. Intell., vol. 45, no. 12, pp. 15820--15833, 2023.
- N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. V. Le, G. E. Hinton, J. Dean, "Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer", in Proceedings of ICLR'2017, 2017.
- W. Cai, J. Jiang, F. Wang, J. Tang, S. Kim, J. Huang, "A Survey on Mixture of Experts in Large Language Models", IEEE Trans. Knowl. Data Eng., vol. 37, no. 7, pp. 3896--3915, 2025.
- S. J. Russell, P. Norvig, "Artificial intelligence: a modern approach", pearson, 2016.
- M. Lindauer, K. Eggensperger, M. Feurer, A. Biedenkapp, D. Deng, C. Benjamins, T. Ruhkopf, R. Sass, F. Hutter, "SMAC3: A versatile Bayesian optimization package for hyperparameter optimization", J. Mach. Learn. Res., vol. 23, no. 54, pp. 1--9, 2022.
- J. Cai, J. Luo, S. Wang, S. Yang, "Feature selection in machine learning: A new perspective", Neurocomputing, vol. 300, pp. 70--79, 2018.
- S. Martello, P. Toth, "Knapsack problems: algorithms and computer implementations", John Wiley \& Sons, Inc., 1990.
- M. M. Keikha, "Improved simulated annealing using momentum terms", in Proceedings of ISMS'2011, 2011.
- S. W. Mahfoud, D. E. Goldberg, "Parallel Recombinative Simulated Annealing: A Genetic Algorithm", Parallel Comput., vol. 21, no. 1, pp. 1--28, 1995.
- M. A. Londe, L. S. Pessoa, C. E. D. Andrade, M. G. C. Resende, "Biased random-key genetic algorithms: A review", Eur. J. Oper. Res., vol. 321, no. 1, pp. 1--22, 2025.
- K. G. Srinivasa, K. R. Venugopal, L. M. Patnaik, "A self-adaptive migration model genetic algorithm for data mining applications", Inf. Sci., vol. 177, no. 20, pp. 4295--4313, 2007.
- R. Baptista, M. Poloczek, "Bayesian Optimization of Combinatorial Structures", in Proceedings of ICML'2018, 2018.
- C. Oh, J. M. Tomczak, E. Gavves, M. Welling, "Combinatorial Bayesian Optimization using the Graph Cartesian Product", in Proceedings of NeurIPS'2019, 2019.
- M. Pelikan, D. E. Goldberg, "Hierarchical Bayesian Optimization Algorithm", Scalable Optimization via Probabilistic Modeling, 2006, 2006.
- C. Huang, Y. Li, X. Yao, "A Survey of Automatic Parameter Tuning Methods for Metaheuristics", IEEE Trans. Evol. Comput., vol. 24, no. 2, pp. 201--216, 2020.
- K. Li, \. Fialho, S. Kwong, Q. Zhang, "Adaptive Operator Selection With Bandits for a Multiobjective Evolutionary Algorithm Based on Decomposition", IEEE Trans. Evol. Comput., vol. 18, no. 1, pp. 114--130, 2014.
- G. Malkomes, C. Schaff, R. Garnett, "Bayesian optimization for automated model selection", in Proceedings of NIPS'2016, 2016.
- W. Kool, H. V. Hoof, M. Welling, "Attention, Learn to Solve Routing Problems!", in Proceedings of ICLR'2019, 2019.
- Y. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, S. Min, "POMO: Policy Optimization with Multiple Optima for Reinforcement Learning", in Proceedings of NeurIPS'2020, 2020.
- C. Gao, H. Shang, K. Xue, D. Li, C. Qian, "Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy", in Proceedings of IJCAI'2024, 2024.
- E. B. Khalil, H. Dai, Y. Zhang, B. Dilkina, L. Song, "Learning Combinatorial Optimization Algorithms over Graphs", in Proceedings of NIPS'2017, 2017.
- C. K. Joshi, T. Laurent, X. Bresson, "An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem", CoRR, vol. abs/1906.01227, 2019.
- R. G\'omez-Bombarelli, J. N. Wei, D. Duvenaud, J. M. Hern\'andez-Lobato, B. S\'anchez-Lengeling, D. Sheberla, J. Aguilera-Iparraguirre, T. D. Hirzel, R. P. Adams, A. Aspuru-Guzik, "Automatic chemical design using a data-driven continuous representation of molecules", ACS central science, vol. 4, no. 2, pp. 268--276, 2018.
- R. Luo, F. Tian, T. Qin, E. Chen, T. Liu, "Neural Architecture Optimization", in Proceedings of NeurIPS'2018, 2018.
- A. Hottung, B. Bhandari, K. Tierney, "Learning a Latent Search Space for Routing Problems using Variational Autoencoders", in Proceedings of ICLR'2021, 2021.
- N. Maus, H. T. Jones, J. Moore, M. Kusner, J. Bradshaw, J. R. Gardner, "Local Latent Space Bayesian Optimization over Structured Inputs", in Proceedings of NeurIPS'2023, 2022.
- S. Lee, J. Chu, S. Kim, J. Ko, H. J. Kim, "Advancing Bayesian Optimization via Learning Correlated Latent Space", in Proceedings of NeurIPS'2023, 2023.
- J. Hu, J. Whitman, H. Choset, "GLSO: Grammar-guided Latent Space Optimization for Sample-efficient Robot Design Automation", in Proceedings of CoRL'2022, 2022.
- H. B. Moss, S. W. Ober, T. Diethe, "Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spaces", in Proceedings of ICML'2025, 2025.
- C. Gao, H. Shang, K. Xue, C. Qian, "Neural Solver Selection for Combinatorial Optimization", in Proceedings of ICML'2025, 2025.
- X. He, H. Shang, C. Qian, "How to Train Algorithm Selection Models: Insights from Black-box Continuous Optimization", in Proceedings of GECCO'2025, 2025.
- A. Kostovska, G. Cenikj, D. Vermetten, A. Jankovic, A. Nikolikj, U. Skvorc, P. Korosec, C. Doerr, T. Eftimov, "PS-AAS: Portfolio Selection for Automated Algorithm Selection in Black-Box Optimization", in Proceedings of AutoML'2023, 2023.
- X. Wu, J. Wu, Y. Zhou, L. Feng, K. Tan, "Towards Robustness and Explainability of Automatic Algorithm Selection", in Proceedings of ICML'2025, 2025.
- P. J. Darwen, X. Yao, "Speciation as automatic categorical modularization", IEEE Trans. Evol. Comput., vol. 1, no. 2, pp. 101--108, 1997.
- D. P. Kingma, M. Welling, "Auto-Encoding Variational Bayes", in Proceedings of ICLR'2014, 2014.
- L. Eshelman, "On crossover as an evolutionarily viable strategy", in Proceedings of ICGA'1991, 1991.
- M. R. Garey, D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", W. H. Freeman, 1979.
- A. Hagberg, P. J. Swart, D. A. Schult, "Exploring network structure, dynamics, and function using NetworkX", 2008.
- G. Fursin, "Collective Tuning Initiative: automating and accelerating development and optimization of computing systems", in Proceedings of the GCC Developers' Summit'2009, 2009.
- J. Leskovec, D. P. Huttenlocher, J. M. Kleinberg, "Predicting positive and negative links in online social networks", in Proceedings of WWW'2010, 2010.
- J. J. McAuley, J. Leskovec, "Learning to Discover Social Circles in Ego Networks", in Proceedings of NIPS'2012, 2012.
- T. Sch\"ops, J. L. Sch\"onberger, S. Galliani, T. Sattler, K. Schindler, M. Pollefeys, A. Geiger, "A Multi-View Stereo Benchmark with High-Resolution Images and Multi-Camera Videos", in Proceedings of CVPR 2017, 2017.
- S. Lloyd, "Least squares quantization in PCM", IEEE Trans. Inf. Theory., vol. 28, no. 2, pp. 129--137, 1982.
- L. Van der Maaten, G. Hinton, "Visualizing data using t-SNE", J. Mach. Learn. Res., vol. 9, no. 11, 2008.
App. ADetailed Experimental Results on Problem Classes Seen in the Training Set
App. A.1Objective Values of MEGO and the Baselines
We compare the objective values achieved by MEGO and the baselines on the training problem classes, while the baselines use the same #FEs as MEGO. Each problem instance is optimized 30 times. The results' statistical significance was tested through the Wilcoxon rank-sum statistic. Table 7, 8, 9 compare the objective values achieved by MEGO and baselines on the OM problem, KP, and MC problem, respectively.
App. A.2Acceleration Ratios of MEGO compared to the Baselines
We record the #FEs required by the baselines to achieve the objective values of MEGO, and based on this, calculate the acceleration ratio of MEGO relative to baselines across various problem classes and various problem dimensions. The #FEs used for a specific problem class with a particular dimension were averaged over 30 runs on the three test instances. The comparison results are shown in Table 10.
App. A.3Objective Values of MEGO+X and the Baselines
MEGO+X uses MEGO as the initial solution generator for X, and X is the baseline. We compare the objective values achieved by MEGO+X and the baselines on the training problem classes while the budget of #FEs is 800. Each problem instance is optimized 30 times. The results’ statistical significance was tested through the Wilcoxon rank-sum statistic. Table 11, 12, 13 compare the objective values achieved by MEGO+X and baselines on the OM problem, KP, and MC problem, respectively.
App. BDetailed Experimental Results on Unseen Problem Classes
App. B.1Objective Values of MEGO and the Baselines
Table 14, 15, 16 compare the objective values achieved by MEGO and baselines on the CA problem, CIM problem, and AS problem, respectively, while the baselines use the same #FEs as MEGO.
App. B.2Acceleration Ratios of MEGO compared to the Baselines
The comparison results in terms of acceleration ratios on the unseen problem classes are shown in Table 17.
App. B.3Objective Values of MEGO+X and the Baselines
Table 18, 19, 20 compare the objective values of MEGO+X and baselines on the CA problem, the CIM problem, and the AS problem, respectively, with the budget of #FEs being 800.
App. CDetailed Experimental Results for Component Study
App. C.1Comparison with Other Expert Selection Strategies
We compare our proposed MEGO method with several alternative expert selection strategies. The methods included in the comparison are:
MAX: The maximum value among the optimal solutions obtained by all experts (The best-case scenario while select one expert).
MEGO: The best solution from the set of experts selected by the MEGO strategy.
SAMPLE: The best solution from a randomly sampled set of experts, where the sample size matches the number selected by MEGO. The reported result is the average over 10,000 independent sampling trials (Randomly select multiple experts).
MEAN: The mean value of the optimal solutions obtained by all experts (Randomly select only one expert).
MIN: The minimum value among the optimal solutions obtained by all experts (The worst-case scenario while select one expert).
The experimental settings are configured as follows. For MEGO and SAMPLE, 64 randomly sampled solutions are used for fine-tuning. Experts are selected based on similarity, with each selected expert generating 4 new solutions. On average, MEGO selects 14 experts. For MAX, MEAN, and MIN, 116 randomly sampled solutions are used for fine-tuning, with each expert also generating 4 new solutions.
All comparative results are presented in Table 21-26. For a robust evaluation, each method was executed for 30 independent runs on every problem instance. The table lists the mean and standard deviation of the performance across these runs. Furthermore, we conducted the Wilcoxon rank-sum test (at a \(0.05\) significance level) to statistically compare the results of MEGO against each of the other strategies per instance. The outcomes of these significance tests are annotated within the table.
App. C.2Performance Comparison in Source Space vs. Latent Space
We compare the performance of our proposed method when searching in two distinct spaces: the source problem solution space and a learned latent space. The two compared strategies are defined as follows:
Source Space: The MEGO method is applied to search directly in the source problem solution space, where 2,000,000 solutions are randomly sampled and evaluated.
Latent Space: The search is performed directly in the latent space of a pretrained VAE. Initially, 1,024 random latent points are sampled and decoded into solutions. The objective function is defined as min \(-y^\prime\), and gradient descent is run for 1,954 steps, resulting in a total of 2,000,896 solution evaluations.
All comparative results are summarized in Table 27-32. Each strategy was run independently 30 times per problem instance. The table reports the mean and standard deviation of the obtained performance. To assess statistical significance, the Wilcoxon rank-sum test (with a significance level of 0.05) was conducted between the results of the two strategies for each instance, and the outcomes are annotated accordingly in the table.
App. C.3Ablation Study on the Solution Mapping Process
We compare the performance of the MEGO framework under two configurations to assess the contribution of its core solution mapping process. The two compared settings are defined as follows:
Mapping: The standard MEGO procedure.
No Mapping: An ablated version where the fine-tuning and solution mapping steps are omitted. After experts are selected, new solutions are sampled directly in the source problem's solution space. These solutions are then truncated or zero-padded to match the target problem's dimension. The top- \(k\) solutions are selected, which are ranked by their performance on the expert models, are finally evaluated on the actual target problem instance.
All comparative results are presented in Table 34-36. Each configuration was executed for 30 independent runs on every problem instance. The table reports the mean and standard deviation of the performance. To determine statistical significance, the Wilcoxon rank-sum test (at a 0.05 significance level) was conducted between the results of the two configurations for each instance, and the outcomes are indicated within the table.
App. DFurther Discussion on Non-Arbitrary Regularities and an Additional Experiment on Arbitrary Random Binary Functions
App. D.1Non-Arbitrary Regularities Across Problem Classes
In the main text, we argue that transfer in MEGO is plausible because practical binary optimization problems often exhibit some coarse-grained reusable structure (regularities) in their solution-quality landscapes. Here we further elaborate on what such structure may look like in the present experiments.
First, variable importance is often highly heterogeneous: some binary decisions are much more influential than others. In generalized OM, the problem provides a clear bit-level signal, because matching certain positions of the hidden reference vector directly improves the objective value. In KP, different items have very different value/weight trade-offs, so their usefulness is far from uniform. In CA, compiler flags also differ greatly in impact: a small number of flags can be highly influential, while many others have weak or even harmful effects. In CIM and AS, different nodes or anchors likewise have very different marginal utilities. Thus, good solutions are typically not formed by treating all variables as equally important.
Second, the effect of one binary decision often depends strongly on the others, rather than being simply additive. In MC, whether selecting a vertex is useful depends on how it relates to the other selected and unselected vertices. In KP, whether an item is worth selecting depends not only on its own value, but also on the remaining budget after other items have been chosen. In CA, compiler flags often interact strongly, so the effect of enabling one flag depends on which others are enabled. In CIM, two seed nodes may either overlap heavily in influence or complement each other. In AS, two anchors may cover highly overlapping subsets of problems or provide complementary coverage. Therefore, the quality contribution of a single bit often cannot be understood in isolation.
Third, good solutions often correspond to selecting a limited compatible subset rather than turning on bits indiscriminately. This is explicit in KP, constrained MC, CIM, and AS, all of which involve size or budget constraints. Although CA has no explicit cardinality constraint, it empirically also exhibits the pattern that only a relatively small compatible subset of flags is useful, and indiscriminately enabling many flags does not continue to improve performance. In this sense, good solutions are sparse but coordinated subsets of decisions.
These regularities are more naturally described at the level of coarse structural tendencies in the solution-quality landscape, rather than as explicit recurring 0-1 patterns that can be directly interpreted. Accordingly, what MEGO appears to exploit is a transferable bias toward certain kinds of structured solution landscapes, such as non-uniform variable importance, interaction-sensitive decisions, and sparse but compatible decision subsets.
App. D.2Additional Experiment on Arbitrary Random Binary Functions
We additionally conducted an experiment in which the target problem instance is an arbitrary random binary function. For each binary solution, we convert its 0-1 string into a hash value using the BLAKE2b function, interpret the hash value as an integer random seed, initialize a pseudo-random number generator with this seed, and define the objective value as the first random number generated from it. Thus, each solution deterministically corresponds to one pseudo-random objective value, while nearby solutions need not bear any meaningful structural relation to each other. Note this experiment is not intended to model a practical application problem. Rather, it serves as a boundary-case test in which the target objective lacks reusable structure that can be shared with the available expert pool.
We compare MEGO with GA, HC, BO, and an additional RANDOM baseline. The RANDOM baseline samples candidate solutions uniformly at random. For a fair comparison, all methods are run with the same #FEs as MEGO. Each method is repeated for 30 independent runs, and the mean and standard deviation of the best objective values are reported.
As shown in Table 39, MEGO is not significantly better than GA, HC, or BO in this experiment, and is even significantly worse than RANDOM. This result is consistent with the interpretation in the main manuscript: when reusable structure is absent, transfer in MEGO is no longer meaningful and negative transfer may occur.