排样系统

排样系统（精选七篇）

排样系统 篇1

关键词：DXF文件,排样系统,余料,交互式排样

1 前言

传统的排样是由排样工人按照经验进行的,排料效率低、速度慢、劳动强度大、差错率高,且效果不理想。而计算机辅助排样是根据一定的优化原则,利用计算机图形学和相关的计算机技术来完成的。它是把传统的排样作业计算机化,把排样师傅丰富的经验和计算机具有的快捷、方便、灵活等特点结合起来,从而快速获得较高材料利用率的一种计算机辅助设计方法。

随着先进制造技术的发展,采用优化排样系统代替人工排样已成为一种必然趋势。在下料生产中采用下料优化排样技术,可以降低成本、提高材料利用率、改善排样工人的劳动条件。在机械制造行业,金属材料是主要原材料之一,随着我国国民经济的快速发展,企业对板材的消耗量日益增大,因此提高金属板材的下料利用率,就具有特别重要的经济意义。统计资料表明,在加工钣金零件的成本中材料支出占60%以上,在大批量生产中,即使材料利用率仅提高1%,其经济效益也是相当可观的,因而对优化排样系统的开发和研究具有重要意义[1]。

为了节省成本,一些以加工简单形状小五金件为主的企业会购买大型企业加工后的余料作为自己的生产原材料。其主要原因是待加工零件尺寸相对较小,可以在余料上进行排样,而余料的成本相对来说小很多。因而,以余料为基础进行优化排样具有很大的现实意义。

2 排样问题

2.1 排样系统

排样问题可以分为三大类:一维下料、二维排样和三维布局。现阶段的排样系统主要有3种:人机交互式排样系统、全自动智能排样系统和半自动排样系统[2]。

2.2 基于余料的排样系统

上述几种类型的排样系统,是根据排样过程中计算机的参与程度来分类的,没有涉及到具体的排样约束条件。其中大部分的排样系统都是基于完好的板材来进行排样工作的,并且一般仅限定板材的宽度,对长度不作限定。

但是对于“基于余料的排样系统”来说,板材并非是完好的,而且同时限定板材的长度和宽度,对可排的区域有严格的约束。可以这样解释基于余料的排样,即在固定长宽的矩形余料上,排放尽可能多的零件,使余料的利用率尽可能的大。现有的一些研究思路显然无法很好的解决该问题。

本系统的半自动排样模块,将余料的已加工位置初始化为矩形,将待排样的零件也初始化为矩形,从而将该问题转化为矩形件排样问题。将该问题转化为矩形件排样问题后,虽然简化了计算,提高了排样效率,得到的排样结果却可能不是最优解(或近似最优解),还达不到尽可能提高材料利用率的目的。因而系统提供了较完善的交互式修改模块,由排样工人根据自己的经验,对半自动排样模块所得结果进行交互式修改。

3 系统设计

3.1 总体设计

3.1.1 功能模块介绍

本系统是一个二维半自动排样系统。功能模块图见图1。

3.1.2 系统开发所运用的技术

根据课题的需要,该系统将主要用于中小型五金零件生产企业,这就要求系统易于安装、使用,因而选择Visual Basic6.0作为开发工具,数据库采用Access。

在系统的管理模块中可以选择合适的余料,然后通过接口程序识别待排样零件的DXF文件,导入待排样零件,预排样以后再作交互式修改,最后输出排样结果(DXF格式)。

3.2 余料和待排零件的预处理

3.2.1 DXF文件

本系统中,余料和待排样零件都是以DXF文件格式存储的,而结果的输出格式也是DXF。

AutoCAD采用了DXF(drawing exchange format)图形交换文件格式在不同的CAD系统间进行数据的交换。随着AutoCAD的广泛使用,DXF文件事实上已经成为国际通用的图形数据交换标准,被大多数CAD系统所接受。

DXF文件由标题段(header)、表段(tables)、块段(blocks)、实体段(entities)和文件结束段(end of file)五部分组成。接口主要是识别和提取实体段(entities)中的相关数据和信息[3]。

多义线是AutoCAD中的特殊图形实体,它由一系列首尾相连的直线和圆弧组成,在图形数据库中以顶点(即相连点)子实体的形式保存信息,与位置、形状有关的信息主要有两个:一是顶点坐标数值,保存在10组码(x坐标)和20组码(y坐标)中;二是顶点凸度(Bulge),保存在42组码中。多义线的直线顶点和圆弧顶点都只保存了直线和圆弧的起点标志,终点坐标则都保存在下一个顶点中[3]。

3.2.2 余料和待排零件的预处理

在导入余料和待排零件之前,要对余料和待排样零件作适当的预处理。具体的处理方法如下。

本系统的接口可以识别DXF文件中的直线、矩形、圆、圆弧和多义线等图形实体对象。因而,余料和待排样零件要求由上述的几种对象组成。一般来说,大多数零件都可以由上述对象的组合表达出来,特殊情况下,只能采取近似的方法,否则排样系统无法识别。

对于余料,其外轮廓在AutoCAD中用矩形画出。已加工位置的轮廓如果是一个圆,直接画出即可。如果包括圆弧和直线,要求用Pedit命令(包括其子命令join)使之组合成一条多义线(Polyline)。最后把图形存储为DXF格式。这样,在该DXF文件中,ENTITIES段中的Rectangle部分存储的信息就是余料的外轮廓,ENTITIES段中的其余部分保存的就是余料已加工部分的信息(包括Circle或者Polyline等)。

对于待排样零件,首先要把待排样零件按实际尺寸在AutoCAD中准确进行绘制。为了选取方便,一般把零件轮廓线组合成一整体。可用Pedit命令(包括其子命令join)使之形成一条多义线(Polyline)。然后用OFFSET命令使其偏移一个搭边值(偏移量由具体加工情况而定),生成等距放大图。保存该等距图的DXF文件于相应的文件夹,即可。

3.3 余料的管理

对于一个具体的待排样零件而言,选择合适的板材(在本系统中是选择合适的余料)非常重要,对板材的材料、厚度以及尺寸形状都有相应的要求。为了便于操作人员选择合适的余料,系统建立了一个小型的数据库,用于余料的选择,包括余料的厚度、材料、文件名、面积、数量等信息,同时包含了余料图形显示的功能。操作人员可以方便地按照合适的约束条件在库存中查找、选择合适的余料。

3.4 系统与AutoCAD之间的接口

本系统与AutoCAD之间接口具有2个功能:

(1)待排样零件和余料图形的识别导入;

(2)排样结果的DXF格式文件输出。

待排样零件和余料图形识别导入,即提取DXF文件的“ENTITIES段”的数据信息,实际就是将一个字符流文件按照“标记+值=一行”规则的读出过程。根据读出的数据信息,在系统中设计自己的图形对象。

在此过程中,相关的多义线的信息提取是关键。按照上述的方法很容易读出多义线的各个顶点的坐标和对应的凸度值。在导入这些信息并绘出图形的过程中,当凸度值不为0时,表明这一条边不是直线段,而是一条圆弧。根据AutoCAD中关于凸度的相关约定,可以确定该圆弧的确切数据信息。

3.5 半自动排样与交互式排样

3.5.1 半自动排样

半自动排样就是用矩形件排样的方法,得到部分排样结果。

在开始排样操作前,采用矩形拟合方法将不规则零件拟合为矩形,然后利用较为成熟的矩形排样方法进行排样。事实上,矩形排样可视为不规则排样的一个特例,由于矩形的几何形状相对简单,且一般不允许任意角度旋转,因此其解空间比一般的不规则排样问题的解空间要小。

用穷举法求零件的最小包络矩形。

如图2所示“12345”为待排样零件,ABCD为其任意一个包络矩形,计算出该矩形的面积为S1,将ABCD的对称轴P1P2旋转一个角度θ,得到O1O2,以O1O2为对称轴作新的包络矩形EFGH,计算其面积S2。如此不断的进行下去,当P1P2旋转了90度以后,且θ取得足够小,则具有最小面积的包络矩形即为所求。

所求出的最小包络矩形可以记作(l、d),其中l、d分别表示矩形的两条邻边。

在开始矩形件排样前要对余料做适当的处理,将余料的已加工区域用一个矩形包络替代,该矩形包络与X轴平行,记为(l',d')(在图3中的剖面线部分)。

将余料划分区域,如图3的1、2、3、4区。将1、2、3、4区记作(l1,d1)、(l2,d2)、(l3,d3)、(l4,d4)。

此时问题转化为矩形件排样。余料将分别在1、2、3、4区4个矩形区域进行排样。

该算法的实质是模拟人工排样的过程,不断的在板材剩余的部分排放矩形待排零件,直到空白处不能再排入零件为止。一般在总体上以“最低最左”(Bottom-Left)原则将待排零件放置于板材的空白处,将零件不停地往下和往左移动,直到碰到板材边界或已排零件的边界而无法再移动为止[4]。

针对本系统的情况,首先在1和4区排样。根据排样的结果对2和3矩形的l2和l3进行相应的扩充,然后在2和3中排样。

在矩形件排样中一般采用正排法(即待排矩形的长或宽与板材区域的长或宽平行)放置待排零件。因而待排矩形只有2种放置方法,即横排(待排矩形的长与板材区域的长平行)和竖排(待排矩形的长与板材区域的长平行)。在1区域,首先由左下角开始以横排方式排样,根据“最低最左”原则,直到不能以该方式再安放待排零件为止。如图4所示。比较ΔD与待排零件的宽度d大小,如果ΔD较大,则将待排零件以竖排方式继续安放,否则停止。

按照同样的方法对区域4进行排样。

此时2和3矩形的l2和l3会发生变化,具体的值根据1、4的排样结果而定。

以同样的方法在2和3矩形区域安放待排样零件的最小包络矩形。

在上述的规则下得到的排样结果,由于不规则形状和矩形之间的误差,待排样零件拟合为矩形后与矩形边界存在很大空隙,可能会存在显著的材料浪费,必须通过交互式排样模块,对现有的排样方案进行修改。

3.5.2 交互式排样

交互式排样充分利用了人的能动性,将排样工人丰富的经验和计算机具有的快捷、方便、灵活等特点结合了起来,具有很好的操作性。

该模块主要提供了对图元(一个待排样零件)的创建、平移、旋转、放大、缩小、删除等操作,在平移或旋转过程中,如果图元之间产生相交的情况,系统会通过改变相交图元的颜色来预警[5]。

