采用离散化处理方式

Vol.16, No.2 .2005 Journal of Software 软 件 学 报 1000-9825/2005/16(02)0316

皮料优化排样的有效方法. 张玉萍1,2+, 张春丽1, 蒋寿伟2 1(上海师范大学 机电学院,上海 200234) 2(上海交通大学 机械与动力学院,上海 200030) An Effective Approach for Leather Nesting ZHANG Yu-Ping1,2+, ZHANG Chun-Li1, JIANG Shou-Wei2 1(School of Mechanical & Electrical Engineering, Shanghai Normal University, Shanghai 200234, China) 2(School of Mechanical & Dynamic Engineering, Shanghai Jiaotong University, Shanghai 200030, China) + Corresponding author: Phn: [phone], E-mail: [email protected], http://www.shnu.edu.cn Received 2003-10-24; Accepted 2004-04-01 Zhang YP, Zhang CL, Jiang SW. An effective approach for leather nesting. Journal of Software, 2005,16(2):316.323. http://www.jos.org.cn/1000-9825/16/316.htm Abstract: This paper presents an effective nesting method for leather manufacturing, such as automobile interior decoration, etc. After the profiles of leather sheets and stencils are obtained, they are discretized to make the processing independent of the distinct geometry. The constraints of profiles are thoroughly considered. A heuristic bottom-left placement strategy is employed to sequentially place stencils on sheets. The optimal placement sequence and rotation are deterimined using a simulated annealing based genetic algorithm (SABGA). A natural concise encoding method is developed to satisfy the possible requirements of the leather nesting problem. Experimental results show that the proposed mehtod not only can be applied to the normal two-dimensional nesting problems, but also can be especially suited for the placement of multiple two-dimensionally irregular stencils on multiple two-dimensionally irregular sheets as well. Key words: nesting; genetic algorithm; simulated annealing; irregular leather; two-dimensional geometry 摘 要: 根据汽车内饰等行业需求,对皮制品加工的优化排样问题进行了研究.创新地采用离散化处理方式,同时引进边界约束,使排样过程与皮料和样片的几何信息无关,使用基于顺序的启发式底左布局将样片顺次布置到皮料上,样片的最优布置顺序和角度依靠随机优化算法来实现.设计了简洁、实用的操作算子,并提出了基于模拟退火技术的遗传算法(simulated annealing based genetic algorithm,简称SABGA),该算法在优化搜索中能自适应地控制变异率,使得优化高效地逼近全局最优解.实验及对比结果表明,提出的优化排样方式特别适用于二维不规则形体在多个二维不规则平面上的优化排样. 关键词: 优化排样;遗传算法;模拟退火;不规则皮料;二维几何 . Supported by the Science-Technology Development Foundation of Shanghai of China under Grant No.005111081 (上海市科技发展基金) 作者简介: 张玉萍(1963－),女,浙江宁海人,博士,副教授,主要研究领域为CAD及优化技术;张春丽(1972－),女,博士,副教授,主要研究领域为CAD及优化技术;蒋寿伟(1939－),男,教授,博士生导师,主要研究领域为CAD及优化技术.

张玉萍 等:皮料优化排样的有效方法 317

