<p>The one-dimensional bin packing problem (1DBPP) is a well-known <i>NP</i>-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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation> Genetic Algorithm (SS<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GA) to generate selection HHs, benefiting from the gradual population updates of steady-state GAs and the efficiency of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GAs with smaller populations for faster iterations. Our experimental results showcase the effectiveness of the SS<InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GA 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 <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GA), the SS<InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GA 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 SS<InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GA were highly competitive, often outperforming those produced by other methods. Furthermore, the SS<InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41598_2025_10790_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu\)</EquationSource> </InlineEquation>GA-generated HHs displayed both specialization for specific instance types and generalization across varied instances.</p>

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

期刊论文
出版模式：

开放获取
发表日期：

2025年7月26日

查看全文

Julio Juárez,
Jesús Guillermo Falcón-Cardona,
José Carlos Ortiz-Bayliss

摘要

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 \(\mu\) Genetic Algorithm (SS \(\mu\) GA) to generate selection HHs, benefiting from the gradual population updates of steady-state GAs and the efficiency of \(\mu\) GAs with smaller populations for faster iterations. Our experimental results showcase the effectiveness of the SS \(\mu\) GA 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 \(\mu\) GA), the SS \(\mu\) GA 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 SS \(\mu\) GA were highly competitive, often outperforming those produced by other methods. Furthermore, the SS \(\mu\) GA-generated HHs displayed both specialization for specific instance types and generalization across varied instances.