（控制理论与控制工程专业论文）基于差分进化算法的罩式炉退火优化调度方法.pdf

大连理工大学硕士学位论文 摘要 复杂工业生产过程的调度问题及其相应的高效算法一直是学术界和工业界的热点 问题，差分进化算法是一种有效的群智能搜索算法，它不仅具有良好的全局收敛性能， 且实现起来较为方便。本文在深入研究差分进化算法全局优化搜索能力的基础上，针对 工业生产中的实际调度问题进行分析，提出了一种改进的差分进化算法。并在经典的t s p 问题上做了该算法与其它优化算法进行对比研究。该算法在交叉过程中采用自适应改变 交叉率的方法，在进化的初始阶段能提高算法的全局搜索能力；在进化的后期能提高算 法的局部搜索能力。 本文针对罩式炉退火过程的优化调度问题，使用现有成熟的建模方法，重新实现了 退火过程调度模型，将改进的差分进化算法应用于该模型之中来对模拟调度方案进行优 化，同时使用其他几种算法在该模型上作了对比分析和研究。最后得出结论，改进差分 进化算法应用于具体的生产调度问题，能够较好的解决复杂组合优化问题。 最后，采用面向对象的思想实现了改进差分进化算法在生产调度问题中的软件设计 与开发，利用其封装和继承特性完成对现场生产过程的仿真。使用n e t 平台，b s ( b r o w s e r s e e r ) 架构实现，数据库使用s q ls e r v e r 2 0 0 0 。采用a d o n e t 技术操作数 据库。 关键词：差分进化算法；智能优化；罩式炉退火；生产调度 基于差分进化算法的罩式炉退火优化调度方法 a b s t r a c t t h ep r o d u c t i o ns c h e d u l i n gp r o b l e mi nc o m p l i c a t e dp r o c e s si n d u s t r y 孤di t sr e l a t e dh i 曲 e 髓e c t i v ea l g o r i t h i na r ca l w a y st h eh o tt o p i c sn o t0 n l yi l la c a d e m i cr e s e a r c hb u ta l s o i n a p p l i c a t i o nf i e l da tp r c s e n t d i f f e r e n t i a le v o l u t i o na l g o r i t h mi s al 【i n do fs e a r c ha l g o r i t h m b a s e d 咖c o l o n yi n t e l l i g e n c e ，w h j c hh a sg r e a t 百o b a ls e a r c ha b i l i t y 柚dt h ec h a r a c t e r i s t i c so f e 舔i l yi m p l e m e n t a t i o n 1 l lt h i sp a p e r ，c o n s i d e r i n gt h em e f i to ft h ec o l o n yi n t e l l i g e n ta l g o r i t h m ， am o d i f i e dd i f 托r e n t i a le v o l u t i o na l g o r i t h mi sp r o p o s e dt os o l v et h ep r o d u c t i o ns c h e d u l i n g p r o b l e mi ni n d u s 仃y ， i nw h i c ht h ea d a p t i v ec r o s s o v e rp r o b a b i l i t yi s p r e s e n t e d o t h e r o p t i m i z a t i o na 1 9 0 枷瑚sw e r ec 0 m p a r e dw i t hm o d i f i e dd i 仟e r e n t i a le v 0 l u t i o na 1 9 0 r i t h m0 n t h ec l 硒s i ct s p q u e s t i o n ；s u c ha p p r o a c hc a ni m p r o v et h e 酉o b a ls e a r c ha b i l i t yi l li n i t i a lp h a s e 卸dt h cl o c a ls e a r c ha b i l i t yi nt h el a t e rp h 硒eo ft h i sa l g o r i t h m i i lt h i st h e s i s ，锄e x i s t i n gm o d e l i n gm e t h o di su s e df o rt h eb e l l - t y p e 姐n e a l i n gp r o c e s s 1 1 l em o d i f i e dd i f f e r e n t i a le v o l u t i o na 1 9 0 r i t h mi s 印p l i e dt 0t h es i m u l a t i o nm o d e li no r d c rt o 0 p t i m i z et h es c h e d u l i n gm o d e l s e v e r a lo t h e ra l g o r i t h m sa r ee m p l o y e dt oc o m p a r ef o rt h e 勰a l y s i sa i l dr e s e a r c h f i n a l l y ，s u c ha 1 9 0 r i t h mc a nb ea p p l i e dt 0t h es p e c i f i cp r o d u c l i o n s c h e d u l i n gp r o b l e m ，a n ds o l v ec o m p l e xc o m b i n a t o r i a l0 p t i m i z a t i o np r o b l e m sb e t t e r f i n a l l y ，t h eo b j e c t - o r i e n t e dm e t h o di su s e dt od e s i 印锄dd e v e l o p 觚a p p l i c a t i o ns y s t e m a s i i n u l a t i o nm o d e li sb u i l df o ra c t u a lo n s i t ep r o d u c t i o nu s i n gt h ee n c a p s u l a t i o na n d i n h e r i t a n c ec h a r a c t e r i s t i c s t h e n e tp l a t f b n ni sa d o p t e di nt h es o n w a i ed e v e l o p i n ga n dt h e b s ( b r o w s e r s e r 、，e r ) s t m c t u r ei si m p l e m e n t e da sw e l l t h es q ls e r v e r 2 0 0 0d a t a b a s ei s e m p l o y e dt ob et i e a t e da st h eb a c k g r o u n dd a t a b a s ei n s t a n c e ，a n dt h ea d o n e tt e c h n o l o g yi s a d o p t e di nt h i ss y s t e m k e yw o r d s ： d i f f e r e n t i a 【e v o 【u t i o na l g o r 让h m ； i n t e l l i g e n to p t i m i z a t i o n ； b e u - t y p e a n n e a i i n g ；p r o d u c t i o ns c h e d u 【j n g i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：翼章差鳘丝亟鳘! 垄鱼鬈封挚l 立凄i 盘! 丝鱼垄盔：王 作者签名：二本赵盏警陋卜一 日期：_ 二叫年上l 月一日 大连理- t 大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 驿乏笙丝鱼互! 圣垒聋擘必趔堑b ! 团疲杰! 墨 作者签名：型盘纽日期：! 三m 堡月丑日 导师签名：型i 兰趁日期：至鲤乞年么乙月上l 日 大连理t 大学硕士学位论文 1 绪论 1 1研究背景 长期以来，学术界和工业界在解决复杂工业生产过程调度问题时一直在努力寻找相 应的高效算法，以解决复杂组合优化问题，并且该算法需有较强的搜索能力，不容易陷 入局部最优，参数设置简单，收敛快速。 本文研究工作的选题来源于国家8 6 3 计划课题：冷轧薄板生产计划与调度一体化技 术及应用。冷轧类企业近年来通过技术革新和新设备的引进以及产销系统( e n t e 甲r i s e r e s o u r o ep l a n n i n g ，e r p 层) 的应用，生产效率得到很大提高，但是对于车间生产计划 与生产调度( m a n u f a c t u r i n ge x e c u t i o ns y s t e m ，m e s 层) 层次的操作仍然主要依靠调度 人员手工完成，存在着工作强度很大，效率不高等缺点。近年来，随着计算机现代集成 制造系统( c o m p u t c ri i l t e g r a t e dm a n u f a c t u r i n gs y s t e m s ，c i m s ) 的发展与应用，迫切需 要实施高效的优化方法来解决m e s 层生产调度问题。本文提出并实现了将一种改进的 差分进化算法应用于解决实际生产调度问题，并通过仿真试验表明了该算法在求解此类 问题上的有效性。 1 2 相关问题的研究现状 1 2 1 优化算法 随着社会经济的发展，生产实际中遇到的问题也越来越复杂，一般遇到较多的是全 局最优化问题。经典算法一般很难避免局部极小问题，因此出现了用于全局搜索的智能 优化算法【。智能优化算法是人们受自然界或生物界的许多自适应优化现象的启发，模 拟自然生态系统机制而设计的求解复杂问题的算法。对于那些受大自然的运行规律或者 面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法( h e u r i s t i c 舢9 0 r i t h m ) 。现在的启发式算法既包括来自自然的规律，也有来自人类长期积累的工作 经验。启发式算法有两种不同的定义，一种定义为，一个基于直观或经验构造的算法， 对优化问题的实例能给出可接受的计算成本( 计算时间、占用空间等) 内，给出一个近似 最优解，该近似解与真实最优解的偏离程度不一定可以事先预计；另一种启发式算法是 一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得 到的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度i l j 。伴 随着计算机技术的发展，计算量较大的启发式算法得到了发展，启发式算法有很多，其 代表性的方法包括遗传算法( g e n e t i c 越g o r i t h m ，g a ) 、模拟退火算法( s i m u l a t e d 基于差分进化算法的罩式炉退火优化调度方法 a n n e a l i n g ，s a ) 、神经网络( n e u r a ln e 觚o r k ，n ) 、粒子群算法( p a n i d es w a 瑚0 p t i m i z a t i o n ， p s o ) 等。启发式优化方法以仿生算法为主，通过启发式搜索策略实现多个可行解并行地、 随机优化，已经成为最优化领域的一个研究热点【2 1 。 1 2 2 生产调度问题 在工业生产过程中，一些资源是可以共享的，包括加工设备、存贮设备、运输设备、 人力、资金和能源等。生产调度就是在一定的时间内，进行可用共享资源的分配和加工 任务的排序，以满足某个或某些特定的生产指标【3 j 。在车间生产中还会涉及生产计划， 它主要是对产品按一定的限制条件进行排序。与生产计划不同，生产调度主要涉及生产 时间地点上的具体安排和资源的详细分配。 文【4 】指出，处理调度问题就是在满足硬性要求的条件下尽可能使生产成本等达到令 人满意的效果。而设备故障，原料供应变化，生产任务变化等非正常情况，都是事先不 能预见的，在进行调度时大都作为不确定因素考虑。 生产调度问题本质上说，是在满足复杂工艺约束的条件下，完成资源分配，优化组 合的问题，其主要目的在于确定生产过程中什么时候，什么地方、由哪个任务占用什么 样的资源，以此保证一系列约束关系包括技术工艺和资源容量等在调度计划执行过程中 得到满足，并使由企业经营目标或用户订单要求所决定的、与调度计划执行过程及执行 结果有关的一系列评价指标得以满足或优化1 5 j 。 1 2 3 生产调度问题的优化算法应用 典型的调度问题通常可以抽象为如下问题：有咒个工作在历台机器上加工，q ，表 示第f 个工件在第，台机器上操作，相应的操作时间瓦为已知，事先给定各种技术约束 条件，要求确定与技术约束条件相容的各机器上所有工作的加工次序，使加工性能指标 达到最优。除了技术约束外，通常还假定每一时刻每台机器只能加工一个工件，且每个 工件只能由一台机器加工，同时加工过程为不间断。针对求解上述典型的生产调度问题， 目前国内外的研究成果中几种常用的智能优化算法简介如下： ( 1 ) 遗传算法( g a ) 。遗传算法是最基本的进化算法，其收敛性已经过了证吲4 1 。它 是模拟生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模 拟自然进化过程搜索最优解的方法。文献【6 1 在解决罩式炉问题中使用了该方法，并使用 了参数白适应调节的方法对原g a 算法进行了改进，取得了较好的优化效果。 ( 2 ) 单亲遗传算法( p g a ) 。p g a 采用单亲繁殖方式，其遗传操作与g a 有着本质的 区别，p g a 的基因重组算子隐含了序号编码g a 的交叉算子的功能，p g a 的子代个体 人连理工大学硕士学位论文 保留了父代个体的大部分遗传特征，具有避免早熟收敛的优点，特别适用于整数编码的 序列优化问题，可以克服传统序号编码遗传算法中的不足，还可以较方便地在遗传操作 过程中处理约束条件，提高了搜索效率。文献【7 】使用p g a 算法解决热轧中厚板自由轧 制计划编制问题，比较好的解决了这一问题。 ( 3 ) 模拟退火算法( s a ) 。s a 算法起源于统计方法，首次被飚r k p a t d c 等引入到优化 问题中来，该算法综合了统计物理学和局部搜索方法的思想，采用m e t r o p o l i s 接受准则， 并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最 优解。其算法特点是局部搜索能力强，缺点是搜索速度较慢。文献f 8 1 使用s a 算法成功 的解决了公交调度问题，得出了合理的公交车发车时刻表。 ( 4 ) 算法的结合。由于各种算法都有自身的优缺点，为了解决一个特定问题，人们 通常将两种优化算法结合起来以达到算法性能的平衡，来解决优化问题。比如文献【9 】 应用s a 与g a 算法的结合来解决t s p 问题。这一搭配是利用s a 搜索能力强的优点来 弥补g a 算法局部搜索能力弱的问题。而g a 把握搜索过程的总体的能力强，正好弥补 了s a 在这方面的不足。 1 3 研究意义 从宝钢冷轧薄板厂的优化调度生产实际情况来看，国内外相关研究在实际应用中存 在着几个困难，主要体现在生产调度问题的复杂特性上，使得想在该领域内找到一种有 效通用的方法具有较大难度。由于调度问题性质复杂，很多问题都已被证明是n p 难问 题，在有限的时间内无法求得最优解，甚至不存在确定多项式时间的优化解法。就罩式 炉退火机组来说，其生产周期长、装炉组合堆垛方式复杂、作业调度过程复杂，作业调 度的结果( 装炉顺序) 对退火车间的生产效率有着很大影响，使得罩式炉退火生产成为 冷轧薄板企业生产的瓶颈工序。而罩式炉退火生产调度问题就成为一个迫切需要解决的 生产调度问题。它的优化排产操作是提高整个薄板企业生产效率的重要手段。对差分进 化算法研究的同时也将其与其它算法做了比较研究，熟悉了生产调度问题中常见的智能 算法的特点。在此基础上对差分进化算法做出改进并用于罩式炉优化调度问题可以有效 的优化调度结果，提高性能指标。事实上在对生产实际的研究中，所有的车间生产调度 问题的特点具有相似性，包括繁多的约束，复杂的相互关系等，而改进差分进化算法在 这个问题上的应用具有一定的普遍意义，该算法的应用可以有效地提高企业的生产效 率、资源利用率，提高企业的核心竞争力。 基丁差分进化算法的罩式炉退火优化调度方法 1 4 本文主要工作 本文主要工作是针对复杂的组合优化问题提出了一种改进的差分进化算法，并将该 算法应用于t s p 问题，做了仿真实验，比较了其他几种优化算法在这一问题上的优化效 果。另外，将该算法应用于实际工业生产调度问题，采用现有成熟的仿真模型，在n e t 平台上将其重新实现，在该模型中使用该算法对其生成的调度方案进行优化。同样采用 几种优化算法对比的形式研究他们在实际优化调度问题上的效果。研究表明将提出的改 进差分进化算法应用于优化调度问题可以很好的解决模型优化的问题，得到令人满意的 优化方案。以下是本文主要的工作： ( 1 ) 第一章重点简述了优化算法，以及生产调度问题的相关情况。并就应用于该问 题的几种智能算法进行学习与研究。 ( 2 ) 第二章重点研究了差分进化算法的基本原理、参数选择、具体实现。并在此基 础上提出一种新的带有参数自适应调节的改进差分进化算法用以解决生产调度问题。在 研究中根据对差分进化算法各个参数对算法影响的研究，通过交叉概率的自适应变化提 高了该算法的寻优效率。在此基础上，研究了经典优化调度问题旅行商问题，并使用该 问题对提出的改进差分进化算法进行了仿真实验。试验中与其他几种常见算法进行了比 较研究。本文在第三章也将改进的差分进化算法同其它的智能算法就应用于具体的优化 调度问题进行了对比研究，结果都表明本文算法不仅能收敛到全局最优解，而且具有很 快的收敛速度，特别适合于解决仿真优化等计算时间花费很大的优化问题。 ( 3 ) 第三章在使用已有的成熟方法来模拟了退火生产过程。并且在如何处理等卸加 热罩操作问题上采用穷举法将所有可能都考虑到设计当中，保证了卸热罩操作得到迅速 准确的处理。继而将第二章给出的改进差分进化算法应用于上述模型，并就三个性能指 标分别优化，对结果进行了大量的对比分析。改进差分进化算法在该问题上具有适应性 和有效性。 ( 4 ) 第四章完成了罩式炉优化排产软件在b s 架构上的重新实现。数据库使用的是 s q l r v e r 2 0 0 0 数据库，其具有与m 玎平台结合好，使用方便、稳定等优点。系统采用 m i 咖n 公司推出的a s p n e t 技术，使用了b s 架构的软件体系结构，所生成的基于 w e b 的应用程序无论是在实用性还是在外观上都较传统的应用程序有较大提高，而且软 件易于维护，相对于传统应用程序来说升级更为方便，有利于降低企业软件安装和维护 成本。 大连理工大学硕士学位论文 2 差分进化算法 2 1 优化问题 优化问题主要包括一类排序、分类、筛选、搜索等问题，此类问题寻求的是一些决 策变量的排列组合，这些决策变量不是连续变量，而是离散变量。这类问题就是组合优 化问题。实际上所有计算机处理的优化问题都是组合优化为题，因为计算机表达的变量 实际上都是离散变量。典型的组合优化问题有旅行商问题，加工调度问题，图着色问题， 聚类问题，装箱问题等。 2 2 优化算法 经典算法的确立可以从解决线形规划的单纯形法开始，但单纯形法不是多项式算 法。随后出现了椭球算法( 多项式算法) 和内点法。对于非线性问题，刚开始的方法是用 线性优化理论去逼近求解非线性问题，后来的非线性理论大多都是建立在二次( 凸) 函数 的基础上，也就是用二次函数去逼近其他非线性函数。在此基础上产生了许多经典的优 化算法。这些传统的最优化方法中，大致分为梯度搜索和非梯度搜索【2 1 。对于梯度搜索， 首先需要知道的是目标函数是否连续可导，且需要可导的解析表达式，需要利用函数的 一阶、二阶导数及偏导数矩阵来确定最优方向和最优步长。以最优梯度法为例，需要知 道目标函数的一次导数的解析式来确定搜索的负梯度方向，任选初始点给定收敛精度后 就可以开始搜索了。所谓负梯度方向其严密的定义是指函数在某一点附近的最速下降方 向，但这是一个局部的性质，并不是全局的性质。所以初始值的选取会就会影响收敛点， 无法获知是否能收敛到全局最优点。梯度搜索是不能广泛应用的，因为相对于非梯度搜 索，虽然梯度搜索收敛速度更快，但是应用条件苛刻，且计算复杂。对于非梯度搜索， 只需要进行函数值的计算与比较来确定最优化的方向和步长。其代表性的方法有进退 法，坐标轮换法，黄金分割法，单纯形算法等。 2 0 世纪8 0 年代以来，应运而生了一系列现代优化算法，这些算法在解决一些复杂问 题的成功应用，使得它们越来越受到科技工作者的重视和广泛应用。这类算法中的每一 个算法都以人类、生物的行为方式或物质的运动形态为背景，经过数学抽象建立算法模 型，通过计算机的计算来求解组合最优化问题，因此这些算法也称为智能优化算法，或 称为启发式算法。本文重点研究了智能优化算法中的差分进化算法及其改进，同时也做 了关于该算法与其他智能优化算法如单亲遗传算法，模拟退火算法等的对比研究。 基于差分进化算法的罩式炉退火优化凋度方法 2 3 差分进化算法简介 差分进化( d i f f e r e n t i a le v o l u t i o n ，d e ) 是一种基于群体差异的启发式随机搜索算法， 该算法是由r a i n c rs t o m 和k e 加e t hp r i c e 为求解切比雪夫多项式而提出的【1 0 】【1 1 1 。差分进化 算法因原理简单、受控参数少、鲁棒性强等特点【1 2 l 。公式2 1 是差分进化算法的差分变 异公式。 ， q = 墨+ k 孵一墨)( 2 1 ) 其中：q “表示变异后的第i + 1 代，r 2 ，r 3 1 ，2 ，) ，x ：为父代基向量( 第f 代) ； 石：一疋称作父代差分向量( 第f 代) ；k 为缩放比例因子。 差分进化算法的全局寻优能力和易于实施使其在诸多应用中取得成功，基于优胜劣 汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自 学习等特征。文献【1 3 】中对d e 算法与其他算法进行了测试，结果表明在1 1 个测试函数上 是速度是最快的，对于另外四个测试函数上效果也很好，d e 在全部1 5 个测试函数上都 达到收敛。然而简单差分算法( s i m p l ed i f f e r e n t i a le v o l u t i o n 9 0 r i t h m ，s d e a ) 完全平 行地以随机性的概率转换机制很容易造成“早熟”或求解时间过长的现象，难以达到全 局最优。为了提高差分进化算法的搜索效率，不少学者在许多方面想方设法，以增强算 法的效率与可靠性。比如在算法控制参数的选择，差分策略的设计，选择策略的改进， 种群重构，多种群进化等发面都做了大量的工作，效果明型协1 4 j 。 d e 算法搜索性能取决于算法全局探索和局部开发能力的平衡，而这在很大程度上 依赖于算法的控制参数的选取，包括种群规模、缩放比例因子和交叉概率等。参数的设 置对于优化方法的优化效果影响是巨大的，事实上d e 的控制变量的选择是依靠经验设 置的，且d e 算法的变异操作有效的解决了变异方式不足的问题1 1 4 】【1 5 j 。 差分进化算法在一定程度上是一种自适应、自组织、自学习的迭代寻优过程，采用 实数编码、基于差分的变异操作和一对一的竞争生存策略，避免了复杂的遗传操作，同 时可以根据当前种群的个体问差异动态调整其搜索策略，具有较好的全局寻优能力和内 在的隐并行性。差分进化算法是采用随机的并行浮点矢量编码，在连续空间中进行随机 搜索的直接搜索，相比于进化算法，d e 算法保留了基于种群的全局搜索策略，采用实数 编码、基于差分的简单变异操作和一对一的竞争生存策略，所以d e 算法具有简单易用、 稳定性好和全局搜索能力强等优点【1 6 】【1 7 1 。 大连理工大学硕士学位论文 2 3 1 复杂环境下的d e 研究 ( 1 ) 离散优化。由于d e 采用实数编码，在连续空间进行搜索，故要利用d e 解决离 散优化问题就必须将d e 的实数编码转换为离散编码，或者是对问题进行变形使之适合 用d e 直接求解。目前这方面工作还很少【1 引。o n w u b o l u 等1 1 9 】利用前向转化机制将整数变 量转化为便于d e 处理的连续变量，经过d e 在两虚空间搜索后利用后向转化机制将连续 变量转化为可以进行目标评价的整数量。 ( 2 ) 多目标优化。目前对d e 的多目标优化设计，都是借鉴多目标优化领域一些成熟 的算法的思想和技术。d e 用于多目标的最初提出者是a b b a s s 等【刎，算法( p d e ) 中应用 了p a r e t o 竞争思想，在种群个体经过交叉和编译后，如果子代个体能支配父代个体则接 受，算法每代对非劣解集进行更新，当非劣解的个数超过阈值时，则采用最近邻法的小 生境技术来删除距离接近的非劣解。 ( 3 ) 约束优化。l a m o i n e n 【2 1 】通过修改传统d e 方法中基于目标函数值的一对一的接受 准则，提出了一种新的基于罚函数的d e 方法，该方法通过增大不可行解朝违背约束少 的方向选择压力，使得种群能以较快速度集中子可行域进行搜索。 本文对d e 算法进行离散化处理，并对d e 算法进行了改进使之适应仿真模型来解决 罩式炉退火过程的优化调度问题。 2 3 2 参数的选择 ( 1 ) 群体规模的选择。从计算复杂度分析，种群规模越大，搜索到全局最优解的可 能性就越大，所需的计算量和计算时间也会相应的增加。事实上最优解的质量并非随种 群规模的增大而一定变好，只有合理选取种群规模才能保证算法有较高的搜索效率1 2 2 】。 这是因为有时种群规模的增大，解的精度不再提高，反而会使最优解的精度降低，不能 达到预期的目的。所以在设计种群规模这一参数时一定要想办法达到多样性和收敛速度 的平衡。如果当种群规模太大时不增加最大进化代数，精度就会降低。另外，随着种群 规模的扩大，种群多样性也随着越来越大，如果种群过早收敛，就要增加种群规模以增 加多样性。 但) 缩放因子k 对优化效果的影响。当k 较大时，差分矢量对子代的影响较大，能 产生较大的扰动，从而有利于增加种群多样性，反之，如果k 较小，扰动也会变小，缩 放因子起到的是局部精细化搜索的作用。因此，k 在一定程度上起到了对种群的多样性 的调节作用【勿。如果k 取值太大，虽然能保持种群多样性，但也会使得算法近似随机搜 索，搜索效率低下，求得的全局最优解精度也会相应的降低；反之，如果k 值太小，种 群多样性丧失的很快，算法很容易就陷入局部最优，也就是出现早熟收敛，一般k 取值 基于差分进化算法的罩式炉退火优化调度方法 在【0 5 ，1 】之间较好。由于d e 算法是一种贪婪选择算法，所以随着种群的不断进化，各 个个体逐渐靠近最优个体，个体间的差异也会逐渐减小。这就意味着，当算法进化到一 定程度时，种群多样性就会丧失。因此，k 对算法的局部搜索和全局搜索起到了一定的 调节作用。k 较大，有利于保持种群多样性和全局搜索；k 较小，有利于局部搜索和提 高收敛速度。 ( 3 ) 交叉因子c ，溅纪对优化效果的影响。c ，溅跎的值较小时，成功率较高， 算法的稳定性好但所需的函数评价次数较大，收敛速度较慢；c 厂d 船砌把的值较大时， 常常会加速收敛，但易于陷入局部最优，发生早熟现象，达到给定精度的成功率低，稳 定性差。可见，成功率和收敛速度是一对矛盾。为了同时保证较高的成功率和较快的收 敛速度，一般对于单峰函数， c r d s ，r 口纪取值相对较大些在区间【o 6 ，0 8 】之内；对其它 复杂、多峰函数c ，仍媲口纪取值应相对小些在区间【0 1 ，o 51 之内较为合适。当c r o s s r 口把 的值越大时，变异个体对子代的贡献越多，有利于开拓新空间，从而加速收敛，但变异 个体也很容易在搜索的后期趋于同一，不利于保持多样性，从而走向早熟，稳定性差； c r d 譬s 砌纪的值越小，则父代对子代的贡献越多，增加了继承性的同时也减弱了算法开 拓新空间的能力，收敛速度相对减慢，但这样却有利于提高种群多样性，从而能保证相 对较高的成功率。 2 3 3 算法步骤描述 d e 算法的流程可描述如下： 步骤1 ：初始化阶段。在问题的可行解空间随机初始化种群 步骤2 ：变异阶段。对当前种群每个个体进行差分变异来产生新的种群。 步骤3 ：交叉阶段。对步骤2 生成的的变异个体进行交叉操作，利用交叉率来控制交 叉频率。 步骤4 ：选择阶段。对实验个体的目标函数进行比较，对于最小化问题选择目标函数 低的个体作为新种群的个体。 步骤5 ：若满足终止准则，则输出最优个体及其目标值；否则转型步骤2 。 然而深入分析差分进化的进化过程，我们发现贪婪选择算子的选择是一个颇有争议 的过程。如果我们以严格的选择机制选择的话就会降低种群多样性而直接导致进化停 滞，但是这样的选择操作却又是算法收敛必不可少的一个环节，也有学者受模拟退火算 法的启发将严格的贪婪选择过程用宽松的概率选择取代，改进后的算法性能有所提高， 但是算法仍然没有充分挖掘利用历史点的信息。 一8 一 大连理工大学硕+ 学位论文 本文改进之处主要是在步骤3 交叉阶段引入交叉率自适应函数，这样交叉率可以随 着迭代次数的增加而自适应变化，以适应算法迭代的不同阶段的收敛特点。 2 4 一种改进的差分进化算法 本文提出的改进算法针对一类采用自然数编码的组合优化问题，将用于解决连续性 问题的差分进化算法进行离散化处理。 d e 算法在搜索过程中变异算子为实常数，实施中变异算子也较难确定。变异率太 大，算法搜索效率较低，求得全局最优解精度低；变异率太小，种群多样性降低，易出 现“早熟 现象。产生早熟收敛的根本原因是迭代次数的增加和种群多样性的快速下降， 形成了“聚集 现象【矧。因此必须在收敛速度和求解精度之间寻求一个平衡点，如果 单纯提高算法收敛速度，候选解个体容易簇拥在一起，变异和交叉操作无法产生更好的下 一代个体，这样随着差分向量的消失，算法容易陷入局部最优解，从而无法保证求解精度。 针对以上问题，为了提高d e 的寻优能力、加快收敛速度、克服启发式算法常见的 早熟收敛现象。本文运用自然数编码和辅助算子解决变异问题，根据生成子代的附带基 向量之间的差异设计的自适应缩放比例因子，让交叉率随进化代数由小变大，在进化的 初始阶段，能提高算法的全局搜索能力，在进化的后期，能提高算法的局部搜索能力。 在选择操作上采用锦标赛机制来选取执行变异操作的父代基向量，同时在实验个体和种 群内最好个体之间的区域进行局部搜索。 2 4 1 编码 改进算法采用自然数编码。定义一个向量( 尼。，刀：，甩，厅。，传) 表示一条个体，其 中咒l ，尼2 ，以3 ，厅4 ，咒5 以。为【1 ，小】中互不相同的小个自然数，肼表示该组合优化问题的规 模，其中每个个体表示一个决策变量。然后随机产生一组个体个。为种群数量。而 这一组个体为初始种群。该种群的每条个体在经过变异、交叉、根据适应度值重新选择 后产生一代新种群，在经过反复迭代最终接近最优解。 2 4 2 变异 差分进化算法在变异操作上是利用随机偏差扰动产生新个体的方式，该方式可以获 得一个有非常好收敛性的结果。按差分公式( 2 1 ) 进行计算得出一个新的个体，式中 ，2 ，毛 1 ，2 ， 互不相同且与f 不同；k 为缩放比例因子，用于控制差分项的幅度， 通常取值为范围是f o ，1 1 。 差分进化算法事实上是用来解决连续问题的。本文提出了一种改进差分进化算法的 方法使其适用于优化调度问题，这些问题通常是离散问题。因此，该改进方法需要在变 基于著分进化算法的罩式炉退火优化调度方法 异操作之后完成离散化处理，具体实现是将得到的编码数组按升序重新排列，将新排列 中的个体在排序前数组中的位置作为新个体数组。这样变异后的个体符合编码规则，便 于下一步迭代。本文使用自然数编码时，变异操作的过程是： 令朋= 5 ，j 【三o 5 ，三2 ； 父代第一个个体为： 啦= ( 1 ，3 ，2 ，4 ，5 ) ；啦= ( 2 ，5 ，3 ，4 ，1 ) ； 按要求随机生成爪m 木3 的数组r 【m ，3 】对应公式( 4 ) 中的，r 2 ，r 3 。 r j j = ( 2 ，4 ，3 ) ，r 彪= ( 2 ，4 ，5 ) ，尺3 = ( 4 ，3 ，2 ) ，尺j 彳= ( 2 ，3 ，4 ) ，凡5 = ( 5 ，2 ，4 ) ，飓j = ( 1 ，5 ，3 ) ，砌= ( 1 ，4 ，3 ) ，砌= ( 3 ，1 ，4 ) ，飓4 = ( 3 ，5 ，1 ) ， 如= ( 1 ，5 ，4 ) 根据公式计算( 4 ) 计算得到的下一代个体编码为： 吨j = ( 4 ，2 5 ，3 5 ，2 5 ，4 5 ) ；琥2 = ( 1 ，2 5 ，2 ，2 5 ，0 5 ) ； 并不符合是【1 川】间互不相同的自然数的编码规则，无法进行下一步迭代。将子代个 体从小到大进行排序为： 慨= ( 2 5 ，2 5 ，3 5 ，4 ，4 5 ) ；琥x 2 = ( o 5 ，1 ，2 ，2 5 ，2 5 ) ； 将子代个体排序后的位置作为新的个体，结果为： 刀奴j = ( 2 ，4 ，3 ，1 ，5 ) ；乃觑2 = ( 5 ，1 ，3 ，2 ，4 ) ； 这样做新生成的数组在【1 朋】间无重复变化。 2 4 3 交叉 交叉操作是以一定的比例选择变异后的个体与子代进行某一片段的交换。显然交叉 率越大，变异操作在子代中的贡献就越大。如公式( 2 2 ) 所示： 【，j ： g j ，竺! i 朋以鼍 d 。枷口纪d ，f m 打) ( 2 2 ) ix ：，d 砌p ，w 括e 、 其中朋打为【o ，m 】间随机生成的数，其作用是保证下一代至少有一条个体经过上一代变 异交叉操作得来的。孵r 口纪为交叉率，其取值范围是o ，1 】。文本将m 醛砌纪设置 为自适应变化参数，即可随着迭代次数的增加而变化。其变化规律如公式( 2 3 ) 所示为： m 黜m 纪= c 曲训掣 ( 2 3 ) 大连理工大学硕士学位论文 其中c 交叉率上限，c m h 为交叉率下限，g 为总的迭代次数，g 为当前迭代次数。显然 在进化的初始阶段，能提高算法的全局搜索能力，在进化的后期，能提高算法的局部搜 索能力，加快收敛速度。 2 4 4 选择 如公式( 2 4 ) 所示将经过交叉变异的实验个体矿与父代进行适应度值的比较，本 文是要解决的是最小化问题，所以选择适应度值小的作为下一代。 x ；= 期箸1 ) ，( 彰”； 旺4 ) 适应度函数的返回值即为每次仿真模拟生产过程中计算出的性能指标。包括最大完 工时间，抛空率和总等待时间。而每一组染色体对应的就是装炉顺序。通过对装炉顺序 的不断调整比较达到性能指标的最优。 2 5 仿真试验 2 5 1 旅行商问题 旅行商问题( t s p ) 具有重要的实际意义和工程背景。它一开始是为交通运输而提 出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用 范围扩展到了许多其他领域，如电缆和光缆布线、晶体结构分析、数据串聚类等多种用 途。旅行商问题是这样的，某销售人员要到若干城市去推销商品，己知各城市之间的路 程( 或旅费) 。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使 总的路程( 或总旅费) 最小。这是一个经典的优化问题，以这个问题来测试改进差分进化 算法是因为它问题描述简单，易于编程实现，更重要的是，它提供了一个研究组合优化 问题的理想平台。很多组合优化问题，比如背包问题、分配问题和t s p 同属n p c o m p l e t e 类，它们都是同等难度的，如果其中一个能用多项式确定性算法解决，那么其他所有的 n p c o m p l e t e 类问题也能用多项式确定性算法解决。很多方法就是从t s p 发展起来的， 有一定的代表性，任何此类问题都可以抽象为旅行商问题。 耶p 问题广泛的存在于许多领域，凡是可以抽象成遍历全程一次，求代价最小的路 径的问题都可以当作t s p 问题来解决。在实用价值方面，t s p 问题的理论意义更加重大。 但是其求解的难度也很大。如果针对t s p 问题提出的某种算法能够取得比较好的计算效 果，就可以应用在其他类型的组合优化问题中。 基丁差分进化算法的罩式炉退火优化调度方法 旅行商问题要达成目标是使得总路程或者总经费最小，所以目标函数就是计算总的 路程或经费，具体实现时习惯取l “) 作为目标函数以形成最小化优化问题。采用自然数 ( 1 ，2 ，3 ，4 ) 作为城市编码，l ( c 1 ，c 2 ) 表示城市c 1 与城市c 2 的距离，假设有，1 个城 市，则总距离的数学表达式为： l ( f ) = 芝三 ，吒+ 1 ) + 己( c 万，c 1 ) ( 2 5 ) 其中，l 表示代数； 厅表示城市数； q 表示城市代码； ( c l ，c 2 ) 表示城市1 与成城市2 之间的距离5 a ) 表示第f 代计算的总距离。 2 5 2 旅行商问题求解 由于t s p 问题属于多约束的组合优化问题，解析法和枚举法很难找到大规模复杂组 合优化问题的全局最优解，所以对于t s p 问题的求解算法，应采用智能优化算法来求解。 将本文提出的改进差分进化算法应用于求解旅行商问题，其编码、变异、交叉选择操作 如上文所述，参数设置如下：城市个数为c i t v n u m = 3 0 ；缩放比例因子k = 0 4 ；交叉率下 限= 0 5 ；交叉率上限= o 9 ；迭代代数g = 5 0 5 ；种群规模n u m = 4 0 。 算法步骤如下： 步骤1 ：初始化路径，种群规模定为1 0 ，随机生成一组城市排列顺序，即旅行商所 要旅行的路径。 步骤2 ：变异操作，对代表当前路径的一组城市代码按照公式2 1 所示进行差分变 异以产生新的种群。 步骤3 ：交叉操作。对步骤2 生成一组城市代码按照公式2 2 所示进行交叉操作， 由于是在这组代码中任取一段进行交叉操作，交叉后可能会引起一组城市代码有重复现 象，这时应在交叉片段里再选取一个城市与其交换，直到不重复为止。利用交叉率来控 制交叉频率。因为该算法的交叉率自适应，其值根据迭代次数可变，具体计算方法参考 公式2 3 。 大连理工大学硕十学位论文 步骤4 ：选择操作。对新生成的路径使用公式2 5 来计算适应度值并进行比较，由 于本文采用公式2 5 中“) 作为目标函数，所以对应优化问题是最小化问题，并以此选 择目标函数低的个体作为新种群的个体。 步骤5 ：若迭代次数达到5 0 5 ，则输出最优个体及其目标值，算法迭代结束；否则 转到步骤2 继续迭代。直到满足迭代次数达到5 0 5 的迭代结束条件。 改进差分进化算法实现的流程图如图2 1 。 ( 磊 否 是 否 匝 巨盘 i，一 图2 1 改进差分进化算法实现的流程图 f i g 2 1 i 唧r o v c dd i f f b 化n t i a lc v o l u t i o na l g o r i t h mn o w c h a n 秦， 基于差分进化算法的罩式炉堰火优化调度方法 2 5 3 仿真实验 采用旅行商问题进行仿真实验是因为其描述简单，并且有实际背景，有代表性，但 是优化求解却根困难。其主要原因是“组合爆炸”问题，可以在一定程度上反映该算法 在解决优化调度问题上的表现。应用差分进化算法解决幅p 问题仿真图如图2 2 所示： r a 臧 图2 2 应用差分进化算法解决珊闩慝仿真图 h 醇2 c h 删缸珊删o m m 咖h 皿衄m l u 哺出口l i 出 由图2 2 可以看出在本次试验中几种优化算法在解决鸭p 问题上都有不错的表现。 改进差分进化算法达到了较好的优化效果，收敛速度也与其他算法相差不多。单亲遗传 算法达到的收敛效果较差，路径距离仅达到2 0 0 0 左右。模拟退火算法收敛速度与改进 差分进化算法的收敛速度相当，但收敛效果较差。蓝色的线表示普通差分进化算法，可 以看出未经改进其收敛速度和收敛效果相对较差。 由此得知，改进差分进化算法搜索能力强，和其他算法一样可