Hybrid genetic algorithms for bin-packing and related problems

The genetic algorithm (GA) paradigm has attracted considerable attention as a promising heuristic approach for solving optimization problems. Much of the development has related to problems of optimizing functions of continuous variables, but recently there have been several applications to problems of a combinatorial nature. What is often found is that GAs have fairly poor performance for combinatorial problems if implemented in a naive way, and most reported work has involved somewhat ad hoc adjustments to the basic method. This paper will describe a general approach which promises good performance for a fairly extensive class of problems by hybridizing the GA with existing simpel heuristics. The procedure will be illustrated mainly in relation to the problem of bin packing, but it could be extended to other problems such as graph partitioning, parallel-machine scheduling and generalized assignment. The method is further extended by using problem size reduction hydrids. Some results of numerical experiments will be presented which attempt to identify those circumstances in which these heuristics will perform well relative to exact methods. Finally, the paper discusses some general issues involving hybridization: in particular, it raises the possibility of blending GAs with orthodox mathematical programming procedures.