矩形件优化排样的自适应遗传模拟退火算法  

Adaptive Genetic Simulated Annealing Algorithm in Optimal Layout of Rectangular Parts

作　　者：董德威[1] 颜云辉[1] 张尧[1] 李骏[1] 

机构地区：[1]东北大学,沈阳110819

出　　处：《中国机械工程》2013年第18期2499-2504,共6页China Mechanical Engineering

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

摘　　要：针对理论上属于NP完全问题的矩形件优化排样问题,提出了一种基于小生境技术的自适应遗传模拟退火算法。研究了将矩形件在板材上的排列方式转换为特定编码的方法,利用遗传模拟退火算法进行全局优化概率搜索,考虑到算法中交叉概率和变异概率的选择影响到算法收敛性,提出了自适应的交叉概率和变异概率,并通过小生境技术对子辈个体是否替换父辈个体加以控制,最终得到矩形件排样的最优次序和排放方式,采用最低水平线策略的启发式排样算法实现自动排样。排样实例表明,该优化排样算法行之有效,具有广泛的适应性。Aiming at the optimal layout problem of two dimensional rectangular parts, which is a NP-complete problem, an adaptive niched genetic simulated annealing algorithm was presented. This paper translated the layout of rectangular parts on a rectangle into a special coding of genetic algorithm, the proposed approach automatically looked for the best sequence of the rectangular parts and each part＇s optimum rotation by the genetic simulated annealing algorithm. Considering the choice of crossover probability and mutation probability affected algorithm convergence, the adaptive crossover probability and mutation probability were put forward. The niche technology controlled whether the child individual replacement the parent individual or not. Finally, the lowest horizontal algorithm completed the automatic layout. Examples indicate that the algorithm is effective and practical.

关 键 词：矩形件优化排样 自适应遗传模拟退火算法 小生境技术 启发式算法 

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