交互式系统有一些基本的设计原则,对功能、易使用性、可靠性、风格一致性、简单性和开放性等发面都有要求。

在交互式图形系统中一般要使用以下一些技术:定位技术、橡皮筋技术、拖拉技术、选择技术、UNDO和RE-DO技术等。本系统中主要运用了选择和UNDO/REDO技术[5]。

对半自动排样结果进行交互式修改的时候,第一步就要选择图元,即计算机对图元的拾取。在图元被拾取以后,图元的线型和颜色将被改变。图元的拾取和选择涉及到大量的计算,需要在精确性和效率问题上进行权衡。

在对图元进行编辑的技术中有2种必须而实现起来有困难的技术:UNDO(撤消)操作和REDO(重做)操作,分别表示恢复最近执行的操作和重新执行最近被撤消的操作。本系统提供了有限级的UNDO和REDO操作。

3.6 系统的操作流程图

4 结语

本文对基于余料的五金零件排样系统进行了研究。该系统用Visual Basic 6.0实现,可以识别和编写DXF格式文件。在AutoCAD中按要求绘制零件和余料图形后,保存为DXF格式。将这些DXF文件分别存放到零件库和余料库。排样前,选择合适的余料,将余料和待排样零件导入系统,进行基于包络矩形的半自动优化排样,之后,在交互式排样模块作交互式修改,显示排样结果,输出排样DXF文件。该系统对于中小型企业具有一定的实用价值。

参考文献

[1]曹炬.实用冲裁件优化排样系统的研究与开发[J].锻压机械,1999(1):44-47.

[2]贾志欣.排样问题的研究现状与趋势[J].计算机辅助设计与图形学学报,2004,16(7):890-897.

[3]何援军.计算机图形学[M].北京:机械工业出版社,2006.

[4]黄宜军,施得恒,徐启富.钣金CAD中一个较优的排料算法[J].计算机辅助设计与图形学报,2000(7):488-491.

[5]苏金明.用Visual Basic开发交互式CAD系统[M].北京:电子工业出版社,2003.

板料优化排样问题 篇2

关键词：优化排样问题,板料优化,算法

在材料的加工制造中,原材料的规格和目标件规格之间具有复杂的组合关系。加工制造的方案确定首先就是确定出这种组合关系。在传统的情况下,往往通过决策者主观的判断来实现这种组合关系的确定,而其中最简单的方法就是按逐个目标件的需求从全材料上进行取材。由于这种决策过程没有从宏观上对材料的利用效率进行考虑,往往在很大程度上浪费了原材料。为此,需要采用一定的优化方案对原材料进行利用,即采用良好的排样方法,实现节约材料的目标。尤其在某些工艺过程中,材料的成本远高于加工成本,而其中的某些材料是不可重复处理的,因此,排样问题在原材料的剪裁过程中至关重要。

优化排样问题是确定原材料和目标件之间的组合关系得问题,由于原材料与目标件之间关系的复杂性,该问题属于非确定型的多项式算法(Nondeterministic Polynomial,NP)完全问题,计算复杂性高,很难通过精确算法在短时间内对问题进行求解[1]。尤其在问题规模较大时,一般的精确算法已不能满足工程应用的需要。为此,很对针对此问题的不确定算法发展起来了,采用这些算法能够实现较优的排样方案,实现求解时间与优化方案之间的调和。为进一步探索板料排样算法的发展,本文对近年来国内在板料排样问题方面所开展的工作综述,以期明确板料排样问题的发展方向。

1 问题描述

板料排样问题是确定原材料分解成多个目标件的方案,由于在某些情况下排样问题具有一定的约束条件,所以又常根据约束条件将板料排样问题分为一维问题、二维问题、三维问题以及1.5维问题。在工程应用领域,其中的二维板料排样问题应用广泛,其问题的直观描述如图1所示。问题表述为,在长为L宽为W的原材料上对目标件所需的区域进行划分,划分的目标是获取m类的bm个长为lm,宽为wm的目标件。即满足如下条件:

排样问题在工业领域具有广泛的应用,主要面向板料冲压领域和轻工业中的皮料分割领域。在冲压领域主要开展的工作是研究少无废料冲裁技术[2,3,4,5,6],这些技术对汽车工业的发展起到一定的推动作用。另外,在其他领域如石料加工和皮料加工中也具有一定的应用,如赵民等人[7]将优化排样应用到石料的优化排样中。在皮料的排样问题中,所需要实现的目前与公式(1)的描述有所差别,其中的原材料是人工从自然界获取的二维形状复杂材料,在原材料上剪裁多边形,需要实现材料的最优利用与多边形边数之间的调和。

2 板料排样问题优化算法

板料排样问题的复杂性决定了求解过程的复杂性,一般情况下很难实现问题的精确求解。目前所采用的求解方案获取的解都是近似解。在不考虑具体算法的情况下,板料排样问题的优化一般包括问题的预处理、问题求解以及问题的后处理等几个步骤,目前的研究主要针对问题的求解算法来开展。

2.1 排样问题的预处理

为了方便问题的求解过程的实现,一般需要对排样问题进行预处理,将原材料和目标件之间的组合关系限制在较小的范围内,方便算法的实现。目前,国内部分学者在排样问题的预处理方面开展了一定的工作,其中包括对初始的零件的预处理、对板材的分割和对零件的拟合等处理过程的研究。对零件的预处理主要从多种零件的组合方式和板材的分割方面进行了考虑。这些工作主要在2000年左右开展,如崔耀东[8]采用组块优化排样法实现多种目标零件的预处理,使多种零件组合首先形成规则的矩形单元,这样有利于零件在原材料上的排布。在板材分割方面,崔耀东等人[9,10]考虑将板材分割为较小的板材,实现在子板材上进行单个目标零件的排样,使排样问题简化。

在排样问题预处理过程中,需要考虑到零件的特征、对待排样零件进行分类以及对零件排样方案进行权重分析等问题。多个课题组在这些方面开展了系列工作。李英华等人[11]对板料排样问题进行了分析,将各种二维几何零件及其排样问题进行了归类,并针对这些归类设计了一套分类码系统,为后续的板料排样问题的求解提供了借鉴。马建等人[12]也对零件的特征进行了考虑,在此基础上提出基于实例(样图)的推理优化方法,设计出了基于这种原理的排样系统结构。张玉萍等人[13,14]采用对皮料的样片进行进行了离散化预处理,减小排样优化过程与皮料和样片的几何信息之间的相关性对计算结果的影响和约束,提高了获取最优结果的可能性。

在工程问题中,由于所面临的板料排样问题可能遇到对复杂多样的零件的排样,这种情况难以采用对矩形件排样的理想方法进行统一处理。在这种情况下,需要对目标零件的轮廓进行拟合,以简化后续的优化过程。一般情况下,所进行的多边形拟合主要把不规则的平面几何图形拟合成平面多边形区域进行处理,最理想的情况是拟合成矩形形状。国内在这方面也开展了大量的工作,曹炬[15]将二维异型件拟合成多边形的基础上对多边形进行了排样优化;赵震等人[16]为了解决图形干涉问题,提出了采用毛坯图形等距放大的算法来对毛坯图形进行预处理。此后王亮申等人[17]、谢晓龙等人[18]、宋亚男等人[19]以及王华昌等人[20]所开展的工作都是基于这种等距放大原理的。

除了实现非规则零件的拟合,等距放大原理还用于考虑多个零件间的干涉。雷贺功等人[21]采用多边形顶点射线算法对零件进行处理,消除了零件在排样过程中的可能发生的相互干涉。宋亚男等人[22]考虑了不规则图形在板料排样过程中可能的干涉情况,专门研究了其中的判交和碰靠过程。这些关于多边形的干涉碰撞算法执行起来还很复杂,其复杂程度与目标多边形的性质相关,尤其在某些非凸多边形的情况,采用自动化的预处理存在一定程度的困难,这方面的工作有待延续。

2.2 排样问题的后处理

经过排样算法进行计算以后,所获取的排样方案只是一种近似的较优结果,所以排样方案可能存在理想的情况,这就需要对排样方案进行后续的人工干预,该过程通常称为排样问题的后处理过程。经过排样问题的后处理可使排样结果更加完善,过去也有少量学者强调了这方面的工作。贾志欣等人[23]运用计算机图形学处理技术结合现代智能算法的方法,按照图形预处理、自动排样、人工交互编辑3步解决了不规则零件的排样问题。黄星梅等人[24]通过交互寻优的手段对自动排样系统产生的排样图实现进一步的优化。

2.3 排样问题的近似求解算法

在板料优化排样问题中,最重要的步骤是采用一定的算法确定优化排样的方案。针对板料排样问题,目前的近似求解算法主要有确定性近似求解算法和启发式近似算法:

2.3.1 确定性近似求解算法

上世纪90年代前,国内外主要解决的板料排样问题主要是对矩形件的排样方案的确定,其中所采用的近似求解算法一般为确定性近似求解算法[25]如基于一维装箱的FFD算法、BFD算法和基于最左最下原则的算法(BottomLeft,BL)、双向背包算法、相近图形组合算法、动态规划算法等。在国内,文贵华等人[26]提出基于动态分割与合一的优化排样算法,将前一轮排样剩下的相邻余料动态地合并成较大的余料参与下一轮排样;崔耀东[27]等人提出连分数分支定界算法,用以实现对单一尺寸矩形毛坯的排样问题进行求解。这些排样算法的特点是具有确定性,求解结果仅决定于原材料和目标件以及求解策略,而与最优结果之间没有必然联系,不仅如此,通过这些方法求解的结果并不一定是较满意的解,而且对于较大的问题不是很适用。

2.3.2 启发式近似算法

