Solving Two-Dimensional Packing Problem Based On Hybrid Partheno-Genetic Algorithm

Packing problem is given to some of the items in accordance with the requirements of different sizes placed into a certain volume of container to get a the best results. Packing problem involves multi-disciplinary, multi-domain knowledge, in the production practice is widely used. Two-dimensional packing problem can be seen everywhere in real life, and people's production and life are closely related. Find an effective algorithm for two-dimensional packing problem can save resources and improve production efficiency, have a significant impact on production and living of the people, and thus have a positive role in promoting for human society. At the same time two-dimensional packing problem solving can also be applied to various algorithms for solving three-dimensional packing problems, the study two-dimensional packing problem has important theoretical significance and application value.Packing problem is a complex combination of constraint optimization problem, in theory, the problem is NP-hard. Its solution is extremely difficult.70 years from the beginning of the 20th century, packing problem has aroused concern. So far, more study of the world is one-dimensional and two-dimensional packing problem, it made a number of algorithms for solving packing problems, of which the most important algorithms are heuristic and genetic algorithms.Firstly, the type of packing problem and the research was reviewed, summarized some of the existing algorithms on the packing problems, including heuristic calculation methods and genetic algorithms. Describes the basic implementation mechanism of genetic algorithms. And partheno-genetic algorithm is outlined. Then for the two-dimensional rectangular packing problem, the existing algorithms FFA and its improved algorithm IFFA were analyzed. Algorithm IFFA is further improved and proposed a IFFA2 algorithm. In IFFA2 algorithm, consider the use of fragmentation, and describes the fragmentation and representation by example. Finally, try to IFFA2 combined with partheno-genetic algorithm to form hybrid partheno-genetic algorithm to achieve the two-dimensional packing problem to solve. And implementation of the algorithm flow chart. In the algorithm, and implementation of the algorithm flow chart. In the algorithm, proposed taking into account the order of items and goods packing orientation of the coding scheme. And designing a new fitness function and genetic operations. Introduced in the decoding process IFFA2 algorithm, the heuristic algorithm and genetic algorithm combined with organic.