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: | Falkenauer Emanuel |
Keywords: | bin packing, genetic algorithms |
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.