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

Area of Science:

• Computer Science
• Operations Research
• Artificial Intelligence

Background:

• The one-dimensional bin packing problem (1DBPP) is an NP-hard optimization challenge with significant real-world applications.
• Exact algorithms are often infeasible for large 1DBPP instances, necessitating the use of heuristics.
• Existing heuristics can be instance-specific, performing inconsistently across different problem types.

Purpose of the Study:

• To develop a method for automatically generating effective selection hyper-heuristics (HHs) for the 1DBPP.
• To leverage the strengths of simple heuristics while mitigating their individual weaknesses.
• To improve the performance and adaptability of algorithms solving the 1DBPP.

Main Methods:

• Introduction of a steady-state μ Genetic Algorithm (SSμGA) for generating selection HHs.
• Utilizing gradual population updates from steady-state GAs and efficiency of μGAs with smaller populations.
• Comparative analysis against other evolutionary generative methods like generational GA, steady-state GA, and generational μGA.

Main Results:

• The SSμGA consistently achieved higher fitness values on the training set compared to other evolutionary methods within the same evaluation budget.
• Selection HHs generated by the SSμGA demonstrated high competitiveness on both generated and literature 1DBPP instances in the testing set.
• SSμGA-generated HHs exhibited a balance of specialization for specific instance types and generalization across diverse instances.

Conclusions:

• The SSμGA is an effective approach for automatically generating high-performing selection hyper-heuristics for the 1DBPP.
• The generated HHs offer improved performance and adaptability over methods produced by other evolutionary techniques.
• This work contributes a robust method for tackling complex combinatorial optimization problems like the 1DBPP.