启发式近似算法是研究人员受到自然界的启发所提出的一系列优化算法,在很多优化问题包括板料排样优化问题中具有较为理想的求解结果。在排样问题中,应用较多的启发式优化算法主要是模拟退火算法和遗传算法。贾志欣等人[28]针对传统的矩形件排样问题采用了模拟退火算法进行求解,建立了板料排样优化问题的模拟退火算法求解关键步骤。在此基础上,后续的研究人员采用模拟退火法解决了很多板料优化排样问题,涌现出很多新兴的工作。在排样问题求解中,遗传算法一种主要的算法,在遗传算法的应用方面开展了较多的工作[29,30]。杨威等人[29]采用遗传算法对大规模矩形零件在板材上的排样方案进行优化。贾志欣等人[30]则将这种算法应用到二维不规则零件排样优化问题中。龚志辉等人[31]提出了一种求解矩形件排样遗传算法的改进方法,实际上是在遗传算法中进行一定的预处理;陶献伟等人[32]将填充算法和遗传算法结合起来,应用填充算法对遗传算法作预处理,使矩形件更为方便;宋亚男等人[33]采用改进免疫算法对排样问题进行求解,探讨了记忆效应的影响。2008年,赵新芳等人[34]重新考虑了矩形件带排样问题的遗传算法,用带符号的有序整数串作为初始种群个体,改善了初始个体解的质量;吴斯等人[35]更提出了小生境免疫遗传算法用以解决硅钢片优化排样问题。采用他们描述的方法保持抗体群的多样性,加快了优良个体的产生,提高了算法的收敛速度。

将多种启发式优化算法结合使用是实现板料排样优化的一种重要方式,到目前为止已经开展了大量工作。张玉萍等人[13]结合了模拟退火算法和遗传算法,提出了基于模拟退火技术的遗传算法,解决了皮料加工中的皮料优化排样问题。在她们所提出的算法中,采用能自适应地控制变异率的优化搜索方法,使得优化高效地逼近全局最优解。蒋兴波等人[36]提出自适应模拟退火遗传算法来对板料排样进行优化,其中通过环形交叉算子和环形变异算子来构造出自适应遗传算法,实现遗传算法的交叉和变异概率的自动调整,从而提高了算法的效率和效果。李明等人[37]结合了模拟退火算法和粒子群算法,在其中采用了交叉算子和柯西变异算子,提高了算法的收敛速度和计算精度,获取了较好的排样优化方案。陈勇等人[38]结合遗传算法和模拟退火算法设计了一种启发式排样算法,用以处理不规则多边形的排样问题。

2.3.3 简化算法

除了确定性近似算法和启发式近似算法之外,还有少数学者提出通过简化算法来实现对板料排样问题的求解。王峰等人[39]针对单一实体排样提出了水平线迭代切割排样算法。许超等人[40]针对数控直角剪排样的要求提出了一种正交阵列排样算法。洪灵等人[41]设计了一种应用于不规则零件排样的快速解码算法,平行线化零件和板料,然后采用左下角(BL)策略驱动零件在板料上的排样。采用简化算法能够较快得到解,虽然在优化效果上没有精心设计的算法好,但仍然能够满足部分工程中的应用,得到工程解的认可。

3 结束语

排样系统 篇3

矩形件排样是指将一系列矩形零件排放到矩形板材区域内, 使得材料利用率最高。矩形件排样问题广泛存在于机械加工、造纸、玻璃等行业中。如何优化排样以提高材料利用率、降低生产成本, 对企业来说具有重要意义。从理论上看, 矩形件排样属于NP完全问题, 计算复杂性很高, 存在组合爆炸[1]。但由于生产实际的需要, 为此不少学者在这方面作了许多工作, 提出了一些近似算法[2,3,4,5,6]。由于各算法自身的局限性, 因而求得的结果并不十分满意。

本文利用模拟退火算法能够全局寻优特点和剩余矩形法的局部寻优特点, 将二者相结合进行矩形件的优化排样。实例表明, 本文算法是有效的。

1 矩形件排样问题描述

其中xi和yi分别表示矩形件pi (1≤i≤n) 在矩形板材上排入后其左下角的横坐标和纵坐标, H为零件排样后在板材上所达到的最大高度。如果零件较多, 在一块板材上排不完, 就在另外一块板材上排。那么H即为两块板材上高度的和。

因此矩形件排样优化问题可表述为:寻求满足约束条件的最佳排样方案, 使得板材的利用率E最大。

2 算法介绍

2.1 模拟退火算法

模拟退火算法[7]是上世纪80 年代初期出现的一种求解组合优化问题的方法。它起源于物理学中对金属退火过程的模拟。在搜索策略上它与传统的随机搜索方法不同。它在迭代过程中不仅接受使目标函数值变“好”的点, 而且还利用Metropolis准则以一定的概率接受使目标函数值变“差”的点。模拟退火算法的这种搜索策略有利于避免搜索过程陷入局部最优解, 从而达到求解全局优化问题的目的。目前, 模拟退火算法已受到人们广泛研究并被应用于多个领域[8,9,10,11,12,13]。

模拟退火算法求解过程如下 (以最小化问题为例) :

(1) 初始化。给定初始温度T0、初始解a0、每个温度T时的迭代次数N, 计算a0的目标函数值f (a0) 。

(2) 对当前解随机扰动产生新解a1, 计算对应的目标函数值f (a1) 。

(3) 计算函数值的增量df = f (a1)  f (a0) 。

(4) 如果df ≤0 , 则接受新解为当前解;否则以概率exp (df/T) 接受新解。

(5) 重复 (2) ~ (4) 步骤迭代N次。

(6) 如果满足算法终止条件, 则输出当前解为最优解, 结束算法;否则继续步骤 (7) 。算法终止条件一般为连续若干个新解a1都没有被接受时终止算法, 或是设定终止温度。

(7) 对当前温度T降温, 转步骤 (2) 。

2.2 剩余矩形排样算法

剩余矩形排样算法是目前提出的一种有效的排样算法[14]。它将所有可以使用的剩余原材料区域作为可以排样的区域, 从而让许多空闲的区域重新利用, 减少废料。剩余矩形算法弥补了BL或最小水平线方法中空区域无法排入矩形件的缺陷, 实现了动态寻优策略。

假设有N个矩形零件, pi为矩形件的序号, ri为排样方式, ri=1 表示将矩形件竖排, ri=0 表示将矩形件横排。对于给定的一个排样方案D ={P, R} ={ (p1, p2, …, pn) , (r1, r2, …, rn) }, 剩余矩形算法排样流程如下:

(1) 设板材的左下角和右上角坐标分别为 (0, 0) 和 (W, H) , 于是开始时剩余矩形数据集中只有一个矩形S1=[ (0, 0, ) , (W, H ) ]。

(2) 从矩形件序列P中取出第一个矩形件p1 (宽wp1, 高hp1) , 将p1根据相应排放方式r1排放在板材的左下角, 计算板材剩余矩形S={S1, S2}。如图1 所示。

若r1=0, 则S1=[ (wp1, 0) , (W, H) ], S2=[ (0, hp1) , (W, H) ];

若r1=1, 则S1=[ (hp1, 0) , (W, H) ], S2=[ (0, wp1) , (W, H) ]。

(3) 排放剩余矩形零件, 计算板材剩余矩形空间。

(1) 判断每个剩余矩形与已排入零件的图形关系, 去除与该零件相交部分, 形成新的剩余矩形数据。

(2) 整理新的剩余矩形数据。去掉面积为零的或已无法排下所剩的任何一个矩形件的剩余矩形, 并且去除具有完全包含关系的剩余矩形中面积小的矩形, 保留有相交关系的矩形。

(4) 进行剩余矩形与入排零件的匹配计算。在剩余矩形集中选择宽高均大于等于此矩形零件的底部最低最靠左的剩余矩形 (先靠下后靠左) , 让矩形件与剩余矩形的左下角重叠。

(5) 返回 (3) 继续执行, 直至零件排放完毕或板材再无可排放空间。

3 应用模拟退火算法和剩余矩形法求解矩形件排样问题

3.1 编解码方法

在优化排样过程中, 必须先确定编码方法。本文对矩形件采用十进制整数顺序编码, 用{0, 1}对各矩形零件的排样方向进行二值编码。规定矩形件横放时编号为0, 竖放时编号为1。例如有包含4 个矩形件的排列{4 0, 2 1, 1 1, 3 0}表示先横放4 号零件, 接着竖放2 号、1 号零件, 最后横放3 号零件。

解码就是将一个零件编号排列解转换为排样图。本文利用剩余矩形法来排放零件。

3.2 目标函数

本文采用 (1) 式作为目标函数, 利用剩余矩形算法计算目标函数值。显然, 目标函数值越大, 材料利用率越高。

3.3 降温方式

降温方式对模拟退火算法优化结果有很大影响。如果温度下降过快, 可能会丢失极值点;反之, 则大大降低算法的收敛速度。本文定义的降温公式为[15]

其中T0>0为初始温度, T (k) 为当第k次迭代的温度, m为大于等于1的常数。

3.4 终止条件

当满足下列条件之一时算法终止:

(2) 温度达到终止温度当达到最大迭代次数时。

本文定义板材高度下界H0为所有矩形零件的面积和与板材宽度的比值。即

4 排样实例

为了测试本文所提排样算法的有效性, 对文献[1]中的算例进行求解, 进行实例验证。按照本文提出的算法, 设置初始温度0.6, 终止温度为0.006, 降温系数m = 1, 得到的排样结果如图2 所示。排样结果的板材利用率为97.56%, 而文献[1]的板材利用率为93.75%。

5 结束语

模拟退火算法已在矩形件排样等组合优化问题求解上得到应用, 但该算法本身存在的不足使其在实际应用中难以保证计算结果的最优性。本文将剩余矩形排样算法和模拟退火算法融合到一起, 求解矩形件排样问题。实例表明, 本文所提算法是有效的。

但是, 本文算法并不保证总能得到最优解, 因此在实际应用中最好采用多种方法或多次求解, 再从这些较优方案中择优选用。

摘要：针对矩形件优化排样问题, 讨论了用模拟退火算法结合剩余矩形法求解问题。首先阐述了矩形件排样问题的数学模型, 然后给出了模拟退火剩余矩形算法求解问题的步骤和方法, 最后用实例进行了算法验证。实例分析表明, 采用模拟退火剩余矩形算法求解矩形件排样问题是适合的。

基于模拟退火的贯通约束不规则排样 篇4

