A grouping genetic algorithm with controlled gene transmission for the bin packing problem

In this study, the one-dimensional Bin Packing Problem (BPP) is approached. The BPP is a classical optimization problem that is known for its applicability and complexity. We propose a method that is referred to as the Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) for Bin Packing. The proposed algorithm promotes the transmission of the best genes in the chromosomes without losing the balance between the selective pressure and population diversity. The transmission of the best genes is accomplished by means of a new set of grouping genetic operators, while the evolution is balanced with a new reproduction technique that controls the exploration of the search space and prevents premature convergence of the algorithm. The results obtained from an extensive computational study confirm that (1) promoting the transmission of the best genes improves the performance of each grouping genetic operator; (2) adding intelligence to the packing and rearrangement heuristics enhances the performance of a GGA; (3) controlling selective pressure and population diversity tends to lead to higher effectiveness; and (4) GGA-CGT is comparable to the best state-of-the-art algorithms, outperforming the published results for the class of instances Hard28, which appears to have the greatest degree of difficulty for BPP algorithms. (C) 2014 Elsevier Ltd. All rights reserved.