不规则件优化排样的小生境遗传模拟退火算法

Optimal Layout of Irregular Parts with Niching Genetic Simulated Annealing Algorithm

提出一种基于小生境遗传模拟退火算法求解不规则件排样问题的方法。该方法首先充分考虑不规则形状零件自身的形状特征,采用组合矩形包络算法将二维不规则零件的排样问题转化为矩形件的排样问题,克服了以往简单采用最小包络矩形代替零件排样存在空白区域,从而导致材料可能发生的利用率过低问题;然后利用遗传模拟退火算法及小生境技术相结合,寻找排样件在排样时的最优次序及各自的旋转角度;最后用"最低水平线与填充算法相结合"策略的启发式排样算法实现自动排样。实例表明了该算法的有效性和实用性。

Firstly, we fully consider the shapes of irregular parts and convert the two-dimensional irregular parts packing problem into rectangular parts packing problem using the combined rectangle enclosure algorithm. We overcome the blank area when minimum enclosed rectangle was simply used to replace the parts packing, which resuits in too low utilization ratio of materials. Secondly, genetic simulated annealing algorithm and niche technique are integrated to search for the best sequence of the packed parts and each part＇s angle of rotation. Finally, the lowest horizontal algorithm and filling algorithm are combined to complete the automatic layout. Examples indicate that our algorithm is effective and practical.