基于GA—SA混合寻优算法的CAPP与PPC 集成原理研究 朱春耕 (浙江师范大学,浙江金华321 01 9) 摘要:评述了OAPP和PPO集成原理,在统一资源库的约束条件下,提出了基于GA—sA混合优化 策略的OAPP和PPO的集成方法;建立了基于GA-SA算法的算法基本框架、算法模型;通过 实例仿真表明,GA—sA混合寻优算法较单一的GA算法具有更好的应用效果。 关键词:OAPP;PPO;遗传算法;模拟退火;集成原理 中田分类号:TH1 62;TP391 文献标识码:A 文章编号:1 009—01 34(2007)01—0058—04 A study of the integration principle of CAPP and PPC based on GA-SA hybird algorithm ZHU Chun。geng (Zhejiang Normal University.Transportation College。Zhejiang Jinhua 321019,China) Abstract:Researches on the integration principle of CAPP and PPC are reviewed.Based on the restriction of uniifed resource database。integration technique of CAPP and PPC based on hybrid evolutionary search algorithm which combines a genetic algorithm and a simulated annealing algorithm is proposed.A novel algorithm frame and algorithm model are put up. The results are presented in this paper.The results show that the proposed hybrid algorithm performs be ̄er than the genetic algorithm. Key words:Computer Aided Process Planning;Production Planning and Contml;genetic algorithms; simulated annealing;integration principle 0引言 遗传算法(GA)是基于群体优化的一种方法, 在产品的设计和制造之间,有两个主要的活 它具有较强的并行搜索的能力,且在一定程度上保 动:工艺设计和生产计划与调度,在现代集成制造 留了历史信息,但交叉和变异只有有限的进化能力, 中,它们是由CAPP(Computer aided process planning, 而且容易出现过早收敛的现象;模拟退火(SA)模仿 CAPP)和PPC(Production planning and control,PPC) 晶体的冷却结晶过程,但收敛的速度较慢,但(SA) 来完成的。CAPP依据CAD传递过来的零件几何信 具有概率突跳性,使其具有避免陷入极小的能力。 息和技术要求为其制定加工工艺{PPC利用工艺设 两者结合有利于丰富优化过程中的搜索行为,增强 计结果,以合理的时间和成本来组织成品的生产。 全局和局部意义下的搜索能力和效率[3】。本文在 为了实现CAPP和PPC的集成,国内外学者提出了 CAPP和PPC集成基本原理的基础上,在并行工程 若干种集成构想,主要有:非线性工艺规划 (Concurrent Engineering,CE)思想的指导下,提出 (Nonlinear Process Planning,NLPP),动态工艺规划 了基于GA-SA混合遗传算法的CAPP和PPC集成优 (Dynamic Process Planning,DPP),并行工艺规划 化策略,对遗传基因编码、适应度函数、启发式基 (Simultaneous Process Planning,SPP),分布式工艺规 因重组等问题进行了详细的讨论,最后以实例加以 划(Distributed Process Planning,DTTP)[1,21等模型。 验证。 这些模型的共同特点就是充分利用CAPP和PPC基 1基于统一资源库的CAPP和PPC 于制造资源的选择这一交叉点,利用CAPP的柔性, 通过对CAPP的某种改良,从而提高整个制造系统 的集成问题描述 的柔性。 基于统一资源库的CAPP和PPC集成的关键环 收稿日期:2006—09—08 基金项目:浙江省教育厅课题(20050273)l浙江师范大学校级一般项目(KYJ05Y05097) 作者简介:朱春耕(1973一),男,浙江义乌人,讲师,硕士,研究方向为工程图学、机械计算机辅助设计。 【58】 第29卷第1期2007—01 维普资讯 http://www.cqvip.com
节是资源的选择和匹配,即在满足一定的优化目标 的前提下,从零件的多工艺路线中选择一条最优的 加工路线和某一工序中特定的加工设备,选择时应 充分考虑各种技术经济因素,如机床的加工精度、 加工效率、设备的状态和资源的利用率等。本文主 要研究在FMS环境下,利用CAPP提供的柔性工艺 规划,在满足资源负荷均衡和系统流通时间最小等 2 CAPP ̄I PPC的集成数学模型的建立 由于在实际的生产中,企业不仅要考虑产品的 加工时间,还要考虑产品的加工成本,因此,在建 立基于GA.SA算法的CAPP与PPC的集成数学模型 中,本文综合考虑加工成本和加工时间,由企业根 据需要确定加工时间和加工成本的权重系数 为综 合考虑加工时间和加工成本,本文采用归一化处理 优化指标情况下,为零件实时地选择适当的制造资 源,实现系统的全局优化目标。CAPP和PPC的集 成模型如图1。 图1 CAPP和PPC集成模型 在CAPP和PPC集成问题中,本文采用文献[4] 中的实例,并做了扩充。有四种不同类型的工件,标 记为 ( l,2,3,4);每种工件的批量是4个,且加工工 序都是3道,每道工序均可以被不止一台机床加工, FMS柔性加工组中共有6台机床设备l调度的目标 是寻找一个可行的调度方案,使得在给定的约束条 件下,获得某种评价的最优解(如加工时间最短或 加工成本最低等)。不同类型工件在不同类型机床上 的加工时间和加工成本见表l,如零件J,的2—2道 工序在M1上的加工时间为4个时间单位,加工成本 为9个价值单位 表1零件加工时间与加工成本 J O M M3 M5 M 1一l 4,5 6,4 8,3 J 1—2 6,5 4。6 8.3 1—3 4.8 8,5 1O.4 2—1 6 6 l0,5 4,5 J2 2—2 8,9 6,4 7,4 2—3 4,4 7,5 11,5 3 1 10.12 12,9 lI ]3 2 8,11 6,ll 10 12 3—3 l2,l8 10,16 l4,20 4—1 l6,20 12,24 l6.20 J 4—2 12。8 8,12 l0,14 4——3 4。10 6,12 6,7 的方式分别表示时间子适应度函数和价值子适应度 函数,然后建立综合适应度评判数学模型。 加工时间子适应度函数: :! 兰! ± !二! 一{maxt(x)+1)-mint(x) 加工成本子适应度函数: rc r :! 兰! ± !二! {maxC(X)+1)-minc(x) 综合适应度函数: I f(x)= , (X)+w2f ( ) 十 =J wl,w2 2 0 式中f∞代表当前某调度方法中各工序的加工时 间之和,c )代表当前某调度方法中各工序的加工成 本之和,maxt(x)与mint(x)分别表示当前种群调度方 法中最长的加工时间与最短的加工时间,maxc(x)与 minc(x)分别表示当前种群调度方法中最高的加工成 本与最低的加工成本。W.与 为权重系数,具体值 可以根据具体情况而定。 。 3 GA-SA算法描述 GA和SA混合优化算法过程如下: Stepl:确定GA和SA各个参数,包括遗传代 数、种群大小、交叉概率P 、变异概率P 和SA中 的初始温度等。 Step2:产生初始种群,执行GA的各项操作(交 叉、复制和变异等等)。 Step3:计算每个个体的目标函数及其适应度, 统计最优解与最差解 Step4:对每个个体执行SA操作。 Step5:判断是否达到指定的迭代次数,如果未 达到则返回Step3。 4实现方法 4.1染色体编码 在文献[4]中介绍了多种染色体编码方案,但它 们仅仅适用于不同零件的单工序调度,从表1可知, 第29卷第1期2007-03 [591 维普资讯 http://www.cqvip.com
务l泣 匐 似 每道工序在调度前是无法为其确定加工设备的,且 同类型零件有多件,因此,为加以区别,本文采用 Tsujimara和Kubota 提出的基于工序的编码方法, 并对其进行扩展和修改。如表2,很容易看出此种编 码方法产生的染色体任意基因序列总是可行调度。 表2调度染色体基因片段 工序321 111 311 412 421 322 编码32 11 31 41 42 32 1:序222 422 323 112 13l 423 编码22 42 32 11 13 42 一 4.2 GA中初始种群的生成及选择.交叉和变异 采用随机法生成多个染色体,考虑到计算时间 和防止过早收敛,本例中采用2O个染色体的种群。 选择(Selection)操作采用最佳个体保存法(Elitist mode1),将父代和子代染色体进行比较,选择两个适 应度较好的染色体放到染色体群中。 交叉(crossover)操作可以将父代的优良信息传 递给子代,但是在本例中,随机的交叉操作可能产 生没有不合法的染色体型。因此,在这里本文采用 基于Gen—Tsujimura—Kubora两点基因交换方法[4J,使 后代染色体合法化。 变异(mutation)采用随机两点间基因码互换,如 图2。 厂——…——~ ④④⑨⑨@@@④④⑥⑨④④④ ’ @⑨⑨⑧@@@@@@⑨④④@ 图2基因变异操作 4.3 SA中各参数设计 状态产生函数选择插入操作(Insert),即随机选择 某个点插入到基因串中的不同随机位置。状态接受 函数是算法产生突跳能力的关键,本文采用min(1, exp(一A/t)>random[O,1】)准则作为接受新状态的条件 最常用方案,其中A=f(s)-f(s’)为新旧状态的适应度函 数差,f为“温度”。初始温度用式 =:一A /Inp,确定, 其中△…为初始种群中两两适应度函数差的最大值, P 为初始接受概率,一般选取0.1。退温函数利用式 = + 进行退温,其中 (0,1)和算法终止准则可以 用循环次数来终止。 4.4调度描述 为解决不同资源的选择问题,本文采用文献[5] 提出的基于事件驱动的滚动窗口技术来实现调度。 先说明文中出现的各标号含义: 【60】 第29卷第1期2007-01 f一工件号(f=1,2,…,,1) 七一床号( 1,2,…, ); 一可以使用机床足的时刻(机床足在此时刻空 闲) 一工件i的第-『道工序可以被加工的时刻点 一工件i的总工序数 一在机床足上加工工序0 的所需要的时间段 一在机床足上完成工件 的第-『道工序的时间 点 E 一工件f的第-『道工序的最早完工时间点 , 一工件i的完工时间点 调度算法过程如下: Step1:计算所有工序的理想可以被加工的开始 时刻 设^ =0, =0 T ̄]=Tiq1)+T/(7 I) .Step 2:如果工序集合中有未被调度的工序,从 集合中取出此刻排在第一位的未被调度的工序转 Step 3,否则,设 Makespan=max(F)(i=1,2,…, ) Step 3:令 =ma)【( , 7)+ Step 4:设Eii=minx(Fii ) 如果户 ,则FyE. 否则,计算 )= 。+h)+( ’ 【7+1)) ( =1,2,…,( -j)) Step s M Ej Step 6:检查集合中是否还有未被调度的工扇 如果有,则转Step 2。否则,有Makespan=max(F ̄) 5实例仿真 本文以前文4类各3共12个工件在6台机床(标 示为Mn,r/取1、2、3、…、6)上的加工为例,在 Windows2000平台上利用Matlab 6.0对GA—SA算 法进行仿真。设定所有种群规模为20,变异概率 P 取0.2,种群交叉概率P 取0.7,初始温度t。取 10000,退火速率九取O.8,用综合适应度函数为计 算目标,其中最早完成时问和加工成本权重分别 取0.8和0.2。算法的终止条件取连续100代适应度 函数值没有变化。在PC(P IV 1.5G)上运行约48s, 算法终止。图3为采用混合算法的四类12个工件 的调度甘特图,其完成时间是56个时间单位,最 后的加工成本为356个成本单位。图4是算法的收 维普资讯 http://www.cqvip.com
M 1_M 2 Il一 l 1M 3 丑二 ]二 二巨[ M4 匝叵[ 二 [ M 5 ;碉[ 巨 二[: M 6 厂 _i —厂 图3四类l2个零件调度千特图 敛对比图,从图中可以看出,采用混合算法后,其 图4算法对比收敛图 【1】LIU M,BAI L,ZHANG S S.Modeling integrated CAPP/PPS 收敛的速度加快了,大约在300代之前,收敛速度 systems【J】.Computers&Industrial Engineering,2004,46: 较单一的遗传算法要快,450代左右适应度值基本 275.283. 稳定;采用单一的遗传算法,在500代之前,其收 【2】王忠宾,王宁生,叶文华.基于非线性工艺规划的CAPP和 敛速度较混合算法要慢,在650代后,其适应度趋 PPC集成原理研究 .机械科学与技术,2002,21(4):645. 于稳定,其最后的适应度值较混合算法要略低。 647. 【3】A GA—SA multiobjective hybird search algorithm for integrat 6结论 ing lot sizing and sequenced in flow・line scheduling[J]. International Journal ofAdvanced Manufacturing Technology, 应用基于GA—SA混合算法和基于事件的滚动 2003,21:126.137. 窗口的启发式调度规则相结合的调度算法,能够解 【4】f日】玄光南,陈润伟.遗传算法与工程设计【M].北京:科学 决柔性工艺路线的调度问题,使CAPP和生产调度 出版社,2000. 的集成系统快速高效地生成较优化的工艺规划。 【5】孙志峻,朱剑英,潘全科.基于遗传算法的多资源作业车间 智能动态优化调度[J】'机械工程学报,2002,38(4):120—125. 参考文献: m m 【上接第34页】 检测精度有很大提高。 4实验结果 参考文献: 实验选用螺纹灰度图像,用经典的Sobel算子, 【1】CANNY.A Computational approach to edge detection【J】. Laplace算子和本文论述的方法进行比较,结果表明 IEEE Trans on PAMI,1 986;8(6):670 698. 本文的方法在去噪和边缘提取上效果明显,螺纹的 【2]MAU AT S G,ZHONG S F.Characterization of Signals from Multi—scale Edges【J】.IEEE Trans.On PAMI,1992,14 (7):7l0—731. 【3】DAVID A.Yocky,Image merging and data fusion by means 0f the discrete two-dimensional wavelet transform【J].Opt. (1)原图 Soc.Am A,1995,l2(9):1834—1841. 【4]王庆有.图像传感器应用技术【M】.北京:电子工业 版社, 2003. 【5】左建中,张新荣 兰风,郭玉申.将小波变换用于机械零 (2)Sobel算子 件尺寸自动检测的研究【J】.机械设计,1999,12(12):24.26. 【6]项震.基于CCD器件特征的图像噪声消除【J1_光电工程, 2001,12(28):66—68. [7]章毓晋.图像分割【M].北京:科学出版社,1998. [8陈武凡.小波分析及其在图像处理中的应用【8]M].北京:科 (3)Laplace算子 学出版社,2002. 【9]段瑞玲,李庆祥,李玉和.图像边缘检测方法研究综述[J】 .光学技术,2005,5(3):415-419. 【l0】武东生,刘秉琦.小波变换在CCD图像边缘检测中的应用 (4)小波算子 【J].应用光学,2004,25(2):48—50. 第29卷第1期2007—01 [61】 n)
因篇幅问题不能全部显示,请点此查看更多更全内容