Enhancing Traditional Genetic Algorithm In Bin Packing Problem

Abstract

The Bin Packing Problem (BPP) is a well-known NP-hard optimization problem with various practical applications. This paper focuses on solving One-Dimension Bin Packing Problem (1D-BPP) by improving the efficiency and effectiveness of an existing meta-heuristic algorithm, which is Genetic Algorithm. Other techniques were thoroughly analyzed through numerous previous studies, especially the introduction of Grouping Genetic Algorithm (GGA) gained significant interest from researchers. That remains a lack of in-depth exploration and modification of the traditional GA specifically tailored for BPP. In this thesis, Enhancing Genetic Algorithm (EGA) aims to bridge this research gap by incorporating enhancements into the standard GA framework. By preserving chromosome structure during crossover, adjusting the mutation rate, and introducing the enhancing and fixing steps, EGA offers a novel approach to improving the performance of GA. While its results through experimental evaluations on benchmark data sets may not consistently effective, they provide valuable insights into the operation and parameter settings of GA for solving BPP issue.