中图法分类号: TP391 文献标识码: A 二维几何形状的排样问题广泛存在于重工业、轻工业、微电子等领域,如金属板材、木材、玻璃、皮革、布料等的下料.皮制品被广泛地应用在生活中,除皮质服装、鞋帽、箱包、家具外,更涉及汽车、豪华游轮等内饰领域.皮质原料造价高,形状不规则,质量不均匀,设计约束条件多且无规律,使得在皮料上尤其是在多个皮料上的排样极具挑战性.针对汽车内饰等行业需求,本文对皮制品加工的优化排样问题展开了研究,探讨在多个任意形状的皮料上如何最优地排列样片,研究成果可以直接转化应用到其他行业. 迄今为止,已有许多算法用于解决不同的排样问题[1].对于二维不规则样件,Bennell[2]以及Gomes[3]基于临界多边形(NFP)采用的处理方法能够执行高效排样,但由于受NFP对几何轮廓处理方式日的局限,不允许样件在两维排放平面内转动,这不符合样片在皮料上的实际排样状况.Heistermann[4]介绍了他们开发的专门针对皮革工业的优化排样软件包,他们采用的是贪婪搜索方法,将皮料的排样区分成活动区(live region)和死区(dead region),活动区可排样,死区不可排样.存在的问题是:1) 样片方面,因为这里将不规则几何形状用小的直线段来逼近,如果样片尺寸越大,它的排样就越困难;2) 皮料方面,如果皮料表面有瑕疵空洞,孔越多需要排样的时间越长.当有5个以上时,排样时间急剧增大,使得排样所花费时间变得不可忍耐,需要采用搭桥特别处理,使各个空洞归为死区.这种处理有一个限制条件,就是搭桥长度不能长,否则样件不能被紧密地排在空洞的旁边,严重影响材料利用率. 以上的启发式算法给出的均为选定算法的布局排样结果,未涉及不同的排布顺序和模式.研究人员试图采用某些随机逼近算法[5,6],如模拟退火(SA)和遗传算法(GA)及人工模拟网络(ANN)来完成.Heckmann[7,8]等人采用模拟退火算法求解,其中考虑了样件的任意角度旋转,主要针对纺织品加工行业,在排样时考虑了花色、条纹的约束,设置的目标函数由两部分组成,一个是占用面积,另一个是重叠面积的惩罚函数,通过变动参变量来获得邻域空间,这种算法的缺陷是有时会陷入局部最优.Hopper[1]以及Jain[9]介绍了他们在解决排样问题中采用的遗传算法,但其研究主要是针对几何形状为矩形展开的,实验结果表明,遗传算法的使用取得了很好的效果.Hopper更重点研究了排样的布局策略,针对“底左”布局策略对于大面积矩形形体会产生大的未排面积缺陷,提出了“底左填充”布局方案,所给出的实验结果也进一步证明“底左填充”策略的有效性. 然而,上述算法最大的问题是仅能针对单个原料进行排样,本文作者提出了二维不规则形体在多个二维不规则平面上的优化排样算法.为了使裁剪浪费的材料最少,并提高排样效率,针对样片与皮料形状都不规则的难题,采用离散化技术使处理过程与皮料和样片的几何轮廓信息无关化,结合遗传算法使得多样性可以用一种更自然的方法实现,同时采用启发式的底左布局策略,以这种新的处理策略实现多皮料的排样.系统流程如图1所示. Output optimal result Discretization of geometricalInformation placement sequenceand encoding design SABGA combination strategyConversion system for data forms CADplatformDigitizer Production User interactionLeathers and stencils Scanning device Fig.1 Flow diagram of the leather nesting system 图1 皮料优化排样流程 1 几何信息的获取以及处理 皮料及样片的几何形状都是二维不规则的,首先要获取原始几何信息并对它们进行处理.现有的技术中有许多途径可以获取到它们,如:(1) 扫描皮料,根据灰度和色差,使用软件转换出皮料的轮廓图形.(2) 使用数字化仪直接得到皮料轮廓等.根据现有设备等条件,我们在实验中使用了第2种方法.

318 Journal of Software 软件学报 2005,16(2)

