An Algorithm Based On The Layout Of The Cross-entropy Method

Packing problem is a typical combinatorial optimization problem, and has NPC difficulty in solving complexity. Not only has it application in many engineering fields, also becomes a hot research problem on which many mathematicians and researchers in computer algorithm area pay attention. Since long time ago, many kinds of algorithms for packing problem have been established and classified in detail. Cross entropy method is a relatively new optimization method established and developed in recent years, and has been successfully applied in solving many combinatorial optimization problems. On the base of deep research on basic theory of cross entropy method, this paper deals with its application in packing problems. Several algorithms based on cross entropy are designed, and numerical experiments have been done to testify their efficiency.Firstly, this thesis begins with reviewing research achievement on modeling and solving algorithm of packing problems at home and abroad. The relationship among P, NP, NPC and NPH problem is also analyzed. Moreover, this thesis makes detailed discussion about statistical aspect of optimal solution and optimization method, which helps introduce main research content in this thesis.Then, starting with the concept of information entropy and analysis about cross method for rare event simulation, this thesis introduces the basic idea of cross entropy optimization method. The fundamental theory of cross entropy method is explained in a recapitulative way; the globally optimal performance of this method is also analyzed. Moreover this thesis compares cross entropy method with other optimization methods, such as GA, ant colony algorithm and SA algorithm, and analyzes the difference and sameness between them.And then, this thesis introduces its main work and contribution. The algorithms based on cross entropy method are given: (1)packing scheme and solving algorithm for 0-1 knapsack problem are given by using Bernoulli distribution and sample correction; (2)bin packing scheme is determined by BL packing strategy and sample generating method based on sequence pair and probability matrix, and the parameter updating mechanism and full algorithm are also given; (3)packing scheme is generated through degenerate sequence pair and its decoding algorithm, and parameter updating based on probability matrix and full solving algorithm are given then. Moreover, this thesis...