A hybrid grouping genetic algorithm for bin packing |
| |
Authors: | Emanuel Falkenauer |
| |
Institution: | (1) Industrial Management and Automation, Research Centre for the Belgian Metalworking Industry (CRIF), 50, av. F.D. Roosevelt, CP 106-P4, B-1050 Brussels, Belgium |
| |
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. |
| |
Keywords: | grouping partitioning bin packing genetic algorithm solution encoding dominance reduction |
本文献已被 SpringerLink 等数据库收录! |
|