|
摘要：利用连续型Hopfield人工神经元网络（CHNN）进行了金属冲压剪切排料的优化求解计算。讨论了连续型Hopfield人工神经元网络的模型，以及排料问题向连续型Hopfield人工神经元网络的映射，并结合矩形排料问题通过软件模拟计算对所讨论的算法进行了验证。结果表明，利用连续型Hopfield人工神经元网络进行排料优化计算可以得到较好的结果，并且求解质量稳定、速度快。
关键词：人工神经元网络；排料；优化；规划
进行排料规划是金属冲压剪切加工前的一项重要工作。这项工作不仅与冲压剪切加工工艺有关，还直接影响着加工生产的效率和材料的利用率。在目前的实际生产中，排料问题往往是依靠经验用人工方式试凑试切，或进行一些简单的优化计算，经过多次反复后找出一个规划方案［1］。而排料问题是复杂的离散组合最优化问题，对实际生产中问题的求解往往是比较困难的。由于受到问题复杂性和求解时间的限制，许多更好的方案在排料设计时经常无法被发现。当生产规模较大，排料物体形状复杂，约束条件增多时，排料问题的求解效果往往成为影响生产效率和生产成本的重要因素。尤其对于实际复杂问题求解的质量和效率还不能令人满意。因此，寻找通用性好、求解质量和效率高、易于实现的排料问题求解算法一直是该领域所追求的目标［2，3］。
人工神经元网络具有自适应性、自学习性、强容错性和巨并行性等特性，利用人工神经元网络求解组合优化问题是一个既新颖又有前途的研究领域。本文尝试将连续型Hopfield人工神经元网络引入排料求解中，并进行了相应的分析和软件模拟计算。
1 连续型Hopfield人工神经元网络
Hopfield人工神经网络（HNN）是由若干基本神经元构成的一个单层全互连神经网络，任意两个神经元之间都有连接，是一种对称连接结构。当选用M-P模型二值神经元时为离散型HNN（DHNN）。DHNN中的神经元主要在以下两方面与真实神经元存在着差异：第一，真实神经元的输入与输出关系是连续的;第二，真实神经元由于存在着时间延迟，其运动方程应由微分方程刻画。为此，Hopfield进一步发展了DHNN，提出了由简明电子线路实现的连续时间神经网络模型（CHNN）。CHNN比DHNN能够更加真实地反映神经元，并有利于VSLI的硬件实现和改善网络的总体性能［4］。
在CHNN中每一个神经元具有连续时间变化的输出值。它用具有饱和非线性的运算放大器模拟神经元的S型单调输入—输出关系。
对于N节点的CHNN模型，其神经元状态变量的动态变化可用下述非线性微分方程来描述： （图片） 式中：VI、uI——分别表示输出和输入电压；
II——输入电流；
Tij——电导；
RI——输入电阻ρI与连接电阻Rij的并联电阻，即：（图片） fI(uI)——神经元的S型作用函数；
f-1(VI)——fI(uI)的反函数，为讨论方便，统一选取为：
（图片） 神经元的状态变化可在［0，1］区间连续取值。
在CHNN模型中，对生物神经元的性质做了大量简化，但它突出体现了生物系统的如下特性：（1）神经元的传输特性具有S型函数特征；（2）神经元的时空整和功能；（3）神经元间的兴奋性和抑制性连接结构。
对于CHNN，能量函数定义为：（图片） 式中：Tij=Tji，并有如下特性：（图片） 对于理想运算放大器，上面定义的能量函数可简化为：（图片） 因此，从任意初态开始，CHNN按照一定的状态轨迹运动，最终能够达到网络的稳定状态（或渐近稳定状态），即能量E的极小点。当（图片）时，可得（图片）＝0，对于所有I成立，即系统达到稳定状态。这说明具有上式的系统的演变过程就是在［0，1］n空间内寻找极小值稳定点（吸引子）的过程，并在达到这些点后稳定下来。因此这种神经网络具有自动求解极小值的计算功能。
2 排料优化问题到CHNN的映射
利用CHNN求解优化计算问题的思想是，首先把优化的问题映射到一种神经网络的特定组态上，此组态相应于优化问题的可能解，然后构造一个适合于待优化问题的能量函数E，此E应正比于优化问题的代价函数。
为验证CHNN求解排料问题的有效性，我们设计了针对矩形的排料过程。该过程将排料看成是对排料对象的分组过程，通过恰当选取分组数目，从而使排料对象放置到板材中。
假设有N个待排料对象并将其分为P组，所追求的目标是：
（1）每组排料对象高度差最小；
（2）各组的宽度差最小（组中所有排料对象的宽度和称为组的宽度）。
该分组过程是一个具有NP完全计算复杂度的过程。综合上述考虑将矩形排料问题按如下方法映射到神经网络：
假设将N个排料对象分为P组，则网络使用N*P个神经元，并且这些神经元按P行N列排列。当网络达到稳定状态时，要求每列中有且只能有一个神经元的输出为1，其余神经元的输出为0，表示每个待排料对象只能使用一次，即只能分在确定的某一组中；所有N*P个神经元中输出值为1的神经元的个数必须为N，确保仅使用规定的N个待排料对象；每行中可有不定数目的神经元的输出为1，其它神经元的输出为0，表示每组中可有任意多个排料对象。若第X行第1列的神经元的输出为1，即Vxi=1则表示排料对象被分在标号为x的组中。
根据上述排料目标，构造如下能量函数：（图片） 式中：A、C、D——正系数；
lI、wI——分别为排料物体I的长度和宽度；
第一项为约束项，该项为0当且仅当每一列中只有一个神经元的输出为1；
第二项为优化项，该项为0当且仅当每组长度相等；
第三项为0当且仅当每组中排料物体的高度相等。这是一个多目标组合优化问题。
3 软件模拟计算及结果分析
通过以上分析，我们对人工神经元网络排料优化求解进行了软件实现［5］。该软件包括初始化模块、计算模块和显示模块，其中初始化模块包括网络参数初始化、网络大小的动态初始化、输入输出函数表的初始化和网络状态初始化；计算模块主要完成能量函数值计算、神经元运动过程模拟计算及状态更新计算；显示模块主要对结果合理性验证并显示合理的排料结果。整个计算过程是一个迭代过程，每迭代完一次，检查结果的合法性即：每个神经元输出“1”或“0”（在软件实现过程中，当输出小于0.01时视为“0”；大于0.99时视为“1”）；每列仅有一个神经元输出为“1”。当相邻网络状态的网络能量改变值小于很小的值时（程序中为1e-10），可视为网络达到极小点，网络运算结束；如果迭代次数大于预先指定的次数时仍然没有结果，则重新计算（视为无法收敛）。
然后从网络参数和网络初始状态两个因素对排料结果的影响进行了研究。在进行模拟计算时，采用的排料物体数目为30，它们的尺寸由计算机随机产生，为方便起见产生的尺寸数值限制在0.50 m之内。产生的排料结果按照产生顺序编号，其初始状态如图1所示。首先在固定A=0.5，C=0.08，D=0.2，N=30，P=3对不同网络初始状态下计算出每次排料的覆盖率（此处取n=100次）。计算得出其有效解的平均值为85.53%，标准差为4.35。此处覆盖率CR（Cover rate）定义为排料物体的面积和与排料结果外接矩形面积的比值。图2是其中的较好解显示。然后在A=0.5及其他参数不变的情况下改变C、D的值，得到一系列排料结果。模拟计算分如下两组情况进行：
第一组 C=0.10,D=0.4; 第二组 C=0.20,D=0.5；（图片）
图1 排料对象初始状态 （图片）
图2 仿真排料结果 同前面一样计算出覆盖率，第一组有效解的平均值为86.13，标准差为3.17；第二组有效解的平均值为87.18，标准差为2.68。通过反复试验发现，权值的选取有一定的规律。因为A对应能量方程的第一项，这项的作用是使神经网络的稳定状态对应于问题的可行解，即神经网络的每一列只能有一个神经元的状态为“1”。C、D分别对应能量方程的第二和第三项，这两项是优化目标。所以若A值相对较大，则第一项在能量方程中的比重较大，神经网络很容易得到问题的解，但得到问题的解有时质量较差。如果过于强调优化问题所追求的目标赋给C、D较大的值，则在程序中所规定的迭代次数（1 000次）内得不到问题可行解的可能性增大。因此应根据求解问题的实际情况调整A、C、D三个参数，在保证一定的求解质量的前提下提高求解速度。
在条件确定的情况下，即网络参数选取某一特定值时，由于神经网络初始状态的随机性，能得到数目众多的局部最优解，可为实际生产提供较多的选择方案。通过程序设定，也可自动获得多个局部最优解中的最好解，使最终排料方案的覆盖率大大高于平均值。
4 结束语
由于一方面对于不规则形状的排料大多是首先对不规则形状进行矩形外包络后，再进行排料;另一方面，对于不同的排料过程，可通过相应的映射来得到其相应的能量函数，而求解思路完全相同，所以，虽然上述的排料过程只是为了验证所研究算法的有效性而针对规则矩形进行的，但上述内容具有广泛的实际意义。
排料结果的覆盖率与设定的运算次数有着直接的关系。当增加运算次数即增加运算时间后可提高覆盖率。
利用CHNN进行排料优化计算可以得到较好的结果，求解质量稳定，速度快。因此，将人工神经网络用于求解排料问题有较好的前景，尤其是将其与其它的智能型算法联合应用时效果会更加显著。
7/14/2004
|
