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 Pa...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2015-03, Vol.55, p.52-64
Main Authors: Quiroz-Castellanos, Marcela, Cruz-Reyes, Laura, Torres-Jimenez, Jose, Gómez S., Claudia, Huacuja, Héctor J. Fraire, Alvim, Adriana C.F.
Format: Article
Language:English
Subjects:
Algorithms
Balancing
Chromosomes
Gene transmission
Genes
Genetic algorithms
Genetic diversity
Genetics
Grouping problems
Heuristics
One-dimensional bin packing
Operations research
Operators
Optimization techniques
Packing problem
Performance enhancement
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2014.10.010