1.1 样片的旋转角度 样片在皮料布置上要考虑一些约束条件,皮料自身有正面和反面之分,所以一般样片在皮料平面上可以在0°~360°内以任意角度排放.如果需要考虑一些样片外观对皮制品的光亮要求,有些样片可能不允许有角度旋转,或者被允许在小角度内旋转,对于角度的限制可以在排样时直接指定每个样片的排样角度. 1.2 几何信息的离散化 对于二维不规则几何形状,从已有的文献看,大多采用多个短小直线逼近描述曲线的方法来表达,在排样过程中,主要通过考察每一个被排样片轮廓的逼近小折线与皮料上要排放处边缘的逼近小折线的匹配情况来选择优先排样序列,但是会出现一些排样结果很差甚至不可采用等情况.由于皮质材料自身轮廓形状为不规则曲线,所以如果能有一种方法脱离皮料及样片的几何形状来进行排样处理,将是非常有益的.受像素处理方式启发[10],我们提出了离散化的处理方式. 根据皮料实际使用的精度,我们采用间距为t的虚拟网格将图形包围在最小的虚拟网格矩形中,t由用户根据实际需要确定,通过检索各个虚拟网格小区域中是否有皮料或样片的轮廓,将各个小区域定义为0或非0,以此将皮料和样片离散化.这里我们定义这样的最小包围矩形网格为虚拟约束网格,对应的矩形网格轮廓框简称虚拟约束矩形框.例如,样片图形实际离散化处理为如图2所示,为解释清晰起见,我们抽象了一些特例放大图形.对于样片,在系统中规定:如果在虚拟网格小区域内及小区域上检索到图素,则定义为0,表示需要在对应的位置进行排放;其余为非0,表示非排放处,如图2(b),图2(c)表示图中间有一个空洞.图中所有非排放处只要标的数字为非0就可以,但是为了后续检索定位方便,我们在处理中使用了编号.这样可以方便地确定被排虚拟约束网格整体沿x方向移动的距离,加快排放速度.图3表示皮料上排放了样件1、样件2以及样件3的情况,其中样件3中有空洞,空洞内正好可以放置下样件1,虚拟网格中的数值表示在这种排放情况下网格值的变化结果. (a) Stencil 1 (b) Stencil 2 (c) Stencil 3 Fig.2 Discrete grids and corresponding pixel values of different stencils 图2 各类样片离散化后的虚拟约束网格图及网格值Fig.3 Discrete grids and the corresponding pixel values after the placement 图3 皮料的离散虚拟约束网格图及对应网格值 为了将矢量数据文件(DXF,IGES等)转化成排样检索使用的虚拟网格形式的网格值,首先需要构造一个数据结构: struct stencil { int spixel int svalue int sdir int snum };

张玉萍 等:皮料优化排样的有效方法 319

经过离散转化算法处理,将皮料以及样片的几何信息转化成最小虚拟网格矩形包罗的一组网格值信息,这里仅给出了对样片的处理. 2 排样的搜索策略和算子操作 如果要在皮料上排放各种样片,首先要解决采用什么样的布置顺序将样片一个个地逐次定位,只有次序确定了,才可以根据使用的算法遍历可能的情况,并且找出其中排放最佳的一种.我们采用的是启发式底左顺次布置样片到皮料上的方式(见第2.1节),样片的布置顺序和角度依靠SABGA(simulated annealing based genetic algorithm)进行优化控制(见第2.2节). 2.1 启发式的底左布局方式 把样片布置到皮料上,主要就是沿x坐标方向顺次检索皮料上各个网格区域的lvalue值,如果为0,就将样片定位于此,然后顺次检索被定位的样片区域内的svalue值是否完全与皮料区域的lvalue值完全为0匹配,如果成功,则样片被排放,如果有不为0情形,查看lvalue值,将样片整体沿x正方向移动lvalue值距离,然后再检索,直到满足条件为止.当一个皮料被排满后,可换置一张新的皮料,继续上述过程,直至所有样片全部被排完,期间对于恰当样片的选取顺序和布放的合理角度由组合优化方法获取. Begin (L[x][y]:皮料, S[x][y]:样片) foreach (所有可以具有一定角度的样件集合) 定位样件的虚拟约束矩形框左下角S[0][0]到皮料虚拟约束矩形框可排料的最底左下角L[x][y]; While(1) 应用扫描技术(见第2.2节); if (确定这个位置是否接受,如果接收) 排定该样件,break; else 获得皮料L[x][y].lvalue值,沿x轴正向将样件定位点S[0][0]移动到x=x+L[x][y].lvalue; if (要排的样件沿x方向排时与皮料虚拟约束矩形框相交), 上移一行从头检索,即y=y+1,x=0; if (要排的样片与皮料虚拟约束矩形框的上边界相交) 检查皮料库是否为空,若是,终止整个排样程序;否则顺序提取下一个皮料并定位样件S[0][0]到该可排料的最底左下角L[x][y]; endif endif endif endwhile endfor End 2.2 扫描技术 扫描技术就是将样片区域的像素值与皮料上定位对应区域的像素值逐一进行比较,如果满足要求都为0,就接收,表示该位置可以排放,如果不为0,采用第2.1节的启发式算法,移动样件或做其他的调整,然后再使用扫描技术进行检索. 3 优化方法 经过上面处理,可以将各种不同的样片排放到多个皮料上,但是否最省材料,需要采用一个实用的优化算法.为此,我们提出了一种新的组合优化方法,是一种改进了的GA算法,能够有效地搜索最优的排放顺序和样片的旋转角度. 3.1 皮料和样片的编码表示 我们提出了一种简洁、抽象处理的编码方式,它含括了对多个皮料的处理.首先将各种皮料编上1,2,3等顺