二维排样问题是一类典型的组合爆炸优化问题,广泛应用于玻璃加工、金属切割、服装等行业。研究排样优化算法对提高原料利用率,建立节约型、环境友好型社会具有重要意义。Bennell等[1]分析了二维排样问题的各种矩形优化算法,对于不规则排样问题,由于其组合的可能性增大,零件之间的重叠、相交及相邻关系判断也较为复杂,因此采用传统的数学规划和单一的启发算法较难解决不规则排样问题[2]。李敬花等[3]采用凸多边形包络法对不规则多边形进行处理,结合遗传算法的快速全局搜索能力和模拟退火算法的局部搜索能力,以遗传算法做外层循环,以模拟退火做内层循环,从而改善遗传算法的早熟缺陷。张德富等[4]提出了一种基于离散临界多边形模型,用于求解二维不规则排样问题。梁利东等[5]将粒子群算法与剩余矩形匹配算法相融合,提高了排样优化问题的收敛速度并可以有效跳出局部最优。上述文献并未考虑排样过程中的贯通性约束条件(guillotine constrain)[6,7,8],即俗称的“一刀切”。贯通性约束是一种重要而常见的加工过程约束,一般认为,由于其计算代价太高,在一般非贯通约束排样方法中加入贯通性约束条件几乎是不可行的,因此,必须针对贯通约束研究专门的不规则排样算法。

贯通约束早期的研究采用矩包法,用不规则零件的最小外接矩形(MER)替代不规则零件本身进行排样,将不规则排样问题转化为矩形排样,然后用得到的排样结果从MER中还原不规则零件,这种处理方式简单易行,但是对于三角形等零件存在大量浪费。二步法[9,10]针对三角形、平行四边形等零件,将零件进行两两配对(pair),形成接近矩形的pair,然后再对配对组合的MER进行排样,在一定程度上解决了矩包法存在的浪费问题,但是仍不能保证每个pair形成近似矩形的图形。韩伟等[11,12]在二步法基础上进一步提出了一种将多个零件聚合成近似矩形的多阶段构造方法。在复合构造过程中,引入形状权重来控制复合图形与矩形的近似程度,权重越大,两个多边形复合后形成的多边形越接近矩形。该算法在前期采用较小的形状权重,有利于提高早期复合的出材率,而在后期采用较大的形状权重,有利于最终进化出接近矩形原片的图形复合。本文在文献[11-12]的基础上,进一步对分阶构造过程的有效性进行了理论分析,并提出了基于温控散列函数的形状权重调整方法。

1 基本概念

定义1一个凸多边形P可以表示为平面直角坐标系中的点组成的一个序列〈p1,p2,…,pn〉,其中n为多边形的边数,pi=〈xi,yi〉(i=1,2,…,n)是多边形的端点。多边形的第i条边记为ei=〈pi,pi+1〉(i=1,2,…,n-1),en=〈pn,p1〉。多边形内部的点的集合记为I(P),边界记为F(P),顶点集合记为V(P)。

定义2一个客户零件订单是一个凸多边形集合D={Pi|i=1,2,…,L},数据D中的多边形称作基元。

定义3凸多边形P(P∈D)的一个变换f可以表示为一个四元组〈m,x,y,t〉。其中m∈{0,1}表示镜像变换,取值1表示X镜像变换,0表示不进行镜像变换。Y镜像变换可由X镜像变换和旋转来完成。x,y∈R分别表示多边形沿x轴和y轴的平移量。t∈(-π,π]表示多边形以参照点p1为中心的旋转量。多边形的变换空间记为ψ,它是各个子变换空间的直积。

定义4设凸多边形P1,P2∈D,f1∈ψ1,f2∈ψ2分别是P1、P2上的变换,函数Φ:D×D→{-1,0,1}为

定义5设凸多边形P1,P2∈D,f1∈ψ1,f2∈ψ2分别是P1、P2上的一个变换,f=f1·f2是P1、P2的一个复合变换,记作f(P1,P2)=f1(P1)∪f2(P2)。若,则f称作P1、P2的不相交变换。

设C(S)表示点集S的最小凸包,则变换f(P1,P2)的最小凸包为C(V(P1)∪V(P2)),记为O(f(P1,P2))。f(P1,P2)的最小外接矩形记为R(f(P1、P2))。

定义6给定多边形P1,P2∈D,A(·)表示多边形的面积。则f(P1,P2)的凸包浪费率和矩包浪费率分别为

由图1可以看出,若凸包浪费率较小,则形成的匹配更为紧致,若矩包浪费率较小,则形成的匹配更近似于矩形,便于后期进行原片填充。据此,我们进一步定义加权浪费率。

定义7给定形状权重w,变换f(P1,P2)的加权浪费率定义为

定义8给定多边形P1、P2∈D及形状权重w,P1、P2的加权匹配是使得加权浪费率最小的不相交变换,记作,其中

由图2看出,若P1、P2是不相交的,则必存在直线e将多边形O(f(P1、P2))切分为两个多边形P1、P2,称e是O的一条贯通线,O相对于P1、P2是可贯通的。

2 复合

2.1 集合的变换

定义9给定集合,fi(i=1,2,…,t)是多边形Pi的一个变换。称作集合T的复合变换,且有f(T)=f1(P1)∪f2(P2)∪…∪ft(Pt)。对应地,T称作f(T)的原像。T上所有变换组成T的变换空间,记为。

定义10给定集合及其上的变换f。若Pi∈T,Pj∈T,i≠j,有,则f称为不相交变换。

定义11若C(S)表示点集S的最小凸包,则f(T)的最小凸包为

定义12给定集合及其上的变换f,O是f(T)的凸包。若满足以下两个条件之一,则f(T)称作可贯通的:1f(T)中含有且仅含有两个多边形Q1、Q2,且O相对于Q1、Q2是可贯通的;2存在O的一条贯通线,将f(T)划分为两个子集T1、T2,且T1、T2是贯通的。

若f(T)是可贯通的,则f称作T上的可贯通变换。进一步,若f是不相交变换,则称f为T上的可行变换。所有可行变换的集合组成可行空间,记为Γ(T)。玻璃排样问题可归结为在可行空间中寻找使得原材料用料最省的零件排样方案。

2.2 复合及其性质

定义15设集合,f1、f2分别是T1、T2上的变换,T1、T2的一个复合变换是一个多边形集合,记为f(T1,T2)=f1(T1)∪f2(T2)。

定义16给定集合,B1、B2分别是T1、T2的变换,O1、O2为B1、B2的凸包,w为权重,则B1、B2的加权匹配fw*(B1,B2)由O1、O2的加权匹配唯一确定,即fw*(B1,B2)=fw*(O1,O2),其中O为O1、O2的凸包。若,则称fw*(B1,B2)为B1、B2的θ-可接受匹配。

定义17设是T的一个变换。若满足下面两个条件之一,则称B是T的一个θ-复合:1B只含有一个元素;2 T可以划分为T1、T2,若B1、B2分别是T1、T2的θ-复合,则B是B1、B2的θ-可接受匹配。

如图3所示,一个θ-复合B对应一棵二叉复合树,记为T(B)。该二叉树以原像T中元素作为叶子节点,以复合B为根节点。根据定义17,T(B)构造如下:若符合条件1则T(B)含有且只含有一个节点B;若符合条件2,则分别以B1、B2构造二叉树T(B1)、T(B2),并进一步以T(B1)和T(B2)作为左右子树构造二叉树T(B)。可以证明,θ-复合是原像T的一个可行变换。证明过程如下。

(1)首先用数学归纳法证明H∈T(B)是其原像的非相交变换。1若H是两个多边形P1、P2的匹配,则H必是P1、P2最优匹配,得证;2若H的左右子树T(H1)、T(H2)均是原像T1、T2的不相交变换,由H是H1、H2的加权匹配,可得H是原像T的不相交变换。

(2)证明H∈T(B)是其原像的贯通变换。1若H是两个多边形P1、P2的匹配,则H必是P1、P2的贯通变换;2若H的左右子树T(H1)、T(H2)均是原像T1、T2的贯通变换,又H是H1、H2的加权匹配,若记O、O1、O2分别是H、H1、H2的凸包,则O相对于O1、O2是可贯通的。

综合(1)、(2),T(B)的任意一个节点是其原像的可行变换,证毕。

3 基于模拟退火的分阶构造算法

3.1 基本例程:两个多边形的匹配

文献[8]给出了两个多边形零件的slide/attach启发式匹配方法,首先对P1的顶点和边进行顺时针编号,对P2的顶点和边进行逆时针编号,定义基本操作函数如下。

(1)镜像M(P,m):对多边形P进行镜像操作,m∈{0,1},取值1表示X镜像变换,0表示不进行镜像变换。

(2)靠接A(P1,P2,i,j):保持P1不变,将P2平移,使其第j个顶点与P1的第i个顶点重合,并旋转P2,使其第j条边与P1的第i条边重合。

(3)滑动S(P1,P2,i,j,d):平移P2,使其第j个顶点沿着P1的第i条边滑动,滑动距离为d,d≤max(0,D(ei)-D(ej))。

图4所示为靠接操作与滑动操作示例。

算法1两个凸多边形启发式匹配算法如下:

3.2 森林

考虑到每个复合可以看作一棵树,我们将所有m阶θ-复合组成的集合称为m阶θ-森林。事实上,利用θ-复合之间定义清晰的组合关系,第m阶森林可以由前m-1阶森林构造出来,如图5所示。

定义18给定权重w及阈值θ,定义第m阶θ-森林为

通过结构化存储已有森林,我们可以利用类似求解Fibonacci序列的构造方法来快速构造高阶森林。实际上,森林构造过程是一个多步决策过程,每阶森林代表一步决策。在森林构造过程中,将来自相同或不同森林的两个复合的外接凸包看作多边形,利用4.1节的多边形匹配基本例程求其匹配。将匹配度作为启发信息,并与阈值θ相比较,以决定是否选入更高阶的森林。之所以不从森林中截取固定数目的复合,是因为通过匹配度来截取更具有灵活性,有利于保持复合的多样性。

3.3 冲突检查及原片约束

森林构造过程需要进行冲突检查,即保证每个新生成复合的原像不包含相同的多边形。对于Bx∈giθ,w,By∈gjθ,w,若Tx、Ty是Bx、By的原像,则要求。需要说明的是,森林内不同的复合可以含有相同的基元多边形,这有利于增强森林内复合的多样性。

森林构造过程中,为保证新构造的每个复合尺寸不超过原片尺寸,需要进行约束检查。设原片的长和宽分别为L和W,对于新构造的复合B,若l(R(B))和w(R(B))分别为B的外接最小矩形的长和宽,则要求l(R(B))≤L,w(R(B))≤W。

3.4 温控散列函数

