A steady state micro genetic algorithm for hyper-heuristic generation in one-dimensional bin packing

Abstract

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 Genetic Algorithm (SSGA) to generate selection HHs, benefiting from the gradual population updates of steady-state GAs and the efficiency of GAs with smaller populations for faster iterations. Our experimental results showcase the effectiveness of the SSGA across multiple training and testing datasets for the 1DBPP. Compared to other evolutionary methodologies, also used as generative HH methods (i.e., generational GA, steady-state GA, and generational GA), the SSGA consistently achieves higher fitness values within the same number of evaluations, on the training set. Additionally, on both generated and literature 1DBPP instances for the testing set, the selection HHs generated by the SSGA were highly competitive, often outperforming those produced by other methods. Furthermore, the SSGA-generated HHs displayed both specialization for specific instance types and generalization across varied instances.