A Genetic Algorithm For The Rectangular Strip Packing Problem

The rectangle packing problem exists widely in many industries, such as the mechanical, furniture and costume industries. Solving this problem can save raw materials, streamline production processes, reduce production cost and increase the efficiency of industry. Irregular layouts can be transformed into rectangular packing problems by computer graphics processing technology. The rectangle strip packing problem (RSPP) can be stated as putting some quantified rectangles P1 , P2 ,…, Pn on the given sheet, which is fixed with width and isn't fixed with height, with an aim to minimizing sheet's unused area. RSPP is an importance branch of computer aid nesting. But it is a high computational complexity NP-complete problem in theory. So when 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.The genetic algorithm is global search optimization compute technology based on biology anagenesis and random selection. It simulates biology anagenesis basal progress, uses the Digital gene string to analog the chromosome, and imitate the basal biology evolution progress through choose,cross,mutation and so forth genetic operation. After a number of generations, the problem solution represented by the most excellent chromosome is the ultimately optimization solution or close to the optimization solution. The multi-colony genetic algorithm utilizes some colonies to replace the singular colony, and every colony carry through side-by-side independently evolution according to their own different evolutional strategy and genetic operation. In the progress of evolution the algorithm can choose and reserve the excellent chromosome from each separate colony, so that it could quicken the speed of evolution, at the same time keep the stability of the excellent chromosome s'evolution, and avoid the prematurity phenomena that can be likely to appear if there is only singular colony.Based on the above considerations, in this paper, we propose a simple approach which Just adopts two colonies and can be used to solve RSPP based on the genetic algorithm. The validity of the algorithm is Confirmed by numerous test examples, and the novelty of this research is as follows:First, the thesis proposes an approximate rectangular packing algorithm. We compare and analyze some approximate rectangular packing algorithms proposed by Chinese and foreign scholars. After Aggregating the advantages and disadvantages of these algorithms, we modifie an approximately rectangular packing algorithm based on the Lowest Horizontal Line Searching Algorithm (LHLSA), and denominate the Optimization Insert Algorithm based on the Lowest Horizontal Line. In the progress of placing the rectangular, the length of the lowest horizontal line is compared with present rectangle's length (in this paper, we firstly define the border of the rectangular paralleled X axis is the length, the other border is figured as the width). If the lowest horizontal line is longer than the length, we put the rectangular in this position. Otherwise, the length of the lowest horizontal line is compared with present rectangle's width. If lowest horizontal line is larger than the width, we rotate the rectangular and put the rectangular in this position. If the lowest horizontal line is less than the length and width, that means the present rectangular couldn't be place on the lowest horizontal line, we search back the position in the current sequence, and choose the classic rectangular (the Optimization), which meet the requirements and whose length or width proximal the length of the lowest horizontal line, and put it in this position. If all the rectangular can't meet this requirement, the lowest horizontal line will be updated. We insert the Optimization before the present location, and insure the sequence of the latter rectangular invulnerable. Because this packing algorithm can make the rectangle place compactly, so reduce the height of placing all rectangles, and improve the layout efficiency on a certain extent.Second, the Optimization Insert Algorithm based on the Lowest Horizontal Line is combined with genetic algorithm. We propose a new algorithm to solve RSPP. 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 use the sequence combining with some approximately rectangle packing algorithm to solve the rectangular packing problem, and get better results. The multi-colony genetic algorithm is a modified algorithm based on basic GA. This article adopts the idea of the multi-colony genetic algorithm, utilizes double different initialize strategy to produce double separate colonies which possess near same numbers chromosomes. They take same genetic operators, and evolve side-by-side, and distribute the more excellent chromosome periodically. The article designs related operation of applying the simple multi-colony algorithm to solve RSPP, define the fitness function and introduce detailed how to apply this algorithms to generate the sequence. According to the Optimization Insert Algorithm based on the Lowest Horizontal Line and this fitness function, the sequence achieves the value of the fitness function and generates layout designs. Compared with the fitness value of the sequence, the better packing designs are achieved.Then, base on the proposed algorithm, we plan and design the system's basic functional modules and a system of computer optimizing nesting is developed. Through numerous examples of testing, the algorithm is compared with the test result of some 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 conclude the research on rectangular packing problem and put forward the orientation of the future work.