模拟退火通过温控参数解决了优化算法在探索(explore)和利用(exploit)上的两难问题,从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即若陷入局部最优解能概率性地跳出并最终趋于全局最优。在早期通过较高的温度使得算法在全局范围搜索,而在后期算法能较快地收敛到当前找寻到的最优区域内。在森林构造算法的早期,采用较小的权重可以使生成的复合具有较小的浪费率。而在后期采用较大的权重可以得到类似矩形的复合,用于填充原片。经验数据显示,森林构造过程中各阶森林中复合的数目大致符合二项式分布,这是因为早期基本图形的组合可能性较大,而后期受到冲突检测和原片尺寸约束,虽然复合的数目增加,但是复合进行继续组合的可能性降低。因此考虑在早期和后期使形状权重的变化率较小,而在中间阶段使形状权重发生明显变化,为此构造了温控参数来适应这一要求。若最大进化代数为mg,权重w的变化区间设定为[0,1],则第i阶森林中,形状权重设定为

式中,T为温度参数;mid=mg/2。

考虑到给定温度参数T,权重w完全由森林代数确定,如图6所示。后文将giθ,wi简记为giθ。

3.5 森林构造算法

算法2森林构造算法(forest construction algorithm,FCA)如下:

4 实验

4.1 实验数据

欧洲切割与排样研究会(ESICUP)网站上载了文献[9]中采用的测试数据作为不规则贯通排样研究公开数据,8个数据集中4个取自Jotika软件公司实际订单数据,另外4个则是抽样数据。表1给出了数据集的统计参数,其中零件的不规则度是其外接最小矩形内的平均浪费率,面积取量纲一单位。实验中,原片量纲一尺寸为3210×2250。

定义19若多边形P的最小外接矩形为R(P),则数据集D的不规则度为。

4.2 实验对比

定义20排样平均出材率为

式中,N为排样原片数量;A为原片面积。

我们选择常数散列和线性散列与温控散列进行对比。常数散列方法是指在构造过程中,形状权重w是一个常数,一般取值为0或者1。线性散列方法是指在构造过程中,权重变化率是常数。第i(i=1,2,…,mg)阶森林中,权重设定为wi=i/mg。表2列出了各个数据集合在不同参数下的平均出材率,测试表明,选取合适的温度参数T,温控散列函数能使排样利用率取得较好的结果。

从表2中可以看出温控参数T应该随阈值θ取值变化,一般增大θ应该适当降低T。这是因为阈值θ越大,则进化的选择压力越大,算法越可能出现早熟,因此排样结果相对较差。一般θ的设定应该接近原片的平均出材率,但在算法运行之前,我们无法获知平均出材率,因此在实际应用中通常根据原片尺寸和零件的平均尺寸来设定。在确定阈值θ的情况下,较大的温控参数T代表较大的选择压力,这是因为较大的T会使得算法早期较小的形状权重产生较久的作用,因此进化得到的低阶森林中复合数目也较少。

4.3 时间复杂度

实验所用计算机的处理器为Intel i5 M520,主频2.4GHz,内存2GB。测试结果见表3。不难看出,算法的运行时间随问题规模大致呈线性增长,这是因为算法充分利用了复合之间的组合关系,采用存储记忆快速构造各阶森林。随着阈值θ和温度T的增大,选择压力也会较大,算法时间也会变短。

5 结论

(1)本文针对不规则凸多边形零件的排样问题,对已有文献提出的分阶段构造算法进行了理论证明和实验分析,发现森林构造过程中各阶森林中复合的数目大致符合二项式分布,这是因为早期基本图形的组合可能性较大,而后期受到冲突检测和原片尺寸约束,虽然复合的数目增加,但是复合进行继续组合的可能性降低。

(2)基于模拟退火思想提出温控散列函数控制形状权重的变化率,使得早期和后期形状权重的变化率小,而在中间阶段使形状权重发生明显变化。

(3)基于ESICUP公开的标准数据,分别对常数散列、线性散列和温控散列进行了对比实验,结果表明温控散列能够有效提高排样出材率。

参考文献

[1]Bennell J A,Oliveira J F.A Tutorial in Irregular Shape Packing Problems[J].Journal of the Operational Research Society,2009,60(1):93-105.

[2]Bennell J,Scheithauer G,Stoyan Y,et al.Tools of Mathematical Modeling of Arbitrary Object Packing Problems[J].Annals of Operations Research,2010,179(1):343-368.

[3]李敬花,樊付见,王昊,等.遗传模拟退火融合算法求解工程二维排样问题[J].计算机集成制造系统,2011,17(9):1962-1967.Li Jinghua,Fan Fujian,Wang Hao,et al.Combination Genetic Simulated Annealing Algorithms for Solving Two-dimensional Packing Problem[J].Computer Integrated Manufacturing Systems,2011,17(9):1962-1967.

[4]张德富,陈竞驰,刘永凯,等.用于二维不规则排样的离散临界多边形模型[J].软件学报,2009,20(6):1511-1520.Zhang Defu,Chen Jingchi,Liu Yongkai,et al.Discrete No-fit Polygon,a Simple Structure for the2-D Irregular Packing Problem[J].Journal of Software,2009,20(6):1511-1520.

[5]梁利东,钟相强.粒子群算法在不规则件排样优化中的应用[J].中国机械工程,2010,21(17):2050-2052.Liang Lidong,Zhong Xiangqiang.Applications of Particle Swarm Optimization for Solving Irregular Part Nesting Problems[J].China Mechanical Engineering,2010,21(17):2050-2052.

[6]Christofides N,Hadjiconstantinou E.An Exact Algorithm for Orthogonal 2-D Cutting Problems Using Guillotine Cuts[J].European Journal of Operational Research,1995,83(1):21-38.

[7]戈鹏,邱厌庆,刘柱胜,等.一刀切问题的优化二叉树排样[J].计算机集成制造系统,2011,17(2):329-337.Ge Peng,Qiu Yanqing,Liu Zhusheng,et al.Optimized Binary Tree Packing of Guillotine Problem[J].Computer Integrated Manufacturing Systems,2011,17(2):329-337.

[8]王桂兰,成亚云,朱龙彪,等.满足“一刀切”要求的木工板排样优化研究[J].工程设计学报,2014,21(3):212-216.Wang Guilan,Cheng Yayun,Zhu Longbiao,et al.Research on Optimum"Guillotine Cutting"Lay Out of Carpentry Board[J].Chinese Journal of Engineering Design,2014,21(3):212-216.

[9]Hifi M,M'Hallah R,Saadi T.Algorithms for the Constrained Two-staged Two-dimensional Cutting Problem[J].Informs Journal on Computing,2008,20(2):212-221.

[10]曹大勇,杨梅,科托夫·弗拉基米尔·米哈伊拉维奇,等.二维一刀切装箱问题的两阶段启发式算法[J].计算机集成制造系统,2012,18(9):1954-1963.Cao Dayong,Yang Mei,Kotov V M,et al.Twostage Heuristic Algorithm for Two-dimensional Guillotine Bin Packing Problem[J].Computer Integrated Manufacturing Systems,2012,18(9):1954-1963.

[11]韩伟,马福民.带贯通约束的不规则排样分阶构造算法[J].小型微型计算机系统,2012(11):2421-2424.Han Wei,Ma Fumin.Layered Constructive Algorithm for Irregular Guillotine Packing Problem[J].Journal of Chinese Computer Systems,2012(11):2421-2424.

排样系统 篇5

矩形件优化排样是在给定的矩形板材上将矩形件按最优方式进行排布, 要求零件排放在板材内, 各个零件互不重叠, 并满足一定的工艺要求, 最大限度地利用板材, 以达到节约材料、提高效益的目的。对于非矩形的不规则件排样问题, 可以通过求取其最小包络矩形的方法简化预处理, 并对一些形状互补的不规则件构造矩形排样单元进行优化组合, 使不规则件组合在最小包络矩形中所占的面积比例尽可能大, 对组合后的图形再求取最小包络矩形, 从而将不规则件排样问题转化为矩形件的排样问题。排样问题广泛应用于机械制造、轻工、家具、服装以及印刷等行业。因此, 研究矩形件在板材上的优化排样具有重要的现实意义。

排样问题实质上是一个组合优化的二维布局问题, 从数学复杂性理论看, 是计算复杂性最高的一类NP完全问题, 其计算复杂度随着排样规模的增大呈指数级增长, 至今还无法找到解决该问题的有效多项式算法。矩形件优化排样应用广泛且具有简单的几何特征, 研究工作开展得较早, 可使用数学规划技术[1,2,3], 但由于其计算量大从而影响了其在矩形件优化排样问题中的应用。曹炬等[4]提出背包算法来解决矩形件排样问题, 但该算法本身同样存在计算量大的缺陷。文献[5-6]分别应用粒子群算法和神经网络对优化排样进行了研究。文献[7-8]使用简单遗传算法来进行优化排样, 但收敛速度和算法稳定性不太理想。Babu等[9]利用遗传算法和启发式算法给出了多张矩形板材上的矩形件排样, 但因对进化过程未进行有效控制, 同样存在收敛速度慢的问题。

遗传算法 (genetic algorithm, GA) 理论上能从概率意义上以随机的方式寻找到最优解, 具有良好的全局搜索能力, 但却存在局部寻优能力差、易早熟收敛等缺点。模拟退火算法 (simulated annealing algorithm, SA) 的基本思想是跳出局部最优解, 理论上能够保证算法以概率1收敛到全局最优解, 因此具有较强的局部搜索能力, 但把握搜索过程的能力不强。本文从遗传模拟退火算法 (genetic simulated annealing algorithm, GSA) 优化策略的构造出发, 同时考虑到:如果交叉概率过大, 则遗传模式被破坏的可能性也大, 使得具有高适应度值的个体结构很容易就被破坏, 而交叉概率过小则会使进化过程缓慢, 以致停滞不前;对于变异概率, 如果取值过小, 则不易产生新的个体结构, 如果取值过大, 那么GA就成了纯粹的随机算法, 故本文采用自适应的交叉概率和变异概率[10,11], 避免了交叉概率和变异概率因上述情况而出现的问题, 同时利用基于预选择机制的小生境技术对子辈个体是否替换父辈个体加以控制, 即将GSA融合小生境技术 (niche technology) , 提出一种基于小生境技术的自适应遗传模拟退火算法 (adaptive niched genetic simulated annealing algorithm, ANGSA) , 用于矩形件优化排样问题, 从而提高了算法的稳定性和收敛速度。最后应用基于最低水平线策略的启发式排样算法来实现自动排样。

1 矩形件排样问题数学模型

1.1 问题描述

