A Study On Genetic Algorithm For Rectangular Packing Problem Based On Statistical Analysis

Rectangle packing problem(RPP) usually consists of packing given rectangle pieces into a large rectangle stock plate, with a maximum usage of the stock plate. It is a typical combination optimization and has been proved to be a NP-complete problem with high complexity of computation.In this thesis, by the analysis of the research actuality both here and abroad and the shortage of traditional GA, a partheno-genetic algorithm based on statistical analysis has been presented to solve the rectangle packing problem.First of all, the partheno-genetic algorithm(PGA) and the surplus rectangle fill algorithm(SRF) have been combined, so that both advantages of those two algorithms could be used efficiently to solve the orthogonal packing problem of rectangles. In several instances, it is proved that solutions achieved by this algorithm excelled those achieved by other common algorithms in both computational accuracy and operation time. Further, based on the algorithm presented above, the relation between the solutions of rectangle packing problems and the characteristics of the problems themselves such as the number of those rectangle pieces, the size diversity of those rectangle pieces, the specification of the stock plate and so on has been researched. As a result, it is found that there exist some statistical laws for the distribution of the suboptima of rectangle packing problems. And then, an improved PGA based on statistical analysis has been designed by adopting superior colony traversal strategy according to those statistical laws gained, to solve rectangle packing problems. Finally, the algorithm has been tested using several available instances. The experimental results have demonstrated that this algorithm can improve the capability of searching the global optimum of some RPP under specific production environment greatly. This shows adequately that the algorithm presented in this thesis is efficacious.