Study And Application Of Rectangular Packing Problem Based On Genetic Algorithm And Ant Algorithm

Rectanglular packing problem is coming from actual manufacture, has been widely used in various industries, such as manufacturing of automobiles, shipbuilding, clothing, machining of glass, manufacturing of furniture and so on. Facing the various of rescource is eliminating, it is important for industries to increase the material utility and economic income.Rectangular is concerned with calculating geometry, computer graphics, operational research, and logical reasoning. It belongs to Nondeterministic Polynomial Complete(NPC) problem with the highest complexity in math. In fact, It can' t be solved in theory, today. In need of actual manufacture, a way using modern science and technology to solve cutting is urgent. The kind of way may gives us a solution close with optimal solution and its efficient is higher than artifical method and the people' s expectation.How to select suitable rectangle and arrange its situation is important to the final purpose. Meanwhile it is a difficulty in rectangular packing problem. This article thinks: Genetic algorithm has the ability of doing a global searching quickly and stochastically. But it can' t make use of enough system output information. It has to do a large redundancy repeat for the result when solving to certain scope. So the efficiency to solve precision results is reduced. Ant algorithm converges on the optimization path through information pheromone accumulation and renewal. It has the ability of parallel processing and global searching. The speed at which the ant algorithm gives the solution is slow, because there is little information pheromone on the path early. The algorithm in this paper is based on the combination of genetic algorithm and ant algorithm. First, it adopts genetic algorithm to give information pheromone to distribute. Second, it makes use of the ant algorithm to give the precision of the solution. Finally, it develops enough advantage of the two algorithms. On the other hand, on the basis of the Lowest Horizontal Line -Search Algorithm, an improved algorithm for rectangular packing problem is proposed in this paper, that is, Lowest Horizontal Line -Rotate Searching Algorithm, which meets the BL condition and overcome the shortcomings of other algorithm for some patterns. The simulation results show that very nice effects are obtained.