关键词: 非规则件优化排样, 小生境技术, 遗传模拟退火算法, 启发式布局算法,
临界多边形

Abstract: Aiming at the optimal packing problem of irregular parts, known as a
NP-complete problem, an approach is presented, which combines adaptive niche genetic
simulated annealing algorithm with a heuristic packing algorithm based on the lowest point of
inside no fit polygon. Considering that the choice of crossover probability and mutation
probability will affect algorithm convergence, the adaptive crossover probability and the adaptive
mutation probability are putted forward. The proposed approach automatically looks for the best
sequence of the irregular parts and each part’s optimum rotation angle by the genetic simulated
annealing algorithm which is based on the niche technology. The lowest point of inside no fit
polygon, which is created by the damaged raw material polygon and the irregular part polygon, is
selected to locate the part. Meanwhile, the overlap of the part and the surface defect of raw
material are avoided. Examples indicate that the approach is effective and practical.

Key words: optimal packing of irregular parts, niche technology, genetic simulated
annealing algorithm, heuristic packing algorithm, no fit polygon