320 Journal of Software 软件学报 2005,16(2)

序代号,样片也同样编号.排样时皮料固定不动,而样片可以根据需要在平面360°内任意旋转,此时使用如图4所示的编码方式可以表达出在数件皮料上需不同角度排放的多个样件的排放形式.例如,要在1,2,3皮料上排放6个形状不同的样件,每个样件可以有不同的旋转角度.具体排放顺序见图4的编码表,首先是样件2,旋转80°排放,然后依次是3,1,4,6和5,以及它们各自要求的角度. Fig.4 Placement sequence and orientation encoding 图4 皮料和样件排放顺序和角度编码 Sheet numbersPart number Rotation angle 3.2 交叉和变异算子 定义个体的适应度函数如下: F=1/(A1+A2+…+Ai+…+An.1+Pn) (1) 上式中Ai(i=1,2,3,...,n.1)表示第i个皮料的面积,Pn表示第n个皮料上被排样区域的面积.对于一组被排样片,如果排样结果A越小,这组样片对应的适应度值越高. 一般地,交叉变异操作是优选具有高的或者较高的适应度值的个体来进行的.交叉过程如图5所示,对选中的具有较高适应度值的Parent 1和Parent 2进行交叉操作,随机选取两个位置数,一个指定在皮料编码区,一个指定在样片编码区,如图指定在Parent 1的编码序列上,将指定位置右边的编码对应各区拷贝到新构造的代码串中,如Intermediate,Intermediate中的空缺代码按照Parent 2的编码顺序将没有出现的皮料和样片顺序填入,这样就完成了交叉操作,实现了子代的构造. 图6表示了变异过程,因为代码分成两个区域,并且在样片区域代码又存在一个变动参数——旋转角度,所以变异操作分成两个部分,其一是皮料和样片的顺序编码,因为各自的序号对应了各个不同的个体,所以产生变化时是在各自不同的区域取两个随机位置,然后交换它们所对应的代码,即完成了变异操作,如图6(a)所示.其二为样片排放时旋转角度的可能变化,如图6(b)所示,它是以一定的概率指定某几个样片,对应的样片角度可以从0°~360°发生变化. Fig.5 Process of crossover operation 图5 交叉操作过程 Fig.6 Process of the mutation operation 图6 变异操作过程 交叉以及变异操作都是以一定的概率进行的,交叉概率记为pc ,变异概率记为pm,其值的选取是比较敏感的问题.实验表明,交叉率pc应该比较大,一般取一个固定值即可,我们使用正交实验的方法研究了交叉率的取值,最后确定为0.4.相对交叉率,变异率的确定要困难得多,对排样结果的影响更大、更直接.为此,我们进行了较深入的研究和实验,找到了一种有效的解决方式,由此提出了一种新的组合优化方法.实验结果表明,这样的处理方法非常有效. 3.3 基于模拟退火技术的遗传算法 在使用普通遗传算法进行优化排样过程中,到后期会出现算法不能高效运行,优化过程发生早熟收敛的现象.究其原因是由于后期种群缺乏多样性,导致早期收敛.另一方面,确定敏感的固定变异率是一个复杂的问题.模拟退火技术是一种普遍的方法,而不是一种特用算法[11],因此,我们创新地开发了基于模拟退火技术的遗传算法SABGA,算法中变异率由一个满足特定冷却曲线的温度来控制,由于仅使用了一个参数,Cauchy冷却方法被采用[12],详细的算法如下.

张玉萍 等:皮料优化排样的有效方法 321

