基于神经网络的不规则件排样技术研究

1、作者简介：翟红岩（1979），女，讲师，研究方向：CAD/CAM/PDM，现代优化技术苏传生（1984），男，硕士研究生，研究方向：现代优化技术基于神经网络的不规则件排样技术研究翟红岩，苏传生，张莹，史俊友(青岛科技大学 机电工程学院，山东 青岛 266061)摘要：提出一种利用人工神经网络求解不规则件排样问题的方法。对于二维不规则零件在排样区域上的优化排列问题，采用自组织特征映射模型(SOM)和Hopfield人工神经网络相结合的方法，寻找排样件在排样时的最优位置及各自的旋转角度，实现二维不规则件自动排样，得到满意的优化排样结果，实例证明了该算法的有效性和实用性。关键词：自组织特征映射模型；

2、Hopfield人工神经网络；不规则件；优化排样 中图分类号：TP 391.7 文献标识码：AThe optimal Layout technology research of irregular parts based on Artificial Neural NetworksZHAI Hong-yan，SU Chuan-sheng，ZHANG Ying，SHI Jun-you(College of Mechanical and Electrical Engineering，Qingdao University of Science and Technology，Qingdao266061，

3、China )Abstract：An irregular parts layout method based on artificial neural networks is proposed in this paper. For the irregular shapes nesting problem in the given nest region of two-dimensional irregular parts, Self-Organizing Map(SOM)and Hopfield artificial neural networks are integrated to look

4、 for the best position of the shaped parts and each parts optimum rotating angle, complete the automatic layout of two dimensional irregular parts, the satisfactory results of optimal layout have been obtained. Examples indicate that our algorithm is effective and practical.Key words：Self-Organizing

5、 Map；Hopfield artificial neural networks；irregular parts；optimal layout最大限度地节约材料，提高材料利用率是实际生产中的一个基本原则，由于在工业生产中排样问题广泛存在，因而解决它具有很深远的理论意义和现实意义。寻找通用性好、求解质量和效率高、易于实现的排样问题求解算法一直是该领域所追求的目标1。人工神经网络具有自适应性、自学习性、强容错性和并行性等特性，已为模式识别、优化技术和其它领域提供了新的技术2。利用人工神经网络求解组合优化问题是一个既新颖又有前途的研究领域。黄兆龙3采用SOM神经网络寻求各排样零件在排样板材上的最优位

6、置；李建勇4等人采用Hopfield神经网络对待排矩形零件进行分组，通过恰当选取分组数目，从而使排料对象放置到板材中。用神经网络解决优化问题的主要难点在于很难找到问题模型与神经网络之间的映射关系。本研究将SOM神经网络和Hopfield神经网络引入排样求解中，运用SOM神经网络对初始随机排布的零件进行平移，寻求各零件的最优位置，运用Hopfield神经网络寻求各排样零件的最优旋转角度组合，最后得到较好的排样方案，并进行了相应的分析和软件模拟计算，验证算法的可行性和有效性。1 模型分析1.1 数学模型一个零件在板材上的定位实际上只需3个参数即可完全确定。这3个参数是该零件的一个给定点在板材上的坐

7、标(X，Y)和该零件的排放角度。当这3个参数确定后，该零件的其它各顶点坐标都可由这3个参数计算。设Gj(jJ，J为零件集合)为零件j的图形，(xj，yj)为该零件的给定点的坐标，则该零件在板材上的定位可以表示为下述过程：先将该零件以该定点为轴旋转角度j，然后再将定点(xj，yj)在板材作位移(xj，yj)。这时零件j在板材上的方位可表示为Gj(xj，yj，j)。零件的数量为n，Sj为零件j的面积。L为板材的长，D为板材的宽，排样图形外接矩形高度为H，宽度为W。定义排样布局的原材料利用率，为排样零件的面积和与排样图形外接矩形的面积的比值。零件优化排样的模型为5： (1)Gj (xj，yj，j )

