Research Of Rectangular Packing Method Based On Diferential Evolution And Adaptive Genetic Algorithm

Rectangular packing problems are widely existed in industrial design such as panel processing, aerospace, machine manufacturing, glass making and so on. Rectangular packing problems always include two situations, one is laying rectangular on the sheet with fixed length and width, the other is laying rectangular on the sheet with fixed width and unfixed length. There are some restrictions when laying rectangular on the sheet:overlapping is not allowed and the rectangular should not beyond the boundary of sheet. And the ultimate purpose is to make the utilization of sheet maximization. While the rectangular packing problem was proofed as a NP complete problem and can not solved by direct computing, it's still a hot topic so far.The packing problem researched in this essay is laying rectangular on the sheet with fixed width and unfixed length. In the modern industries like cloth cutting, glass cutting, furniture panel stock etc, we always meet the same problem:the length of sheet is unfixed and only after laying all the rectangles can we obtain the length of sheet we need. Thus, the problem involved in this essay will be useful for many industries in our society.Focused on the rectangular packing problem, firstly, two optimization algorithm were used to solve the packing sequences:one was adaptive genetic algorithm, in which operators with better performance were applied to find the rectangular sequences, and the method with the crossover probability and mutation probability can be adaptively adjusted was used to improve the genetic algorithm's convergence speed and stability; The other was discrete differential genetic algorithm, which combined the advantages of differential evolution algorithm with the advantages of genetic algorithm to improve the performance of optimization algorithm. Secondly, multi-strip strategy and concentrated surplus rectangle area strategy were proposed as two decoding methods respectively. Finally, the proposed algorithm was realized in C# on VS2010 then applied in some experiments. According to experiment results, the proposed packing method was proofed as an effective and reasonable method with a higher utilization of sheet and of great realistic significance.