应用临界多边形方法与小生境遗传算法求解不规则排样问题  

Using No-fit Polygon Method and Niche Genetic Algorithm to Solve Irregular Packing Problem

作　　者：刘海明[1] 周炯[1] 吴忻生[1] 

机构地区：[1]华南理工大学自动化科学与工程学院,广州510640

出　　处：《小型微型计算机系统》2016年第5期1002-1007,共6页Journal of Chinese Computer Systems

基　　金：广东省科技专项项目(2014A010104004)资助;中央高校基本科研业务费专项重点项目(2014ZZ0033)资助

摘　　要：针对现代制造业中广泛存在的不规则排样问题进行了研究,提出一种基于临界多边形排样策略和小生境遗传算法的排样优化算法.算法通过改进的移动碰撞法计算零件之间的临界多边形,以确定最佳的零件靠接排放位置;通过基于小生境策略的遗传算法优化零件的排样顺序,确定最佳排样序列.对所提出的排样优化算法作了实验测试和算法评估,验证算法的可行性与有效性.排样实验结果表明,该算法能够用于求解不规则排样问题,且在一定程度上优于已有算法,能够提高材料利用率.For the issue of irregular packing problem widely existed in modem manufacturing, this paper conducted a study on it and presented a packing optimization algorithm based on no-fit polygon method and niche genetic algorithm. The algorithm calculates no-fit polygon between two parts by the improved collision approach to determine the best packing position for the part, and searches for the optimal packing order by genetic algorithm based on niche strategy. Experimental test was performed to verify and evaluate feasibility and efficiency of the proposed optimization algorithm. The results of packing test show that the proposed algorithm can solve the irregular packing problem, provide better results than existing algorithm to some extent and improve utilization of material.

关 键 词：不规则排样 临界多边形 遗传算法 小生境策略 

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