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

Autor: Marcela Quiroz-Castellanos, S Claudia Gómez, Héctor Joaquín Fraire Huacuja, Laura Cruz-Reyes, Adriana C. F. Alvim, Jose Torres-Jimenez
Rok vydání: 2015
Předmět:
Zdroj: Computers & Operations Research. 55:52-64
ISSN: 0305-0548
DOI: 10.1016/j.cor.2014.10.010
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: