Font Size: a A A

Based On Genetic Simulated Annealing Algorithm For Two-dimensional Irregular Polygon Nesting Problems

Posted on:2008-01-25Degree:MasterType:Thesis
Country:ChinaCandidate:Y ShiFull Text:PDF
GTID:2208360212479297Subject:Computational Mathematics
Abstract/Summary:PDF Full Text Request
The aim of the computer aided optimal layout of the parts with different shapes is to find the arrangement of parts and producing the least waste. The problem of optimal layout belongs to the NP-complete problem with tiptop calculate complexity. It is very difficult to find the optimal solution for such a problem because of the high complexity of shapes and computation. Conventional layout works all adopt manual operation that have many shortcomings such as low yield, inefficient and long time consuming. People cry for a solution by the modem science and technology because of the need of production. Most of the papers published in this field are concerned with the packing problem of regular shapes (such as rectangle), only a few are about the irregular shapes.A method for disposing the irregular shapes directly is developed based on genetic simulated annealing algorithm, which search optimal shape sequence in the space. The layout of each sequence is fixed by heuristic location algorithm, and then evaluates it by fitness evaluation function, to ensure the good sequence can be preserved in the evolutionary process.In analyzing the existing location algorithms for irregular polygon, this paper presents a new heuristic algorithm based on parallel trapezium decomposition. This method can directly determine the precise location of the irregular polygon, and have good operational efficiency. These excellent performances are that the existing methods do not have. For genetic simulated annealing algorithm, this paper confirms the chromosome coding and the parameters according to the actual problems. The specific individual fitness evaluation function also is given.This theory and method were applied to the development of a system for XX Company. The actual application shows that this method meets the needs of the project, and has good layout results and practical value.
Keywords/Search Tags:Irregular shapes, optimal layout, Heuristic algorithm, Genetic simulated annealing algorithm
PDF Full Text Request
Related items