基于遗传规划的连接板优化排料算法的研究

An Algorithm for Optimization of Connecting Plate Layout Based on Genetic Programming

遗传规划(GP)是遗传算法的一个重要分支,是提供找到解决问题的计算机程序的统一途径。矩形排料优化问题是NP完全问题,每块给定尺寸的板材上所排的矩形件数量随环境的动态改变而改变,类似于遗传规划中的分层特性,对应于不同深度的算法树个体。针对连接板下料中的排料优化问题,将连接板优化排料问题转化为矩形优化排料问题,提出一种全新的基于遗传规划的连接板优化排料算法。介绍了连接板的最小包容矩形的求取方法、遗传规划用于矩形件排料的算法及应用遗传规划进行矩形件排料的基本步骤,并用具体的排料实例进行验证。最后得到结论并指出未来可能的发展方向。

Being an important branch of genetic algorithm, genetic programming（GP） is an unitary approach to providing computer programs that find problem solutions. The rectangle layout optimization problem is an NP-complete problem, namely, the number of rectangles layered on every plate of a given size changes with that of their environment, resembling the layering characteristics of genetic programming and corresponding to an algorithm tree＇s individual of different depths. In laying out the connecting plates, I translate their layout optimization problem into rectangle layout optimization problem, creating a brand-new algorithm for optimizing the layout of connecting plates based on the GP. I present a method for seeking their rectangles of the least content, the GP algorithm used for rectangle layout and the procedures for using the GP. Finally I use an instance of layout to verify the algorithm.