SABGA组合算法. (N:种群大小.α,β:变量用来表示种群中的个体.T0:初始温度.T:温度.) 开始 1 输入样片以及皮料几何尺寸和角度等约束条件; 2 随机地初始化第1代并采样建立T0; 3 对第1代中的个体估价适应度; 4 while not (stopCriterion( )) 5 while (innerLoopCriterion( )) 6 foreach (N * 交叉率) 7 基于等级式选择方法选中第1个双亲; 8 随机地选择第2个双亲; 9 进行交叉操作产生一个子代; 10 endfor 11 从父代和子代中选出适应度最大的N个个体并作为新的一代; 12 foreach (N/2) 13 对于一个个体成员α的克隆体β进行变异操作; 14 .C=Cost(β)–Cost(α); 15 if (.C<0) 16 α=β; 17 else if (U(0,1)≤e..C/T) 18 α=β; 19 endif 20 endfor 21 endwhile 22 更新T和变异率; 23 endwhile 24 输出最佳排样结果; 结束 在输入了皮料和样件几何信息和约束条件后,随机产生第1代,初始温度T0与具体问题的规模有关,它为5次随机布局状态的面积平均值,stopCriterion( )确定了进化过程终止的条件,即在某一代内平均适应度不小于最佳适应度,或者在一个预定义的连续繁衍代内没有进步发生,或者已完成一组预先指定的繁衍代数.innerLoopCriterion( )在整个进化过程中控制着一个特定的局部平衡过程,10代作为一个局部循环,其中温度和变异率保持稳定.在复制过程中,交叉操作执行完毕后,就建立一个新的衍生代.变异操作基于新的衍生代中一半的个体成员,这样不仅加强了随机扰动的效果,而且改善了运行时间上的不足.变异操作是作用在一个成员个体的克隆体上,如果变异后的克隆体的价值小于原始个体或满足Metropolis公式,原始成员个体被变异后的克隆体取代,否则放弃变异后的克隆体.内部循环体嵌套在外部循环体内,温度和变异率在内部循环体外被更新,最后输出搜索得到的最优个体. 4 实验结果 我们进行了大量实验来验证提出算法的有效性,主要分成两类,一类是对于各类不规则几何形状的样片在一个或多个皮料上的排样结果,主要考察该方法的实用结果.另外一类就是扩展使用,对布料、金属板材等其他材料的排样,我们实验了各种线性多边形样件在矩形或线性多边形平面内的排样结果,并与Gomes[3],Heistermann[4]和Jain[9]的方法进行了比较.我们所有的工作是用C++程序语言实现的,使用的计算机微处理器是Pentium II,主频333MHz,内存128 MB,操作系统为Windows. 图7为选定10,20,30,65和100五种不同种群规模的实验,它显示了种群规模与获得优化结果运行代数的关系,结果表明,算法是逐步收敛的.对于种群数在30~100的规模,具有相似性,经过约650代运行后,物种新的变化特征已经丧失,收敛结果之前已经产生.为减小计算时间,我们设定种群数为30. 图8为在3个不规则皮料上排放64个不规则样片的实验,皮料1上有9个瑕疵,排放了26个样片,材料利

322 Journal of Software 软件学报 2005,16(2)

用率为78.80%,皮料2上有2个瑕疵,排放了26个样片,材料利用率为80.02%,皮料3上有一个瑕疵,将12个样片排放其上,未排满,它的有效材料利用率是73.6%.一共运行了760代,耗费的CPU时间是43′22″.使用我们这种几何处理方法,在排样中能够很好地识别孔洞,获得的排样效率能够达到要求.从排样结果来看,并非都是较大面积的样片先排就能获得较高的排样效率,这需要根据样片和皮料的具体形状全局确定. 60657075808525125225325425525625725GenerationMaterial Usage Rate(%)10203065100 (a) 9 flaws (b) 2 flaws (c) 1 flaw Fig.7 The efficiencise and generations for different population sizes 图7 不同种群规模运行的效率 Fig.8 Nesting results in three sheets 图8 非规则样片在3个皮料上排样的情况 Our approach Our approach Our approach Heistermann[4] approach Gomes[3] approach Jain[9] approach (a) (b) (c) Fig. 9 Comparsion between our apporoach and the approaches from Heistermann[4], Gomes[3] and Jain[9] 图9 我们的方法及Heistermann[4],Gomes[3]和Jain[9]方法对线性多边形样片在单个矩形平面中的排样实例 19818526425712944510020030040081.9%71.2%79.8%62.5%100%100%60%70%80%90%100%our approach GomesHeistermannJainabc(d) Comparison of material usage rates abc (e) Comparison of runtimes 相对于文献所介绍的Heistermann[6]和Gomes[8]排样方法,这里进行了3组比较实验,如图9所示.图9(a)为在单个给定皮料上排放15~20个给定样片,用我们的方法,15个样片经过427代进化得到排样优化结果,与Heistermann方法相比,不但所用时间少,而且材料利用率提高约10%.图9(b)为在一个长度界限不定的平面内排放4类共计43个多边形样件,我们的方法因采用左底策略,所以需先对排样平面旋转预处理,成为高度可变平面,经过601代进化后,获得优化结果,将其反转90°回原位.与Gomes方法结果比较,排样效率提高12.49%. 图9(c)为3种14个线性多边形样件在40mm×60mm矩形平面上的排样.通过表1的数字可以看出,我们提出方法的有效性.3组实验的效率和CPU运行时间的比较如图9(d),图9(e)所示. 以上两类实验表明,我们提出的优化方法能快速、有效地将各类样片排放到各类型单个或多个平面中,尤其突出的是,它能够灵活地完成非规则形状的样片在多个非规则平面上排样的功能,并且材料利用率能够达到70%以上,排样时间在用户接纳范围内,对于50个样片在10个平面内的排样规模,通常1小时内可以完成,这对于皮革加工业是可以接受的.