8、Gk(xk，yk，k ) = ， jk (2)S.t. 0 Yji (xj，yj，j )L ji = 0，1， nj (3)0 Xji (xj，yj，j )D ji = 0，1， nj (4)式(2)表示零件j与零件k互不重叠；和为零件j的第i个顶点的坐标，式(3)和式(4)表示零件不能排在板材之外。1.2 零件预处理使排样问题复杂化的主要原因是重叠性的计算，而重叠性计算的复杂性主要由零件的表达方式决定。因此，零件的表达方式是影响排样问题复杂程度的一个重要因素。加之考虑存储和提取信息的方便，对实体的端点进行排序处理，将零件表达成外轮廓逆时针走向、内轮廓顺时针走向的实体的集合。针对零件图形内部有

9、空白区域的情况，必须在不发生干涉的前提下，选择合适的零件对内空白区域进行填充，以获得优化的排样方案。另外，如果有多个零件都可以填充到一个空白区域中，则采用最佳面积适配法。设区域面积为SE，各零件面积为Si，且SiSE，计算S=min(SE - Si)，则S所对应的零件即为填充的零件。图1 SOM网络结构模型6Fig.1 The structure of SOM 62 算法描述2.1 自组织辅助排样算法自组织辅助排样算法使用Kohonen提出的自组织特征映射模型(SOM)进行优化排样。SOM具有无监督的学习结构，是单层前馈网络，所以它的学习速度很高。应用自组织特征映射神经网络进行排样的网络结构模

10、型如图1所示。其中，输出神经元对应于零件的参考点；输出神经元之间的连接对应于零件在板材上的重叠面积；输入节点的数目与排料的维数相等。在算法中，每个零件的位置由向量wi=w1i, w2i 表示。其中w1i，w2i分别表示第i个零件参考点的x，y坐标值。在学习过程中，输入向量对应于排样区域中的随机选择点。自组织排样的具体算法如下：Step1初始化，t = 0(t为迭代次数)，通过给所有零件的位置向量设定很小的随机值，使零件随机分布在板料的中心附近；Step2随机选择两个零件，交换它们的位置，比较交换前后的两个方案，如果新方案的面积矩不小于原方案的面积矩，则不交换；Step3产生一个新的输入向量x(

11、t) = x1(t)，x2(t)。输入向量应均匀分布在板料区域内；Step4确定与输入向量欧几里得(Euclidean)距离最小的零件pj*；Step5计算学习率(t)及pj*邻域大小nb(t)，对位于pj*邻域之内的零件的位置进行更新，以使这些零件更加靠近当前的输入；Step6如果重叠面积小于a或t = tmax，则停止；否则，增加t，转步骤2。2.2 优化排样问题到Hopfield人工神经网络的映射利用Hopfield人工神经网络求解优化问题，将优化问题的目标函数和限制条件映射为神经网络的能量函数，使优化解对应于能量函数的极小值点，然后利用神经网络动态特性，求出优化问题的解。要保证极小值是

12、合法的，能量函数取极小值时问题的约束条件被满足7。假设选择N个不规则件在板材上排布，每个零件可以通过旋转或镜像而产生M种位置方式，则神经网络使用N*M个神经元，并且这些神经元按M行N列排列一个M*N矩阵，用表示。当网络达到稳定状态时，此矩阵满足如下条件：每列中有且只有一个神经元的输出为“1”,其余神经元的输出为“0”，表示每个零件只能被使用一次；每行中可有不定数目的神经元的输出为“1”，其它神经元输出为“0”，表示不同的零件可以有相同的排样方式。研究表明，零件旋转角度时，各数据变换很小，取旋转角度，则在内零件可以旋转40次，故取M=40。根据拉格朗日乘子法构造神经网络的能量函数，将有约束的排样

