第43卷第2期 Vol. 43No. 2
计算机应用：
假压技木
FORGING & STAMPING TECHNOLOGY
2018年2月 Feb.2018
基于复合评价因子的改进遗传算法求解矩形件排样问题
罗强，李世红2，袁跃兰？，饶运清，刘泉辉（1.华中科技大学数字制造装备与技术国家重点实验室，潮北武汉430074；
2.贵州交通职业技术学院，贵州贵阳550008；3.华中科技大学电气与电子工程学院，湖北武汉430074）
摘要：矩形件排样问题是NP-Hard的组合优化间题，计算复杂度随矩形件的规模急剧增加，难以在可接受的时间内获得精确解。在最低水平线算法的基础上，综合考患矩形件的高度、宽度和面积这3个影响排样效果的因素，提出复合评价因子对矩形进行评价，从中选择较优的矩形排人相应的位置。通过合理的使用遗传算子，改善遗传算法的局部搜索能力，提高矩形件排样问题解的质量。实验结果表明，在广泛使用的算例N和算例C申，本文算法求得的平均最佳相对距离比GA+BLF和 SA+BLF算法分别降低约70%和55%，说明了本文算法的有效性、实用性和稳定性。
关键词：遗传算法；最低水平线算法；矩形件排样；复合评价因子；适应度 DOI: 10. 13330/j. issn. 1000-3940. 2018. 02. 029
中图分类号：TP391
文献标识码：A
文章编号：1000-3940（2018）02-0172-10
Rectangular workpiece nesting based on an improved genetic algorithm of
composite evaluation factor
Luo Qiang', Li Shihong, Yuan Yuelan", Rao Yunqing', Liu Quanhui?
(1. State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Seience and Technology , Wuhan 430074, China; 2. Guizhou Communications Polyteching, Guiyang 550008, China; 3. School of Electrical and Electronic
Engineering, Huazhong University of Secience and Technology, Wuhan 430074, China)
Abstract : The rectangular workpiece nesting is a combinational optimization problem of NP Hard. Because its computation complexity is increased with the number of rectangles sharply, it is dificult to obtain an exact solution within an acceptable time. Based on the: lowest horizontal algorithm , considering the effect factors of height, width and area of rectangular, a composite evaluation factor was presented to evaluate the rectangle, and the superior rectangle was opted to be nested. Then, the local searching capability of genetic algorithm was improved by reasonable genetic operators, and the nesting quality of rectangle was improved. Being widely used in the example N and C, the experiment result shows that the average best relative distance is lower than that of GA + BLF and SA + BLF algorithm by 70% and 55% respectively. Thus, the approach is effective, efficient and stable.
Key words : genetic algorithm; the lowest horizontal line; rectangular workpiece nesting; composite evaluation factor ; fitness
在船舶、航空、报刊、服装、玻璃等行业中，产品从设计到下料加工的过程中存在着排样问题，自动化排样比人工排样具有更高的效率，而排样算法是实现自动化排样的核心，良好的排样算法可以提高材料的利用率，避免资源的浪费，降低企业成本，实现绿色制造。
收稿日期：20171018；修订日期：20171227
基金项目：国家重点基础研究发展计划（2014CB046705）
作者筒介：罗强（1994-），男，颈土研究生 E-mail: luoqiang0002@ 163. com
通讯作者：谈运清（1968-），男，博士，教投万方蒙据ail：ng@hust.eda.cn
矩形件排样问题属于二维排样问题，在数学计算复杂性理论上，属于NP完全问题，当矩形零件数量较大时，计算复杂度大，难以在短时间内找到最优解，因此，国内外许多学者都对该问题进行了研究，提出了许多切实可行的求解方法，
矩形件排样优化问题一般分为矩形件的定序和定位两部分，即确定矩形件的排放顺序和矩形件在板材中的位置。对于矩形件定位方法，Baker BS 等提出了BL排样算法，一些学者在这基础上进行改进，提出了基于BF的填充算法Bottom-Left Pill（BLF）[2]，填充排样中产生的空洞。刘德全等[3]在 BL策略的基础上提出一种下台阶方法，贾志欣等[+]