An Experimental Study of Grouping Crossover Operators for the Bin Packing Problem

Abstract

The one-dimensional Bin Packing Problem (1D-BPP) is a classical NP-hard problem in combinatorial optimization with an extensive number of industrial and logistic applications, considered intractable because it demands a significant amount of resources for its solution. The Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) is one of the best state-of-the-art algorithms for 1D-BPP. This article aims to highlight the impact that the crossover operator itself can have on the final performance of the GGA-CGT. We present a comparative experimental study of four state-of-the-art crossover operators for 1D-BPP: Uniform, Exon Shuffling, Greedy Partition and Gene-level; this is the first time that the Uniform, Exon Shuffling and Greedy Partition operators are adapted and studied as a part of the GGA-CGT; moreover, the Uniform crossover has never been used before for solving the 1D-BPP. We measure the performance of the GGA-CGT by replacing its original crossover operator (Gene-level) with each of the other three state-of-the-art operators. Furthermore, we propose a new version of the Uniform crossover and examine two replacement strategies for the Gene-level crossover. Experimental results indicate that the Gene-level crossover operator is shown to have a greater impact in terms of the number of optimal solutions found, outperforming the other operators for the class of Hard28 instances, which has shown the greatest degree of difficulty for 1D-BPP algorithms.