Vol.16, No.2 .2005 Journal of Software Software Dictionary 1000-9825 / 2005/16 (02) 0316
Effective method for leather optimization of the sample. Zhang Yuping 1, 2 , Zhang Chunli 1, Jiang Shouwei 2 1 (School of Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai Jiaotong University Machinery and Dynamics, Shanghai 200030) An Effective Approach for Leather Nesting ZHANG Yu-Ping1,2 , ZHANG Chun-Li1, JIANG Shou-Wei2 1 (School of Mechanical & Electrical Engineering, Shanghai Normal University, Shanghai 200234, China) 2 (School of Mechanical & Dynamic Engineering, Shanghai Jiaotong University, Shanghai 200030 CHINA) CORRESPONDING Author: Phn: 86-21-57122373, E-mail:
YP_ZHANG@shnu.edu.cn,
Http://www.shnu.edu.cn receivated 2003-10-24; ACCEPTED 2004-04-01 ZHANG YP, Zhang Cl, Jiang SW. An Effective Approach for Leather Nesting. Journal of Software, 2005, 16 (2) : 316.323.
http://www.jos.org.cn/1000-9825/16/316.htm Abstract: This paper presents an effective nesting method for leather manufacturing, such as automobile interior decoration, etc. After the profiles of leather sheets and stencils are obtained, they are discretized to make the processing independent of the distinct geometry. The constraints of profiles are thoroughly considered. A heuristic bottom-left placement strategy is employed to sequentially place stencils on sheets. The optimal placement sequence and rotation are deterimined using a simulated annealing based genetic algorithm (SABGA). A natural concise encoding method is developed to satisfy the possible requirements of the leather nesting problem. Experimental results show that the proposed mehtod not only can be applied to the normal two-dimensional nesting problems, but also Can Be Especially Suited for the Placement of Multiple Two-Dimensionally Irregular Stencils on Multiple Two-Dimensionally Irregular Sheets As Well. Key Words: N Esting; Genetic Algorithm; Irregular Leather; Two-Dimensional Geometry Abstract: According to industry needs such as automotive interiors, the optimized sampling of leather products is studied. Innovative use of discrete treatment, and introduce boundary constraints To make the sample process independent of the geometric information of the shelf and the sample, the sample-based heuristic bottom left layout is sequentially arranged to the skin, and the optimal arrangement order and angle of the sample rely on the random optimization algorithm. Design Simple, practical operation operator, and proposed a genetic algorithm based on analog annealing technology (SABGA), which can optimize the performance of the variants in optimization of the search, so that optimization efficient approximation The optimal solution. Experiments and comparison results show that the proposed optimized row mode is especially suitable for optimized drain on multiple two-dimensional irregularities in multiple two-dimensional irregular planes. Key words: optimized row; genetic algorithm; simulated annealing Illegal leather; 2D geometry. Supported by the science-technology development Foundation of Shanghai of China under grant No.005111081 (Shanghai Science and Technology Development Fund) Author: Zhang Yuping (1963-), female, Zhejiang Ninghai, Ph.D. Associate professors, main research areas for CAD and optimization technology; Zhang Chunli (1972-), female, doctoral, associate professor, main research field is CAD and optimization technology; Jiang Shouwei (1939-), male, professor, doctoral tutor, major research field For CAD and optimization technology. Zhang Yuping et al: an effective method of optimizing the sample 317
MACK CD number: TP391 Document Node: A 2D geometric row of row of moisture, light industry, microelectronics, etc., such as metal sheet, wood, glass, leather, cloth, etc. It is widely used in life, in addition to leather clothing, shoes, bags, furniture, more involved in car, luxury cruise ships and other interior fields. Clemarant material cost is high, the shape is irregular, the quality is uneven, the design constraint has more conditions Regularity, it is made challenging on the skin, especially in multiple skin, is aimed at industry demand for automotive interiors. This paper has been studied for optimized oriented row of leather products, and discusses any arbitrary How to optimally arrange the sample on the shape of the skin, and the research results can be directly converted to other industries. So far, many algorithms have been used to solve different sampling problems [1]. For two-dimensional irregular samples, Bennell [2] and GOMES [3] The processing method used by the critical polygon (NFP) can perform efficient sampling, but due to the limitations of the geometric contour processing mode, the sample is not allowed to rotate in two-dimensional emissions planes due to the NFP. Does not comply with the actual situation of the sample in the skin. Heistermann [4] introduced the optimized drain package for the leather industry, who used to use the greedy search method, divided into a moving material Live Region and Dead Region, the active area can be drained, the dead zone is unmissible. The problem is: 1) Samples, because the irregular geometry is used to approach the small line segment, If the size is large, its row is more difficult;
2) In terms of the skin, if the surface of the skin is flawed, the more the hole needs the sample time. When there are more than 5 times, the sample time has increased dramatically, making it spending time that the row is time, It is necessary to use a bridge special treatment, so that each empty hole is dead. This treatment has a restriction condition, which is that the length of the bridge cannot be long, otherwise the sample cannot be tightly ranked next to the empty hole, which seriously affects the material utilization. Inspiration The layout of the algorithm is given to the selection algorithm, and there is no different arrangement order and mode. Researchers attempt to adopt certain random approximation algorithms [5, 6], such as annealing (SA) and genetic algorithm (GA) and artificial simulation network (ANN) to complete. Heckmann [7,8] and other people use an annealing algorithm to solve, which considers any angle of rotation of the sample, mainly for the textile processing industry, considering the color when row The striped constraints, the target function of the set is composed of two parts, one is the occupied area, the other is a penalty function of the overlap area, and the neighbor space is obtained by a variable parameter. The defect of this algorithm is sometimes fell into local optimal. . Hopper [1] and Jain [9] introduced their genetic algorithms used in solving the problem, but its research mainly was launched for the geometry. The experimental results show that the use of genetic algorithms has achieved good Effect. Hopper more focused on the layout strategy of the drain, for the "bottom left" layout strategy to produce large unscapsed area defects for large-area rectangular shapes, proposed "bottom left filling" layout scheme, the experimental results given It is also further proved to prove the effectiveness of the "bottom left fill" strategy. However, the above algorithm is only possible for single raw materials, this author proposes optimization of two-dimensional irregularities in multiple two-dimensional irregular planes. Coampling algorithm. In order to minimize cropping materials, and improve row efficiency, the discrete technique is independent of the treatment process and the geometric contour information of the leather and the sample to the skin and the sample. Genetic algorithm makes diversity can be implemented in a more natural way, using heuristic bottom left layout strategies to achieve polypothelial moiety with this new processing strategy. System flow is shown in Figure 1. Output Optimal result discretization of geometricalInformation placement sequenceand encoding design SABGA combination strategyConversion system for data forms CADplatformDigitizer Production User interactionLeathers and stencils Scanning device Fig.1 Flow di Agram of the Leather Nesting System Figure 1 Leather Optimized Crash Process 1 Geometric Information Acquisition and the geometry of the processes and samples are two-dimensional irregular, first to obtain the original geometric information and process them. Existing There are many ways to obtain them, such as: (1) scanning skin, according to grayscale and color difference, use software to convert the contour graph of the leather. (2) Directly to directly get a flexible profile. According to now With equipment and other conditions, we used the second method in the experiment. 318 Journal of Software Software 2005, 16 (2)
1.1 The rotation angle sample of the sample can consider some constraints on the leather arrangement. The skin itself has a positive and reverse surface, so the general sample can be discharged at an arbitrary angle on the single angle on the plane of the leather. Considering the brightness of the skin products, some samples may not be allowed to rotate at an angle, or allowed to rotate within a small angle, and for the angle limit can specify the sampling angle of each sample when the sampling. 1.2 Geometry The discretization of information is expressed in a two-dimensional irregular geometry. From the existing literature, most of them use multiple short straight line approximation to describe the curve method, during the row, mainly through the approximation of each smear contour The small fold line and the matching of the approximation small fold line to be discharged on the skin, but there are very differences that some of the sample results will be very different. Since the cortical material itself is in the shape of an irregular curve, Therefore, if there is a method of detaching from the geometry of the skin and the sample, it will be very beneficial. Important by pixel processing [10], we propose discrete processing method. According to the accuracy of the actual use of the skin We use the virtual grid with the spacing to enclose the graphic to the smallest virtual grid rectangle. T is determined by the user according to the actual needs, by retrieving whether there is a leather or the profile of the sample in each virtual grid cell, will each The small area is defined as 0 or non-0 to discrirtize the fur and sample. Here we define such a minimum surrounding rectangular mesh for virtual constraints, the corresponding rectangular grid profile box referred to as virtual constraint rectangular box. For example, The actual discretization treatment of the sample graphics is as shown in Figure 2, and we abstract some special examples of magnification. For samples, if the sample is specified: If you retrieve in the virtual grid small area, Then define 0, indicating that it is necessary to discharge at the corresponding position; the rest is non-0, indicating non-discharge, as shown in Fig. 2 (b), Figure 2 (c) shows a hole in the figure. All non-emissions in the figure. The target number is not 0, but for the subsequent retrieval positioning, we use the number in the process. This makes it easy to determine the distance moved in the X direction in the X direction in the X direction. Figure 3 shows the emission speed. Figure 3 shows the skin The case of the sample 1, the sample 2, and the sample 3 are discharged, where there is a hollow in the sample 3, and the sample 1 can be placed inside the empty, and the value in the virtual grid is indicated in this emission. Results of the variation of the value. (A) Stencil 1 (b) Stencil 2 (c) Stencil 3 Fig.2 Discrete Grids and corresponding Pixel Values of Different Stencils Figure 2 Durable Virtual Constraints After Samples Difficult Virtual Constraints and Grids Fig.3 Discrete Grids and the Correspond ING PIXEL VALUES AFTER THE PLACEMENT Figure 3 Leather Discrete Virtual Constraints Map and Correspondence Grid value to convert vector data files (DXF, IGES, etc.) to the virtual grid form of the virtual grid used in the row search, first Need to construct a data structure: struct steel / * Defines the data structure on each virtual grid area in the Swatch Virtual Constraint Rectangle * / {Int Spixel / * Sample Virtual Constrained Pixel Value in Virtual Grids in the Virtual Constraints in the Rectifier Box, which The value is defined as: the respective virtual grid spixel values covered by the samples are 0, and the sample contour intersects or coincides with each virtual grid, its spixel value is also 0, and the other is not 0 * / int SVALUE / * sample virtual If the grid value on each virtual grid in the constraint rectangle is 0, indicating that there is a swatch unit on the grid area, the sample space is required, and the non-0 means no sampling space * / int SDIR / * sample contour in the virtual The current grid position or state of the adjacent grid of the adjacent grid is obtained in the constraint rectangle. It is 4 species, 0, 1, 2, and 3, respectively, indicating the grid relative position, and is at the lowest or local minimum. The relative position of the grid is in the rising state, the grid relative position is in the overall or local highest, the grid relative position is in the decreased state * / int SNUM / * Sample closed contour mark, set the outermost contour 1, internal holes The cave closed contour can be ranked 2, 3, etc. * /}; Zhang Yuping, etc.
After discrete conversion algorithm, the geometric information of the skin and the sample is converted into a set of grid value information for the minimum virtual grid rectangle, here only gives the samples of the sample. 2 Search policies and operator operations If you want to discharge a variety of samples on the skin, you must first solve what kind of arrangement is used to position the samples one by one by one, and only the order is determined, it can be traversed according to the algorithm used, and find the most emission One of the best. We use the way the heuristic bottom left sequarters (see Section 2.1), the arrangement order and angle of the sample rely on SABGA (Simulated Annealing Based Genetic Algorithm) optimized (see Section 2.2). 2. The heuristic bottom left layout is placed onto the skin, mainly in the X coordinate direction, sequentially retrieves the Lvalue value of each grid area on the fur, if 0, position the sample to Therefore, then the SVALUE value in the positioned sample area is sequentially retrieved is completely 0 matching the Lvalue value of the fur, if successful, the sample is discharged, if there is a 0 case, view the Lvalue value, will sample the sample The overall movement of the LVALUE value distance in the X forward direction, then retrieves until it meets the conditions. When a single skin is full, it can be exchanged for a new type of leather, continue the above process until all the samples are all tied. During the period, the reasonable perspective of the appropriate sample selection order and the reasonable angle of the plaza is acquired by a combined optimization method. BeGin (L [X] [Y]: Leather, S [x] [Y]: Sample) Foreach (all can have a certain angle Parts Set) Virtual Constrained Rectangle Frame of Positioning Sample S [0] [0] to the bottom left corner L [X] [Y]; while (1) Application Scanning Technology for the Leather Virtual Constraint Rectangular Box (See Section 2.2); if (determine if this location is accepted, if the received) is scheduled, Break; ELSE obtains the leather L [X] [Y] .lvalue value, positioning the sample forward in the X-axis Point S [0] [0] Move to X = X L [x] [Y] .LValue; if (the sample to be row is intersronized with the leather virtual restraint rectangle when the X direction), move the row from the head Retrieval, ie Y = Y 1, x = 0; if IF (Sample of the sample to be row with the upper boundary intersect of the single boundary) / * indicates that the shelf is no longer rowned * / check if the leather material is empty If it is, the entire sample program is terminated; otherwise, the next type is extracted and the sample S [0] [0] [0] is sequentially extracted to the bottom left corner L [X] [Y]; ENDIF ENDIF ENDWHILE ENDFOR End 2.2 Scanning Technology Scanning Technology is to compare the pixel values of the sample area to the pixel value of the corresponding area of the corresponding area on the skin, such as If you meet the requirements are 0, you receive it, indicating that this location can be discharged, if not 0, use the heuristic algorithm, moving the sample, or other adjustments in Section 2.1, and then use the scanning technology to search. 3 optimization method After processing, various samples can be discharged to multiple skin, but whether the most provincial materials need to be used to adopt a practical optimization algorithm. To this end, we propose a new combination optimization method, a kind Improved GA algorithm can effectively search the optimal emission order and the rotation angle of the sample. 3.1 Coding of the skin and the sample indicates a simple, abstract coding method, which contains multiple skin Treatment of materials. First, all kinds of leather items 1, 2, 3, etc. 320 Journal of Software Software Journal 2005, 16 (2)
The sample number, the sample is also numbered. When the sample is fixed, the sample can be fixed according to the need to rotate in the plane 360 ° according to the needs. At this time, the encoding method shown in Fig. 4 can be expressed on a number of shelves. Differential emissions of multiple samples of different angles are required. For example, six different types of different types of shapes are discharged on 1, 2, and 3, each sample can have different rotation angles. Specific emission sequence see 4 The coding table, first of all the sample 2, rotate 80 ° discharge, then it is 3, 1, 4, 6, and 5, and their respective angles. Fig.4 placement sequence and orientation encoding Figure 4 Price and sample Part NumBerspart Number Rotation Angle 3.2 Cross and Variation Operator Defines the individual's adaptation function as follows: f = 1 / (A1 A2 ... AI ... AN.1 PN) (1) above AI (i = 1, 2, 3, ..., n.1) represents the area of the i-th possible, PN represents the area of the neotheraque area. For a set of discharged samples, if The smaller the sample results A, the higher the corresponding adaptivity value corresponding to this set of samples. Generally, the cross-mutation operation is preferably an individual having a high or higher adaptivity value. The cross process is shown in Figure 5. The selection of PARENT 1 and PARENT 2 for selecting higher adaptivity values, and randomly selects the number of two positions, one specified in the leather coding area, one designated in the sample coding area, as shown in the coding sequence of Parent 1. On the first part of the coding on the right side of the specified location, it is copied into the new constructed code string, such as intermediate, the vacancy code in Intermediate, in the encoding order of Parent 2, will be filled in the order in the order of the Parent 2, so that the cross is completed. Operation, a sub-generation structure. Figure 6 shows a mutation process because the code is divided into two regions, and there is a variation parameter-rotation angle in the sample area code, so the mutation operation is divided into two parts, one is the skin The order of the materials and the samples, since the respective serial numbers correspond to each different individual, so when the change is changed, two random locations in each of the different areas, then exchange the code corresponding to the code, that is, the variation operation, as shown 6 (a) indicated. It is possible to change the angle of rotation when the sample is discharged, as shown in Figure 6 (b), is specified in a certain probability, the corresponding sample angle can range from 0 ° to 360 ° Changes. Fig.5 Process of Crossover Operation Figure 5 Cross Operation Procedure FIG.6 Process of The Mutation Operation Figure 6 Multiplexing operation processes cross and variation operations The probability of the probability, the cross probability is recorded as PC, and the variation probability is written as PM. The selection of its value is a relatively sensitive problem. Experiments show that the cross-rate PC should be relatively large, generally take a fixed value, we use orthogonal experiment The method of the cross-rate is studied, and finally determined to be 0.4. Relative crossward rate, the determination of variability is much more difficult, more influence on the results of the sample, more direct. To this end, we have conducted more research And experiments, found an effective solution, thereby proposing a new combination optimization method. Experimental results show that such processing methods are very effective. 3.3 Genetic algorithms based on simulated annealing technology are optimized using ordinary genetic algorithms During the ordering process, the algorithm does not function efficiently, and the optimization process has a premature convergence. The reason is due to the lack of diversity due to the lack of diversity, resulting in early convergence. On the other hand, determining the sensitive fixed variation rate is a complexity Problem. Simulated annealing technology is a universal approach, not a special algorithm [11], so we innovately develop genetic algorithm based on simulated annealing technology SABGA, algorithm variability by a specific cooling curve The temperature is controlled. Since only one parameter is used, the Cauchy cooling method is used [12], the detailed algorithm is as follows. Zhang Yuping et al: Method for optimizing the sample 321
SABGA combination algorithm. (N: population size. Α, β: variables are used to represent individuals in the population. T0: initial temperature .T: Temperature.) Start 1 input sample and leather geometry and angle constraints; 2 random Initialization of the first generation and sampling T0; 3 on individual valuation of the first generation; 4 while not (stopcriterion ()) / * external loop * / 5 While (InnerLoopcriterion ()) / * internal loop * / 6 Foreach (N * Cross Rate) 7 Select the first dupe based on the level selection method; 8 randomly selects the second duplex; 9 for crossover operations; 10 EndFor 11 Select the appropriate degree from the parent and child generation The maximum N individual body is also a new generation; 12 foreach (n / 2) 13 is mutated for a cloning body β of an individual member α; 14.c = COST (β) -COST (α); 15 IF (. C <0) 16 α = β; 17 else IF (u (0, 1) ≤ E..C / T) / * u (0, 1) is a uniform distributed random number generator * / 18 α = β; 19 ENDIF 20 ENDFOR 21 ENDWHILE 22 Update T and Variable Rate; 23 EndWhile 24 Outputs the best sampling result; end after entering the geometric information and constraints of the leather and sample, randomly generates the first generation, initial temperature T0 and specific The size of the problem is related to the area average of 5 random layout states, and stopcriterion () determines the conditions of the termination of the evolution process, that is, the average adaptation degree in a certain generation is not less than the best fitness, or in a predefined continuous continuous There is no advancement in the reproduction, or a set of pre-specified dyezers have been completed. InnerLoopcriterion () controls a specific local balance process during the entire evolution, and 10 generations as a partial loop, wherein the temperature and variable rate remain stable. During the replication process, after the cross operation is completed, establish a new derivative generation. The variation operation is based on the individual members of the new derivative generation, which not only strengthens the effect of random disturbance, but also improves the runtime. Insufficient. The variation operation is acting on the clones of a member individual, and if the value of the clones after the variation is less than the original individual or meet the Metropolis formula, the original member individual is replaced, otherwise the cloning body after the variation is given. Internal circulation The body is complex in the external cycle, the temperature and variant rate is updated outside the internal cycle body, and finally outputs the optimal individual. 4 Experiment We carry out a large number of experiments to verify the effectiveness of the proposed algorithm, mainly divided into two categories, one Class is for all kinds of irregularities The shape of the sample of the sample in one or more layers mainly examines the practical results of the method. The other is extended, the sample of other materials such as cloth, metal sheet, we experimentally various linear polygons The sample is compared in the rectangular or linear polygonal plane, and compared with Goms [3], Heistermann [4] and Jain [9]. All our work is implemented with C programming, use The computer microprocessor is Pentium II, the main frequency 333MHz, the memory 128 MB, the operating system is Windows. Figure 7 is an experiment of selecting 10, 20, 30, 65, and 100 five different populations, it shows the size and obtaining The results of the optimization results are the relationship of the algebra, and the results show that the algorithm is gradually convergent. For the size of the population at 30 to 100, similarity, after about 650 generations, the new variation characteristics have been lost, and the results have been generated before convergence In order to reduce the calculation time, we set the number of groups of 30. Figure 8 shows the experiment of 64 irregular samples on three irregular skin, 9 flaws on the skin, emitted 26 samples, Materials Lee 322 Journal of Software Software Journal 2005,16 (2)
There are 2 2 2 2 2 2 排 排 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕 瑕The effective material utilization is 73.6%. A total of 760 generations, cost-consuming CPU time is 43'22 ". Use our geometric processing method, can recognize holes well in the row, the obtained row can achieve Requirements. From the perspective of the rules, it is not a larger area of samples to get higher row efficiency, which requires global determination according to the specific shape of the sample and the fur, 6065707588525125725GenerationMaterial USAGE RATE (%) 10203065100 a) 9 flaws (b) 2 flaws (c) 1 flaw fir.7 the effect population sizes Figure 7 Different groups of scale running efficiency fig.8 Nesting results in Three Sheets Figure 8 Non-regular samples in 3 skin Absewise Sample Our Approach Our Approach Our Approach Heistermann [4] Approach Gomes [3] Approach Jain [9] Approach (a) (b) (c) Fig. 9 Compension Between Our Approach and the approaches from heistermann [4 ], Gomes [3] and Jain [9] Our method and heistermann [4], gomes [3] and jain [9] method for linear polygon samples in a single rectangular plane in a single rectangular plane Example 1981852645712944510020030040081.9% 71.2% 79.8 % 62.5% 100% 100% 60% 70% 80% 90% 100% Our Approach Gomesheistermannjainab (D) Comparison of Material Usage Rates ABC (E) Comparison of Runtimes relative to Heistermann [6] and Gomes [6] and Gomes [8] Sampling method, three sets of comparative experiments here, as shown in Figure 9. Figure 9 (a) is an emission of 15 to 20 given samples on a single given skin, with me In all of the methods, 15 samples have been obtained by 427 generations, which are not only used than the heistermann method, but also increased by about 10%. Fig. 9 (b) is a plane in a length of a length limit. In-room discharge 43 polygon samples, our method is to use the left floor strategy, so it is necessary to first rotate the sample plane, becomes a height variable plane, after 601 generations, the optimization results are obtained, Turn 90 ° back to the origin. Compare the results of GOMES method, increased drainage efficiency by 12.49%. Figure 9 (c) is a slight of three 14 linear polygonal samples on a 40 mm × 60 mm rectangular plane. By numbers through Table 1 It can be seen that we propose the effectiveness of the method. The efficiency of the group experiment and the comparison of CPU runtime are shown in Fig. 9 (d). The above two types of experiments show that the optimization method we propose quickly Effectively emissively discharge each type of sample into a single or multiple planes, especially in which it can flexibly complete the function of non-rule-shaped swatches on a plurality of irregular planes, and the material utilization can be More than 70%, the sample time is within the range of the user, and 50 samples can be completed within 1 hour, which is acceptable for the leather processing industry. Zhang Yuping, etc.: Leather Effective method for optimizing the sample 323
Tabel 1 Comparison between our apporoach and the approach from Jain [9] on an example of nesting multiple polygon parts in a single rectangle in Table 1 are two methods of data comparison nesting Method Our approach Jain [9] approach Pattern size (mm × mm 40 × 20 25 × 45 25 × 40 20 × 45 × 40 Number of Generations 302 1 10 20 100 UTILIZATION (%) 100 71.1 80 88.8 100 CPU TIME 2'9 "21" 1'32 "2'49" 7 '25 5 Conclusion The text is creatively discretized, and the border constraint is introduced, and the processing target of the subsequent algorithm is unified, and thus the proposed optimized row mode is particularly applicable to the shaped irregular two-dimensional body. Using geometric information discretization processing, completely solve the problem of contour geometry constraints, the order-based bottom left discharge strategy makes optimized sampling smoothly, the selection of the sample order and the rotation angle relies on the SABGA algorithm to search completion. SABGA algorithm set The advantages of GA and SA, it also handles the variability of the variability in the completion of the sort search, and uses the special temperature of the simulated annealing algorithm to apply adaptive control, which is controlled by a temperature that satisfies a specific cooling curve. The random chromosome change of the genetic algorithm is relatively large in the initial stage of optimization, then getting smaller and smaller until the last search converges, supprested the premature conjunction of the optimization process. We propose this optimization method not only applies to irregularities Samples of single or more irregular surfaces, also applicable to rules forms on a single or multiple regular planes, and the experimental results show that our processing method is widely used. References: [1] Hopper E , Turton BCH A review of the application of mete-heuristic algorithms to 2D regular and irregular strip packing problems Artificial Intelligence Review, 2001,16:.... 257.300 [2] Bennell JA, Dowsland KA, Dowsland WB The irregular cuttin g-stock problem-A new procedure for deriving the no-fit polygon Computers and Operations Research, 2001,28 (3):... 271.287 [3] Gomes AM, Oliveira JF A 2-exchange heuristic for nesting problems European Journal. O / Operational Research, 2002,141 (3): 359.370. [4] Heistermann J, Lengauer T. The Nesting Problem in The Leather Manufacturing Industry. Annals of Operational Research, 1995,57: 147.173. [5] xing wx, Xie Jx. Modern Optimization Calculation Methods. Beijing: TSHINGHUA UNIVERSITY PRESS, 2000 (In Chinese). [6] Reeves Cr. Modern Heuristic Techniques for CombinationMs. Oxford:
