Content area
The one-dimensional bin packing problem (1DBPP) is a well-known NP-hard problem in computer science and operations research that involves many real-world applications. Its primary objective is to allocate items into bins while minimizing the number of bins used. Due to the complexity of the problem, exact algorithms are often impractical for large instances, which has led to a reliance on tailored heuristics that may perform well on some instances but poorly on others. In this study, we propose a method to automatically generate selection hyper-heuristics (HHs), which are then applied to solve 1DBPP instances by leveraging the strengths of simple heuristics while avoiding their drawbacks. Specifically, we introduce a steady-state
Introduction
The bin-packing problem (BPP) is a classical combinatorial optimization problem with diverse applications in supply chain management1, manufacturing2, aircraft arrangement3, among others. The goal of the problem is to find the minimum number () of bins, of a given capacity , to store a set of n items , each one of a size . Thus, the solution to the BPP is a partition . The BPP is present in many real-world situations, ranging from packing clothes in a suitcase before taking an airplane to loading the containers of a cargo ship or placing computer files of specified sizes into fixed-sized memory blocks. Consequently, producing high-quality solutions for this problem benefits many fields.
However, since the BPP is an NP-hard problem, finding exact solutions is impractical for many instances. Hence, it is common to rely on techniques that approximate its solution, such as heuristics 4, 5, 6, 7–8. Among the different algorithms, several greedy heuristics have been commonly utilized4,5. The simplest greedy heuristic is the Next-Fit (NF) algorithm, where an item i is directly placed in the current opened bin , if possible; otherwise, another bin is opened. On the other hand, the First-Fit (FF) heuristic places an item i in the first bin with enough capacity9. In addition to NF and FF, other heuristics have been proposed such as Best-Fit (BF)10, Worst-Fit (WF)11, and Almost-Worst-Fit (AWF)11. It is worth emphasizing that none of these approximation algorithms can achieve a performance ratio better than 3/2 unless 4.
Despite the good theoretical results of greedy heuristics11, Evolutionary Algorithms (EAs) have gained the attention of the community for tackling large BPP instances6,12. EAs are stochastic population-based metaheuristics (MHs) that efficiently explore and exploit the search space. Among EAs, Genetic Algorithms (GAs) have extensively been applied on the BPP 13, 14–15. The core of all the GA-based approaches is the definition of an encoding of the BPP. Then, a GA evolves a population of solutions to optimize a fitness value (e.g., the average bin usage). A common aspect of most EA-based approaches is that they meet the problem directly. In other words, they evolve partitions of I. However, EAs may suffer from sparse search spaces for large-scale BPP instances. Thus, their behavior may resemble a random search16.
Instead of using EAs directly to solve a BPP instance, they can be used to design a high-level solver that takes advantage of low-level heuristics. This high-level solver is a hyper-heuristic (HH) that serves as an alternative for tackling the complexity of the BPP and other combinatorial optimization problems7,17. An HH combines the strengths of low-level heuristics (e.g., FF, BF, WF, and AWF) using a set of rules that indicate which heuristic should be called depending on the problem state under exploration. In this regard, an EA should discover the best possible combination of rules to generate the so-called selection HHs in the space of heuristics. Regarding the BPP, GAs and Genetic Programming (GP) approaches have been extensively studied7,8,18, 19–20. Despite their promising results when tackling different BPP instances, a common drawback of all the EA-based approaches is the consumption of many function evaluations to find a good HH. As a result, EAs are time-consuming and exhibit a low convergence behavior when evolving populations of hundreds of HHs.
In this work, we focus on speeding up the convergence behavior of EAs to generate selection HHs for the one-dimensional BPP (1DBPP). To this aim, we propose a steady-state micro-GA (GA), extending the work by8. The underlying idea of using a GA21 as a search engine is due to using small populations and reinitialization strategies when nominal convergence is reached22. Hence, we can drastically reduce the number of function evaluations and the overall computational overhead. Furthermore, the selection of a steady-state approach is based on their proven theoretical advantages over generational EAs23. Under this light, a steady-state GA prevents stagnation and continuous reinitializations. Our approach leverages the combined qualities of both the steady-state approach and small-sized populations to produce high-quality HHs. As a result, two main contributions are derived from our work:
The proposal of a steady-state GA. All the previous works with GAs opted for generational schemes. We proposed replacing only one individual in the population per generation, which seems beneficial for the search as it improved the results obtained by the generational GA in this work.
A steady-state GA-based generative hyper-heuristic approach for producing selection hyper-heuristics that outperform those generated by other evolutionary methods in the literature for the 1DBPP (or similar problems), achieving superior performance in terms of average bin usage during the training stage, and competitive performance on unseen instances.
Foundations
The one-dimensional bin packing problem
1DBPP is a classic optimization problem in computer science where we aim to allocate n items of various sizes into the minimum number () of bins without exceeding their capacity 5. In the following, we formally define this problem. Let be a finite set of n items and and be two binary variables. On the one hand, if item is allocated in bin j; otherwise, . On the other hand, if bin is used; otherwise, it is zero. Each item has a size , where is the capacity of each bin j. Hence, 1DBPP is defined as follows:
1
subject to:2
3
It is worth emphasizing that the constraints of the problem force each item not to exceed the capacity of each bin (Eq. 2), and allocate each item into exactly one bin (Eq. 3).Note that this problem has some straightforward lower and upper bounds on the number of bins we can use. First, since bins can allocate at least a single item, the number of bins cannot exceed the number n of items. Second, the number of used bins cannot be less than the sum of the size of all the items divided by the bin capacity. Consequently, the optimal number of bins is bounded by the following inequality:
4
Given , an instance for the 1DBPP is a sequence , where is the current item to pack. In other words, is an n-permutation of I. An algorithm for the 1DBPP consumes in order from item until . Furthermore, let be a subsequence of starting from . indicates the sequence of items that remain to be processed by an iterative algorithm. From this point onwards, let us call as a problem state.Classic heuristics for the 1DBPP
Typically, heuristic approaches for the BPP are categorized into two types: online and offline4. Online approaches assume that items arrive in a specific sequence , and must be packed as soon as received. Even when some statistics about the set of items are known in advance, the order in which they arrive is unknown and cannot be altered. Conversely, offline approaches may assume that the ordering of the items in is either known in advance or can be rearranged before deciding which bin to pack. In this study, we will mainly focus on heuristic approaches for the online version of the problem. Some classical heuristics for the online 1DBPP are described as follows:
First Fit (FF) FF selects the first bin with enough capacity to pack the current item. The bins are revised following a FIFO strategy, where the first open bins are revised first9.
Best Fit (BF) BF selects the bin where packing the current item minimizes the waste10.
Worst Fit (WF) WF selects the bin where packing the current item maximizes the waste11.
Almost Worst Fit (AWF) AWF selects the bin where packing the current item produces the second largest waste11.
For clarity, we will briefly outline how these heuristics operate, using a small instance as an example. Let be a set of five items arriving at the order defined by the sequence . The sizes of each item are given by the set , where represents the size of item , and the bin capacity is . Let us also informally define a configuration of the system in our example as the tuple , where the subsequence in the tuple represents the remaining items to be processed. On the other hand, the second component represents the items in each bin that have already been packed (the empty brackets represent an empty bin, the underscript (u) represents the index of the bin, and the superscript (s) represents the contents of the bin). Using any heuristic H (denoted by ) over a configuration would yield the system to another configuration. Then, starting with empty bins, using FF repeatedly for each item arriving in the sequence given by , it would work like this:Similarly, using BF heuristic on the same example would work like this:Coincidentally, for this example, WF heuristic would have an identical behavior as FF, and AWF heuristic would have an identical behavior as BF.
Related work
The BPP is NP-hard, and its corresponding decision version is NP-Complete, which means that computing an optimal solution in a reasonable time is out of the reach of current algorithms5. This calls for alternative approaches that focus on producing near-optimal solutions in polynomial time. Many early heuristics developed for the BPP are frequently described as online approaches. In these methods, the order of arriving items is not known beforehand and cannot be altered. Despite this limitation, they were relatively effective. Notably, heuristics such as BF and FF were shown to produce solutions at most 1.7 times the optimal number of bins, rounded down26,27. The potential for improving these methods, plus their simplicity, led to efforts to integrate them with other strategies, including MHs and HHs.
In the following subsections, we will briefly review relevant approaches, with particular emphasis on those that harness the synergy between MHs, HHs, and classic heuristic methods.
Metaheuristic approaches
MHs are a family of stochastic algorithms designed to explore wide search spaces in optimization problems efficiently. Often considered general-purpose optimization methods due to their problem domain independence, MHs have been one of the most popular off-the-shelf algorithms for dealing with complex combinatorial optimization problems12, including 1DBPP.
Most MH implementations for the 1DBPP, as found in the literature, focus on the offline version of the problem6,28, where the arriving items are known in advance and can be rearranged before packing. In these cases, many MHs employ permutation-based encodings representing the order in which items should arrive or be processed. This sequence is then decoded using classic online heuristics, typically BF or FF.
Early MHs that utilized permutation-based item representations and heuristic decoding were mainly typical nature-inspired algorithms29,30.30, for instance, proposed a simple genetic algorithm to optimize the item sequence, with decoding performed by a bin-packing heuristic to minimize the number of bins used. Later, an ant colony optimization algorithm was adapted to solve instances of the BPP31. In this approach, ants build a tour among items, filling bins one at a time. The decision of each ant to move from one item to another is partly based on a variant of FF and the previous pheromone trails. The solution is represented as a sequence of items packed according to NF.15 proposed a biased random-keys GA for the two and three-dimensional BPP. Since a direct chromosome representation of bin packing would be too complex, they used an indirect representation where the chromosome encodes the order of items, their orientation, and a placement heuristic that is used to decode it into a solution. More recently, a survey of 1DBPP reviewed and compared swarm-based MHs, including the firefly algorithm, cuckoo search, and artificial bee colony, which utilize permutation-based item representations combined with classic heuristic decoding techniques28. Additionally, a modified squirrel search algorithm was introduced in32, incorporating a BF variation for the population initialization mechanism.
Other MHs for the 1DBPP employ a more direct representation, such as group-based representations for grouping problems (like the BPP). In these approaches, the correspondence between items and bins is explicitly encoded within the chromosome33. In other words, there is no need for an additional heuristic to reconstruct the solutions from their representations, whether at the end of the optimization process or during fitness evaluation. However, since these representations are pretty specific and the variation process might break some constraints, classic heuristics like FF are still often used during recombination operations or as a kind of repair mechanisms14,34.
Overall, these studies help to emphasize that classic heuristics, even within modern MHs, remain instrumental at various stages of the optimization process —whether initializing solutions, decoding permutation-based representations, assisting in crossover operations, or repairing infeasible solutions.
Hyper-heuristic approaches
HHs are high-level strategies designed to select, combine, or generate low-level heuristics to address computational search or optimization problems17. HHs are typically categorized into two main types: selection-based and generation-based approaches. In the context of the BPP and other related combinatorial problems, HHs frequently use traditional heuristics as a pool of low-level components and rely on mechanisms to guide their application. Many of these mechanisms have been optimized through genetic and evolutionary approaches.
The use of genetic programming as an HH was first introduced by18 to solve the BPP considering an online environment. Their approach was to evolve functions to assist the decision of whether or not to pack a current item in a current bin. Although their approach does not rely on existing packing heuristics, this work laid the foundations for subsequent research on HHs in this domain.
Pillay took a different approach by evolving disposable heuristics for the BPP in offline environments7. The evolved heuristics were sequences of low-level heuristics particular for every problem instance, hence disposable. They explored the evolution of both a sequence of bin selection heuristics and a sequence of tuples of item selection and bin selection heuristics. A similar approach for a scheduling problem was proposed by35. Both studies showcased the potential of these types of HHs to outperform low-level heuristics when applied in isolation.
Other HH approaches for the BPP operate on under a semi-online setting with full look-ahead information, that is, the item sequence remains fixed but full information about the items is available in advance. These approaches are often linked to the algorithm selection problem, where problem instances are mapped to heuristics. Once a heuristic is selected based on the instance, it is applied uniformly to all items in the sequence.36 presented a recurrent neural network with long-short term memory model that predicts heuristics without the need for feature extraction, relying instead on the temporal sequence of items in the instance. The same authors later extender their work incorporating recurrent neural network with generated recurrent units37. Recently, for the 3DBPP,38 proposed a set of online low-level heuristics with complementary performance across a diverse set of instances. Using supervised learning models (a neural network, a support vector machine and k-nearest neighbors), they trained these models to predict which online heuristic to apply given the instance features of a full look-ahead environment.
In another direction, for a problem closely related to the BPP (the 2D-regular Cutting Stock Problem),19 proposed a messy GA to generate selection HHs, which sequentially select classic low-level online heuristics based on partial information that characterizes the remaining sequence of items to be processed (but not a full look-ahead of the sequence of items). This approach evolves (trains) a set of conditionaction rules that function as the selection HH in a semi-online environment. The generated HHs operate as constructive methods, generating a solution step-by-step from scratch, often changing the heuristic applied at each step. At each step, the current problem configuration—determined by the characterization of the remaining items—is matched to the closest predefined condition, which triggers the corresponding action and updating the problem configuration. This approach was later extended for the two-dimensional BPP (2DBPP)20, the bi-objective 2DBPP39, and constraint satisfaction problems40. Most recently, inspired by these approaches,8 proposed using a GA to evolve selection HHs in the form of conditionaction rule sets for the 1DBPP. To manage the computational overhead of evaluating large populations of HHs, their approach focuses on evolving a smaller population with multiple restarts upon stagnation.
Steady-state µGA as a hyper-heuristic generator
Since the 1DBPP is an NP-hard combinatorial problem, we need to use heuristics to approximate its solution. However, due to the No-Free Lunch theorem, no single heuristic performs well in every 1DBPP instance41. Consequently, we need an automatic method that decides which heuristic is the best suited for a given 1DBPP instance. In this section, we propose a methodology to generate well-performing selection HHs for the 1DBPP. This methodology relies on utilizing a steady-state GA (SSGA) that gradually updates a population of selection HHs and replaces one individual every generation. SSGA explores the space of selection HHs to find one such HH with good generalization performance over different 1DBPP instances. In other words, our SSGA behaves as a generation HH. Furthermore, it is worth noting that SSGA represents an extension of the preliminary study by Ortiz-Bayliss et al.8.
The intuition behind using an SSGA as an optimization engine is to leverage the combined qualities of both the steady-state approach and small-sized populations (typically denoted by the symbol). On the one hand, steady-state GAs introduce gradual changes to the population, preserving diversity, whilst replacing only the most unfit individuals42. On the other hand, GAs operate with a small-sized population (typically five to ten individuals), allowing for faster iterations and less computational overhead43. Furthermore, the potential diversity and stagnation issues of having a small population are balanced out with a population reinitialization mechanism. Hence, our SSGA proposal weighs on the benefits of the GA part while the steady-state nature delays stagnation and reinitializations, allowing for promising populations to be exploited further. In the following sections, we describe two main aspects of SSGA: the encoding of each selection HH and the fitness assignment function. Then, we provide the complete description of SSGA to evolve selection HHs for the 1DBPP.
Representation of a selection hyper-heuristic
Each selection HH is represented as a finite set of conditionaction rules. For each rule, the condition is a point , where m is the number of features that characterize a problem state (remember that is a tuple that represents the remaining items to be processed). On the other hand, an action represents a heuristic in the set to pack item . In this article, we use a function to quantitatively represent the problem state. Consequently, a selection HH behaves as an automaton that packs item using an heuristic if is minimum, where represents the Euclidean distance, , and T is the number of rules that compose the given selection HH. It is worth emphasizing that the value of T may change from one selection HH to another.
Problem state features
Because we deal with the 1DBPP in this work, we can only represent a problem state using variations in the item length. Hence, given a problem state , we propose the following five straightforward features to represent it.
AVG The average length of the items within .
STD The standard deviation of the length of the items in .
SMALL The proportion of small items within . Items are considered small if they have a length that is less or equal to 15% of the bin’s original capacity.
MEDIUM The proportion of medium-length items within . Items are considered of medium length if they have a length that is larger than 15% but less or equal to 30% of the bin’s original capacity.
LARGE The proportion of large items within . Items are considered large if they have a length that is greater than 30% of the bin’s original capacity.
Chromosome encoding and decoding
In our proposal, each individual (i.e., a selection HH) is encoded by a variable-length binary string chromosome. The total length T of a chromosome is determined by its number of genes, with each gene encoding a single conditionaction rule (see Fig. 1). The minimum number of genes per chromosome is 1, and the maximum can be derived from the number of iterations of SSGA, the population size , and the crossover operator employed.
Each rule is encoded as a binary string of fixed length , where m is the number of features that characterize a problem state, k is the number of bits used to code the value of each feature, and . Under this approach, we can map unique values for each feature. When decoding the value of a feature, we can calculate its corresponding 10-base value aswhere if the bit is equal to 1, or , otherwise. In the case of the heuristics, decoding the corresponding string is straightforward since each unique string maps to a unique heuristic in . In our implementation, we use the five features () described in "Representation of a selection hyper-heuristic" section, each represented using ten bits (), and the four heuristics () described in Classic Heuristics for the 1DBPP" section represented using two bits. Consequently, each rule within the chromosome requires 52 bits for encoding.
Let us recall that each set of conditionaction rules, of each individual, acts as a selection constructive HH. The condition part of a rule corresponds to a problem state, defined by its feature values, while the action part specifies the heuristic to apply. Whenever an item arrives and is to be packed, the Euclidean distance between the current problem state and the condition in each rule is calculated. The condition closest to the problem state then triggers the corresponding heuristic. After applying the heuristic, the problem state is updated, and the process repeats until all the items have been packed.
[See PDF for image]
Fig. 1
An example of a chromosome encoding three conditionaction rules. Each rule contains three artificial features (, and , where i is the rule number) that characterize the problem state and four available heuristics to apply.
An encoding-decoding example
Let us use the chromosome depicted in Fig. 1 as a problem-independent example. Such a chromosome codes three conditionaction rules. The chromosome represents three features using four bits, then and . Besides, we can choose from the four different heuristics in , so , thus, we can use four 2-bit strings to code such heuristics.
For example, in Fig. 1, Rule 1 (R1) conditionaction is encoded as follows. The feature values of the condition part are f11 =
Moreover, let us recycle our example from "Classic heuristics for the 1DBPP" section, where arriving at the order defined by the sequence , whose sizes are given by the set , and the capacity of the bins is . In the beginning, the problem configuration would be described by , with all items left to pack, and all the bins empty. To define our problem state, let us choose three features from "Representation of a selection hyper-heuristic" section, AVG, STD, and LARGE. Then, the problem state of the current configuration would be described by the following tuple (0.6857, 0.2457, 0.8000).
At this point, we are in the position to illustrate how the selection HH encoded in Fig. 1 operates. From the initial problem state described by (0.6857, 0.2457, 0.8000), using Euclidean distance, the closest condition would be that of R3, which indicates us to trigger actionBF. Applying BF one time, would yield the following problem configuration , which in turn generates the following problem state (0.7142, 0.2672, 0.75). From the new current problem state, the closest condition would be again that of R3, triggering actionBF. Applying BF once again would yield , whose corresponding problem state is (0.7222, 0.2832, 0.6667). This process continues until no other items remain to be packed.
Fitness evaluation
The core idea of our proposal is that an SSGA evolves a population of selection HHs for the 1DBPP, where the best-performing ones must survive according to a fitness function. Since each selection HH is a general problem solver for the 1DBPP, the fitness function should numerically characterize how well this HH generalizes the problem. At the level of the solution to the 1DBPP, a single heuristic is to minimize the number of bins used, thus reducing the waste. Thus, the number of bins used may represent a suitable measure to estimate the performance of a single heuristic. However, if SSGA (which is a generator of selection HHs) uses the number of bins as a fitness function, this would lead to stagnation because many individuals are likely to have the same value13. Furthermore, SSGG should have a fitness value that indicates if the selection HHs have a good generalization behavior, i.e., a selection HH should have a good performance over different 1DBPP instances. In other words, given a training set, a selection HH is expected to have good fitness values that encompass the performance over all the instances in the training set. In consequence, we use the average bin usage (ABU) as both an indicator of HH performance and a fitness value for SSGA; similar to the fitness function used by18. The usage of a single bin is calculated as the sum of the lengths of the items contained in the bin divided by the bin’s capacity. Thus, the ABU is the average of the usage among all bins. The closer the ABU is to 1.0, the smaller the waste of space per bin, the fewer bins needed, and the better the solution. In this context, the ideal heuristic will always produce solutions that yield an ABU of 1.0. Note that ABU is a real number in [0, 1], thus, it provides a wider resolution than the bin usage, which is an integer number. Hence, this avoids stagnation of SSGA.
Workflow of the steady-state GA
Figure 2 shows the overall sequence of actions followed to produce and test a selection HH using SSGA. The process starts by creating a small random population of selection HHs represented by chromosomes. Each chromosome is randomly initialized with three to five coded conditionaction rules. Then, each chromosome is evaluated over all the training set instances to compute its ABU fitness value.
[See PDF for image]
Fig. 2
A graphical depiction of SSGA that searches for selection HHs to solve an instance of the 1DBPP.
Once the initial population is evaluated, we use tournament selection of size two and one-point crossover to produce a single offspring. Since our SSGA uses variable-length chromosomes, the crossover point is calculated on the parent with the smallest chromosome. Once the offspring is generated, it is evaluated and added to the population. Now that the population has one additional chromosome, we can remove the one with the smallest fitness evaluation. If we reach the maximum number of fitness function evaluations, the search stops, and the best individual from the last population is returned. If the stop criteria are not met, we check if the population is stagnated (there is little difference between the fitness of the selection HHs in the population). If this is the case, we keep the best chromosome and replace the remaining ones in the population with randomly generated chromosomes. Then, the process is repeated from the population evaluation. When the termination criterion is reached, the best selection HH in the last population is returned as the selection HH produced by the model. Finally, we solve the instances in the test set using the selection HH produced with SSGA.
Experimental setup, datasets and preliminary experimentation
This section describes the 1DBPP instances considered for this work, the experiments conducted, and their results and analysis. We implemented all the algorithms considered for this work using Java (SDK 11.0.24). The experiments (both preliminary and confirmatory) ran on a Linux-based machine (Linux Mint 21.2 Cinnamon) with 16 GB of RAM and Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz 4.
Problem instances (datasets)
In this article, we use three types of instances: (i) synthetically generated instances, (ii) well-known benchmark instances from the literature, and (iii) instances derived from real-world applications. The synthetic instances were generated using a modified implementation of the evolutionary-based method proposed by Plata et al.44. The benchmark instances were recovered from the work by Delorme et al.45, while the real-world instances were retrieved and adapted from Umetani et al. and Matsumoto et al.46,47. Since our proposed SSGA requires a training process, we required two separate sets of instances, one for training (evolving) the selection HHs, and another set for testing their performance.
Training instances: the synthetic instance generator
The instance generator used in this investigation is similar to the one proposed by Plata et al.44. It uses a GA to evolve the structure of 1DBPP instances, guided by a specific fitness function. The GA modifies the length of the items until it finds a configuration where the heuristics exhibit the desired behavior. Our GA requires three input elements: the number of items in the instance, the maximum length per item (), the bin capacity (C, which is the same for all the bins), and the fitness function (), which varies according to the heuristic to benefit/harm. The evolutionary process within the GA starts with a population of randomly initialized binary strings that we will refer to as chromosomes. Each chromosome encodes a 1DBPP instance of n items. Each item in the encoded instance uses bits. Therefore, gives the number of bits within the chromosome.
We proposed four categories of instances, one per heuristic in . We generated instances suitable for a particular heuristic using the method proposed by44. While44 originally designed their approach to generate Knapsack Problem instances, we adapted it to generate instances for the 1DBPP. Then, we have four categories of instances, and the category defines the heuristic that is the best choice. This strategy guarantees that each heuristic is the best performer in around 25% of the cases (its corresponding category). We generated 250 instances per category, totaling a thousand instances.
It is essential to highlight a critical difference between our training set and the one used for the GA proposed by8. In the former approach, instances were generated to be pathological for each heuristic. For each heuristic, several instances were generated to represent a challenge for that particular heuristic. Consequently, a selection HH could overcome the drawback of a particular heuristic simply by avoiding it. In contrast, in our work, a selection HH must correctly identify and select the most suitable heuristic for each instance, posing a more challenging scenario.
The instance generator used in this work and the instances generated are freely available at https://bit.ly/3RWEmx9. The instance generator was implemented in Java (SDK 11.0.24) using Apache Netbeans IDE 24.
Testing instances: synthetic and real-world instances
For testing, we employed three different sets of problem instances: Benchmark Testing Suite I (BTS-I), BTS-II, and BTS-III. In the following, we describe each test suite.
BTS-I It consists of an additional set of 1000 synthetic instances, generated in the same manner as the training set. Specifically, 250 instances were created for each category. We refer to this instance set simply as the test set.
BTS-II Includes six families of well-established instance sets from the literature (freely available by45 at https://site.unibo.it/operations-research/en/research/bpplib-a-bin-packing-problem-library), which are detailed as follows:
FalkenauerU33. This is a set of 80 instances with uniformly distributed item sizes, , and the bin capacity .
Scholl48. These are 1210 instances with uniformly distributed item sizes and . The instances are divided into three subsets (Scholl1, Scholl2 and Scholl3) of 720, 480, and 10 instances, respectively. The bin capacity is , , and for Scholl1, Scholl2, and Scholl3, respectively.
Wäscher49. These are 17 hard instances with and .
Hard2850. This is a set of 28 hard instances, with and .
Irnich51. This set is comprised of 240 instances with B either or , with uniformly distributed item sizes between and , and .
Augmented Non IRUP and Augmented IRUP52. These benchmarks correspond to two hard-to-solve sets (IRUP and non-IRUP) of 250 instances each. Each benchmark is divided into five subsets of 50 instances with and , respectively. That is, the first subset corresponds to 50 instances with and , and so on.
Tube47. This set consists of six instances derived from a real-world application in a paper tube manufacturing company in Japan. The instances feature a number of items n ranging from 780 to 1500, and tube stock lengths (bin capacity B) ranging from 1800 to 2100.
Fiber46. These instances originate from a real-world application in a chemical fiber company in Japan. The dataset includes 39 instances (the authors report using 40 instances in their paper, but only 39 could be retrieved from the Web), with the number of product types ranging from 6 to 29 and a demand per product type varying between 2 and 264 units. Stock roll lengths (the bin sizes B in our case) are either 9080 or 5180 units, while the lengths of the individual product types range from 500 to 2000 units.
Parameter settings
The running parameters of SSGA employed in our experiments are shown in Table 1. We decided to set the parameters for parent selection, crossover rate, and mutation rate to the values recommended on the original GA43. In addition, we set the offspring size and replacement to the values used in the original steady-state GA presented in42.
Table 1. Running parameters for SSGA.
Parameter | Value |
|---|---|
Selection scheme | |
Parent selection | Tournament of size 2 |
Crossover | One-point |
Crossover rate | 1 |
Mutation | N/A |
Mutation rate | N/A |
Offspring size () | 1 |
Replacement | 1 |
Population size () | 6 |
Evaluations | 1500 |
Other parameters such as population size and number of individual evaluations were determined through preliminary tests as presented in the following "Preliminary experiments" section.
Preliminary experiments
Our preliminary experiments aimed to explore the feasibility of the proposed approach: a SSGA to produce HHs for the 1DBPP. To do so, we explored three scenarios related to configuring and justifying our approach. We briefly describe the preliminary experiments as follows.
Effect of population size ("Preliminary experiments" section). We defined the population size through experimentation. Throughout this experiment, we produced 70 selection HHs using the proposed SSGA, ten for each population size (ranging from four to ten individuals).
Effect of the training set size ("Preliminary experiments" section). With this experiment, we estimated the effect on the performance of the resulting selection HHs when changing the number of instances used for training. We produced 30 selection HHs using the proposed approach, considering different training subsets (120, 400, and 1000 instances). We evaluated the performance of the selection HHs in both the complete training (1000 instances) and the test set from BTS-I.
Effect of extending the problem characterization ("Preliminary experiments" section). In this experiment, we focused on the benefit of extending the set of features that characterize the instances. Thus, we generated 20 selection HHs using the proposed SSGA; ten using AVG and STD as features and ten more considering AVG, STD, SMALL, MEDIUM, and LARGE, as described in "Representation of a Selection Hyper-Heuristic" section. We evaluated the performance of the selection HHs in both the training and test set from BTS-I.
The effect of population size
To determine an appropriate population size and number of evaluations, we conducted a preliminary experiment. We performed ten independent runs of the GA for each population size, ranging from four to ten individuals, over the training set and controlling for fitness function evaluations. In all cases, other parameters (i.e., selection, crossover, mutation) were set as outlined in Table 1.
[See PDF for image]
Fig. 3
The 50% empirical attainment functions of ABU, corresponding to the best individual per number of evaluations of ten independent runs of SSGA for various population sizes (four to ten).
Figure 3 shows the 50% EAFs among the ten independent runs for each configuration (population size). From this figure, we observe that no particular configuration outperforms the others. However, we can see that the configuration with six individuals strikes a good balance between population size and performance. Therefore, we will use this population size for the subsequent experiments in this section. Additionally, 1500 fitness function evaluations appear sufficient for any considered configuration to reach a point where further improvement is minimal. Based on this, we fixed the number of fitness function evaluations to 1500 for the remaining experiments.
The effect of the training set size
Now that we have empirically determined the parameters for SSGA, we experimented to evaluate the effect of the training size on the learning process of our solution model. Let us recall that we are using a nominally more challenging training set than the one used by8 for the reasons explained in Sect. 5.1. In this spirit, we divided the training set into three sizes: 120, 400, and 1000 instances. We evaluated their performance evolution in each case based on the ABU and the number of function evaluations in the training set. Fig. 4 presents the 50% EAFs derived from this experiment.
[See PDF for image]
Fig. 4
The 50% empirical attainment functions of ABU, corresponding to the best individual per number of evaluations of ten independent runs of SSGA for various training set sizes (120, 400, and 1000 instances). The dotted lines represent the median ABU obtained on the test set (BTS-I) for each case.
Based on the results presented in Fig. 4, we observe that the fewer instances used for training, the better the performance of the evolved selection HHs over the training set. Specifically, the selection HHs that evolved with 120 instances achieved a higher ABU than those with 400 and 1000 instances. However, their performances behave differently when evaluating these selection HHs over the 1000-instance generated test set (the BTS-I presented in "Problem instances (datasets)" section). The dotted lines in Fig. 4 show the performance of the resulting selection HHs on BTS-I. Contrary to the performance of the selection HHs over the training set, in the test set, the best results are obtained by the selection HHs evolved with larger training sets. In other words, the results indicate that selection HHs evolved using a larger training set tend to generalize better than their counterparts trained on smaller sets.
The effect of extending the problem characterization
In this experiment, we explored the impact of extending the set of features that characterize 1DBPP instances so that the selection HHs can map instances to heuristics in such a way that we can improve the search and the results obtained. For this reason, we generated ten independent selection HHs using the two features originally proposed by8 and another ten using the extended set of features proposed in this work. In all the cases, we used the configuration depicted in Table 1.
[See PDF for image]
Fig. 5
The 50% empirical attainment functions of ABU, corresponding to the best individual per number of evaluations of ten independent runs of SSGA for two sets of features to characterize the problem state (AVG, STD) and (AVG, STD, SMALL, MEDIUM, LARGE). The dotted lines represent the median ABU obtained on the test set (BTS-I) for each case.
The results shown in Fig. 5 showcase the 50% EAFs on the effect of extending the set of features that characterize the problem state. By considering the additional three features proposed in this work (SMALL, MEDIUM, and LARGE) the performance of the selection HHs increases significantly, both in the training, shown with the continuous line, and the test set (BTS-I), represented by the dotted line.
Comparison of evolutionary approaches for hyper-heuristic generation
In this section, we aimed to show the benefits of using the proposed SSGA in both the instances we artificially produced (BTS-I) and some others taken from the literature including real-world applications (BTS-II and BTS-III). The performance was measured in ABUs and the number of bins used, and compared against other evolutionary approaches for generating selection HHs for the 1DBPP in semi-online scenarios. For that, we conducted two main experiments as follows.
Performance analysis I: Performance comparison on training set ("Performance comparison on training set" section). In this experiment, we compared and contrasted the efficacy of different evolutionary frameworks in generating selection HHs for the 1DBPP. For this task, we produced 40 selection HHs using four evolutionary approaches: generational GA (GA), generational GA (GA)8, steady-state GA (SSGA)40, and our proposal, SSGA; that is, ten HHs per approach. We compared these approaches on both the instances of the training set and BTS-I.
Performance analysis II: Performance comparison on testing sets ("Performance comparison on testing sets" section). Aiming at estimating how well the selection HHs produced with each evolutionary framework generalize to unseen instances. We arbitrarily selected two selection HHs per approach from the previous experiment. We used them to solve the instances in BTS-I, BTS-II and BTS-III. For this experiment, we considered the ABU and the number of bins used.
Overview of comparative evolutionary approaches
State-of-the-art approaches for the 1DBPP vary depending on the problem-type scenario. The approaches designed for online and semi-online environments often do not perform as well compared to approaches designed for offline settings, where full instance information is available in advance, and items can be rearranged before processing. Consequently, a comparison between these approaches is not equitable. Similarly, comparisons among algorithms for the 1DBPP in semi-online environments characterized by full look-ahead information are not generally suitable for direct comparisons with algorithms for semi-online environments with partial look-ahead information. Thus, we compared and contrasted the efficacy of different evolutionary frameworks in generating selection HHs for the 1DBPP in semi-online scenarios with partial look-ahead item information.
We describe the models we used for comparison as follows.
GA This recent approach relies on a GA to produce selection HHs for the 1DBPP8. The parameters used in this approach consist of a population size of five chromosomes, a crossover rate of 1.0, and no mutation. The crossover operator takes two parents and produces two offspring (using one-point crossover). The offspring replace each generation, the whole population, but the best chromosome. When the standard deviation of the fitness among the chromosomes is below 0.001, we restart and randomly regenerate all the chromosomes in the population, but the best one.
GA Although we have no evidence that this model has been published before, it is simple to consider it a variation of the work by40. This time, the GA is generational, allowing for the replacement of the entire population. This type of algorithm requires a larger population, so we used 100 chromosomes in the population, and all of them are replaced each generation. We keep a record of the best chromosome found so far, so we do not lose it if it disappears from the population. The remaining parameters are similar to those used by40: tournament selection of size two, one-point crossover (takes two parents and produces two offspring), and mutation rate (flip mutation) of 1.0 and 0.1, respectively.
SSGA It consists of a steady-state GA with dynamic-length chromosomes that evolves selection HHs for constraint satisfaction problems40. This approach has not been applied to the 1DBPP, so we took the parameters as they appear in the corresponding publication: 25 chromosomes in the population, tournament selection of size two, replacement of only the two worst individuals in the population, one-point crossover (takes two parents and produces two offspring) and mutation rate (flip mutation) of 1.0 and 0.1, respectively. Their work used the number of generations, not the evaluations, as stopping criteria (250 generations, around 525 fitness function evaluations).
Performance comparison on training set
The intention with this experiment is to compare our SSGA against three other GAs (from "Overview of comparative evolutionary approaches" section), acting as generation HHs. For each generation framework, we conducted ten independent runs using the training set instances, and evaluate the fitness evolution throughout the training of the models.
[See PDF for image]
Fig. 6
The 50% empirical attainment functions of ABU, corresponding to GA, GA, SSGA, and SSGA. The dotted horizontal lines represent the median ABU obtained on the test set (BTS-I) for the resulting HH produced by each evolutionary framework. The dotted vertical line indicates the control point at which SSGA outperforms the other approaches.
The comparison results from the training are illustrated in Fig. 6. The continuous colored lines represent the 50% attainment functions of ABU over the training set throughout the evolutionary process for each framework (one for each color). At 1500 function evaluations, the median of the best HHs produced by our approach, SSGA, achieves the highest ABU compared to the median of the best HHs generated by other methods. Additionally, the vertical dotted line marks the point at 734 function evaluations, beyond which the ABU of the median of the best HHs produced by SSGA is never exceeded by corresponding HHs from other methods. In other words, there is a certain point at which SSGA yields higher-valued HHs with less number of function evaluations. Since a faster specialization on the train set may lead to reduced generalization, the horizontal dotted lines display the ABU values of the median of the best resulting HHs, when evaluated on the test set BTS-I. From this, we observe that SSGA not only converges faster but also produces HHs with the highest ABU on BTS-I, showcasing superior performance on unseen instances.
Performance comparison on testing sets
While the previous section focused on comparing the overall performance of all the generated selection HHs, in this section, we compare the performance of specific resulting selection HHs for solving 1DBPP instances. Two selection HHs were selected from those generated by each method—GA (HHGA and HHGA), GA (HHGA and HHGA), SSGA (HHSSGA and HHSSGA), and SSGA (HHSSGA and HHSSGA). The eight selected HHs were employed to solve instances from both benchmark suites: the generated testing set, BTS-I (with instances similar to the ones used for training), six classic families of datasets from the literature, BTS-II, and two datasets derived from real-world applications, BTS-III. The quality of the produced 1DBPP solutions determines the HH’s performance. The ABU and the number of bins used assess the quality of a solution. It is important to recall that ABU is the fitness function that guided the evolutionary process in all cases. In contrast, the number of bins used corresponds to the objective function of the 1DBPP. The overall results for each selection HH are presented in terms of mean performance, standard deviation, cumulative error relative to the best-performing low-level heuristic, the number of solutions that are worse than the best-performing low-level heuristic, the number of solutions matching the best-performing low-level heuristic, and the number of results surpassing the best-performing low-level heuristic across each problem instance per dataset.
Results on BTS-I
Table 2 shows the performance of each selection HH regarding ABU across the instances of BTS-I, while Table 3 shows the performance regarding the number of bins used on the same dataset. In both tables, the results are organized by dataset. The first rows present the results for instances favorable to FF, followed by those favorable to BF, and so on. The rows labeled “Overall” present the aggregated results of all the instances from the benchmark. Additionally, the first set of columns corresponds to the performance of the low-level heuristics, followed by the results of the selection HHs. Finally, the best results among selection HHs are highlighted by boldface characters, while underlined characters correspond to the second-best values—zeros are not highlighted.
One of the first things to note in both Tables 2 and 3 is that they share almost identical positions in the top rankings of the selection HHs. From these tables, we can observe that the best-performing selection HHs are HHGA, HHGA, HHGA, HHSSGA, HHSSGA, consistently obtaining the best and second-best results. Moreover, note that these selection HHs specialize in one or two datasets. Specifically, observe that HHGA and HHGA have specialized in FF-type of instances. HHGA shows specialization in both BF- and AWF-type instances, while HHSSGA in BF- and FF-type instances. Finally, HHSSGA is the only selection HH among the eight to show WF-type instances specialization. These results show that they all show competitive performances, with HHGA perhaps showing some of the best results. However, note that in the Overall dataset, both selection HHs produced from our approach, HHSSGA and HHSSGA, share the top results among the mean and cumulative error performance values.
Table 2. Average Bin Usage (ABU) obtained by the heuristics and a few selected HHs on the test set (BTS-I).
Dataset | Stat | FF | BF | WF | AWF | HHGA | HHGA | HHGA | HHGA | HHSSGA | HHSSGA | HHSSGA | HHSSGA |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
FF-type | Mean | 0.9874 | 0.8775 | 0.8168 | 0.8759 | 0.9683 | 0.9566 | 0.9723 | 0.8802 | 0.9453 | 0.9516 | 0.9529 | 0.9497 |
Stddev | 0.0116 | 0.0287 | 0.0315 | 0.0293 | 0.0374 | 0.0473 | 0.0337 | 0.0293 | 0.0498 | 0.0482 | 0.0464 | 0.0489 | |
Error | 0.0000 | 27.4620 | 42.6526 | 27.8776 | 4.7669 | 7.6888 | 3.7651 | 26.7870 | 10.5237 | 8.9574 | 8.6136 | 9.4253 | |
Worse | 0 | 250 | 250 | 250 | 61 | 88 | 49 | 250 | 122 | 104 | 109 | 107 | |
Equal | 250 | 0 | 0 | 0 | 171 | 152 | 188 | 0 | 118 | 138 | 127 | 131 | |
Better | 0 | 0 | 0 | 0 | 18 | 10 | 13 | 0 | 10 | 8 | 14 | 12 | |
BF-type | Mean | 0.8234 | 0.9877 | 0.7728 | 0.8178 | 0.9147 | 0.9178 | 0.9100 | 0.9524 | 0.9403 | 0.9307 | 0.9283 | 0.9438 |
Stddev | 0.0244 | 0.0124 | 0.0331 | 0.0244 | 0.0531 | 0.0493 | 0.0499 | 0.0480 | 0.0446 | 0.0466 | 0.0489 | 0.0509 | |
Error | 41.0890 | 0.0000 | 53.7352 | 42.4705 | 18.2589 | 17.4819 | 19.4356 | 8.8204 | 11.8459 | 14.2620 | 14.8584 | 10.9902 | |
Worse | 250 | 0 | 250 | 250 | 191 | 197 | 207 | 106 | 151 | 171 | 175 | 128 | |
Equal | 0 | 250 | 0 | 0 | 56 | 53 | 41 | 144 | 99 | 77 | 74 | 119 | |
Better | 0 | 0 | 0 | 0 | 3 | 0 | 2 | 0 | 0 | 2 | 1 | 3 | |
WF-type | Mean | 0.8574 | 0.8576 | 0.9808 | 0.8561 | 0.8576 | 0.8576 | 0.8576 | 0.8579 | 0.8576 | 0.8576 | 0.8813 | 0.8576 |
Stddev | 0.0256 | 0.0255 | 0.0169 | 0.0255 | 0.0255 | 0.0255 | 0.0255 | 0.0255 | 0.0255 | 0.0255 | 0.0333 | 0.0255 | |
Error | 30.8521 | 30.8121 | 0.0000 | 31.1769 | 30.8198 | 30.8129 | 30.8199 | 30.7217 | 30.8117 | 30.8121 | 24.8791 | 30.8153 | |
Worse | 250 | 250 | 0 | 250 | 250 | 250 | 250 | 250 | 250 | 250 | 249 | 250 | |
Equal | 0 | 0 | 250 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |
AWF-type | Mean | 0.8873 | 0.8876 | 0.8277 | 0.9823 | 0.8876 | 0.8876 | 0.8875 | 0.9397 | 0.8876 | 0.8876 | 0.8844 | 0.8876 |
Stddev | 0.0289 | 0.0288 | 0.0321 | 0.0141 | 0.0288 | 0.0289 | 0.0288 | 0.0506 | 0.0288 | 0.0288 | 0.0294 | 0.0288 | |
Error | 23.7667 | 23.6763 | 38.6547 | 0.0000 | 23.6913 | 23.6756 | 23.6933 | 10.6681 | 23.6882 | 23.6881 | 24.4796 | 23.6873 | |
Worse | 250 | 250 | 250 | 0 | 250 | 250 | 250 | 121 | 250 | 250 | 250 | 250 | |
Equal | 0 | 0 | 0 | 250 | 0 | 0 | 0 | 109 | 0 | 0 | 0 | 0 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 20 | 0 | 0 | 0 | 0 | |
Overall | Mean | 0.8889 | 0.9026 | 0.8495 | 0.8830 | 0.9070 | 0.9049 | 0.9069 | 0.9076 | 0.9077 | 0.9068 | 0.9117 | 0.9097 |
Stddev | 0.0656 | 0.0561 | 0.0838 | 0.0656 | 0.0555 | 0.0537 | 0.0552 | 0.0561 | 0.0532 | 0.0532 | 0.0504 | 0.0557 | |
Error | 95.7078 | 81.9504 | 135.0425 | 101.5250 | 77.5369 | 79.6592 | 77.7139 | 76.9972 | 76.8695 | 77.7196 | 72.8307 | 74.9181 | |
Worse | 750 | 750 | 750 | 750 | 752 | 785 | 756 | 727 | 773 | 775 | 783 | 735 | |
Equal | 250 | 250 | 250 | 250 | 227 | 205 | 229 | 253 | 217 | 215 | 201 | 250 | |
Better | 0 | 0 | 0 | 0 | 21 | 10 | 15 | 20 | 10 | 10 | 16 | 15 |
Table 3. Number of bins used by the heuristics and a few selected HHs on the test set (BTS-I).
Dataset | Stat | FF | BF | WF | AWF | HHGA | HHGA | HHGA | HHGA | HHSSGA | HHSSGA | HHSSGA | HHSSGA |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
FF-type | Mean | 22.53 | 24.04 | 24.90 | 24.05 | 22.80 | 22.97 | 22.73 | 23.99 | 23.12 | 23.04 | 23.02 | 23.06 |
Stddev | 2.07 | 2.40 | 2.38 | 2.42 | 2.18 | 2.38 | 2.11 | 2.39 | 2.41 | 2.39 | 2.27 | 2.34 | |
Error | 0 | 378 | 594 | 380 | 67 | 110 | 51 | 366 | 148 | 127 | 122 | 133 | |
Worse | 0 | 250 | 250 | 250 | 59 | 86 | 47 | 249 | 117 | 102 | 100 | 105 | |
Equal | 250 | 0 | 0 | 0 | 191 | 164 | 203 | 1 | 133 | 148 | 150 | 145 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
BF-type | Mean | 24.58 | 22.26 | 25.32 | 24.61 | 23.27 | 23.22 | 23.35 | 22.76 | 22.93 | 23.05 | 23.09 | 22.88 |
Stddev | 3.47 | 3.16 | 3.63 | 3.49 | 3.29 | 3.19 | 3.31 | 3.26 | 3.23 | 3.20 | 3.24 | 3.28 | |
Error | 581 | 0 | 765 | 588 | 252 | 240 | 272 | 124 | 168 | 198 | 207 | 156 | |
Worse | 250 | 0 | 250 | 250 | 187 | 191 | 202 | 101 | 147 | 168 | 172 | 124 | |
Eequal | 0 | 250 | 0 | 0 | 63 | 59 | 48 | 149 | 103 | 82 | 78 | 126 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
WF-type | Mean | 28.16 | 28.16 | 26.19 | 28.16 | 28.16 | 28.16 | 28.16 | 28.15 | 28.16 | 28.16 | 27.73 | 28.16 |
Stddev | 2.40 | 2.40 | 2.21 | 2.40 | 2.40 | 2.40 | 2.40 | 2.40 | 2.40 | 2.40 | 2.36 | 2.40 | |
Error | 492 | 492 | 0 | 493 | 492 | 492 | 492 | 490 | 492 | 492 | 385 | 492 | |
Worse | 250 | 250 | 0 | 250 | 250 | 250 | 250 | 250 | 250 | 250 | 248 | 250 | |
Equal | 0 | 0 | 250 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
AWF-type | Mean | 24.50 | 24.50 | 25.40 | 23.19 | 24.50 | 24.50 | 24.50 | 23.78 | 24.50 | 24.50 | 24.55 | 24.50 |
Stddev | 2.34 | 2.34 | 2.42 | 2.07 | 2.34 | 2.34 | 2.34 | 2.27 | 2.34 | 2.34 | 2.32 | 2.34 | |
Error | 328 | 327 | 552 | 0 | 327 | 327 | 327 | 149 | 327 | 327 | 340 | 327 | |
Worse | 250 | 250 | 250 | 0 | 250 | 250 | 250 | 117 | 250 | 250 | 250 | 250 | |
Equal | 0 | 0 | 0 | 250 | 0 | 0 | 0 | 133 | 0 | 0 | 0 | 0 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Overall | Mean | 24.94 | 24.74 | 25.45 | 25.00 | 24.68 | 24.71 | 24.68 | 24.67 | 24.68 | 24.69 | 24.60 | 24.65 |
Stddev | 3.32 | 3.37 | 2.75 | 3.25 | 3.33 | 3.32 | 3.33 | 3.32 | 3.36 | 3.34 | 3.21 | 3.37 | |
Error | 1401 | 1197 | 1911 | 1461 | 1138 | 1169 | 1142 | 1129 | 1135 | 1144 | 1054 | 1108 | |
Worse | 750 | 750 | 750 | 750 | 746 | 777 | 749 | 717 | 764 | 770 | 770 | 729 | |
Equal | 250 | 250 | 250 | 250 | 254 | 223 | 251 | 283 | 236 | 230 | 230 | 271 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
The one-sided Wilcoxon rank-sum tests presented in Supplementary Table SI-3 and Supplementary Table SI-4, conducted on the results shown in Tables 2 and 3, support many of the previous observations. Both HHGA and HHGA achieved statistically better ABU values (p < 0.05) than all other HHs on the FF-type test subset. In contrast, HHGA showed statistically worse ABU values compared to all other HHs on this subset. Interestingly, HHGA was also the only method to achieve statistically better ABU values across all others on the BF-type test subset. For the WF-type, AWF-type, and overall test subsets, the best-performing methods in terms of ABU were HHSSGA, HHGA, and HHSSGA, respectively. In terms of the number of bins used, only HHGA and HHGA showed statistically significant improvements, specifically on the WF-type and AWF-type subsets, respectively.
Results on BTS-II
Table 4 and Table 5 present the results of the selection HHs, on 1DBPP instances from the literature (BTS-II), reported in terms of bin usage and number of bins used, respectively. Similar to the previous tables, the best results are highlighted using boldface characters, and the second-best results are identified by characters with an underlined format.
From Table 4 we can observe that among the top performing selection HHs are HHGA, HHSSGA, HHSSGA and HHSSGA, as they show one or more top values in at least six of the nine benchmark subsets. Interestingly, one of the best-performing HHs on BTS-I, HHGA, is missing from this list—although if we only consider the last four benchmarks (Hard28, Irnich, IRUP and nonIRUP), it stands out as one of the best performing HHs. Conversely, HHSSGA was not among the top-performing selection HHs on BTS-I, but it is now on BTS-II. One reason for that might be that, based on the results on BTS-I, HHGA showed an over-specialization on BF-type (and AWF-type) of instances along with an inefficiency for FF-type of instances, whereas HHSSGA showed a balance of preference between BF-type of problems and FF-type of problems, which are both common between instances from the BTS-II datasets. Also, in a case-by-case analysis from this table, we observe that HHGA is a top performer on the Wäscher dataset, HHGA on FalkenauerU dataset, HHGA on Hard28, IRUP and nonIRUP datasets, HHSSGA had some of the best results on Scholl02, Irnich, IRUP and nonIRUP datasets, HHSSGA showed top results on Scholl01 and Hard28 datasets, and HHSSGA presented the best values on FalkenauerU, Scholl01 and Hard28 datasets. Overall, we can see that both HHSSGA and HHSSGA were the most consistent top performers among all selection HHs. Remarkably, although HHSSGA is consistently among the worst-performing methods in terms of mean ABU values and error, it was consistently among the top two results in producing better results than the low-level heuristics. Overall, HHSSGA produced 49 solutions that have a better ABU value than the best-performing low-level heuristic.
From Table 5, we observe that the results are very similar among the methods. This was somewhat expected since the count of bins does not usually produce a lot of variance among methods. Nonetheless, we can see that HHSSGA is consistently among the best-performing methods overall. Furthermore, despite being among the worst-performing selection HHs overall, HHSSGA still found three solutions with a smaller number of bins than the best low-level heuristic.
Table 4. Average Bin Usage (ABU) obtained by the heuristics and a few selected HHs on the literature testing set (BTS-II).
Dataset | Stat | FF | BF | WF | AWF | HHGA | HHGA | HHGA | HHGA | HHSSGA | HHSSGA | HHSSGA | HHSSGA |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
FalkenauerU | Mean | 0.8866 | 0.8951 | 0.7594 | 0.8486 | 0.8949 | 0.8951 | 0.8951 | 0.8948 | 0.8950 | 0.8951 | 0.8548 | 0.8951 |
Stddev | 0.0210 | 0.0204 | 0.0253 | 0.0185 | 0.0205 | 0.0204 | 0.0204 | 0.0204 | 0.0204 | 0.0204 | 0.0603 | 0.0204 | |
Error | 0.7786 | 0.1046 | 10.9561 | 3.8191 | 0.1191 | 0.1058 | 0.1063 | 0.1263 | 0.1062 | 0.1059 | 3.3612 | 0.1055 | |
Worse | 65 | 14 | 80 | 80 | 20 | 15 | 17 | 21 | 16 | 16 | 71 | 15 | |
Equal | 15 | 66 | 0 | 0 | 58 | 65 | 62 | 58 | 64 | 64 | 3 | 65 | |
Better | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 1 | 0 | 0 | 6 | 0 | |
Scholl01 | Mean | 0.8115 | 0.8276 | 0.7092 | 0.7812 | 0.8271 | 0.8273 | 0.8274 | 0.8274 | 0.8275 | 0.8275 | 0.7623 | 0.8276 |
Stddev | 0.0660 | 0.0654 | 0.0486 | 0.0548 | 0.0650 | 0.0652 | 0.0653 | 0.0653 | 0.0653 | 0.0653 | 0.0883 | 0.0654 | |
Error | 11.8965 | 0.3705 | 85.5878 | 33.7754 | 0.6871 | 0.5429 | 0.4582 | 0.4565 | 0.4245 | 0.3752 | 47.3314 | 0.3706 | |
Worse | 676 | 44 | 719 | 710 | 97 | 93 | 54 | 53 | 52 | 46 | 658 | 45 | |
Equal | 44 | 676 | 1 | 10 | 617 | 626 | 666 | 666 | 668 | 674 | 57 | 675 | |
Better | 0 | 0 | 0 | 0 | 6 | 1 | 0 | 1 | 0 | 0 | 5 | 0 | |
Scholl02 | Mean | 0.8877 | 0.8898 | 0.8404 | 0.8817 | 0.8892 | 0.8892 | 0.8892 | 0.8875 | 0.8893 | 0.8892 | 0.8803 | 0.8892 |
Stddev | 0.0507 | 0.0508 | 0.0542 | 0.0499 | 0.0503 | 0.0503 | 0.0503 | 0.0485 | 0.0503 | 0.0503 | 0.0614 | 0.0503 | |
Error | 1.1100 | 0.1259 | 23.8095 | 3.9988 | 0.4066 | 0.3923 | 0.4029 | 1.2083 | 0.3719 | 0.3948 | 4.7693 | 0.3888 | |
Worse | 209 | 77 | 430 | 281 | 122 | 136 | 136 | 153 | 125 | 136 | 185 | 132 | |
Equal | 271 | 403 | 50 | 199 | 356 | 343 | 344 | 321 | 355 | 344 | 285 | 348 | |
Better | 0 | 0 | 0 | 0 | 2 | 1 | 0 | 6 | 0 | 0 | 10 | 0 | |
Scholl03 | Mean | 0.7975 | 0.7975 | 0.7939 | 0.7970 | 0.7975 | 0.7975 | 0.7975 | 0.7975 | 0.7975 | 0.7975 | 0.7975 | 0.7975 |
Stddev | 0.0120 | 0.0120 | 0.0109 | 0.0114 | 0.0120 | 0.0120 | 0.0120 | 0.0120 | 0.0120 | 0.0120 | 0.0120 | 0.0120 | |
Error | 0.0022 | 0.0022 | 0.0385 | 0.0076 | 0.0022 | 0.0022 | 0.0022 | 0.0022 | 0.0022 | 0.0022 | 0.0022 | 0.0022 | |
Worse | 5 | 5 | 7 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |
Equal | 5 | 5 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Waescher | Mean | 0.9093 | 0.9067 | 0.8507 | 0.9006 | 0.9089 | 0.9059 | 0.9060 | 0.9057 | 0.9067 | 0.9059 | 0.9067 | 0.9060 |
Stddev | 0.0178 | 0.0208 | 0.0494 | 0.0217 | 0.0175 | 0.0205 | 0.0205 | 0.0208 | 0.0209 | 0.0204 | 0.0208 | 0.0205 | |
Error | 0.0134 | 0.0570 | 1.0089 | 0.1603 | 0.0188 | 0.0707 | 0.0695 | 0.0737 | 0.0587 | 0.0702 | 0.0579 | 0.0695 | |
Worse | 6 | 1 | 17 | 14 | 4 | 5 | 5 | 8 | 4 | 6 | 3 | 5 | |
Equal | 11 | 16 | 0 | 3 | 13 | 12 | 11 | 9 | 12 | 11 | 13 | 12 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
Hard28 | Mean | 0.8679 | 0.8887 | 0.7016 | 0.8049 | 0.8885 | 0.8884 | 0.8886 | 0.8887 | 0.8886 | 0.8887 | 0.8587 | 0.8887 |
Stddev | 0.0315 | 0.0297 | 0.0256 | 0.0246 | 0.0298 | 0.0300 | 0.0298 | 0.0297 | 0.0298 | 0.0297 | 0.0319 | 0.0297 | |
Error | 0.6061 | 0.0237 | 5.2603 | 2.3689 | 0.0287 | 0.0320 | 0.0263 | 0.0240 | 0.0260 | 0.0237 | 0.8632 | 0.0237 | |
Worse | 25 | 3 | 28 | 28 | 12 | 14 | 12 | 4 | 10 | 3 | 28 | 3 | |
Equal | 3 | 25 | 0 | 0 | 15 | 14 | 16 | 24 | 18 | 25 | 0 | 25 | |
Better | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Irnich | Mean | 0.9263 | 0.9326 | 0.7570 | 0.8535 | 0.9325 | 0.9326 | 0.9326 | 0.9326 | 0.9326 | 0.9326 | 0.9134 | 0.9326 |
Stddev | 0.0287 | 0.0292 | 0.0222 | 0.0141 | 0.0291 | 0.0292 | 0.0292 | 0.0292 | 0.0292 | 0.0292 | 0.0643 | 0.0292 | |
Error | 1.5214 | 0.0000 | 42.1449 | 18.9898 | 0.0377 | 0.0051 | 0.0038 | 0.0150 | 0.0031 | 0.0053 | 4.6298 | 0.0048 | |
Worse | 239 | 0 | 240 | 240 | 43 | 23 | 24 | 24 | 20 | 20 | 165 | 16 | |
Equal | 1 | 240 | 0 | 0 | 192 | 216 | 214 | 216 | 219 | 216 | 71 | 221 | |
Better | 0 | 0 | 0 | 0 | 5 | 1 | 2 | 0 | 1 | 4 | 4 | 3 | |
IRUP | Mean | 0.9387 | 0.9590 | 0.7573 | 0.8465 | 0.9400 | 0.9389 | 0.9588 | 0.9588 | 0.9588 | 0.9510 | 0.9584 | 0.9556 |
Stddev | 0.0148 | 0.0153 | 0.0144 | 0.0090 | 0.0157 | 0.0148 | 0.0153 | 0.0152 | 0.0155 | 0.0149 | 0.0157 | 0.0178 | |
Error | 5.0781 | 0.0000 | 50.4265 | 28.1368 | 4.7399 | 5.0209 | 0.0519 | 0.0397 | 0.0941 | 2.0430 | 0.1500 | 0.8502 | |
Worse | 250 | 0 | 250 | 250 | 250 | 250 | 126 | 38 | 55 | 212 | 154 | 147 | |
Equal | 0 | 250 | 0 | 0 | 0 | 0 | 114 | 212 | 160 | 34 | 78 | 100 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 0 | 35 | 4 | 18 | 3 | |
nonIRUP | Mean | 0.9309 | 0.9503 | 0.7523 | 0.8406 | 0.9368 | 0.9318 | 0.9500 | 0.9502 | 0.9501 | 0.9479 | 0.9501 | 0.9488 |
Stddev | 0.0176 | 0.0132 | 0.0215 | 0.0124 | 0.0186 | 0.0174 | 0.0133 | 0.0132 | 0.0132 | 0.0151 | 0.0132 | 0.0145 | |
Error | 4.8406 | 0.0000 | 49.4970 | 27.4095 | 3.3778 | 4.6076 | 0.0625 | 0.0128 | 0.0301 | 0.6022 | 0.0503 | 0.3702 | |
Worse | 250 | 0 | 250 | 250 | 242 | 250 | 93 | 13 | 27 | 186 | 120 | 144 | |
Equal | 0 | 250 | 0 | 0 | 1 | 0 | 157 | 233 | 220 | 54 | 125 | 105 | |
Better | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 4 | 3 | 10 | 5 | 1 |
Table 5. Number of bins used by the heuristics and a few selected HHs on the literature testing set (BTS-II).
Dataset | Stat | FF | BF | WF | AWF | HHGA | HHGA | HHGA | HHGA | HHSSGA | HHSSGA | HHSSGA | HHSSGA |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
FalkenauerU | Mean | 198.44 | 197.64 | 215.47 | 203.49 | 197.64 | 197.64 | 197.64 | 197.68 | 197.64 | 197.64 | 200.82 | 197.64 |
Stddev | 141.78 | 141.41 | 154.54 | 146.05 | 141.38 | 141.41 | 141.41 | 141.43 | 141.41 | 141.41 | 141.62 | 141.41 | |
Error | 70 | 6 | 1433 | 474 | 7 | 6 | 6 | 9 | 6 | 6 | 262 | 6 | |
Worse | 49 | 6 | 80 | 76 | 7 | 6 | 6 | 9 | 6 | 6 | 63 | 6 | |
Equal | 31 | 74 | 0 | 4 | 72 | 74 | 74 | 71 | 74 | 74 | 16 | 74 | |
Better | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |
Scholl01 | Mean | 115.35 | 114.29 | 123.87 | 118.07 | 114.31 | 114.30 | 114.30 | 114.30 | 114.30 | 114.29 | 119.55 | 114.29 |
Stddev | 99.16 | 98.31 | 106.69 | 102.11 | 98.30 | 98.30 | 98.31 | 98.31 | 98.31 | 98.31 | 103.58 | 98.31 | |
Error | 770 | 8 | 6902 | 2724 | 17 | 13 | 11 | 11 | 10 | 8 | 3795 | 8 | |
Worse | 450 | 8 | 713 | 579 | 17 | 13 | 11 | 11 | 10 | 8 | 631 | 8 | |
Equal | 270 | 712 | 7 | 141 | 703 | 707 | 709 | 709 | 710 | 712 | 89 | 712 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Scholl02 | Mean | 44.15 | 44.08 | 45.58 | 44.39 | 44.09 | 44.09 | 44.09 | 44.14 | 44.09 | 44.09 | 44.56 | 44.09 |
Stddev | 43.89 | 43.81 | 45.84 | 44.32 | 43.81 | 43.81 | 43.81 | 43.85 | 43.81 | 43.81 | 44.83 | 43.81 | |
Error | 34 | 3 | 724 | 151 | 9 | 8 | 8 | 30 | 8 | 8 | 236 | 8 | |
Worse | 32 | 3 | 273 | 89 | 9 | 8 | 8 | 28 | 8 | 8 | 84 | 8 | |
Equal | 448 | 477 | 207 | 391 | 471 | 472 | 472 | 452 | 472 | 472 | 394 | 472 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | |
Scholl03 | Mean | 61.90 | 61.90 | 62.00 | 61.90 | 61.90 | 61.90 | 61.90 | 61.90 | 61.90 | 61.90 | 61.90 | 61.90 |
Stddev | 0.32 | 0.32 | 0.47 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | |
Error | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Worse | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Equal | 10 | 10 | 9 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Waescher | Mean | 18.41 | 18.47 | 19.00 | 18.53 | 18.41 | 18.47 | 18.47 | 18.47 | 18.47 | 18.47 | 18.47 | 18.47 |
Stddev | 5.61 | 5.69 | 6.23 | 5.76 | 5.61 | 5.69 | 5.69 | 5.69 | 5.69 | 5.69 | 5.69 | 5.69 | |
Error | 0 | 1 | 10 | 2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
Worse | 0 | 1 | 7 | 2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
Equal | 17 | 16 | 10 | 15 | 17 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Hard28 | Mean | 75.93 | 75.00 | 84.32 | 78.61 | 75.00 | 75.00 | 75.00 | 75.00 | 75.00 | 75.00 | 76.39 | 75.00 |
Stddev | 8.15 | 7.93 | 8.37 | 8.39 | 7.93 | 7.93 | 7.93 | 7.93 | 7.93 | 7.93 | 8.53 | 7.93 | |
Error | 27 | 1 | 262 | 102 | 1 | 1 | 1 | 1 | 1 | 1 | 40 | 1 | |
Worse | 21 | 1 | 28 | 28 | 1 | 1 | 1 | 1 | 1 | 1 | 22 | 1 | |
Equal | 7 | 27 | 0 | 0 | 27 | 27 | 27 | 27 | 27 | 27 | 6 | 27 | |
Better | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Irnich | Mean | 1188.29 | 1184.42 | 1316.67 | 1237.65 | 1184.48 | 1184.42 | 1184.42 | 1184.45 | 1184.42 | 1184.42 | 1194.86 | 1184.42 |
Stddev | 634.06 | 632.33 | 697.34 | 657.97 | 632.32 | 632.34 | 632.34 | 632.33 | 632.34 | 632.33 | 630.14 | 632.33 | |
Error | 930 | 0 | 31741 | 12776 | 15 | 2 | 1 | 7 | 1 | 2 | 2507 | 2 | |
Worse | 231 | 0 | 240 | 240 | 13 | 2 | 1 | 7 | 1 | 2 | 140 | 2 | |
Equal | 9 | 240 | 0 | 0 | 227 | 237 | 238 | 233 | 238 | 236 | 99 | 236 | |
Better | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 2 | 1 | 2 | |
IRUP | Mean | 204.78 | 202.74 | 227.64 | 215.68 | 204.61 | 204.78 | 202.74 | 202.75 | 202.75 | 203.52 | 202.76 | 203.01 |
Stddev | 96.75 | 96.27 | 107.11 | 102.24 | 96.52 | 96.75 | 96.27 | 96.27 | 96.26 | 96.32 | 96.25 | 96.29 | |
Error | 511 | 0 | 6225 | 3236 | 469 | 511 | 1 | 4 | 4 | 199 | 5 | 69 | |
Worse | 236 | 0 | 250 | 250 | 228 | 236 | 1 | 4 | 4 | 136 | 5 | 62 | |
Equal | 14 | 250 | 0 | 0 | 22 | 14 | 249 | 246 | 245 | 112 | 245 | 188 | |
Bbetter | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | |
nonIRUP | Mean | 205.67 | 203.92 | 228.04 | 216.35 | 204.91 | 205.64 | 203.92 | 203.92 | 203.92 | 204.00 | 203.92 | 203.96 |
Stddev | 97.17 | 96.55 | 107.13 | 102.51 | 96.41 | 97.18 | 96.55 | 96.55 | 96.55 | 96.46 | 96.55 | 96.50 | |
Error | 439 | 0 | 6031 | 3109 | 251 | 432 | 0 | 0 | 0 | 21 | 0 | 10 | |
Worse | 226 | 0 | 250 | 250 | 171 | 226 | 0 | 0 | 0 | 21 | 0 | 10 | |
Equal | 24 | 250 | 0 | 0 | 77 | 24 | 250 | 250 | 250 | 229 | 250 | 240 | |
Better | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
The one-sided Wilcoxon rank-sum tests presented in Supplementary Tables SI-5 and SI-6, based on the results from Tables 4 and 5, suggest that there is generally little performance difference among all HHs. However, specific differences across certain datasets are noteworthy. For instance, HHSSGA appears to have over-specialized on BTS-I, as its ABU performance on several BTS-II benchmarks is statistically worse than that of all other HHs. Interestingly, on both the IRUP and non-IRUP benchmarks, HHSSGA, HHGA, HHGA, and HHSSGA achieved statistically better ABU values compared to HHGA, HHGA, HHSSGA, and HHSSGA. Even more interesting, on these same benchmarks, both HHGA and HHGA were statistically worse than all other HHs in terms of both ABU and the number of bins used.
Results on BTS-III
Although a comparison was conducted using real-world derived instances, these turned out to be somewhat easy for the heuristics to solve, as most of them exhibited similar performance-with the exception of the WF heuristic. In this sense, the instances behaved similarly to pathological cases that disproportionately affect WF. That is, a good enough performance could generally be achieved as long as WF was avoided. This type of behavior was previously shown to be easily handled by the GA-generated HHs8.
Given the above, the corresponding results were placed in the Supplementary Information. There, ABU performance and its statistical comparison are provided in Supplementary Tables SI-1 and SI-7, respectively, while the performance in terms of the number of bins used and its statistical comparison are presented in Supplementary Tables SI-2 and SI-8.
Understanding the impact of the SSGA components
Aiming to understand the aspects within our approach that have the largest impact on its performance, we conducted a factorial design involving the following factors, each with two levels: type of GA (generational or steady state), population size (6 or 25 individuals), and minimum fitness standard deviation in the population to restart the population ( or ). We conducted five independent runs for each combination of levels using the corresponding configuration. Then, we conducted a three-way factorial analysis of variance (ANOVA) with the data we gathered.
The results obtained from this analysis show that the type of GA has a statistically significant effect on the performance of the resulting hyper-heuristics (p-value = 0.00441). This means that changes in the type of GA (generational or steady state) lead to meaningful changes in the resulting performance. The other two main factors, population size (p = 0.57863) and minimum fitness standard deviation in the population to restart the population (p-value = 0.40936), do not have significant individual effects on the performance of the hyper-heuristics produced. None of the two-way or three-way interactions between the factors are statistically significant (all exhibit a p-value larger than 0.05), indicating that the effect of one factor does not depend significantly on the level of the others. However, the residuals capture a large portion of the variance, suggesting substantial unexplained variability exists in the data. To summarize, the statistical evidence suggests that replacing only a small fraction of the population at each iteration (using a steady state GA instead of a generational one) is the element within our model that impacts the performance of the hyper-heuristics produced most.
Potential bottlenecks
Although we recognize the results obtained by our model are competitive and promising, we understand that a more in-depth analysis of the underlying causes of any potential performance bottlenecks would be beneficial. For this reason, we have carefully revised our model, looking for potential elements that could lead to slower convergence or increased computational overhead. We identified two aspects that may represent a bottleneck in future scenarios:
textitRestarting the population Whenever we restart a population due to its low variance, the new population is randomly initialized (with only the best individual from the previous population preserved). Since the individuals in the new population are randomly initialized (this is the only way to add diversity since we lack a mutation operator in our model), such individuals likely exhibit a low quality. Then, solving the instances in the training set may take longer for the first generations than for the last ones (where the population has converged to a competent hyper-heuristic).
Updating the problem state In most instances, calculating the features’ values to characterize the problem state might not represent a significant overhead. However, we must recall invoking the hyper-heuristic whenever we pack an item. So, we calculate the problem state as many times as the number of bins in the instance. This might represent a problem when the number of bins or features increases drastically because it implies looping over the items repeatedly. In these cases, we expect the model to be slower for producing the hyper-heuristics and applying them once they have been trained.
For example, a fraction of the population could be reinitialized using a mutation operator instead of doing this completely at random. This strategy would produce individuals that represent variations of the best one, increasing the probability of exhibiting a good performance, but at the price of reducing the exploratory nature of the population restart. Another way to deal with the restart process would be to use a heuristic approach to generate a fraction of the new population.
Concerning the problem of continually updating the problem state, we could implement a variation of a delta evaluation. Then, the evaluation of the problem will not need to be conducted from scratch every time we need it. Instead, it will be updated using fast operations and keeping a few additional variables related to the problem state. For example, the first time we calculate AVG (at ), we can calculate it as . However, if we save the sum of the weights and the number of items () for future calculations, once we remove item j (with its correesponding weight, ), we can recalculate AVG at time as . Finally, we would only need to update . Using this strategy, we would avoid calculating the features from scratch, which would reduce computation time.
Discussion and scientific relevance
Collectively, the results presented in this section highlight the potential of the selection HHs for both specialization and generalization. Regarding the performance of the selection HHs produced by our proposed method, we observed that their effectiveness largely depends on the characteristics of the instances they were trained on. In this case, the training instances balanced features that allowed the selection HHs to generalize well on the BTS-I instances (similar to those from the training set). On BTS-II, the results were more varied, producing an overall competitive selection HH (HHSSGA) and another HH (HHSSGA), which performs poorly overall but occasionally produces better results than its composing low-level heuristics in isolation. On BTS-III (as shown in Supplementary Table SI-1 and Supplementary Table SI-2), the results from each method were very similar to each other. Nonetheless, this outcome was somewhat expected, as the instances were relatively easier than those from the other two benchmark test suites.
Overall, the contributions and scientific relevance of our proposed method are as follows. First, the steady-state selection scheme improves the diversity of HHs by delaying stagnation and controlling the number of population reinitializations. This is a critical point since the number of restarts has an impact on the quality of the generated selection HHs: too many restarts hinder convergence, while too few limit exploration. Therefore, the steady-state approach strikes a balance, improving both performance and stability. Second, we expanded the set of features used to describe a problem state from two to five (AVG, STD, SMALL, MEDIUM, and LARGE). As validated in "Preliminary experiments" section, this richer representation leads to the generation of higher-quality selection HHs. Third, in our previous work, we trained GA on pathological 1DBPP instances (i.e., instances crafted to be difficult for a specific heuristic)8. In contrast, we trained SSGA on 1DBPP instances where a specific heuristic is known to perform well. As a result, this requires SSGA to generate selection HHs that accurately select the appropriate heuristic for each instance, rather than merely avoiding poor choices—thus posing a harder and more practical learning task (see "Problem instances (datasets)" section). Following this line, each selection HH was evaluated not only on a synthetic test set (BTS-I) resembling the properties of the training instances but also on well-established instance sets (FalkenauerU, Scholl, Wäscher, Hard28, Irnich, Augmented Non IRUP, and Augmented IRUP) as well as two real-world datasets adapted from the 1D Cutting Stock Problem (BTS-III). Finally, we extended the analysis in addition to ABU, we also report the number of bins used during testing, aligning our analysis with the actual objective of the 1DBPP. This dual reporting strengthens the empirical validity of our findings. Finally, it is worth emphasizing that SSGA contributes to the scarcely explored field of generation HHs that construct selection HHs, highlighting its novelty and relevance in the state of the art54.
Conclusion and future work
In this study, we presented a steady-state GA methodology for generating selection HHs for the classic 1DBPP. This work improves the solution approach proposed by8. Our proposal introduces the integration of a steady-state selection scheme that improves population diversity and stability by effectively managing the number of reinitializations. We also enrich the problem state representation with five descriptive features (namely, AVG, STD, SMALL, MEDIUM, and LARGE), enhancing the quality of the generated selection HHs. Unlike prior work focused on pathological instances, our approach trains on instances where a specific heuristic is optimal, demanding more accurate and meaningful heuristic selection. The proposed method was validated on a wide range of synthetic, benchmark, and real-world datasets, and performance was assessed using both ABU and the number of bins used. Together, these elements underscore the novelty and practical relevance of our SSGA in the context of generative HHs.
Our experimental results demonstrate the feasibility and advantages of the proposed approach across various training and testing datasets. First, preliminary experiments showed that a population size of six individuals for our SSGA provided a good balance between resulting selection HH quality and computational resource consumption. Furthermore, our experiments also showed that increasing the training set size led to better generalization, as selection HHs trained on larger datasets performed better on unseen test instances. Additionally, including features beyond the simple statistical measures (average and standard deviation) improved the effectiveness of the mapping between instances and heuristics, leading to consistently better performance across both the training and test datasets.
Compared with other generative methodologies based on evolutionary approaches, our proposed SSGA outperformed a generational GA, a steady-state GA, and a generational GA, consistently reaching higher fitness values within the same number of evaluations, during training. During testing, our results on benchmark datasets (BTS-I, BTS-II and BTS-III) revealed that the selection HHs produced by SSGA were highly competitive, often outperforming HHs generated by the other methods, particularly on the instances of BTS-I. Additionally, our SSGA generated selection HHs with strong specialization for certain instance types and others with generalization capabilities. Unfortunately, a limitation in this work is that BF was the best-performing heuristic in almost all the cases of BTS-II and BTS-III. This behavior makes it challenging to produce an HH that does not include BF as one of the options. Since BF is the best option for many instances, the HHs tend to replicate its behavior. This phenomenon is similar to what happens in other learning approaches when the training set is biased. Although this does not mean a bad result since the HHs do learn, it opens a path for future work in which we should explore ways to overcome the problem of working with “unbalanced” sets of instances, where one of the heuristics is almost always the best performer.
As a natural continuation of this work, we plan to extend the application of SSGA to more complex variants of the BPP, such as two- and three-dimensional BPPs. Furthermore, exploring its performance on additional problem domains and refining the instance characterization are promising directions to improve the generalization capabilities of the generated selection HHs. Lastly, we consider analyzing the cross-domain behavior of SSGA, even if it requires incorporating heterogeneous feature representations.
Author contributions
All authors contributed to the study conception and design. Material preparation and data collection were performed by all the authors. The analysis of the results was performed by all the authors. The first draft of the manuscript was written by J.J., and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.
Data availability
The data with the performance of the hyper-heuristic produced is available under request to the corresponding author at jcobayliss[at]tec[dot]mx.
Declarations
Competing interests
The authors declare no competing interests.
Supplementary Information
The online version contains supplementary material available at https://doi.org/10.1038/s41598-025-10790-9.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
References
1. Eliiyi, U; Eliiyi, DT. Applications of bin packing models through the supply chain. Int. J. Bus. Manag.; 2009; 1, pp. 11-19.
2. Luo, Q; Rao, Y; Du, B. An effective discrete artificial bee colony for the rectangular cutting problem with guillotine in transformer manufacturing. Appl. Soft Comput.; 2024; 159, 111617.
3. Luo, Q; Rao, Y; Peng, D. Ga and gwo algorithm for the special bin packing problem encountered in field of aircraft arrangement. Appl. Soft Comput.; 2022; 114, 108060.
4. Coffman, E. G., Garey, M. R. & Johnson, D. S. Approximation algorithms for bin packing: a survey, 46–93 (PWS Publishing Co., USA, 1996).
5. Korte, B. & Vygen, J. Bin-Packing, 489–507 Springer (2018).
6. Munien, C; Ezugwu, AE. Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications. J. Intell. Syst.; 2021; 30, pp. 636-663.
7. Pillay, N. A study of evolutionary algorithm selection hyper-heuristics for the one-dimensional bin-packing problem. S. Afr. Comput. J.; 2012; 48, pp. 31-40.
8. Ortiz-Bayliss, J. C., Juárez, J. & Falcón-Cardona, J. G. Using genetic algorithms for hyper-heuristic development: A preliminary study on bin packing problems. In: 2023 10th International Conference on Soft Computing & Machine Intelligence (ISCMI), 54–58 (IEEE, 2023).
9. Rhee, WT; Talagrand, M. On line bin packing with items of random size. Math. Oper. Res.; 1993; 18, pp. 438-445.1250128
10. Johnson, DS; Demers, A; Ullman, JD; Garey, MR; Graham, RL. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput.; 1974; 3, pp. 299-325.434396
11. Coffman, E.G., Galambos, G., Martello, S. & Vigo, D. Bin packing approximation algorithms: Combinatorial analysis. Handbook of Combinatorial Optimization: Supplement Volume A 151–207 (1999).
12. Blum, C; Roli, A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. (CSUR); 2003; 35, pp. 268-308.
13. Falkenauer, E. & Delchambre, A. A genetic algorithm for bin packing and line balancing. In: Proceedings 1992 IEEE International Conference on Robotics and Automation, 1186–1192 (IEEE, 1992).
14. Quiroz-Castellanos, M et al. A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Comput. Operat. Res.; 2015; 55, pp. 52-64.3284217
15. Gonçalves, JF; Resende, MG. A biased random key genetic algorithm for 2d and 3d bin packing problems. Int. J. Prod. Econ.; 2013; 145, pp. 500-510.
16. Tian, Y et al. Evolutionary large-scale multi-objective optimization: A survey. ACM Comput. Surv. (CSUR); 2021; 54, pp. 1-34.
17. Burke, EK et al. Hyper-heuristics: A survey of the state of the art. J. Operat. Res. Soc.; 2013; 64, pp. 1695-1724.
18. Burke, E. K., Hyde, M. R. & Kendall, G. Evolving Bin Packing Heuristics with Genetic Programming. In: Parallel Problem Solving from Nature - PPSN IX, 860–869 (Springer (eds Runarsson, T. P. et al.) (Berlin Heidelberg, Berlin, Heidelberg, 2006).
19. Terashima-Marín, H., Farías Zárate, C.J., Ross, P. & Valenzuela-Rendón, M. A ga-based method to produce generalized hyper-heuristics for the 2d-regular cutting stock problem. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO ’06, 591-598 (ACM, New York, NY, USA, 2006).
20. López-Camacho, E; Terashima-Marin, H; Ross, P; Ochoa, G. A unified hyper-heuristic framework for solving bin packing problems. Exp. Syst. Appl.; 2014; 41, pp. 6876-6889.
21. Coello Coello, C. A. & Toscano Pulido, G. A micro-genetic algorithm for multiobjective optimization. In: Evolutionary Multi-Criterion Optimization, 126–140 (Springer (eds Zitzler, E. et al.) (Berlin Heidelberg, Berlin, Heidelberg, 2001).
22. Goldberg, D.E. Sizing populations for serial and parallel genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, 70–79 (Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1989).
23. Agapie, A; Wright, AH. Theorerical analysis of steady state genetic algorithms. Appl. Math.; 2014; 59, pp. 509-525.3255793
24. Ortiz-Bayliss, J.C., Gárate-Escamilla, A.K. & Terashima-Marín, H. Missing data and their effect on algorithm selection for the bin packing problem. In Mezura-Montes, E., Acosta-Mesa, H. G., Carrasco-Ochoa, J. A., Martínez-Trinidad, J. F. & Olvera-López, J. A. (eds.) Pattern Recognition, 34–43 (Springer Nature Switzerland, Cham, 2024).
25. Silva-Gálvez, A. et al. Discovering action regions for solving the bin packing problem through hyper-heuristics. In : 2020 IEEE Symposium Series on Computational Intelligence (SSCI), 822–828 (IEEE, 2020).
26. Dósa, G. & Sgall, J. First fit bin packing: A tight analysis. In : 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) (Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2013).
27. Dósa, G. & Sgall, J. Optimal analysis of best fit bin packing. In: International Colloquium on Automata, Languages, and Programming, 429–441 (Springer, 2014).
28. Munien, C et al. Metaheuristic approaches for one-dimensional bin packing problem: A comparative performance study. IEEE Access; 2020; 8, pp. 227438-227465.
29. Reeves, C. Hybrid genetic algorithms for bin-packing and related problems. Ann. Oper. Res.; 1996; 63, pp. 371-396.
30. Hussain, S; Sastry, V. Application of genetic algorithm for bin packing. Int. J. Comput. Math.; 1997; 63, pp. 203-214.1455231
31. Levine, J; Ducatelle, F. Ant colony optimization and local search for bin packing and cutting stock problems. J. Operat. Res. Soc.; 2004; 55, pp. 705-716.
32. El-Ashmawi, WH; Abd Elminaam, DS. A modified squirrel search algorithm based on improved best fit heuristic and operator strategy for bin packing problem. Appl. Soft Comput.; 2019; 82, 105565.
33. Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. J. Heurist.; 1996; 2, pp. 5-30.
34. Iima, H. & Yakawa, T. A new design of genetic algorithm for bin packing. In: The 2003 Congress on Evolutionary Computation, 2003. CEC’03., vol. 2, 1044–1049 (IEEE, 2003).
35. Salhi, A; Vázquez Rodríguez, JA. Tailoring hyper-heuristics to specific instances of a scheduling problem using affinity and competence functions. Memet. Comput.; 2014; 6, pp. 77-84.
36. Alissa, M., Sim, K. & Hart, E. Algorithm selection using deep learning without feature extraction. In: Proceedings of the Genetic and Evolutionary Computation Conference, 198–206 (2019).
37. Alissa, M; Sim, K; Hart, E. Automated algorithm selection: from feature-based to feature-free approaches. J. Heurist.; 2023; 29, pp. 1-38.
38. Ali, S; Ramos, AG; Carravilla, MA; Oliveira, JF. Heuristics for online three-dimensional packing problems and algorithm selection framework for semi-online with full look-ahead. Appl. Soft Comput.; 2024; 151, 111168.
39. Gomez, JC; Terashima-Marín, H. Evolutionary hyper-heuristics for tackling bi-objective 2d bin packing problems. Genet. Program Evolvable Mach.; 2018; 19, pp. 151-181.
40. Ortiz-Bayliss, JC; Terashima-Marín, H; Conant-Pablos, SE. Combine and conquer: An evolutionary hyper-heuristic approach for solving constraint satisfaction problems. Artif. Intell. Rev.; 2016; 46, pp. 327-349.
41. Wolpert, DH; Macready, WG. No free lunch theorems for optimization. IEEE Trans. Evol. Comput.; 1997; 1, pp. 67-82.
42. Whitley, D. The genitor algorithm and selection pressure: why rank-based allocation of reproductive trials is best. In: Proceedings of the Third International Conference on Genetic Algorithms, 116–121 (1989).
43. Krishnakumar, K. Micro-genetic algorithms for stationary and non-stationary function optimization. Intell. Control Adapt. Syst.; 1990; 1196, pp. 289-296.1990SPIE.1196.289K
44. Plata-González, LF et al. Evolutionary-based tailoring of synthetic instances for the knapsack problem. Soft. Comput.; 2019; 23, pp. 12711-12728.
45. Delorme, M; Iori, M; Martello, S. Bpplib: A library for bin packing and cutting stock problems. Optim. Lett.; 2018; 12, pp. 235-250.3767875
46. Umetani, S; Yagiura, M; Ibaraki, T. One-dimensional cutting stock problem to minimize the number of different patterns. Eur. J. Oper. Res.; 2003; 146, pp. 388-402.1935288
47. Matsumoto, K; Umetani, S; Nagamochi, H. On the one-dimensional stock cutting problem in the paper tube industry. J. Sched.; 2011; 14, pp. 281-290.2800379
48. Scholl, A; Klein, R; Jürgens, C. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Operat. Res.; 1997; 24, pp. 627-645.
49. Wäscher, G; Gau, T. Heuristics for the integer one-dimensional cutting stock problem: A computational study. Operat-Res-Spekt; 1996; 18, pp. 131-144.
50. Schoenfield, J. E. Fast, exact solution of open bin packing problems without linear programming (Draft, US Army Space and Missile Defense Command, Huntsville, Alabama, USA, 2002).
51. Gschwind, T; Irnich, S. Dual inequalities for stabilized column generation revisited. INFORMS J. Comput.; 2016; 28, pp. 175-194.3465907
52. Delorme, M; Iori, M; Martello, S. Bin packing and cutting stock problems: Mathematical models and exact algorithms. In EJOR; 2016; 255, pp. 1-20.3513785
53. Fonseca, C.M., Guerreiro, A.P., López-Ibáñez, M. & Paquete, L. On the Computation of the Empirical Attainment Function. In Takahashi, R.H., Deb, K., Wanner, E.F. & Grecco, S. (eds.) Evolutionary Multi-Criterion Optimization, 6th International Conference, EMO 2011, 106–120 (Springer. Lecture Notes in Computer Science Vol. 6576, Ouro Preto, Brazil, 2011).
54. Drake, JH; Kheiri, A; Özcan, E; Burke, EK. Recent advances in selection hyper-heuristics. EJOR; 2020; 285, pp. 405-428.4085187
© The Author(s) 2025. This work is published under http://creativecommons.org/licenses/by-nc-nd/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.