矩形件的优化排样问题是在若干张宽度为W、长度为L的板材内, 将若干矩形件P1, P2, …, Pn按最优方式进行排样, 排样的目的是使板材的利用率最高, 因为在排样过程中对具体矩形件的需求数量未必是1, 所以Pi和Pj (i≠j;i, j=1, 2, …, n) 可能是尺寸相同的矩形件。排样过程要求满足以下约束条件:①Pi、Pj互不重叠;②Pi必须放置在板材内部;③Pi的边与板材的边平行;④满足一定的工艺要求。

1.2 排样数学模型

任意一个矩形件Pi (i=1, 2, …, n) 均可用一个七元组表示:

其中, (xi, yi) 表示矩形件Pi的左下角坐标; (x′i, y′i) 表示矩形件Pi的右上角坐标; (wi, li) 表示矩形件Pi的宽度和长度;θi表示矩形件Pi的旋转角度, θi∈{0°, 90°}。

对于右上角坐标 (x′i, y′i) :

假设任意两个矩形件的左下角和右上角坐标分别为 (x1, y1) , (x′1, y′1) 和 (x2, y2) , (x′2, y′2) , 则满足下面4个条件之一便能保证矩形件互不重叠:

板材的利用率F是指所有矩形件的面积与所使用的板材的面积之比, 假设排样共使用m张板材, 同时考虑约束条件, 矩形件的优化排样问题的数学模型可表述为

其中, L′为优化排样后矩形件所占用的板材长度, 由于所需矩形件未必能够在一张板材内排下, 则第k (1<k≤m) 张板材的左下角坐标为 (0, kL) 。最后两个约束条件是为了保证同一矩形件在同一张板材内排样。

2 矩形件排样算法流程及关键技术

本文先由ANGSA得到矩形件的最优排样顺序和排放方式, 再由基于最低水平线策略的启发式排样算法实现自动排样, 因此, 首先对算法的一些关键技术及流程作如下说明。

2.1 遗传算法

2.1.1 个体编码

矩形件的优化排样采用整数编码, 将n个矩形件P1, P2, …, Pn分别用整数1, 2, …, n进行编号, 零件编号构成一个整数串X={x1, x2, …, xn}, 1≤|xi|≤n, 表示矩形件的一个排样顺序, 其中, 每个xi都有正负之分, xi取正时表示θi=0°, xi取负时表示θi=90°, 即由其正负来表示矩形件的排放方式。这样, 一个整数串就是一个个体, 若干个个体便构成了GA的一个群体。假设某个个体为{-4, 6, -1, -3, 5, 2}, 表示排样顺序为4, 6, 1, 3, 5, 2, 编号为4, 1, 3的矩形件旋转90°, 其他矩形件不旋转进行排放。

2.1.2 自适应的群体规模

群体规模的大小直接影响到算法的收敛速度和求解结果, 群体规模过大, 算法收敛速度慢;群体规模过小, 群体多样性变差, 影响最终的求解结果。因此, 本文采用了自适应的群体规模大小, 群体规模N随待排样矩形件个数n而变化, 考虑到个体的长度与矩形件的个数n相等, 并且每个矩形件有两种排放方式, 这里取N=2n。

2.1.3 适应度函数

GA中对一个个体的好坏用适应度函数评价, 适应度函数值越大, 个体的质量越好。因此, 本文的适应度函数便可以用板材的利用率F来表示。即对于个体Xi (1≤i≤N) , 其适应度函数值为F (Xi) 。

2.1.4 遗传算子

(1) 选择算子。为了减少父辈群体产生的最佳个体丢失, 同时使适应度函数值较高的个体有更多的生存机会, 选择算子采用精英选择策略与“轮盘赌”式的正比选择法相结合的算法, 将父辈群体中适应度函数值最大的个体直接选择到下一代, 其余的N-1个个体采用“轮盘赌”策略进行选择。

(2) 交叉算子。交叉是产生新个体的主要方法。本文采用双点交叉, 首先将父辈群体中的N个个体进行两两随机配对, 得到N′对个体, N′等于N/2的下取整。对一对个体中的两个个体X1、X2执行交叉操作之前, 先在[0, 1]之间生成一个随机数r, 如果r大于交叉概率Pc, 则对这对个体执行交叉操作, 产生两个新个体X1new、X2new, 否则不执行。双点交叉是在1~n范围内随机产生两个交叉位b1、b2 (1≤b1<b2≤n) , 将X1中位于b1和b2之间的基因复制作为X1new前面的基因, 剩余基因按在X2new中出现的顺序复制到X1new的后面, 同理可以得到另一个子辈个体X2new。假设X1={-4, 6, -1, -3, 5, 2}, X2={-5, -2, 6, 1, 4, -3}, 交叉位b1=2, b2=4, 则执行交叉算子之后得到的新个体X1new={6, -1, -3, -5, -2, 4}, X2new={-2, 6, 1, -4, -3, 5}。

(3) 变异算子。变异是产生新个体的辅助方法。针对个体编码的形式, 本文对父辈群体中任意一个个体X分别采用顺序变异和旋转变异两种变异方式。对一个个体X执行变异操作之前, 先在[0, 1]之间生成一个随机数r′, 如果r′大于变异概率Pm, 则对这个个体执行变异操作, 否则不执行。顺序变异就是随机生成两个1~n范围内的顺序变异位c1、c2 (1≤c1<c2≤n) , 将个体X中的第c1个基因和第c2个基因的位置互换。假设X={-4, 6, -1, -3, 5, 2}, 顺序变异位c1=2, c2=4, 则执行顺序变异之后得到的个体X′={-4, -3, -1, 6, 5, 2}。旋转变异就是随机生成一个1~n范围内的旋转变异位d, 将执行顺序变异之后得到的新个体X′的第d个基因的符号取反, X′={-4, -3, -1, 6, 5, 2}, 假设d=5, 则执行旋转变异后得到的新个体Xnew={-4, -3, -1, 6, -5, 2}。

2.1.5 基于预选择机制的小生境技术

为了有效地保持群体的多样性并考虑到子辈个体与父辈个体之间的相似性, 本文对于交叉操作和变异操作之后得到的子辈个体是否替换父辈个体采用了基于预选择机制的小生境技术[12]。

交叉运算中:对于X1和X1new, 如果F (X1new) >F (X1) , 则用X1new替换X1, 否则保留X1;对于X2和X2new, 如果F (X2new) >F (X2) , 则用X2new替换X2, 否则保留X2。

变异运算中:对于X和X′, 如果F (X′) >F (X) , 则用X′替换X, 否则保留X。

2.1.6 自适应的交叉概率和变异概率

执行交叉算子和变异算子时都是通过判断所生成的随机数与交叉概率Pc和变异概率Pm的大小来决定是否执行的。因为算法的性能在很大程度上受到了Pc和Pm的影响, 所以本文采用了自适应的Pc和Pm。当某个个体的适应度函数值低于群体的平均适应度函数值时, 说明该个体性能较差, 应取较大的交叉概率和变异概率;反之, 如果其适应度函数值高于群体的平均适应度函数值, 说明该个体性能优良, 应取较小的交叉概率和变异概率。本文将GA中的自适应交叉概率和变异概率[13]表示为

式中, Fmax为群体中的最大适应度函数值;Favg为每代群体的平均适应度函数值;F′为执行交叉操作的2个个体中较大的适应度函数值;F为执行变异操作的个体的适应度函数值。

Pc1、Pc2、Pm1、Pm2需事先确定, 且Pc1, Pc2, Pm1, Pm2∈[0, 1]。

2.2 模拟退火算法

为了避免GA算法出现早熟收敛, 陷入局部最优解, 对执行完GA选择、交叉和变异所得到的N个个体进行模拟退化运算, 通过状态产生函数来得到每个个体所在邻域内的一个新个体, 然后对适应度函数值低于原个体的新个体按新个体接受概率进行保留, 从而避免原个体为局部最优解时GA算法遗失最优解的可能。将新生成的N个个体作为下一次迭代时GA的群体。在执行SA时, 有以下几点需要需要说明。

2.2.1 初始温度

SA对初始温度的要求为足够高, 以便满足接受概率为1的初始要求。但初始温度为无穷大是无法实现的。本文中初始温度设为

式中, α为调节参数;n为个体长度;Fmin为初始群体中的最小适应度函数值。

2.2.2 降温函数

SA中, 线性降温会在高温区停留较长时间, 而在低温区时, 温度下降又会过快, 故不能很好地完成搜索工作。比例降温弥补了这一缺陷, 因此本文采用比例降温函数:

式中, β为降温系数, β∈ (0, 1) 。

2.2.3 状态产生函数

为了得到个体X的邻域中的一个新个体X′, 以便当X为局部最优解时能够使算法跳出局部最优, 同时结合本文中个体的编码方式, 将状态产生函数设计为对X中始于第i (1≤i<n) 个基因的连续k (2≤k≤n) 个基因执行逆序操作, 假设X={-4, 6, -1, -3, 5, 2}, i=2, k=3, 则由状态产生函数得到的新个体X′={-4, -3, -1, 6, 5, 2}。

2.2.4 新个体接受概率

为了保证适应度函数值低于原个体的新个体以一定的概率被保留下来, 对新个体接受概率进行如下定义:对个体X和X′分别计算其适用度函数值F (X) 、F (X′) 及其差值, 则当ΔF≤0时, 用新个体X′代替个体X;当ΔF>0时, 如果大于一个0~1之间的随机数, 则用新个体X′代替个体X, 否则保留原个体X[14]。

2.3 启发式排样算法

由以上所述的ANGSA得到一个个体的编码之后, 要想得到该个体的适应度函数值就需要对该个体进行解码, 也就是得到该个体所对应的排样图, 启发式排样算法便可以实现这个过程。然而, 考虑到最左最下 (bottom-left, BL) 算法易产生排样图左侧偏高以及“下台阶”算法易发生排样图右侧偏高的问题, 本文采用基于最高轮廓线的最低水平线启发式排样算法[15]来对个体编码进行排样即解码, 该算法具体步骤如下:

(1) 设置初始最高轮廓线为板材最下面的边;

(2) 每当要排入一个矩形件Pi时, 选取最高轮廓线最低的一段水平线, 如有数段, 则选取最左边的一段, 测试该段的宽度是否大于或等于要排入矩形件的宽度。如果该段的宽度大于或等于要排入矩形件的宽度, 则将该矩形件在此位置排放, 更新最高轮廓线;否则, 查询与最低水平线段相邻的左、右两段水平线, 将最低水平线提升至与高度较低的一段平齐, 更新矩形件最高轮廓线;

