3.1 Find the minimum envelope rectangle
Below we will discuss how to perform preliminary nesting pre-processing on the unfolded two-dimensional graphics of sheet metal parts. Layout of the processed two-dimensional graphics can achieve the purpose of simplifying the layout model and is more conducive to the establishment of layout rules. In this chapter, the minimum envelope rectangle method will be selected as the pre-processing method of the two-dimensional unfolded graphics, and the convex hull of the two-dimensional graphics will be obtained before the minimum envelope rectangle.
3.1.1 Find the convex hull of a polygon
Popularly speaking, the convex hull of a polygon refers to the convex polygon formed by a string tightly wound around the polygon, and the convex hull of the convex polygon is itself. At present, there are many algorithms for calculating the convex hull of a plane point set, the more classic ones are incremental method, Graham scanning method (Graham), gift wrapping method (gift.wrapping method) and divide and conquer method. The incremental method first establishes the initial convex hull through several points. When there is a point on the outside of the convex hull, this point is added to the convex hull to form a new convex hull until there are no vertices on the outside of the convex hull. The time complexity of the incremental method is O(n2 ), the volume wrapping method uses the basic principle of convex polygons: the vertices of the convex polygon are on the side of the line of adjacent vertices: the time complexity of the volume wrapping method is (n2), and the divide and conquer method is to press all points The coordinate position is divided into two disjoint parts, and the convex hull of each part of the point set is obtained respectively, and then the convex hull of the two convex hulls is the convex hull of all points.
Based on the advantages of the above algorithms, this paper selects the Graham algorithm to optimize sheet metal parts. The basic principle is to convert a polygon into a point set represented by each vertex, and then use the lowest point as the starting point to each other. The points are connected, and then the angle between these line segments and the horizontal line and the length of the line segment are used as parameters. The convex hull of this polygon can be obtained by connecting the points that meet the requirements according to the established rules. Its time complexity is O( nlogn). The specific steps are as follows:
(1) Establish a point set of polygons according to their vertices, as shown in Figure 3.1(a)(b).
(2) Take the point with the smallest ordinate value of the point set as the starting point to connect to other points, as shown in Figure 3.1(c).
(3) Let's say that the endpoints of a line segment are sorted by the size of the angle between the line segment and the horizontal line. If the size of the angle is the same, the second judgment is made according to the length of the line segment.
(4) With geometric knowledge, the points of a convex polygon must be on the same side of any side of the polygon. Connect the points in sequence and delete the points that do not meet the requirements
(5) Update the ranking of the remaining point sets, and connect the points in sequence to form a convex hull.
Figure 3.1 Find the convex hull of a polygon
3.1.2 Solving the minimum envelope rectangle
The enveloping rectangle of a polygon means that any point of the known polygon is within a certain rectangle or the area contained by the rectangle, and each side of this rectangle is in contact with the known polygon, then this rectangle is the enclosing rectangle of the polygon. Any polygon will have countless envelope rectangles, but there is always a rectangle with the smallest area among these countless envelope rectangles. The envelope rectangle with the smallest area is called the smallest envelope rectangle. It can be known from the geometric relationship in mathematics that for convex polygons, the smallest envelope rectangle is the smallest envelope rectangle generated after any side of the polygon coincides with one side of the rectangle. From this, we can get the method to find the best envelope rectangle, the steps are as follows:
(1) The two-dimensional graphics of the sheet metal parts are transformed into convex polygons through convexization. If they are convex polygons, then go directly to the second step.
(2) Make an envelope rectangle, and one side of the envelope rectangle coincides with one of the sides of the convex polygon. The number of envelope rectangles like this is less than or equal to the number of sides of the convex polygon.
(3) Find the area of the enveloping rectangle.
(4) Compare the areas of all envelope rectangles, and select the envelope rectangle with the smallest area as the rectangle we want.
Figure 3.2 Find the minimum envelope rectangle
From Figure 3.2, Figure (a) is a known polygon, Figure (b) is a convex polygon transformed by convexity, and Figures (c), (d), (e) are based on the edges of the convex polygon. Envelope rectangle, Figure (f) is the final envelope rectangle selected by comparison. The purpose of adopting the spherical envelope rectangle: the two-dimensional graphics formed after the sheet metal parts are unfolded are processed by embossing and rectangular envelope processing, which will simplify the two-dimensional graphics of the original sheet metal parts and make the sheet metal parts Automated layout and blanking are easier to achieve, which improves work efficiency, but it is detrimental to the utilization rate of plates. In this regard, some scholars have proposed different methods, such as combining multiple convex polygons or two-dimensional graphics of sheet metal parts to find the minimum envelope rectangle, which is beneficial to improve the utilization rate of materials. Hope that there will be a better solution in future research.
3.2 Commonly used heuristic layout positioning strategy
The layout optimization problem of rectangular parts is a two-dimensional layout problem. For the two-dimensional layout problem, the I Ching has been studied more. With the development of computer technology, artificial intelligence technology has been very good in the two-dimensional layout problem. However, the application of artificial intelligence technology in the two-dimensional nesting problem depends on the positioning strategy of the two-dimensional graphics on the board. This positioning strategy will be based on the obtained coding information on the two-dimensional graphics board, so a reasonable selection and use of positioning strategy to improve the utilization rate of materials and improve the efficiency of layout optimization is very beneficial. Now we introduce several common heuristic positioning strategies for rectangular layout: step down method, lowest horizontal line method, and remaining rectangle method.
3.2.1 Downstairs algorithm
The basic idea of the step-down algorithm is like the human body is going down the steps, so that the rectangular parts are discharged from the upper right to the lower left corner of the plate. The principle of downward movement is the priority during the discharge process. When it cannot move downward, it moves horizontally to the left until it is downward. You can move down according to the principle of priority to move down after you can move. Repeat the movement until the position of the holding part is fixed. The specific steps are as follows (Figure 3.3).
Figure 3.5 Downstairs algorithm
Place the rectangular part A at the position of figure (a), and then move it vertically down to the position of figure (b). When it can no longer move downwards, move it horizontally to the left to the position (c), and then continue to move downwards , And then move down to the position of figure (d) until it can not move downwards and move to the left when moving, and finally the rectangular part A is fixed in the position of figure (e).
3.2.2 Algorithm of the lowest horizontal line
The lowest level refers to the lowest level limit of the sheet material remaining after the sheet material removes the discharged rectangular parts during the discharge process. The idea of the minimum horizontal line method is to always look for the lowest horizontal line that can be placed into the rectangular part when placing each part, and place the parts here, so the minimum horizontal line method will always fill the lowest position. The minimum horizontal line method can avoid the phenomenon that the right side of the lower step method is higher, but the minimum horizontal line method still cannot solve the gap filling problem in the discharge process. The basic steps of the minimum horizontal line method are as follows:
(1) Initialize the lowest edge of the remaining plates as the lowest horizontal line.
(2) Take the lowest horizontal line when the rectangular parts Pi (i=1, 2,...3) are discharged into the sheet, if the width of the lowest horizontal line can update the lowest horizontal line data when the rectangular parts pi are discharged, If the lowest horizontal line has multiple sections, the parts will be placed in the leftmost section. If the width of the lowest horizontal line cannot be used to fill the rectangular parts, compare the two horizontal lines on both sides of the lowest horizontal line and increase the lowest horizontal line to one of the two horizontal lines. At the lower part of the horizontal line, then re-arrange the rectangular part pi.
(3) Arrange all the rectangular parts into the plate.
Figure 3.4 Algorithm for the lowest horizontal line
In the initial discharge, the lower boundary of the plate is the lowest horizontal line, and the rectangular parts 1, 2, 3, 4 are discharged successively, as shown in Figure (a), when the part 5 is discharged, the lowest horizontal line is the upper edge of the part 3, and the rectangular parts The side length of 5 is greater than the width of part 3 as shown in figure (b), so it cannot be arranged here, and the lowest horizontal line is increased to the upper edge of part 4 as shown in figure (c), and the lowest horizontal line data is updated. At this time, the lowest horizontal line is The upper edge of the part 1, and the length of the part 5 is less than the width of the part 1, insert the part 5 here as shown in figure (d).
3.2.3 Remaining rectangle algorithm
The remaining rectangle algorithm is an algorithm that is more suitable for use in computers. The main idea of the remaining rectangle layout algorithm is to digitize the size information and diagonal position information of the plates and parts, and store this information in the data list. Generally, the area in the plate that has been arranged in rectangular parts and the area that has not been arranged in rectangular parts are marked and stored in the data list respectively. The process of arranging rectangular parts into the plate is to arrange the rectangular parts to be arranged into unarranged parts. Area and the process of updating new data. The remaining rectangle algorithm combines the advantages of the BL algorithm in the process of arranging rectangular parts, and achieves the purpose of using the blank area. The basic steps are as follows:
(1) Create a set of remaining rectangles. At the beginning, there is only one remaining rectangle in the set, namely the plate ((0,0)(W,H)), (0,0) represents the coordinates of the lower left corner of the rectangular plate, and (W,H) represents the rectangle The coordinates of the upper right corner of the sheet, and the diagonal coordinates are used to represent the sheet and rectangular parts.
(2) Arrange the rectangular pieces A into the remaining rectangles and update the remaining rectangle set. Assuming that the length of the rectangular part A is h and the width is k, the rectangular part A is placed at the lower left corner of the sheet, and the remaining rectangle set is updated to {f(0,k). (w,H)],[(h,O),(W,k)]) or {[(0,k),(h,H)],[(h,O),(W,h)] ).
(3) Put all the rectangular parts into the remaining rectangle in turn to update the remaining set: ①When placing the rectangular parts in the remaining rectangular area, select the area whose length and width are greater than this rectangle, and place the rectangular parts in the bottom and leftmost position. When selecting the rectangular area to be placed, choose an area with a high degree of matching relative to the part. ②The update rule of the new rectangle set: remove the elements whose area is zero and can no longer fit into any rectangle, remove the rectangle element with the smallest area among the remaining rectangles that have a complete containment relationship, and keep all the rectangle areas that have an intersection relationship.
Figure 3.5 Remaining rectangle algorithm
Figure 3.6 Schematic diagram of segmentation
Several common layout strategies have been introduced above. The layout strategy is to place the parts to be arranged on the board in the layout sequence according to a predetermined method. Through the analysis of the above several nesting strategies, the BLF algorithm has the idea of inserting blanks, so this paper chooses the BLF algorithm as the nesting strategy adopted in this paper. The nesting strategy is to solve the problem of how to place the parts on the plate in order, but the nesting strategy cannot produce the order of the parts. The type of nesting sequence increases exponentially with the growth of the number of parts, and the amount of calculation for generating the nesting sequence is very large. The following introduces artificial intelligence algorithms to provide ideas for establishing a sheet metal part nesting system.
3.3 Artificial intelligence algorithm
3.3.1 Application of Tabu Search Algorithm in Layout
The main idea of the tabu search method is to establish a search structure and a control structure at the same time, and the control structure includes a data table and a search range control system. The data table mainly stores and clears the obtained data values. The search range control system evaluates and processes the data values provided by the search structure, and updates the data table and data search range through the search range control system. The search structure performs the next search based on the return value provided by the search range control system, and then provides the new value obtained from the search to the search range control system for evaluation, while storing and updating data. In this way, after a limited number of iterative searches, the optimal value is taken from the data table as the search result (as shown in Figure 3.7).
Figure 3.7 Flow chart of tabu search algorithm
(1) When the evaluation value of the solution sequence is the best so far, it is evaluated as meeting the requirements;
(2) When the evaluation value of the solution sequence differs greatly from the evaluation value of the current sequence, mark processing should be performed here, and processing should also be performed to meet the requirements.
(3) When the continuously searched values are in the taboo table, in order to prevent entering the local optimum, the sequence with the lower evaluation value is set as the current sequence.
Tabu search algorithm is a loop iterative relationship composed of three parts: search structure, data table and search range control system. The design method of these three parts will determine the efficiency of the entire search process and the search quality. The commonly used search structure is: search in the vicinity of the last optimal value. The design of the search range control system should avoid falling into the local optimum. The method of increasing the data table improves the efficiency of the global search. In the tabu search algorithm, the design of the search structure is relatively flexible, which is suitable for nesting with a moderate size.
3.3.2 Application of simulated annealing algorithm in nesting
The simulated annealing method is a highly versatile optimization algorithm. It applies the simulated annealing process in metal thermodynamics to the solution of the nesting problem. The simulation heats the solid to high enough, the internal energy increases, and the internal organization gradually becomes disordered. When the temperature decreases slowly, the solid tissue at each temperature can reach a stable equilibrium state, and the internal energy also reaches the minimum. As shown in Figure 3.7.
Inner loop: ①The neighborhood solution is generated from the current solution through the determined neighborhood search structure. Commonly used neighborhood search structures include random search methods and methods of transforming the elements of the solution: ②Calculate the neighborhood solution and the goal of the current solution Poor function; ③ judge whether the neighborhood solution is accepted as the current solution or the probability value of being accepted as the current solution; ④ judge whether the termination condition is reached, if not, judge whether the number of cycles is reached, if not, return to ①. Outer loop: If the inner loop is completed, decrease the value of D before entering the inner loop until the termination condition is reached, the calculation is terminated, and the current solution is output as the optimal solution.
Figure 3.8 Flow chart of simulated annealing algorithm
The idea of simulated annealing algorithm SA (simulated annealing) was first proposed by Metropolis et al. In the process of falling from a higher temperature to a lower temperature, the probabilistic description of understanding is increased through the Metropolis acceptance law, so that the search for the optimal solution can jump out of the local optimal and tend to the global optimal. The simulated annealing algorithm has progressive convergence. In theory, it is a global optimization algorithm that converges to the global optimal solution with probability 1. But it requires that the initial temperature is high enough, the cooling process is slow enough, the cooling time is long enough, and the termination temperature is low enough. If the above conditions are met, the calculation amount will increase accordingly.
3.3.3 Application of genetic algorithm in nesting
The genetic algorithm was established in 1975. Professor Holland gave the basic theorem of genetic algorithm and a large number of proofs of mathematical theory. The principle of genetic algorithm: an algorithm produced by imitating the evolutionary theory of humans or other species. It is used for the selection of arranging sequence. The superior sequence factors are retained and the inferior sequence factors are eliminated, so as to select sequences that meet the conditions. The use of genetic algorithm first needs to determine the coding method, that is, to number the parts. Commonly used coding methods include binary method, decimal method, and mixed coding method. Then genetically manipulate the code:
(1) Copy operation, through the evaluation of the individual fitness value of the parents, according to a certain ratio
The rule re-determines the proportion of individuals in the population through the duplication operation to form a new offspring population, thereby increasing the proportion of individuals with high fitness in the population. This step is more flexible in actual operations;
(2) Crossover operation: randomly pair the individuals in the parent population to perform crossover operations to generate m individuals to form the offspring population. Commonly used crossover methods are: single-point crossover, double-point crossover;
(3) Mutation operation: Mutation operation is to change the value in the code with a small probability. Commonly used mutation methods include rotation mutation and position mutation, that is, changing the placement angle and placement of the parts.
Decode the codes obtained by genetic operations. The purpose of decoding is to convert a set of codes into a layout map. Commonly used decoding methods include BL method, lower step method and lowest horizontal line method. Evaluate the nesting chart to determine whether it meets the termination criterion. Commonly used termination criteria include fitness value and generated genetic algebra. If yes, stop the calculation and output the layout data, if not, enter the genetic operation again to generate the next generation code. The genetic algorithm solving process is shown in Figure 3.9.
Figure 3.9 The solution flow chart of genetic algorithm
Genetic algorithm is to digitize the nesting problem by coding the nested parts. The object of genetic operation is these data. Therefore, it is less restricted by the problem itself during the nesting process, and genetic algorithm has strong versatility. Through mutation and probabilistic selection of codes, early convergence is avoided. The open structure of genetic algorithm is conducive to integrating with other algorithms to improve efficiency and accuracy, such as adaptive genetic simulated annealing algorithm, niche genetic algorithm, etc.
3.3.4 Application of particle swarm algorithm in nesting
The particle swarm algorithm is inspired by observing the flight rules of bird groups. Birds use the sharing of information among individuals in the group to make the movement of the entire group change from disorder to order. Similar to genetic algorithm, it is optimized through iteration. The key point of genetic algorithm is crossover and mutation, and the key point of particle swarm algorithm is to always follow the guidance of optimal particles. The particle swarm algorithm process is shown in Figure 3.10.
(1) Set the parameter values c1, c2, the maximum evolutionary algebra and other parameters, and initialize a group of particles with a size of n, including random positions and speeds;
(2) Evaluate the fitness of each particle;
(3) Select the position with the best fitness from the current particle swarm and P1 as the new p1; select the position with the best fitness from the entire particle swarm and pg as the new pg;
(4) Change the speed and position of the particles according to the particle movement formula;
(5) Determine whether the termination condition is reached. If satisfied, output the global optimal value, otherwise return (2).
Figure 3.10 Flow chart of particle swarm algorithm
The particle swarm algorithm has good convergence performance and robust performance, its structure fusion is strong, the parameters are simple, and it is suitable for combined use with other algorithms. However, the particle swarm algorithm has the shortcomings of local extreme points, poor local search ability, and strong dependence on parameters. Therefore, many scholars have proposed improved strategies, such as Dou Quansheng, who proposed simulated annealing and particle swarm optimization with division of labor strategies. , Improved the poor local search ability of the particle swarm algorithm. The calculation results have been greatly improved. Gao Ying et al. proposed a composite algorithm combining particle swarm algorithm and immune algorithm, which improved the ability to get rid of local extreme points, and improved the speed and accuracy of convergence. Li Hui proposed a tabu particle swarm algorithm combined with a tabu search algorithm.
Particle swarm algorithm also has the advantages of simple and easy implementation, few adjustable parameters, and fast convergence speed. For the optimized layout of relatively single layout parts or relatively regular part contours, it is helpful to avoid the problem of local convergence and improve the efficiency of layout.
3.3.5 Application of ant colony algorithm in nesting
Ant colony algorithm is a simulated evolutionary algorithm. From the perspective of biological evolution and bionics, the Italian scholar Dorigo et al. proposed the ant colony algorithm to study the behavior of ants in finding paths, and used this method to solve TSP problems, secondary formula problems and job scheduling. In the problem, it shows its advantages in solving more complex discrete problems. Particle swarm optimization is a promising intelligent calculation method. The following is a simple description of the application of ant colony algorithm in the layout of rectangular parts. .
The ant colony algorithm calculation process:
(1) The ants are randomly placed on n rectangular pieces
(2) Initialize data
The information of the rectangular piece, related system parameters, the amount of information of the rectangular piece and the amount of information on the path;
(3) The action of a single ant
①The i-th rectangular piece moves to the next rectangular piece j according to a certain movement rule;
② Update the amount of information for the rectangular piece i, j and the path of j→i according to the established rules;
③Store the rectangular piece j in the taboo table [n], and do not repeat the visit;
④Repeat ①②③ into n rectangles for all visits, and finally form a path arrangement;
⑤Generate a layout drawing according to the predetermined layout algorithm, and calculate the target value:
(4) If there are m ants, there will be m path arrangements and their target value results;
(5) Find the current best ant and compare it with the best ant so far, choose the better one as the new best ant so far and save it;
(6) Globally update the information on the path of the best ant so far according to certain rules, and check whether the predetermined termination condition is reached, then terminate the calculation and output the optimal result. Otherwise, repeat (3), (4), (5).
The ant colony algorithm has a positive feedback function, a strong heuristic ability, and can quickly find the optimal solution: distributed computing is beneficial to avoid premature convergence, jump out of the local optimal solution, and search for the optimal solution in the world. However, the distribution of the initial information of the ant colony algorithm will affect the search results. The ant colony algorithm adopts a random strategy, and the convergence speed is slow in the initial stage. The improvement measures mainly include path selection, pheromone update, multiple ant colony algorithm, and combination with other algorithms.
Artificial intelligence algorithms have good results in solving nonlinear problems and non-deterministic polynomial solving problems. This article briefly introduces several nesting algorithms. Each algorithm has different principles, and also has its own advantages and Disadvantages, appropriate nesting methods should be selected for different nesting conditions. In practical applications, artificial intelligence algorithms and heuristic algorithms are often used to combine nesting algorithms to solve nesting problems. Neural network algorithms have a wide range of applications and a high degree of intelligence, but the algorithm design process is complex and difficult to implement, requiring more research. With the development of computer technology, more high-quality algorithms will emerge, computer-aided layout technology will continue to be improved, and the application of artificial intelligence technology in layout optimization will become a development trend.
3.4 Summary
This chapter is based on the content of the previous chapter, specifically discussing how to optimize the layout after irregular parts are transformed into rectangular parts. This chapter explains the overall steps of sheet metal parts layout optimization. First, the unfolded sheet metal parts are embossed and the smallest envelope rectangle is obtained, and then the sheet metal parts are optimized based on the layout algorithm of rectangular parts. .
This article discusses the principles and advantages of a variety of artificial intelligence nesting optimization algorithms, and also introduces the application of several commonly used rectangular part positioning strategies in sheet metal parts nesting optimization. Through the research in this chapter, the overall idea and solution of sheet metal parts layout optimization are established, and at the same time, it provides a reference for deeper research. In addition, in the future research, we need to pay attention to the three parts of mathematical modeling of irregular parts, comprehensive and efficient positioning strategy, and stable layout algorithm.
