The Realization Of G4 Algorithm And The Research On Cross-Entropy Algorithm For Packing Problem

Packing problem is a classic combinatorial optimization problem. Its practical utility and its NP-completeness character draw researchers from engineering, math, and computer science to do deep and vast reaseaches. Methods to solve different concrete problem emerge in endlessly. G4 algorithm is a highly efficient algorithm for pallet loading problem (one typical packing problem). In order to digest its idea, this thesis firstly programs to re-realize it. Then this thesis proposes employing the new meta-heuristic algorithm, the Cross-Entropy (CE) algorithm, to solve 2-and 3-dimensional packing problems. The validity of the CE method in solving packing problem is verified by experimental tests.First of all, the research task is brought forward based on summarizing and analyzing current research literatures both domestically and abroadly.Combined the requirement of enterprise with the high efficiency of G4 algorithm, this thesis re-programs the algorithm and digests the idea of the algorithm. The basic concept, idea, and theory of dynamic programming were introduced before introducing the G4 algorithm for the theory of G4 algorithm is dynamic programming.Then a brief introduction of the origin and development of entropy, the math formula of Shannon Entropy and CE are given. Based on the math formula of CE, the basic theory of Rare-Event Simulation with CE method is introduced. In general, the probability of the optimistic result of the related optimistic problem is rare, so the basic theory of transforming an optimistic problem to a related Rare-Event Simulation problem, and then taking CE method to solving it were presented. In roder to have a better understanding of CE algorithm, a comparison of the difference and similarity between CE method and other classic meta-heuristic methods for optimistic problem are presented.And then the thesis proposes using CE for the two dimension packing problem based on the feasibility of CE theory for the optimistic problem: sample generating method based on probability matrix and the DROP and DROPF decoder strategies for one sample sequence to determine a packing scheme are presented, the parameter updating mechanism and the full algorithm are also given. The main data structure of DROP and DROPF decoder are explained, and flow chart for DROPF decoder strategies are also presented. Based on the theory, large amount of experiments have been done. The comparison of the experimental results with the results obtained by classic meta-heuristic shows that the the algorithm works well and is highly efficient.Afterward, a tentative research for the container loading problem with CE method is proposed: encoder method based on the distribution of Bernoulli and the space decomposition decoder strategy is presented. An experimental result to testify the feasibility of the CE algorithm for the container loading problem after the detailed illumination of the encoder method based on the distribution of Bernoulli and the decoder strategy based on space decomposition is given.In the end, conclusions are drawn and the future research directions are suggested.