Solving Rectangular Packing Problem Based On Discrete Particle Swarm Optimization Algorithm

The problem of rectangle packing, which can be stated as putting the needed rectangles on the given sheet with an aim to minimizing sheet's unused area, is an importance branch of computer aid nesting. The rectangle packing problem exists widely in the industry, such as mechanism, furniture and costume. Solving this problem can save raw materials, streamline production processes, reduce production costs and increase the efficiency of industry. Irregular layouts can be transformed into the rectangular packing problems by computer graphics processing technology. But the rectangle packing problem is a high computational complexity NP-complete problem in theory, while the scale of the problem is large, we can not use exact algorithm to acquire the optimal solution. Therefore, the study has important practical and theoretical value.Particle Swarm Optimization (PSO) algorithm, which is proposed by Doctor Eberhart and Kennedy in 1995, is a new bionic evolutionary computation techniques derived from the study of feeding habits. The proposed algorithm immediately triggered widespread attention in the fields of optimization algorithm and evolutionary computation. PSO algorithm has been widely used in function optimization, neural networks, pattern classification, control of Fuzzy Systems and other areas. But the current study is still at the initial stage, the basic theory and practical application of the algorithm have a lot of work to do. To improve this algorithm has important significance for solving the practical problem.Based on the above considerations, in this paper, we propose an approach which can be used to solve the rectangle packing problem based on the discrete particle swarm optimization algorithm. The validity of the algorithm is demonstrated by numerous examples of testing,and the novelty of this research is as follows:First, the thesis proposes an approximate rectangular packing algorithm. We compared and analyzed with some approximate rectangular packing algorithms proposed by Chinese and foreign scholars. In summing up the advantages and disadvantages of these algorithms, we modified an approximately rectangular packing algorithm based on the Lowest Horizontal Line Searching Algorithm (LHLSA). The LHLSA use rectangular with a plus or minus sign to judge whether rectangular rotated 90 degrees before it is packed, the aim is to change the packing mode, so that more rectangular can be packed at present and the waste of the sheet are reduced as much as possible. The code in this article are all positive number, the lowest horizontal line is compared with present rectangle's width, if lowest horizontal line is larger than the width, put the rectangular in this position. Otherwise, the lowest horizontal line is compared with present rectangle's length. If lowest horizontal line is larger than the length, put the rectangular in this position. We rotate the rectangular and put the rectangular in this position. If the lowest horizontal line is less than the wide and length, search back in the position in the current sequence, we choose one of the largest rectangular put in this position. If all the rectangular can't meet this requirement, then the lowest horizontal line will be updated. Because the time complexity of these two processes is same, the modified approximately packing algorithm can make the code simpler, expand the scope of the search and improve the layout efficiency.Second, the modified approximately packing algorithm is combined with discrete particle swarm algorithm. We proposed a new algorithm to solve the rectangle packing problem. How to construct the sequence is a key issue of the rectangular packing problem. Many scholars have applied genetic algorithms, simulated annealing algorithm and so on to construct sequence, and used the sequence combine with some approximately rectangle packing algorithm to solve the rectangular packing problem, and achieved better results. Discrete particle swarm optimization algorithm is a modified algorithm based on PSO. This article analyzed the discrete particle swarm optimization algorithm, design related operation of applying the discrete particle swarm optimization algorithm to solve the rectangular packing problem, defined the fitness function and apply this algorithms to generate the sequence. Compare the approximately packing algorithm with fitness function of rectangle packing problem, the sequence achieved the value of the fitness function and generated layout designs. Compared with the fitness value of the sequence, the better packing designs are achieved.Then, base on the proposed algorithm, we planned and designed the system's basic functional modules and a system of computer optimizing nesting was developed. Through numerous examples of testing, the algorithm is compared with the test result with genetic algorithm and random algorithm. The experimental results indicate that our algorithm of this system is validity about sheet utilization and packing time. Lastly, author concluded the research on rectangular packing problem and put forward the orientation of the future work.