基于小生境遗传模拟退火算法的不规则件优化排样

1基于小生境遗传模拟退火算法的不规则件优化排样史俊友，苏传生，翟红岩(青岛科技大学机电工程学院，山东青岛266061)摘要：对于二维不规则图形零件在排样区域上的最优排列，将排样和制造工艺联系起来，将多边形各边向外扩充，为零件预留加工余量；然后采用遗传模拟退火算法与小生境技术相结合，寻找排样件在排样时的最优次序及各自的旋转角度，再用基于“最低水平线与填充算法相结合”策略的启发式排样算法实现二维不规则件自动排样，得到满意的优化排样结果。关键词：遗传模拟退火算法；小生境；加工余量；最低水平线；优化排样中图分类号：TP391.7文献标识码：AOptimallayoutofirregularpartsbasedonNichingGeneticSimulatedAnnealingAlgorithmSHIJun-you，SUChuan-sheng，ZHAIHong-yan(CollegeofMechanicalandElectricalEngineering，QingdaoUniversityofScienceandTechnology，Qingdao266061，China)Abstract：Tosolvethetwo-dimensionalirregularpartspackingproblem,firstlytheproblemisassociatedwithmanufacturingprocess,everysideofpolygonsisexpandedinconsiderationofthemachiningallowance.Thengeneticsimulatedannealingalgorithmandnicheareintegratedtolookforthebestsequenceoftheirregularpartsandeachpart'soptimumrotatingangle,finallythelowesthorizontalalgorithmandfillingalgorithmarecombinedtocompletetheautomaticlayout.Thesatisfactoryresultsofoptimallayouthavebeenobtained.Keywords：geneticsimulatedannealingalgorithm；niche；machiningallowance；thelowesthorizontalalgorithm；optimallayout最大限度地节约材料，提高材料利用率是实际生产中的一个基本原则，由于在工业生产中排样问题广泛存在，因而解决它具有深远的理论意义和现实意义。寻找通用性好、求解质量和效率高、易于实现的排样问题求解算法一直是该领域所追求的目标[1]。遗传算法和模拟退火算法是当今优化技术领域应用最广泛的智能优化算法[2,3]。然而，大量研究表明[4]，遗传算法存在早熟收敛、局部寻优能力差等许多不足，这使得最终搜索结果可能是局部最优解。模拟退火算法能够跳出局部最优解，具有较强的局部搜索能力，但其把握搜索过程的能力不强。近年来，许多研究人员把不规则零件排样转化为矩形件排样来处理，这种方法简单易行，但由于没有充分考虑零件具体的外形特征，会导致材料利用率的降低。为此本文充分考虑不规则件自身的形状特征，将排样和制造工艺联系起来，将多边形各边向外扩充，为零件预留加工余量，对扩充后的零件，求取其最小包络矩形，并对一些形状互补的零件构造矩形排样单元进行优化组合，使零件区域在最小包络矩形中所占的比例尽可能大，对组合后的图形再求取最小包络矩形，同时对多边形的外轮廓与包络矩形之间产生的空白区域进行填充；从遗传模拟退火算法优化策略的构造出发，融合小生境技术的思想，形成一种小生境遗传模拟退火算法—NGSA算法，算法具有较强的全局和局部搜索能力，在此基础上开发了不规则件优化排样系统。收稿日期：2008-12-03作者简介：史俊友(1970-)，男(汉)，教授．21排样模型零件在板材上的定位实际上只需3个参数即可完成。这3个参数是该零件的一个给定点在板材上的坐标(X，Y)和该零件的排放角度θ。当这3个参数确定后，该零件的其它各顶点坐标都可由这3个参数计算。设Gj(jJ，J为零件集合)为零件j的图形，(xj，yj)为该零件的给定点的坐标，则该零件在板材上的定位可表示为下述过程：先将该零件以该定点为轴旋转角度θj，然后再将定点(xj，yj)在板材作位移(∆xj，∆yj)。这时零件j在板材上的方位可表示为Gj(∆xj，∆yj，θj)。零件的数量为n，Sj为零件j的面积。L为板材的长，D为板材的宽，排样图形外接矩形高度为H，宽度为W。定义排样布局的原材料利用率，为排样零件的面积和与排样图形外接矩形的面积的比值。零件优化排样的模型为[5]：j1HnjSW(1)Gj(∆xj，∆yj，θj)∩Gk(∆xk，∆yk，θk)=Ф，j≠k(2)S.t.0≤Yji(∆xj，∆yj，θj)≤Lji=0，1，…nj(3)0≤Xji(∆xj，∆yj，θj)≤Dji=0，1，…nj(4)式(2)表示零件j与零件k互不重叠；jiX和jiY为考虑加工余量后零件j的第i个顶点的坐标，式(3)和式(4)表示零件不能排在板材之外。2零件预处理2.1多边形的近似表示排样过程中，通过与CAD的接口，可以方便地提取零件中各实体的信息。在获取零件中的各实体信息后，还需进一步得知零件中各实体之间的拓扑关系。所以必须对实体的端点进行排序处理，使其成为一个封闭的轮廓，满足零件表达的要求。加工余量的大小对零件的加工质量和制造的经济性均有较大的影响。对每个不规则件考虑其加工余量r，将零件多边形各边向外扩充r距离，各边延长相交，得到与原多边形相似的新多边形，如图1所示。由原多边形各顶点坐标求出考虑加工余量后各多边形顶点坐标，并将此作为进行优化计算的基本数学信息。2.2多边形外包络矩形的求取不规则件的优化排样通常采用近似法，即把不规则件近似为矩形件来处理，从而简化为矩形件排样问题。但如果在近似过程中未充分考虑零件的形状特征，把不规则件简单地当成矩形件来处理，有可能导致材料利用率的降低。采用求取零件最小包络矩形的方法，先设定一矩形包络率，对包络率满足要求的零件用最小包络矩形替代，对不满足要求的零件进行优化组合，使零件区域在最小包络矩形中所占比例尽可能大，对组合后的图形再求取最小包络矩形，二维不规则件排样问题就转化为矩形件排样问题。针对零件图形内部有空白区域的情况，在不发生干涉的前提下，选择合适的零件对内空白区域进行填充，如果有多个零件可以填充到一个空白区域中，采用最佳面积适配法。设区域面积为SE，图2空白区域填充Fig.2Thefillingofblankspacer图1多边形加工余量Fig.1Themachiningallowanceofpolygon3各零件面积为Si，且Si≤SE，计算S=min(SE-Si)，S所对应的零件即为填充的零件。空白区域填充[6]如图2所示。3算法描述3.1GASA混合优化策略遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法，引入了局部搜索过程；以遗传算法运算流程为主体流程，将模拟退火机制融入其中，进一步调整优化群体。整个算法的执行过程由两部分组成：首先通过遗传算法部分的进化操作(侧重全局搜索)产生较优良的一个群体，再利用模拟退火算法部分的退火操作(侧重局部搜索)来进行基因个体的优化调整，运行过程反复迭代，直到满足终止条件为止。这种算法思想策略，从对全局最优解的搜索角度和算法的进化速度上来提高模拟退火遗传算法的性能。3.2小生境技术在生物学中，把某种特定环境及其在此环境中生存的组织称为小生境(niche)[7]，而把有共同特性的一些组织称作物种。基本遗传算法在进行个体交配时采用的是随机方式，这增强了对问题解空间的搜索能力，但也带来了交配的有效性以及优化效率不太理想等问题。为解决这些问题，在基本遗传算法中引入小生境技术。其不仅能够有效地保证群体中解的多样性，而且在问题求解的收敛速度、计算精度、全局搜索能力等方面表现出明显的效果，是一种较有效的方法。3.3NGSA混合优化策略NGSA算法应用于不规则件的求解过程可描述为：(1)设置进化代数计数器t=1，随机产生含M个个体的初始种群P0(t)，同时求出各个体的适应度Fi(i=1，2…，M)；(2)对种群P0(t)中的个体按其适应度大小降序排列，记录前N个个体(NM)为较好群体P1(t)，以免部分适应度高的个体在遗传操作中被淘汰掉；(3)采用遗传算法进行选择、交叉、变异等操作，生成群体P2(t)；①对种群P0(t)进行预选择操作，得种群Pop1(t)，选择操作时，先进行赌盘选择，再采用精英选择。②采用单点交叉算子对种群Pop1(t)进行交叉操作，得种群Pop2(t)；③采用均匀变异算子对种群Pop2(t)进行变异操作，得到种群P2(t)；(4)以P2(t)为初始种群，对其中各个体进行模拟退火运算，得到新的规模为M的群体P3(t)；(5)将P1(t)、P2(t)、P3(t)合并构成一个规模为N+M×2的新群体P4(t)，采用小生境技术进行淘汰，两两比较各个体间的海明距离，若两者间的海明距离在预先指定的数值之内，对适应度较低的个体施加一个较强的罚函数，极大地降低其适应度，即增加其被淘汰的概率；(6)对P4(t)进行评价，取出其中较好的前M个个体构成P0(t)，降低退火温度，转步骤(2)，循环开始结束初始化算法参数，确定解码、编码方案初始化种群M，设置进化代数计数器评价当前种群各个体，记录前N个个体是否满足收敛准则执行GA的选择、交叉、变异操作得到SA的初始种群，确定抽样数目进行SA搜索进行SA搜索计数器替换计数器替换输出优化排样结果对M+N个遗传个体、M个模拟退火个体构成的新群体进行小生境技术淘汰运算YN......图3NGSA算法流程图Fig.3TheflowchartofNGSAalgorithm4执行。(7)判断是否满足收敛条件，如不满足终止条件，则更新进化代数计数器，即t=t+1，转至(6)；若满足终止条件，则终止运算，输出计算结果。算法流程如图3所示。3.4NGSA算法的设计实现(1)编码机制由于二进制编码不能直接反映多边形的排样方式，因此本文采用十进制整数编码方法，它具有编码和解码操作简单、遗传操作便于实现等优点。将所有参加排样不同类型的零件按面积大小排列并加以编号，染色体的长度与排样件的类型数相同。此编码方式是基于一种排列顺序的基因编码方式，即所有排样类型的一个排列顺序作为一个染色体。编码设计的关键是在染色体中产生不同编号的遗传算子，相应的解码方法则根据所采用的解码方法把具体的零件定位在板材上。(2)解码方法由遗传算法产生一个个体的编码后，能否快速求出其对应的排样图是一个关键，同时只有求出该个体所对应的排样图，才能计算其对应的适应度值，并对该个体进行评价。笔者采用一种基于零件最高轮廓线的“最低水平线”[8]和填充算法相结合的解码方法。对于在多张板材上排放零件的问题，当零件的最高轮廓线y坐标大于板材的长度或者最高轮廓线的终点x坐标大于板材的宽度时，更换新板材，更新最低水平线及最高轮廓线，然后在新板材上按顺序继续排放零件。4运行实例笔者应用小生境遗传模拟退火算法开发了实用的不规则件优化排样系统。已证明该系统能有效地解决任意二维不规则零件的最优排样问题。以下算例可以证明此算法的有效性和可行性。(1)矩形板材上的优化排样实例1：多种不规则件NGSA算法排样从过程装备制造厂零件数据库中随机选取了一组具有不同形状的多种类、单数量零件进行混合排样计算。从板材库中选择矩形板材宽为600mm，设置算法基本运行参数：群体规模为50，最大迭代数为100，交叉率为0.6，变异率为0.06，马可夫链长度为8000，衰减参数为0.95，迭代初始温度为500，容差为0.0001，小生境之间的参数距离为2.5，零件种类为30，各零件加工余量