An Experimental Study on Grouping Mutation Operators within the GGA-CGT Applied to the One-Dimensional Bin Packing Problem

Abstract

The Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) is among the most effective algorithms for solving the one-dimensional Bin Packing Problem (1D-BPP), a classical NP-hard combinatorial optimisation problem with numerous industrial and logistical applications. This study aims to identify the characteristics that enable a mutation operator to perform better within this algorithm by implementing five state-of-the-art mutation operators: Elimination, Merge & Split, Swap, Insertion, and Item Elimination. Performance was evaluated in terms of the number of optimal solutions obtained. Our findings indicate that the GGA-CGT performs best with the least disruptive operators and that both the gene selection strategy and the item selection strategy can enhance the performance of mutation operators. These findings were validated by redesigning and improving a state-of-the-art item-oriented operator, achieving a 26% improvement over the best baseline version of the same operator.