缺陷板材非规则件优化排样  

Optimal Packing of Irregular Parts on Plates with Defects

作　　者：董德威[1] 颜云辉[1] 

机构地区：[1]东北大学机械工程与自动化学院,辽宁沈阳110819

出　　处：《图学学报》2013年第2期31-37,共7页Journal of Graphics

基　　金：国家自然科学基金资助项目(50574019);国家高技术研究发展计划(863计划)资助项目(2008AA04Z135);中央高校基本科研业务费专项资金资助项目(N100603002)

摘　　要：针对理论上属于NPC问题的非规则件优化排样问题,论文提出一种基于小生境技术的自适应遗传模拟退火算法与基于内靠接临界多边形最低点的启发式布局算法相结合的方法。考虑到算法中交叉概率和变异概率的选择影响到算法收敛性,提出了自适应的交叉概率和变异概率,通过基于小生境技术的遗传模拟退火算法对非规则件排样的最优顺序和各自的旋转角度进行优化搜索。将非规则件定位在有缺陷原材料和非规则件多边形的内靠接临界多边形最低点以实现个体的解码,同时避开了原材料表面缺陷。排样实例表明,该优化排样算法行之有效,具有广泛的适应性。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.

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

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术]