(3) 重复步骤 (2) , 直至能排入该矩形件;

(4) 重复上述过程, 直至所有矩形件排放完毕。

对于个体编码{-1, 2, -3, 4}, 采用该算法的排样过程如图1所示。

将矩形件1、2排放之后, 最低水平线位于最右端, 接着要排放矩形件3, 此时最低水平线的宽度小于矩形件3的宽度, 因此将提升该段最低水平线与高度较低的左段最低水平线平齐, 此时左段最低水平线的宽度大于矩形件3的宽度, 因此将矩形件3排放在此, 同理可排放矩形件4。

2.4 算法收敛准则

在算法求解过程中, 整个过程是趋于收敛的。本文设定的收敛准则为:如果两代相邻种群的平均适应度函数值之差小于0.05%, 则认为算法收敛并停止迭代;否则, 当遗传代数大于特定代数Gmax时, 迭代自动停止, 则整个迭代过程中适应度函数值最大的个体所对应的排样方案为最终排样方案。

2.5 矩形件排样算法流程

本文提出的针对矩形件排样的算法流程如图2所示。

3 实例分析

为了验证所提出的ANGSA的有效性, 本文对从某机械制造厂的零件库中随机选取的一组不同尺寸的矩形件进行了排样计算。ANGSA的参数设置如下:初始交叉概率Pc1=0.9, Pc2=0.6, 初始变异概率Pm1=0.5, Pm2=0.1, 初始温度调节参数α=5, 降温函数的降温系数β=0.95, 算法收敛准则中Gmax=100。排样板材长度L=1000mm, 板材宽度W=640mm, 随机选取12种矩形件, 矩形件尺寸及所需数量如表1所示。

某次运行排样结果如图3所示。由排样结果可知, 排样共使用三张板材, 图3中虚线为排样结果的最高轮廓线, 其高度为2722mm, 板材利用率达到93.12%。

为了验证本文所提出的ANGSA的求优性能, 在采用上述实例的基础上将应用GA和GSA对矩形件优化排样的求优性能与其进行对比, 解码均采用基于最高轮廓线的最低水平线启发式排样算法。为了减小参数选择对算法性能的影响, 对三种算法中的相同参数取相同值。ANGSA参数设置如上所述;GA的参数设置如下:群体规模N=200, 交叉概率Pc=0.9, 变异概率Pm=0.1, 算法收敛准则中Gmax=100;GSA的参数设置如下:群体规模N=200, 交叉概率Pc=0.9, 变异概率Pm=0.1, 初始温度调节参数α=5, 降温函数的降温系数β=0.95, 算法收敛准则中Gmax=100。对三种算法分别运行10次, 得到各自的最大排样长度Lmax、最小排样长度Lmin、平均排样长度Lavg。对比结果如表2所示。

mm

从表2可知, 本文提出的ANGSA对矩形件优化排样的求解效果无论是最大排样长度Lmax、最小排样长度Lmin还是平均排样长度Lavg, 均优于GA和GSA。因此, ANGSA的求优性能优于GA和GSA, 相对于GA和GSA, ANGSA能够求得更优解。

4 结语

本文对在实际应用和理论研究方面都具有重要意义的矩形件优化排样问题进行了研究, 提出了ANGSA算法, 通过GSA得到矩形件排样的最优次序和排放方式, 同时考虑到种群的多样性以及算法的收敛速度, 利用小生境技术对子辈个体是否替换父辈个体进行控制, 并使用了自适应的群体规模以及自适应的交叉概率和变异概率, 用基于最高轮廓线的最低水平线启发式排样算法快速实现矩形件的自动排样。通过与GA和GSA的实验数据对比, 证明ANGSA的求优性能更佳。在大批量生产时, 本文提出的算法能够明显地提高板材的利用率, 可带来显著的经济效益, 因此具有重要的现实意义。

排样系统 篇6

薄金属材料冲裁一般是指冲压件的精度在±0.01 mm以内,平面度控制在±0.03mm以内的冲裁。 由于薄金属在冲裁过程中精度要求高, 且难以有效控制材料变形,一直是冲压模具设计的难点。本文主要通过对薄金属材料冲模排样的分析, 结合工厂的实际工作经验, 介绍了薄金属材料冲模排样设计方法和防跳废料的处理措施, 对相似类型的模具设计具有一定借鉴意义。

1工艺分析

如图1所示为薄金属的产品展开示意图。 设中心层系数为K,弯曲内平径为r,材料厚度为t,弯曲角度为 α,L1,L2为直线部分长度, 展开长度为L,则有L=L1+L2+2π( r+kt) α/360,中心层系数K的大小根据实践经验按以下公式选取:

当 r/t≤1.0 时K=0.3

当 1.0<r/t≤5.0 时K=0.4

当 r/t>5.0 时K=0.5

该公式适合一切材料厚度的弯曲展开计算,实践应用中应根据经验适当调整。

对产品图面进行分析。

( 1) 产品图面检查。 包括:1产品的要求是否合理;2产品的毛边面及冲切面要求;3无指定R角的决定;4被加工板材的压延方向的影响;5外观品质的要求,冲切加工的限制等。

( 2) 图面数据的重组。 包括:1依制品的尺寸公差决定加工目标值; 2考虑制品精度的重要度决定料条的连接方式; 3考虑制品及废料的收取及处理决定其冲切形状。

2排样设计

2.1料带布置的设计原则

( 1) 依产品的要求,确定产品在排样时是否有纤维方向的要求。

( 2) 依产品展开尺寸大小决定料宽及步骤, 决定产品在料带上的布置以达到较高的材料利用率。

( 3) 注意冲切加工时 ,料条连结部的变形现象。

( 4) 切刃的形状应尽可能简单化 ,应避免引起跳屑的形状, 形状衔接处应减少,考虑冲头强度。

( 5) 冲导引孔的下一工序应设计导引销以保证料带的送料与定位精度。

( 6) 考虑冲切及料条变形决定冲切形状的顺序。

( 7) 重要部分应在同一工站至少应在相邻工站加工。

2.2常用带料方式

常用带料方式如图2所示。 有两侧系带法、单侧系带法、中央系带法、两侧系带桥带共用法等。

2.3料带的补强设计

在一般的薄材模具设计中, 料带的

整体强度决定着产品的稳定性,为增加料带的强度, 在料带强度较差处的废料上增加补强, 提高料带的送料强度。

( 1) 凸包补强。 此方法适用于一般较窄料带( 150 mm以内) 、模具较短的情况( 1500mm以内) 。 设计时需注意,不应因为打补强凸包而增加料带的宽度,凸包高度一般有0.2mm~0.5mm即可,注意后续工序的让位,如图3所示。

( 2) 折弯补强。 此补强一般用于较宽料带( 150mm以上) 、模具较长( 1500mm以上) 的模具当中,也可以与凸包补强两者综合运用。设计时需注意,补强折弯的高度取1.5mm~2.0mm为宜, 多了浪费材料,少了影响补强折弯的质量。 90°折弯冲头与材料接触面做平面( 图4) ,有夹角时会因为角度而先接触材料,影响补强折弯的稳定性。

做折弯补强后用浮升导料块送料, 受折弯角度的影响, 料带与浮升块的导料间隙取0.2mm~0.5mm为宜。 其他做法与两用销相同。

3防跳废料的处理

3.1处理废料上冲头防跳废料

( 1) 冲头上加卡槽防止跳废料,如图5所示。

( 2) 规则废料上加挂钩可有效防止跳废料。

3.2冲头做内脱料销防跳废料

使用时要注意顶料销的顶出高度, 保证在开模状态下顶料销的高度不能露出脱料板, 反之易将材料顶变形,影响产品质量,如图7所示。

3.3加内吹防跳废料

设计时需注意在做小吹气孔时保证冲头的强度,如图8所示。

3.4处理下模刀口防跳废料

下模刀口防跳废料设计如图9所示。 1刀口入子分上下两层,刀口直身位做短,下垫块做逃孔( 图9a) 。 2小圆孔下模入子做逃孔,单边+0.2mm~0.3mm( 图9b) 。 3刀口间隙局部做小一半 ,此方法一般用在刀口间隙大于0.01时选用,对加工要求很高( 图9c) 。

4结束语

排样系统 篇7

二维排样问题就是将一系列形状不同的零件排放在给定的板材上,选择最优的排布方法使板材的利用率最高,从而达到节约资源、降低生产成本的目的。 其实质就是零件在板材上的组合优化问题, 其求解过程属于非确定性多项式( Nondeterministic Polynomial, NP) 完全问题 , 在人工智能技术中人工智能算法使得NP问题得到了有效的近似解决办法[1],因此随着计算机技术的飞速发展, 人工智能算法在排样技术中的应用成为重点。通过计算机排样降低了人力,提高了排样的质量,增加了企业的经济效益,增强了企业的竞争力。随着计算机技术的发展,排样智能化将是必然的发展趋势[2]。常用的排样算法有禁忌搜索算法、模拟退火算法、遗传算法、粒子群算法、蚁群算法、神经网络算法等。

1排样算法

1.1禁忌搜索算法在排样中的应用

禁忌搜索法的主要思想是同时建立一个搜索结构和一个控制结构, 控制结构又包括数据表和搜索范围控制系统。 数据表主要是对所得到的数据值进行存储和清除, 搜索范围控制系统是对搜索结构提供的数据值进行评价及处理, 搜索范围控制系统将决定哪些值会被存贮在数据表内, 哪些值可以作为返回值返回给搜索结构。 搜索结构根据搜索范围控制系统提供的返回值进行下一步搜索, 然后再将搜索得来的新值提供给搜索范围控制系统进行评价, 同时进行数据的存贮和更新。如此,进行有限次的迭代搜索后,从数据表中取出最优值作为搜索的结果,如图1所示。

禁忌要求为:

( 1) 当解序列的评价值在目前为止是最优时 ,则评定为满足要求;

( 2) 当解序列的评价值与当前序列的评价值差值很大时,此处应进行标记处理,亦应作满足要求处理;

( 3) 当连续搜索的值都在禁忌表时 ,为防止进入局部最优,设定评价值较低的序列为当前序列。

