A hybrid grouping genetic algorithm for bin packing

A hybrid grouping genetic algorithm for bin packing

0.00 Avg rating0 Votes
Article ID: iaor20003201
Country: United States
Volume: 2
Issue: 1
Start Page Number: 5
End Page Number: 30
Publication Date: Jan 1996
Journal: Journal of Heuristics
Authors:
Keywords: bin packing, genetic algorithms
Abstract:

The grouping genetic algorithm (GGA) is a genetic algorithm heavily modified to suit the structure of grouping problems. Those are the problems where the aim is to find a good partition of a set or to group together the members of the set. The bin packing problem (BPP) is a well known NP-hard grouping problem: items of various sizes have to be grouped inside bins of fixed capacity. On the other hand, the reduction method of Martello and Toth, based on their dominance criterion, constitutes one of the best OR techniques for optimization of the BPP to date. In this article, we first describe the GGA paradigm as compared to the classic Holland-style GA and the ordering GA. We then show how the bin packing GGA can be enhanced with a local optimization inspired by the dominance criterion. An extensive experimental comparison shows that the combination yields an algorithm superior to either of its components.

Reviews

Required fields are marked *. Your email address will not be published.