Employing Subgroup Evolution for Irregular-Shape Nesting
This paper introduces a new method to solve the irregular-shape, full-rotation nesting problem by a genetic algorithm. Layout patterns are evolved in hierarchical subgroups to facilitate the search for an optimal solution in such a complex solution space. The genotype used in the genetic algorithm contains both the sequence and rotation for each shape, requiring new genetic operators to manipulate a multi-type genetic representation. A lower-left placement heuristic coupled with matrix encoding of the shapes and plate prevents overlap and constrains the solution space to valid solutions. This new method is able to efficiently search the solution space for large problems involving complex shapes with 360 degrees of freedom. The algorithm generates better solutions than previously published evolutionary methods.
A. D. Fischer and C. H. Dagli, "Employing Subgroup Evolution for Irregular-Shape Nesting," Journal of Intelligent Manufacturing, Springer Verlag, Apr 2004.
The definitive version is available at http://dx.doi.org/10.1023/B:JIMS.0000018032.38317.f3
Engineering Management and Systems Engineering
Keywords and Phrases
Evolutionary Computing; Gentic Algorithms; Geometric Modeling; Nesting; Optimization; Stock-Cutting
Article - Journal
© 2004 Springer Verlag, All rights reserved.