张玉萍 等:皮料优化排样的有效方法 323

Tabel 1 Comparison between our apporoach and the approach from Jain[9] on an example of nesting multiple polygon parts in a single rectangle 表1 两种方法排样的数据对比 Method Our approach Jain[9] approach Pattern size (mm×mm) 40×20 25×45 25×40 20×45 20×40 Number of generations 302 1 10 20 100 Utilization (%) 100 71.1 80 88.8 100 CPU time 2′9″ 21″ 1′32″ 2′49″ 7′25″ 5 结 论 文中创造性地将皮料和样片进行离散化处理,同时引进边界约束,使得后续算法的处理对象统一化,因而提出的优化排样方式特别适用于形状不规则的二维形体.采用几何信息离散化的处理方式,彻底解决了轮廓几何约束的困扰,基于顺序的底左排放策略使得优化排样顺利进行,样片顺序和旋转角度的选择依靠SABGA算法来搜索完成.SABGA算法集中了GA和SA的优点,它在完成排序搜索过程中,还很好地处理了变异率的选取,利用模拟退火算法的特长对变异操作施加自适应控制,由一个满足特定冷却曲线的温度来控制,使得遗传算法的随机染色体变化在优化的初始阶段比较大,然后越来越小,直到最后搜索收敛为止,这样抑制了优化过程的早熟收敛.我们提出的这种优化方法不但适用于不规则形体在单个或多个不规则表面的排样,也适用于规则形体在单个或多个规则平面上的排样,实验结果表明,我们的处理方法是具有广泛使用意义的. References: [1] Hopper E, Turton BCH. A review of the application of mete-heuristic algorithms to 2D regular and irregular strip packing problems. Artificial Intelligence Review, 2001,16:257.300. [2] Bennell JA, Dowsland KA, Dowsland WB. The irregular cutting-stock problem—A new procedure for deriving the no-fit polygon. Computers and Operations Research, 2001,28(3):271.287. [3] Gomes AM, Oliveira JF. A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 2002,141(3):359 .370. [4] Heistermann J, Lengauer T. The nesting problem in the leather manufacturing industry. Annals of Operational Research, 1995,57: 147.173. [5] Xing WX, Xie JX. Modern Optimization Calculation Methods. Beijing: Tshinghua University Press, 2000 (in Chinese). [6] Reeves CR. Modern Heuristic Techniques for Combinational Problems. Oxford: Blackwell Scientific Publications, 1993. [7] Heckmann R, Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry. Annals of Operational Research, 1995,57:103.133. [8] Heckmann R, Lengauer T. Computing closely mathing upper and lower bounds on textile nesting problems. European Journal of Operational Research, 1999,108(3):473.489. [9] Jain S, Chang HG. Two-Dimensional packing problems using genetic algorithms. Engineering with Copmuters, 1998,14(3): 206.213. [10] Cui Y. The Processing and Analysis for Images. Beijing: The Science and Technique Publisher, 2000. 65.86 (in Chinese). [11] Babu AR, Babu NR. Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int’l Journal Produce Research, 1999,37(7):1625.1643. [12] Liu Y. Simulated Annealing with a Potential Function with Discontinuous Gradient and an Adaptive Simulated. Beijing: Peking University Press, 1999. 15.80. 附中文参考文献: [5] 邢文训,谢金星.现代优化计算方法.北京:清华大学出版社,2000. [10] 崔屹.图像处理与分析.北京:科学技术出版社,2000.