禁忌搜索算法是由搜索结构、 数据表和搜索范围控制系统三部分组成的循环迭代关系。 这三部分的设计方法将决定整个搜索过程的效率搜索质量。 常用的搜索结构是: 在上一次的最优值的附近进行搜索。 搜索范围控制系统的设计应避免陷入局部最优的情况。 增加数据表的方法使得全局搜索效率得到提高[3]。 在禁忌搜索算法中,搜索结构的设计相对灵活,适用于排样规模适中的排样中。

1.2模拟退火算法在排样中的应用

模拟退火法是一种通用性很强的优化算法,它将金属热力学中的模拟退火过程应用到排样问题的求解中[4]。模拟将固体加热到足够高,内能增大,内部组织逐渐变为无序状态,当温度缓慢降低时,每一温度固体组织都能达到一种稳定的平衡状态, 内能也达到了最小( 如图2所示) 。

内循环:1通过已定的邻域搜索结构由当前解产生邻域解,常用的邻域搜索结构有随机搜索方法、 对解的元素进行变换等方法; 2计算邻域解与当前解的目标函数差; 3判断邻域解是否被接受为当前解或被接受为当前解的概率值; 4判断是否达到终止条件,若没有,判断是否达到循环次数,若没有则返回1。

外循环:若内循环完成,则降低T值再进入内循环,直到达到终止条件,终止计算,输出当前解作为最优解。

其要点有:

( 1) 根据Metropolis法则,P=exp( -△t/T) ,可知当T较小时,△t较小的改变就能带来P较大的改变量, 而 △t越小则概率越趋向于1;

( 2) 在内循环中 ,T是恒定的 ,改变的是邻域解S′及其改变量 △t, 得出在此T值下的最优当前解 。 在外循环中,T值逐渐变小,最终得到全局最优解;

模拟退火算法SA( simulated annealing) 的思想最早是由Metropolis等提出的[5]。 当从较高的温度降到较低的温度过程中, 通过Metropolis接受法则增加了解的概率性描述[6],使得在对最优解的搜索过程中能够跳出局部最优而趋于全局最优。 模拟退火算法具有渐进收敛性, 在理论上是一种以概率1收敛于全局最优解的全局优化算法。 但其要求初始温度足够高,降温过程足够慢,降温时间足够长,终止温度要足够低,如满足以上条件其计算量也相应增大。

1.3遗传算法在排样中的应用

1975年 ,Holland教授给出了遗传算法的基本定理和大量的数学理论证明[7]。 遗传算法的原理为: 基于达尔文进化论的观点,依照适者生存、优胜劣汰等自然进化法则, 通过计算机来模拟生命进化的机制,进行智能优化计算和问题搜索求解[8]。 使用遗传算法首先需要确定编码方法,即对零件进行编号,常用的编码方法有二进制法、十进制法、混合编码法[9]。 然后对编码进行遗传操作:

( 1) 复制操作 。 通过对父辈个体适应度值的评价, 按照一定的比例规则通过复制操作重新确定个体在种群中比例值,形成新的子辈种群,由此增加适应度高的个体在种群中的比例。 本步骤在实际操作中应用比较灵活。

( 2) 交叉操作。 将父辈种群中的个体随机两两配对进行交叉操作,产生m个个体构成子辈群体。 常用的交叉方法有:单点交叉、双点交叉。

( 3) 变异操作:变异操作是以很小的概率改变编码中的数值, 常用的变异方式有旋转变异和位置变异,即改变零件的摆放角度和摆放位置。

将遗传操作得到的编码进行解码,解码的目的是把一组编码转化为排样图, 常用的解码方法有BL法、 下台阶法和最低水平线法等。 对排样图进行评价,确定其是否达到终止准则,常用的终止准则有适应度值、产生的遗传代数。 若是,则停止计算并输出排样数据 ,若否 ,再次进入遗传操作生成下一代编码。

遗传算法求解过程如图3所示。

遗传算法是通过对排样零件进行编码使排样问题数据化,进行遗传操作的对象是这些数据,因此在排样过程中受到问题本身的约束条件较少, 遗传算法具有较强的通用性。遗传算法还具有自组织性、自适应性、隐含并行性等特点。通过变异和概率性选择编码避免了较早的收敛发生。遗传算法的开放性结构, 有利于和其他算法综合达到提高效率和精度的目的,例如自适应遗传模拟退火算法[10]、小生境遗传算法[11]等。

1.4粒子群算法在排样中的应用

粒子群算法是通过观察鸟类群体飞行规律得到的启发,鸟类利用群体中个体对信息的共享,使整个群体的运动从无序变得有序。同遗传算法类似,是通过迭代进行优化的。而遗传算法在于交叉和变异,粒子群算法在于始终追随最优粒子的引导。

粒子移动公式:

式中:Xt———粒子在t次迭代后的位置;

V———粒子的移动向量;

c1,c2———设定参数;

r1,r2———[0,1]之间的随机数;

Pi———单个粒子所经历的最优位置;

Pg———全局粒子所经历过的最优位置。

粒子群算法流程如图4所示。

( 1) 设定参数值c1、c2最大进化代数等参数,初始化一群规模为n的粒子,包括随机位置和速度;

( 2) 评价每个粒子的适应度;

( 3) 对每个粒子,将其适应值与其经历过的最好位置Pi作比较,如果较好,则将其作为当前的最好位置Pi;对每个粒子,将其适应值与全局所经历的最好位置作Pg比较,如果较好则重新设置Pg;

( 4) 根据粒子移动公式变化粒子的速度和位置;

( 5) 判断是否达到终止条件。若满足则输出全局最优值,否则返回( 2) 。

粒子群算法有较好的收敛性能和鲁棒性能,其结构融合性强、参数简单,适合与其他算法结合使用[12]。 但是粒子群算法存在着易出现局部极值点、 局部搜索能力差、对参数依赖性强的缺点,因此,很多学者提出了改进策略,如窦全胜[13]提出模拟退火及有分工策略的粒子群算法, 改善了粒子群算法局部搜索能力差的弱点,计算结果有了很大提高。 高鹰[14]等提出将粒子群算法与免疫算法结合等复合算法,改善了摆脱局部极值点的能力,提高了收敛速度和精度。李辉[15]提出与禁忌搜索算法结合的禁忌粒子群算法。 粒子群算法还具有简单易于实现、可调参数少、收敛速度快等优点[16,17]。对于排样零件相对单一或者零件轮廓较为规则的优化排样, 有利于避开局部收敛问题,且有利于提高排样的效率。

1.5蚁群算法在排样中的应用

蚁群算法是一种模拟进化算法, 意大利学者Dorigo等人从生物进化和仿生学角度出发, 研究蚂蚁寻找路径的行为提出了蚁群算法[18],并用该方法在求解TSP问题、 二次配方问题和作业调度问题中, 展示出它在解决较复杂的离散方面的问题的优势,粒子群算法是一种很有前景的智能计算方法,下面以矩形件排样问题简单叙述蚁群算法在排样中的应用[19]。

蚁群算法计算流程:

( 1) 蚂蚁随机放在n个矩形件上。

( 2) 初始化数据 ,包括矩形件的信息 、相关系统参数、矩形件的信息量和路径上的信息量。

( 3) 单只蚂蚁的行动。 1有第i矩形件按一定的移动规则移动到下一矩形件j上;2按已定的规则对矩形件i,j及i→j路径进行信息量的更新;3将矩形件j存入禁忌表[n]中,不再重复访问;4重复123成n个矩形的全访问,最终形成一个路径排列; 5按已定的排样算法生成排样图,并计算目标值。

( 4) 有m只蚂蚁就会有m个路径排列及其目标值结果。

( 5) 找出当前最优蚂蚁并与至今最优蚂蚁比较, 选择较优者为新的至今最优蚂蚁并保存。

( 6) 对至今最优蚂蚁的路径按一定规则进行信息的全局更新, 并且查看是否达到了预定的终止条件,是则终止计算,输出最优结果。 否则,重复( 3) 、 ( 4) 、( 5) 。

蚁群算法具有正反馈功能,有较强的启发能力, 能够快速找到最优解; 分布式计算有利于避免过早的收敛,跳出局部最优解,在全局内搜索到最优解。 但是, 蚁群算法的初始信息量的分布将对搜索结果产生影响。蚁群算法采用随机策略,在初始阶段收敛速度较慢。其改进措施主要有路径选择、信息素的更新、多重蚁群算法、与其他算法相结合等。

1.6神经网络算法

神经网络的概念是由人工智能神经网络研究的先锋Mc Culloch等曾提出的一种叫做“ 似脑机器” 的思想[20],这种机器可由基于生物神经元特性的互联模型来制造。 20世纪70年代Grossberg对神经网络研究做出了重要贡献[21]。 神经网络具有学习和适应、 自组织、函数逼近和大规模并行处理的能力。在智能系统发展中起重要作用,根据连接拓扑结构不同,神经网络可分为四大类:分层前向网络、反馈前向网络、互联前向网络、广泛互联网络。 常用的学习算法有:有师学习、无师学习、强化学习,遗传算法即使用了强化学习的思想人工神经网络典型模型有自适应谐振理论( ART) 、双向联想记忆( BAM) 、博尔茨曼( Boltzmann) 、Hopfield网络 、 自组织映射( SOM) 等 。 关于神经网络算法在优化排样中的应用, 翟红岩等提出的采用自组织特征映射模型( SOM) 和Hopfield人工神经网络相结合的方法寻找排样的最优位置和旋转角[22],李建勇等提出的用连续型Hopfield人工神经元网络( CHNN) 进行排料优化的计算,都得到了较好的排样结果[23]。

2结语

人工智能算法在非线性求解问题、 非确定性多项式求解问题中具有很好的解决效果。 本文简单介绍了几种排样算法,每一种算法存在着不同的原理, 也存在着各自的优势和缺点, 针对不同的排样条件应选择适当的排样方法。 在实际应用中常运用人工智能算法和启发式排样算法组合的算法求解排样问题。 神经网络算法应用面广泛、智能化程度高,但算法的设计过程复杂、实现难度高,需投入更多研究。 随着计算机技术的发展,更多的优质算法也将涌现, 计算机辅助排样技术将不断得到完善, 人工智能技术在排样优化中的应用将成为发展趋势。

摘要：排样问题广泛存在于加工制造业的各个方面,智能化排样技术直接影响到材料利用率的高低和工人的劳动强度,对排样问题的研究具有重要的经济意义。文中介绍了各种排样算法的基本原理、流程及优缺点。