Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems

A popular approach when using a genetic algorithm in the solution of constrained problems is to exploit problem specific information by representing individuals as ordered lists. A construction heuristic is then often used as a decoder to produce a solution from each ordering. In such a situation further information is often available in the form of bounds on the partial solutions. This paper uses two two-dimensional packing problems to illustrate how this information can be incorporated into the genetic operators to improve the overall performance of the search. Our objective is to use the packing problems as a vehicle for investigating a series of modifications of the genetic algorithm approach based on information from bounds on partial solutions.