13、优化问题转化为非约束问题。能量函数为： (5)图2 不规则零件排样过程流程图Fig.2 The flow chart of the layout for irregular parts式(5)中x，y表示每个零件的不同位置，i，j表示不同的零件，Vxi表示矩阵中(x，i)单元的值；fov表示零件i，j的重叠面积，fhv表示排样图形外接矩形面积；式中A、B、D为正数，第1项为约束项，该项为0当且仅当每一列中只有一个神经元的输出为1，表示每个零件只能被使用一次且确保仅使用N个零件排样；第2项为约束项，该项为0时，表示零件间的重叠面积为零；第3项为优化项，保证原材料的利用率最高。2.3 神经网络应用

14、于不规则件的求解过程首先用自组织辅助排样算法对随机排布的零件进行平移，然后使用Hopfield神经网络进行迭代运算，对平移后的各个零件进行旋转，当网络状态稳定时，得到各零件的最佳旋转角度。排样过程流程图如图2所示。算法的具体步骤如下：Step1初始化，t = 0(t为迭代次数)，零件随机分布在板料的中心附近；Step2随机选择两个零件，交换它们的位置，比较交换前后的两个方案，如果新方案的面积矩不小于原方案的面积矩，则不交换；Step3产生一个新的输入向量x(t) = x1(t)，x2(t)；Step4确定最接近输入向量的零件j*，并计算学习率(t)及j*邻域大小nb(t)；Step5对位于j*

15、邻域之内的零件的位置进行更新；Step6如果重叠面积a或t = tmax，则转步骤7。否则，增加t，转步骤2；Step7 初始化Hopfield神经元初始状态和网络参数A、B、D；Step8 计算能量函数的值。计算神经元动态方程，更新神经元状态；Step9 若相邻两次能量函数差小于给定值，如果输出解合法，则输出排样结果，排样结束；如果输出解不合法，且迭代次数小于给定值，转步骤8，否则计算失败。图3为神经网络算法的流程图。图3 神经网络算法流程图Fig.3 The flow chart of neural networks algorithm3 软件模拟计算及结果分析基于上述算法，笔者开发了不规

16、则件优化排样系统。已证明系统能有效地解决任意二维不规则零件的最优排样问题。以下算例可以证明此算法的有效性。在进行模拟计算时，设置基本运行参数：SOM神经网络最大迭代次数为tmax=10000、学习率=1/(t+1)、初始邻域为板材宽度的一半，以后每次迭代中邻域减小为上次的一半；Hopfield最大迭代次数为1000，能量函数E参数A0.5， B0.8，D0.5；板材宽为600mm，排料零件数目为33，它们由计算机在零件库中随机选取。排样结果如图4(a)所示。 (a) (b)图 4 排样结果图(a) 神经网络算法排样结果 (b) NGSA算法排样结果Fig.4 Layout drawing (a

17、) Layout drawing of neural networks algorithm (b) Layout drawing of NGSA神经网络算法与文献8采用NGSA算法相比，系统运行时间相对较短，同时由图4a、b排样结果图可以看出神经网络算法在寻找排样件最优(排列最紧密)的排样次序及各自的旋转角度方面,均比NGSA好，可以获得材料利用率更高的排样方案，这也进一步证明了采用神经网络算法的有效性。无论从定性分析还是运行过程中的数值分析方面, 神经网络混合算法在搜索能力、优化效率、鲁棒性和多样性等方面都具有明显的优越性；且能够在很短的时间内较精确地寻找到问题的近似最优解。 4 结语实践证

18、明，本研究采用的神经网络混合优化策略结合了SOM神经网络和Hopfield神经网络的特点，是一种优化能力、效率和可靠性较高的优化方法，能够明显地提高材料的利用率，带来显著的经济效益，它的研究对智能优化理论的发展与应用也很有意义。参考文献1 Julia A Ben Nell，Kathryn A Downs-land，William B Downs-landThe irregular cutting-stock problem-a new procedure for deriving the no-fit polygonJComputers and Operations Research，2001，28：271-2872 王宏达，尚久浩，樊养余智能排样算法分析与展望J机电工程技术，2004，33(10)：9-113 黄兆龙用启发算法和神经网络法解决二维不规则零件排样问题