设计题目.ppt

毕业设计(论文)-柔性制造系统中机床调度优化研究

收藏

压缩包内文档预览:(预览前20页/共21页)
预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图
编号:9744381    类型:共享资源    大小:514.82KB    格式:RAR    上传时间:2018-03-24 上传人:好资料QQ****51605 IP属地:江苏
45
积分
关 键 词:
柔性制造系统 机床 调度 优化 研究 钻研
资源描述:
毕业设计(论文)-柔性制造系统中机床调度优化研究,柔性制造系统,机床,调度,优化,研究,钻研
内容简介:
一种新的改进遗传算法及其性能分析摘要虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称,但是它仍然有一定的缺陷,比如收敛速度慢。本文根据几个基本定理,提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法,它的主要思想是在进化的开始阶段,我们使用短一些的变异染色体长度和高一些的交叉变异概率来解决,在全局最优解附近,使用长一些的变异染色体长度和低一些的交叉变异概率。最后,一些关键功能的测试表明,我们的解决方案可以显著提高遗传算法的收敛速度,其综合性能优于只保留最佳个体的遗传算法。关键字编译染色体长度;变异概率;遗传算法;在线离线性能遗传算法是一种以自然界进化中的选择和繁殖机制为基础的自适应的搜索技术,它是由HOLLAND1975年首先提出的。它以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称。然而它也有一些缺点,如本地搜索不佳,过早收敛,以及收敛速度慢。近些年,这个问题被广泛地进行了研究。本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明,我们的解决方案可以显著提高遗传算法的收敛速度,其综合性能优于只保留最佳个体的遗传算法。在第一部分,提出了我们的新算法。第二部分,通过几个优化例子,将该算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分,就是所得出的结论。最后,相关定理的证明过程可见附录。1算法的描述11一些定理在提出我们的算法之前,先给出一个一般性的定理(见附件),如下我们假设有一个变量(多变量可以拆分成多个部分,每一部分是一个变量)XA,B,XR,二进制的染色体编码是1定理1染色体的最小分辨率是S定理2染色体的第I位的权重值是WII1,2,L定理3单点交叉的染色体搜索步骤的数学期望ECX是ECXPC其中PC是交叉概率定理4位变异的染色体搜索步骤的数学期望EMX是EMXBAPM其中PM是变异概率12算法机制在进化过程中,我们假设变量的值域是固定的,交叉的概率是一个常数,所以从定理1和定理3我们知道,较长的染色体长度有着较少的染色体搜索步骤和较高的分辨率;反之亦然。同时,交叉概率与搜索步骤成正比。由定理4,改变染色体的长度不影响变异的搜索步骤,而变异概率与搜索步骤也是成正比的。进化的开始阶段,较短染色体(可以是过短,否则它不利于种群多样性)和较高的交叉和变异概率会增加搜索步骤,这样可进行更大的域名搜索,避免陷入局部最优。而全局最优的附近,较长染色体和较低的交叉和变异概率会减少搜索的步骤,较长的染色体也提高了变异分辨率,避免在全局最优解附近徘徊,提高了算法收敛速度。最后,应当指出,染色体长度的改变不会使个体适应性改变,因此它不影响选择(轮盘赌选择)。13算法描述由于基本遗传算法没有在全局优化时收敛,而遗传算法保留了当前一代的最佳个体,我们的方法采用这项策略。在进化过程中,我们跟踪到当代个体平均适应度的累计值。它被写成XTT其中G是当前进化的一代,FAVG是个体的平均适应度。当累计平均适用性增加到最初个体平均适应度的KK1,KR倍,我们将染色体长度变为其自身的MM是一个正整数倍,然后减小交叉和变异的概率,可以提高个体分辨率、减少搜索步骤以及提高算法收敛速度。算法的执行步骤如下第一步初始化群体,并计算个体平均适应度FAVG0,然后设置改变参数的标志FLAG。FLAG设为1第二步在所保留的当代的最佳个体,进行选择、再生、交叉和变异,并计算当代个体的累积平均适应度FAVG第三步如果且FLAG1,把染色体的长度增加至自身的M倍,减少交叉和变异概率,并设置FLAG等于0否则继续进化。第四步如果满足结束条件,停止;否则转自第二步。2测试和分析我们采用以下两种方法来测试我们的方法,和只保留最佳个体的遗传算法进行比较21收敛的分析在功能测试中,我们进行了以下政策轮盘赌选择,单点交叉,位变异。种群的规模是60。L是染色体长度,PC和PM分别是交叉概率和变异概率。我们随机选择4个遗传算法所保留的最佳个体来与我们的方法进行比较,它们具有不同的固定染色体长度和交叉和变异的概率。表1给出了在100次测试的平均收敛代。在我们的方法中,我们采取的初始参数是L010,PC003,PM001和K12,当满足改变参数的条件时,我们调整参数L30,PC01,PM001。从表1中得知,我们的方法显著提高了遗传算法的收敛速度,正符合上述分析。表1功能测试结果方法我们的算法L10PC01,PM01L10PC01,PM01L30PC01,PM01L30PC01,PM01F1257152363579116264363F21982697342374450543322在线和离线性能的分析DEJONG提出了遗传算法的定量评价方法,包括在线和离线性能评价。前者测试动态性能,而后者评估收敛性能。为了更好地分析测试功能的在线和离线性能,我们把个体的适应性乘以10,并F1和F2分别给出了4000和1000代的曲线A在线B离线图1F1的在线与离线性能A在线B离线图2F2的在线与离线性能从图1和图2可以看出,我们方法的在线性能只比第四种情况差一点点,但比第二种、第三种、第五种好很多,这几种情况下的在线性能几乎完全相同。同时,我们方法的离线性能也比其他四种好很多。3结论本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明,我们的解决方案可以显著提高遗传算法的收敛速度,其综合性能优于只保留最佳个体的遗传算法。附件有了第一部分中假定的条件,定理1和定理2的验证是显而易见的。下面给出定理3和定理4的证明过程定理3单点交叉的染色体搜索步骤的数学期望ECX是ECXPC其中PC是交叉概率证明如图A1所示,我们假设交叉发生在第K个基因位点,从K到L的父基因位点没有变化,基因位点1到K上的基因改变了。在交叉过程中,1到K基因位点上的基因改变的概率为05“1”变化”0”或者”0”变为”1”,因此,交叉之后,基因位点上的染色体搜索步骤从1到K的数学期望是此外,每个位点的染色体发生交叉的概率是相等的,即PC。交叉后,染色体搜索步骤的数学期望是把EQA1替换为EQA2,我们得到其中L是非常大的,所以图1单点交叉定理4位变异的染色体搜索步骤的数学期望是其中PM是变异概率。证明每个基因位点上的基因的变异概率是相等的,比如PM,因此变异搜索步骤的数学期望是参考1LIHAIMIN,WUCHENGKE自适应变异概率的遗传算法以及其性能分析JACTAELECTRONIASINICA,1999,27589922NARAKOICHI基于大规模的分布式系统损失最小化的改进遗传算法A进化计算IEEE会议C19951201253LEIYIN,WEIHONG一种改进的遗传算法以及它在E计划波导过滤器设计重点额应用JACTAELECTRONIASINICA,2000,2861211244ENRIQUEALBA,JOSEMTROYA迁移策略在结构化的随机交配群体中的并行分布遗传算法的影响J应用智能,2000,121631815RUDOLPHR经典遗传算法的收敛分析J基于神经网络的IEEE转录,1994,5196101IMPROVEDGENETICALGORITHMANDITSPERFORMANCEANALYSISABSTRACTALTHOUGHGENETICALGORITHMHASBECOMEVERYFAMOUSWITHITSGLOBALSEARCHING,PARALLELCOMPUTING,BETTERROBUSTNESS,ANDNOTNEEDINGDIFFERENTIALINFORMATIONDURINGEVOLUTIONHOWEVER,ITALSOHASSOMEDEMERITS,SUCHASSLOWCONVERGENCESPEEDINTHISPAPER,BASEDONSEVERALGENERALTHEOREMS,ANIMPROVEDGENETICALGORITHMUSINGVARIANTCHROMOSOMELENGTHANDPROBABILITYOFCROSSOVERANDMUTATIONISPROPOSED,ANDITSMAINIDEAISASFOLLOWSATTHEBEGINNINGOFEVOLUTION,OURSOLUTIONWITHSHORTERLENGTHCHROMOSOMEANDHIGHERPROBABILITYOFCROSSOVERANDMUTATIONANDATTHEVICINITYOFGLOBALOPTIMUM,WITHLONGERLENGTHCHROMOSOMEANDLOWERPROBABILITYOFCROSSOVERANDMUTATIONFINALLY,TESTINGWITHSOMECRITICALFUNCTIONSSHOWSTHATOURSOLUTIONCANIMPROVETHECONVERGENCESPEEDOFGENETICALGORITHMSIGNIFICANTLY,ITSCOMPREHENSIVEPERFORMANCEISBETTERTHANTHATOFTHEGENETICALGORITHMWHICHONLYRESERVESTHEBESTINDIVIDUALKEYWORDSVARIANTCHROMOSOMELENGTHVARIANTPROBABILITYGENETICALGORITHMONLINEANDOFFLINEPERFORMANCEGENETICALGORITHMISANADAPTIVESEARCHINGTECHNIQUEBASEDONASELECTIONANDREPRODUCTIONMECHANISMFOUNDINTHENATURALEVOLUTIONPROCESS,ANDITWASPIONEEREDBYHOLLANDINTHE1970SITHASBECOMEVERYFAMOUSWITHITSGLOBALSEARCHING,PARALLELCOMPUTING,BETTERROBUSTNESS,ANDNOTNEEDINGDIFFERENTIALINFORMATIONDURINGEVOLUTIONHOWEVER,ITALSOHASSOMEDEMERITS,SUCHASPOORLOCALSEARCHING,PREMATURECONVERGING,ASWELLASSLOWCONVERGENCESPEEDINRECENTYEARS,THESEPROBLEMSHAVEBEENSTUDIEDINTHISPAPER,ANIMPROVEDGENETICALGORITHMWITHVARIANTCHROMOSOMELENGTHANDVARIANTPROBABILITYISPROPOSEDTESTINGWITHSOMECRITICALFUNCTIONSSHOWSTHATITCANIMPROVETHECONVERGENCESPEEDSIGNIFICANTLY,ANDITSCOMPREHENSIVEPERFORMANCEISBETTERTHANTHATOFTHEGENETICALGORITHMWHICHONLYRESERVESTHEBESTINDIVIDUALINSECTION1,OURNEWAPPROACHISPROPOSEDTHROUGHOPTIMIZATIONEXAMPLES,INSECTION2,THEEFFICIENCYOFOURALGORITHMISCOMPAREDWITHTHEGENETICALGORITHMWHICHONLYRESERVESTHEBESTINDIVIDUALANDSECTION3GIVESOUTTHECONCLUSIONSFINALLY,SOMEPROOFSOFRELATIVETHEOREMSARECOLLECTEDANDPRESENTEDINAPPENDIX1DESCRIPTIONOFTHEALGORITHM11SOMETHEOREMSBEFOREPROPOSINGOURAPPROACH,WEGIVEOUTSOMEGENERALTHEOREMSSEEAPPENDIXASFOLLOWSLETUSASSUMETHEREISJUSTONEVARIABLEMULTIVARIABLECANBEDIVIDEDINTOMANYSECTIONS,ONESECTIONFORONEVARIABLEXA,B,XR,ANDCHROMOSOMELENGTHWITHBINARYENCODINGIS1THEOREM1MINIMALRESOLUTIONOFCHROMOSOMEISSTHEOREM2WEIGHTVALUEOFTHEITHBITOFCHROMOSOMEISWII1,2,LTHEOREM3MATHEMATICALEXPECTATIONECXOFCHROMOSOMESEARCHINGSTEPWITHONEPOINTCROSSOVERISECXPCWHEREPCISTHEPROBABILITYOFCROSSOVERTHEOREM4MATHEMATICALEXPECTATIONEMXOFCHROMOSOMESEARCHINGSTEPWITHBITMUTATIONISEMXBAPMWHEREPMISTHEPROBABILITYOFMUTATION12MECHANISMOFALGORITHMDURINGEVOLUTIONARYPROCESS,WEPRESUMETHATVALUEDOMAINSOFVARIABLEAREFIXED,ANDTHEPROBABILITYOFCROSSOVERISACONSTANT,SOFROMTHEOREM1AND3,WEKNOWTHATTHELONGERCHROMOSOMELENGTHIS,THESMALLERSEARCHINGSTEPOFCHROMOSOME,ANDTHEHIGHERRESOLUTIONANDVICEVERSAMEANWHILE,CROSSOVERPROBABILITYISINDIRECTPROPORTIONTOSEARCHINGSTEPFROMTHEOREM4,CHANGINGTHELENGTHOFCHROMOSOMEDOESNOTAFFECTSEARCHINGSTEPOFMUTATION,WHILEMUTATIONPROBABILITYISALSOINDIRECTPROPORTIONTOSEARCHINGSTEPATTHEBEGINNINGOFEVOLUTION,SHORTERLENGTHCHROMOSOMECANBETOOSHORTER,OTHERWISEITISHARMFULTOPOPULATIONDIVERSITYANDHIGHERPROBABILITYOFCROSSOVERANDMUTATIONINCREASESSEARCHINGSTEP,WHICHCANCARRYOUTGREATERDOMAINSEARCHING,ANDAVOIDFALLINGINTOLOCALOPTIMUMWHILEATTHEVICINITYOFGLOBALOPTIMUM,LONGERLENGTHCHROMOSOMEANDLOWERPROBABILITYOFCROSSOVERANDMUTATIONWILLDECREASESEARCHINGSTEP,ANDLONGERLENGTHCHROMOSOMEALSOIMPROVESRESOLUTIONOFMUTATION,WHICHAVOIDWANDERINGNEARTHEGLOBALOPTIMUM,ANDSPEEDSUPALGORITHMCONVERGINGFINALLY,ITSHOULDBEPOINTEDOUTTHATCHROMOSOMELENGTHCHANGINGKEEPSINDIVIDUALFITNESSUNCHANGED,HENCEITDOESNOTAFFECTSELECTIONWITHROULETTEWHEELSELECTION13DESCRIPTIONOFTHEALGORITHMOWINGTOBASICGENETICALGORITHMNOTCONVERGINGONTHEGLOBALOPTIMUM,WHILETHEGENETICALGORITHMWHICHRESERVESTHEBESTINDIVIDUALATCURRENTGENERATIONCAN,OURAPPROACHADOPTSTHISPOLICYDURINGEVOLUTIONARYPROCESS,WETRACKCUMULATIVEAVERAGEOFINDIVIDUALAVERAGEFITNESSUPTOCURRENTGENERATIONITISWRITTENASXTTWHEREGISTHECURRENTEVOLUTIONARYGENERATION,ISINDIVIDUALAVERAGEFITNESSWHENTHECUMULATIVEAVERAGEFITNESSINCREASESTOKTIMESK1,KROFINITIALINDIVIDUALAVERAGEFITNESS,WECHANGECHROMOSOMELENGTHTOMTIMESMISAPOSITIVEINTEGEROFITSELF,ANDREDUCEPROBABILITYOFCROSSOVERANDMUTATION,WHICHCANIMPROVEINDIVIDUALRESOLUTIONANDREDUCESEARCHINGSTEP,ANDSPEEDUPALGORITHMCONVERGINGTHEPROCEDUREISASFOLLOWSSTEP1INITIALIZEPOPULATION,ANDCALCULATEINDIVIDUALAVERAGEFITNESS,ANDSETCHANGEPARAMETERFLAGFLAGEQUALTO1STEP2BASEDONRESERVINGTHEBESTINDIVIDUALOFCURRENTGENERATION,CARRYOUTSELECTION,REGENERATION,CROSSOVERANDMUTATION,ANDCALCULATECUMULATIVEAVERAGEOFINDIVIDUALAVERAGEFITNESSUPTOCURRENTGENERATIONSTEP3IFKANDFLAGEQUALS1,INCREASECHROMOSOMELENGTHTOMTIMESOFITSELF,ANDREDUCEPROBABILITYOFCROSSOVERANDMUTATION,ANDSETFLAGEQUALTO0OTHERWISECONTINUEEVOLVINGSTEP4IFENDCONDITIONISSATISFIED,STOPOTHERWISEGOTOSTEP22TESTANDANALYSISWEADOPTTHEFOLLOWINGTWOCRITICALFUNCTIONSTOTESTOURAPPROACH,ANDCOMPAREITWITHTHEGENETICALGORITHMWHICHONLYRESERVESTHEBESTINDIVIDUAL21ANALYSISOFCONVERGENCEDURINGFUNCTIONTESTING,WECARRYOUTTHEFOLLOWINGPOLICIESROULETTEWHEELSELECTION,ONEPOINTCROSSOVER,BITMUTATION,ANDTHESIZEOFPOPULATIONIS60,LISCHROMOSOMELENGTH,PCANDPMARETHEPROBABILITYOFCROSSOVERANDMUTATIONRESPECTIVELYANDWERANDOMLYSELECTFOURGENETICALGORITHMSRESERVINGBESTINDIVIDUALWITHVARIOUSFIXEDCHROMOSOMELENGTHANDPROBABILITYOFCROSSOVERANDMUTATIONTOCOMPAREWITHOURAPPROACHTAB1GIVESTHEAVERAGECONVERGINGGENERATIONIN100TESTSINOURAPPROACH,WEADOPTINITIALPARAMETERL010,PC003,PM001ANDK12,WHENCHANGINGPARAMETERCONDITIONISSATISFIED,WEADJUSTPARAMETERSTOL30,PC01,PM001FROMTAB1,WEKNOWTHATOURAPPROACHIMPROVESCONVERGENCESPEEDOFGENETICALGORITHMSIGNIFICANTLYANDITACCORDSWITHABOVEANALYSISTAB1RESULTOFFUNCTIONTESTINGFUNCTIONSOURALGORITHML10PC01,PM01L10PC01,PM01L30PC01,PM01L30PC01,PM01F1257152363579116264363F21982697342374450543322ANALYSISOFONLINEANDOFFLINEPERFORMANCEQUANTITATIVEEVALUATIONMETHODSOFGENETICALGORITHMAREPROPOSEDBYDEJONG,INCLUDINGONLINEANDOFFLINEPERFORMANCETHEFORMERTESTSDYNAMICPERFORMANCEANDTHELATTEREVALUATESCONVERGENCEPERFORMANCETOBETTERANALYZEONLINEANDOFFLINEPERFORMANCEOFTESTINGFUNCTION,WEMULTIPLYFITNESSOFEACHINDIVIDUALBY10,ANDWEGIVEACURVEOF4000AND1000GENERATIONSFORF1ANDF2,RESPECTIVELYAONLINEBONLINEFIG1ONLINEANDOFFLINEPERFORMANCEOFF1AONLINEBONLINEFIG2ONLINEANDOFFLINEPERFORMANCEOFF2FROMFIG1ANDFIG2,WEKNOWTHATONLINEPERFORMANCEOFOURAPPROACHISJUSTLITTLEWORSETHANTHATOFTHEFOURTHCASE,BUTITISMUCHBETTERTHANTHATOFTHESECOND,THIRDANDFIFTHCASE,WHOSEONLINEPERFORMANCESARENEARLYTHESAMEATTHESAMETIME,OFFLINEPERFORMANCEOFOURAPPROACHISBETTERTHANTHATOFOTHERFOURCASES3CONCLUSIONINTHISPAPER,BASEDONSOMEGENERALTHEOREMS,ANIMPROVEDGENETICALGORITHMUSINGVARIANTCHROMOSOMELENGTHANDPROBABILITYOFCROSSOVERANDMUTATIONISPROPOSEDTESTINGWITHSOMECRITICALFUNCTIONSSHOWSTHATITCANIMPROVECONVERGENCESPEEDOFGENETICALGORITHMSIGNIFICANTLY,ANDITSCOMPREHENSIVEPERFORMANCEISBETTERTHANTHATOFTHEGENETICALGORITHMWHICHONLYRESERVESTHEBESTINDIVIDUALAPPENDIXWITHTHESUPPOSEDCONDITIONSOFSECTION1,WEKNOWTHATTHEVALIDATIONOFTHEOREM1ANDTHEOREM2AREOBVIOUSTHEOREM3MATHEMATICALEXPECTATIONECXOFCHROMOSOMESEARCHINGSTEPWITHONEPOINTCROSSOVERISECXWHEREPCISTHEPROBABILITYOFCROSSOVERPROOFASSHOWNINFIGA1,WEASSUMETHATCROSSOVERHAPPENSONTHEKTHLOCUS,IEPARENTSLOCUSFROMKTOLDONOTCHANGE,ANDGENESONTHELOCUSFROM1TOKAREEXCHANGEDDURINGCROSSOVER,CHANGEPROBABILITYOFGENESONTHELOCUSFROM1TOKIS“1”TO“0”OR“0”TO“1”SO,AFTERCROSSOVER,MATHEMATICALEXPECTATIONOFCHROMOSOMESEARCHINGSTEPONLOCUSFROM1TOKISFURTHERMORE,PROBABILITYOFTAKINGPLACECROSSOVERONEACHLOCUSOFCHROMOSOMEISEQUAL,NAMELYPCTHEREFORE,AFTERCROSSOVER,MATHEMATICALEXPECTATIONOFCHROMOSOMESEARCHINGSTEPISSUBSTITUTINGEQA1INTOEQA2,WEOBTAINWHERELISLARGE,SOFIGA1ONEPOINTCROSSOVERTHEOREM4MATHEMATICALEXPECTATIONOFCHROMOSOMESEARCHINGSTEPWITHBITMUTATION,WHEREPMISTHEPROBABILITYOFMUTATIONPROOFMUTATIONPROBABILITYOFGENESONEACHLOCUSOFCHROMOSOMEISEQUAL,SAYPM,THEREFORE,MATHEMATICALEXPECTATIONOFMUTATIONSEARCHINGSTEPISREFERENCES1LIHAIMIN,WUCHENGKEGENETICALGORITHMWITHADAPTIVEMUTATIONPROBABILITYANDANALYSISOFITSPROPERTYJACTAELECTRONIASINICA,1999,27589922NARAKOICHIIMPROVEDGENETICALGORITHMFORLARGESCALEDISTRIBUTIONSYSTEMSLOSSMINIMUMPROBLEMAPROCEEDINGSOFTHEIEEECONFERENCEONEVOLUTIONARYCOMPUTATIONC19951201253LEIYIN,WEIHONGANIMPROVEDGENETICALGORITHMANDITSAPPLICATIONINEPLANEWAVEGUIDEFILTERDESIGNJACTAELECTRONIASINICA,2000,2861211244ENRIQUEALBA,JOSEMTROYAINFLUENCEOFTHEMIGRATIONPOLICYINPARALLELDISTRIBUTEDGASWITHSTRUCTUREDANDPANMICTICPOPULATIONSJAPPLIEDINTELLIGENCE,2000,121631815RUDOLPHRCONVERGENCEANALYSISOFCANONICALGENETICALGORITHMJIEEETRANSONNEURALNETWORKS,1994,5196101西安文理学院本科毕业设计(论文)中期检查表题目柔性制造系统中机床调度优化研究学生姓名王磊学号08102080225专业名称机械设计制造及其自动化指导教师边培莹、吕荣生检查时间201146班级08机械2班毕业设计(论文)进展情况通过对柔性制造系统中机床调度优化研究的相关资料的学习,以及对整个设计的了解,现基本完成以下设计工作1完成机床调度优化目标的总结与分析。基本了解实现机床调度优化的算法。2确定了总体设计方案,以及具体采用的调度优化算法。3开始对遗传算法进行深入学习,并学习C的相关知识。4初步确定了论文的提纲和核心下一步设计工作内容是通过采用遗传算法实现对机床的调度优化,并利用C软件仿真得出结果。以及毕业论文的撰写。指导教师意见自开题以来,通过查阅资料并积极与老师的沟通,该生比较清楚自己的设计内容和技术路线,能按计划、分步骤的展开设计任务,并能按时接受指导,有问题随时联系老师,保持了良好的指导关系。基本达到了上述设计进展。签字年月日教研室意见签字年月日西安文理学院机械电子工程系本科毕业设计(论文)题目柔性制造系统中机床调度优化研究专业班级08级机械(2)班学号08102080225学生姓名王磊指导教师边培莹吕荣生设计所在单位西安文理学院2012年5月西安文理学院本科毕业设计(论文)任务书题目柔性制造系统中机床调度优化研究学生姓名王磊学号08102080225专业班级08级机械2班指导教师边培莹、吕荣生职称助教、副教授教研室机械毕业设计(论文)任务与要求1在柔性生产方式下,机床设备的调度对生产效率的影响非常大,设计适合的调度算法对机床各种工作情况进行实时的调度,以优化提高生产任务的加工效率;2设计要求分析机床的各种主要工作情况及设备状态,对应的设计调度算法,要有评价方法对调度效果作出评价;3开题报告及中期检查各一份;4利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法;5撰写毕业论文,包括文献综述(另翻译英文资料一份)及主要仿真结果说明等;毕业设计(论文)工作进程起止时间工作内容201211020122282012312012320201232120124102012411201242020124212012511分析任务书,了解所选课题,选择相应期刊及论文资料,制定开题报告。研究学习各种调度优化算法工作原理、及仿真软件的编程语言(如VC语言),并提出该机床的调度方案。进行详细调度优化算法的设计并论证其合理性。进一步对确定的方案进行设计,并编制仿真程序。完成毕业设计论文的撰写、整理工作。开始日期2012110完成日期2012511教研室主任(签字)系主任(签字)西安文理学院本科毕业设计(论文)开题报告题目柔性制造系统中机床调度优化研究学生姓名王磊学号08102080225专业名称机械设计制造及其自动化指导教师边培莹、吕荣生开题时间2012228班级08机电(2)班一、选题目的和意义“柔性”是指生产组织形式和生产产品及工艺的多样性和可变性,可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产,可迅速适应产品变化,具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点。但是系统的这些优点能否发挥,取决于各生产设备调度后的运行效率情况,如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床,并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主,如“最小制造周期”、“机床利用率”、“工件流通时间”等,这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则,在时间和空间上可有效利用系统的有限资源,以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性,通过设计适合的调度算法对机床各种工作情况进行实时的调度研究,具有非常现实的意义,它的优化可提高生产任务的加工效率。二、本课题在国内外的研究状况及发展趋势柔性制造系统是70年代末、80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展,新产品的出现,产品市场寿命也随之缩短,相应的更新换代的速度加快,中小批量生产比例增加,以这种生产方式生产的产品占制造业总值的70,其中采用优化调度的方法可提高30的生产效率。尤其是近年来,国外一些工业技术比较发达的国家为进一步提高劳动生产率,降低生产成本,缩短产品的生产周期以增强产品更新换代和产品市场竞争力,所以柔性制造企业对调度优化的要求越来越高,由此带动的学术界对该问题的研究也越来越多。由于调度问题的复杂性,不同的研究者提出不同的算法和优化过程,最初是集中在整数规划,仿真和简单的规则上,随着各种新的交叉学科和优化技术的建立和发展,出现了很多智能调度优化的方法,如神经网络,模拟退火法,遗传算法,禁忌搜索法等,使调度问题的方向向多元化方向发展。在未来的发展中,如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性,确定简洁实用的算法将是重中之重。目前对物料运送车辆AGV的调度和对仓库的调度的研究非常多,而机床的调度相对薄弱,主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的,所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。三、主要研究内容1确定方案了解柔性制造系统的工作原理及主要功能,提出该系统下机床优化调度设计方案;2算法分析根据系统功能,选择合适的算法,实现机床的优化调度。3系统设计用仿真软件实现对具体的算法仿真验证。4完成毕业论文的撰写。指导教师意见及建议王磊同学能较认真的查阅本毕业设计课题相关的参考资料与相关文献,对所设计的机床调度问题发展现状清楚、调度方案思路清晰,也积极展开了相关软件的学习。同意开题签字年月日教研室审核意见签字年月日注此表前三项由学生填写后,交指导教师签署意见,经教研室审批后,才能开题。西安文理学院机械电子工程系本科毕业设计(论文)题目柔性制造系统中机床调度优化研究专业班级08级机械(2)班学号08102080225学生姓名王磊指导教师边培莹吕荣生设计所在单位西安文理学院2012年5月2目录第一章绪论111引言112课题提出的目的和意义113课题相关研究领域的发展状况及趋势114本课题主要研究内容和设计任务2第二章调度与遗传算法相关理论421调度的定义4211机床调度的定义4212机床主要调度问题422调度问题的描述和分类423调度的优化算法524遗传算法基本理论725遗传算法基本概念826遗传算法主要步骤927适应度函数928遗传操作算子10281选择算子10282交叉算子11283变异算子1229遗传算法参数的选择13210遗传算法的应用与发展趋势13第三章基于遗传算法进行机床调度1531静态车间调度1532问题的描述1533基本遗传算法的构造15331编码15332解码161基于机器编码的机器工件队列之间的冲突消解162最后解码计算最大调度时间1734初始种群的产生1735选择操作1736交叉操作1837变异操作1838动态车间调度1839动态调度类型19310动态调度控制方法203101急件到来203102机器故障223103订单取消24311应用实例26第四章C语言相关知识及编程31341C语言相关知识3142C语言程序的特点3143C语言程序的开发步骤3244C语言编程3245输出结果37第五章全文总结与展望3951全文总结3952展望39结束语40致谢41参考文献42柔性制造系统中机床调度优化研究摘要随着市场的多变以及市场对产品个性化的需求,多品种、小批量生产方式已经逐渐成为制造业的发展主流。研究批量调度的优化方法,对于先进制造业的现代化具有重要的理论价值和实际意义。本文介绍了机床调度的概念及其发展过程、研究现状和发展趋势;对车间调度的各种研究方法进行了简要的介绍和比较;概述了遗传算法的基本原理和步骤,介绍了遗传算法常用的一些算子,分析了遗传算法的特点,并对遗传算法的一些理论进行了讨论。对三种常见的动态事件(急件到来、设备故障、订单取消)的重调度控制方法进行了研究,并在静态调度问题研究的基础上,运用自适应遗传算法对动态调度问题进行了研究,获得了动态调度的控制策略和重调度方法。此控制策略和重调度方法可以较好地解决由于动态事件的出现而导致的静态调度方案不再适用的问题,从而保证了FMS系统在有扰动时也能持续地运行。关键词遗传算法,动态调度,柔性制造系统2FLEXIBLEMANUFACTURINGSYSTEMINMACHINETOOLRESEARCHONSCHEDULINGOPTIMIZATIONABSTRACTWITHMUCHCHANGEOFTHEMARKETANDTHEDIVERSIFICATIONOFCUSTOMERNEED,VARIETYANDSMALLBATCHPRODUCTIONMODEHASBECOMETHEMAINWAYOFMANUFACTURINGGRADUALLYTHESTUDYOFOPTIMIZATIONMETHODFORBATCHSCHEDULINGISVERYIMPORTANTTOMODERNIZATIONOFADVANCEDMANUFACTURINGBECAUSEOFITSTHEORETICALANDPRACTICALINRESEARCHESINCURRENTANDINTHEFUTUREOFJOBSHOPSCHEDULINGAREINTRODUCED,SOMERESEARCHMETHODSAREINTRODUCEDANDCOMPAREDBASICFOUNDATION,PROCESSANDOPERATIONSOFGAARESTATEDBRIEFLY,ANDTHECHARACTERISTICSANDERTHEORETICAREDISCUSSEDTHERESCHEDULINGCONTROLMETHODOFTHREEDYNAMICEVENTS(THEARRIVALOFNEWPARTS,MECHANICALFAILURES,CANCELEDORDERSARESTUDIED,ANDBASEDONTHESTATICSCHEDULINGPROBLEM,THEADAPTIVEGENETICALGORITHMISUSEDFORTHESTUDYOFDYNAMICSCHEDULINGINTHISPART,DYNAMICSCHEDULINGANDCONTROLSTRATEGYAREPUTFORWARDAPPLICATIONOFTHECONTROLSTRATEGIESANDRESCHEDULINGMETHODSCANSOLVETHEPROBLEMTHATTHEAPPEAROFDYNAMICEVENTSLEDTOSTATICSCHEDULINGPROGRAMISNOTAPPLY,SOENSURINGTHEFMSSYSTEMCANCONTINUETOOPTIMIZETHEOPERATIONINTHECASEOFADISTURBANCEHAPPENINGKEYWORDSGENETICALGORITHMS,WORKSHOPSCHEDULING,FMSSCHEDULING,DYNAMICSCHEDULING31第一章绪论11引言近一世纪以来,企业所处的环境经历了巨大的变化。20世纪初期,现代企业处于刚刚起步的阶段,生产规模尚未达到一定的程度,产品处于供不应求阶段,企业只要保障生产能力和基本产品质量即可。但从70年代开始,企业所面临的环境发生了极大的变化,主要体现在1市场需求的改变20世纪50年代以后,全球制造业生产能力不断扩大,生产规模和效率迅速提高。进入70年代,世界主要市场开始进入需求导向的时代。消费观念也出现了结构性变化,消费需求趋向多样化和个性化。20世纪90年代,产品的销售半径不断增大,制造商必须面对处于不同地域、不同文化和不同环境下的全球用户。进入21世纪,全球市场需求的多样化趋势更加明显,制造业面临全球性多样化、个性化需求的挑战。2技术的不断创新科学技术日新月异,以信息技术、自动化技术、现代管理与制造技术相结合的先进制造技术应运而生。3全球化的竞争随着科技的发展和全球贸易的提出,生产和销售已经变得的没有国界。这种情况,加剧了企业之间的竞争,对产品的生产提出了更高的要求。12课题提出的目的和意义“柔性”是指生产组织形式和生产产品及工艺的多样性和可变性,可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产,可迅速适应产品变化,具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点1、2。但是系统的这些优点能否发挥,取决于各生产设备调度后的运行效率情况,如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床,并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主,如“最小制造周期”、“机床利用率”、“工件流通时间”等,这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则,在时间和空间上可有效利用系统的有限资源,以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性,通过设计适合的调度算法对机床各种工作情况进行实时的调度研究,具有非常现实的意义,它的优化可提高生产任务的加工效率。本文主要针对机加工车间加工机床的调度问题进行研究,并运用经典调度算法进行优化,寻求最佳加工路径。13课题相关研究领域的发展状况及趋势20世纪50年代调度问题受到了应用数学、运筹学、工程技术等多个领域学者的关注,并运用运筹学中的线性规划、动态规划及决策分析等方法,研究和解决了一系列具有代表意义的调度和优化问题。柔性制造系统是70年代末、80年代初出现的一种具有高度柔性的自动化制2造系统。随着科学技术的发展,新产品的出现,产品市场寿命也随之缩短,相应的更新换代的速度加快,中小批量生产比例增加,以这种生产方式生产的产品占制造业总值的70,其中采用优化调度的方法可提高30的生产效率3、4、5。尤其是近年来,国外一些工业技术比较发达的国家为进一步提高劳动生产率,降低生产成本,缩短产品的生产周期以增强产品更新换代和产品市场竞争力,所以柔性制造企业对调度优化的要求越来越高,由此带动的学术界对该问题的研究也越来越多。由于调度问题的复杂性,不同的研究者提出不同的算法和优化过程,最初是集中在整数规划,仿真和简单的规则上,随着各种新的交叉学科和优化技术的建立和发展,出现了很多智能调度优化的方法,如神经网络,模拟退火法,遗传算法,禁忌搜索法等,使调度问题的方向向多元化方向发展6。在未来的发展中,如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性,确定简洁实用的算法将是重中之重。目前对物料运送车辆AGV的调度和对仓库的调度的研究非常多,而机床的调度相对薄弱,主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的,所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。为解决存在的问题,对调度问题的研究主要有以下几种发展趋势(1)调度算法和调度系统的深入研究和开发目前对调度算法和调度系统的研究己取得很大进展,但由于调度问题的性质而不可能在短期内取得突破性进展,这就要求人们进一步拓宽研究范围和思路,在原来调度算法的基础上继续寻找可行的能够获得最优解而且求解速度快的调度算法。基于人工智能、计算智能和实时智能的调度算法将会是未来调度算法的主流7。(2)调度专家的作用问题研究调度专家具有丰富的经验,纯粹的自动调度是不现实且很难实现的。因此,具有最终决策职责的调度专家的重要作用在任何时候都不能忽略。所以研究调度专家的作用以及如何与调度系统的协调等问题也是一个重要的研究方向。(3)多种调度方法的结合研究目前许多新的算法应用于调度领域,但由于需要特定的应用环境,所以就出现了调度理论和实践的不一致性8、9。因此,集成各种调度算法求解生产调度问题充分发挥各种调度算法自身的优势,是今后研究和解决实际调度问题的重要方向之一10、11。总之,车间调度领域的研究,随着科学的进一步发展,必然朝着集成化、柔性化,多标准化、动态实用化高层次优化方向发展。14本课题主要研究内容和设计任务本课题主要是运用生产调度相关知识来解决机加工车间的机床调度优化问题。本课题的设计任务是分析机床的各种主要工作情况及设备状态,对应的设计调度算法,要有评价方法对调度效果作出评价;利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法。本文的主要内容是主要针对机床调度问题的调度方法进行研究,并运用遗传算法对调度问题进行优化,寻求最佳调度方案。本文共分五章第一章首先提出通过引言提出课题研究的目的和意义;然后进一步介绍了FMS中机床调度问题的研究现状,研究方法,存在的问题及发展趋势;最后给出课题的主要工作及内容。3第二章首先阐述了调度的相关理论;然后对调度问题进行分类和总结其特点,说明在实际调度问题中需要调度的方面;其次对调度算法进行归类,并分别描述各算法的基本思想和特点。根据调度问题选择遗传算法,并对遗传算法的基本理论和操作步骤进行描述。为下文的实例做理论铺垫。第三章依据上述的调度和遗传算法基本理论,分静态和动态分别应用遗传算法进行调度,并给出实例。第四章给出基于遗传算法进行调度的实例,并根据所给的实例进行编程,验证算法的可行性和调度后起到的优化作用。第五章结论与展望4第二章调度与遗传算法相关理论21调度的定义211机床调度的定义机床调度可以描述为若干个任务在一些机器上进行加工,如何按时间对机器和工序等进行安排,使某些目标函数,例如产品制造时间或者成本等达到最优。在一定的约束条件下,调度的目标是将生产合理地安排到各机床,并合理安排作业的加工次序和加工开始时间,同时优化一些性能指标12。机床调度目标是在满足系统约束条件下,依据反映了客户需求和市场需求的生产计划合理安排各加工任务的实施时间及使用的设备,为生产线上的各台设备和各个工件形成可行的加工安排,并尽可能优化系统的性能指标,最佳地安排与组织生产,为企业带来显著的经济效益。212机床主要调度问题机床调度问题一般可以描述为N个工件在M台机器上加工,一个工件K道工序,每道工序可以在若干台机器上加工。每台机器在每个时刻只能加工某个工件的某道工序,而且只能在上道工序加工完成后才能开始下一道工序的加工12。机床调度问题是根据加工对象的加工需求,运用不同的调度决策规则和优化算法,规划系统的加工事件,并根据系统动态仿真运行的结果或者优化结果形成最佳的生产加工顺序,同时实现设备集和任务集的合理最优化结合。调度的特点是多个工件在有限的机器上加工,每台机器在切换不同的工件生产时需要一定的准备时间。调度的决策内容包括分配决策工件的加工顺序和时间决策工件各工序的加工时间以及路径决策工件各工序的加工设备的分配。22调度问题的描述和分类生产调度问题是一类典型的实际调度问题,它很早就受到了生产管理者们的关注,但那时还没有进入到理论研究的阶段,只是一些简单的思想,也没有被广泛的应用到实际中。那时人们主要关注的问题是如何分配工作以及哪些操作者能够胜任这样的工作。起初人们主要从应用数学的角度来研究调度问题,调度问题通常被定义为“对一种资源进行分配来执行一种任务”,也就是对零件进行“排序(SEQUENCING)”的问题。如GANTT提出了使用可视化的图标来表示生产的进度状况,CO阐述了一种机械的调度技术。而在后来的生产中,针对先进制造系统,调度问题被更为具体地定义为“生产调度是针对一项可分解的生产任务,探讨在尽可能满足约束条件的前提下,通过下达生产指令,安排其组成部分使用哪些资源、其加工时间以及加工顺序,以获得生产任务执行时间或成本的最优化6。所以车间调度就是在一定条件下,对一个可用的加工设备集,5在时间上进行加工任务分配,以满足某个给定的性能指标。1根据加工任务,可将调度分为静态调度和动态调度。静态调度是指所有待安排加工的工件均处于待加工状态,因而进行一次调度后,各作业的加工被确定,在以后的加工过程中就不再改变;动态调度是指作业依次进入待加工状态,各种作业不断进入系统接受加工,同时完成加工的作业又不断离开,还要考虑作业环境中不断出现的不可预测的动态扰动,如作业加工超时、设备损坏等。实际生产调度问题往往是由JOBSHOP和FLOWSHOP等基本调度类型组合而成,而其体现的特征是随机性的、动态的13。2根据零件和车间构成不同进行分类有(A)单机车间调度问题加工系统中只有一台机床,所有零件都在该机床上进行加工,待加工的零件有且只有一道工序。一般来说,此问题是最简单的调度问题。(B)并行机车间调度问题加工系统中所有的加工机床是完全相同的,工件可以在任意一台机床上进行加工,并且每个工件只有一道工序。(C)开放车间调度问题工件的加工没有特定的路线约束,每个工序之间没有先后关系的约束。每个零件工序之间的加工顺序是任意的。零件的加工可以从任何一道工序开始,在任何一道工序结束。(D)流水车间调度问题加工系统中有一组功能不同的机床,待加工的零件包含多道工序,每道工序在一台机床上加工,所有零件的加工路线都是相同的。每个工件的工序之间有先后顺序约束关系。(E)作业车间调度问题加工系统中有一组功能不同的机床,待加工的零件包含多道工序,每道工序在一台机床上加工,零件的加工路线互不相同。每个工件工序之间有先后顺序约束,不同工件3根据性能指标可以分为基于调度费用和调度性能的指标。4根据生产环境的特点将调度问题分为确定性调度、随机性调度。5根据作业的加工特点分为静态调度、动态调度。静态调度是指所有的加工的作业都处于待加工状态,因此进行一次调度后所有作业的各个加工都被确定下来,而且在以后的加工过程中不再改变;动态调度是指作业依次进入系统进行加工。完成加工的作业一次离开,同时还要考虑实际加工环境中不断出现的动态扰动,如作业的加工超时、机床损坏等。因此动态调度要根据系统中作业、机床等状况不断地进行重调度。本文在机加工车间环境下,在考虑机床一种资源的情况下,主要针对单件、小批量生产车间如何安排零件在机床上的加工顺序的调度问题进行研究,同时考虑实际生产中的约束条件和优化目标的限制,使得系统能够高效、优化地运行,以确保生产的最大利润。23调度的优化算法调度问题的研究方法,最初是集中在整数规划、仿真和简单的规则上,这些方法一般都存在一定的局限性,不是调度结果不理想就是难以解决复杂问题。随着各种新的相关学科与优化技术的建立与发展,在调度领域出现了许多新的优化方法,比如神经网络、模拟退火算法、遗传算法、禁忌搜索法等,使得调6度问题的研究方法向多元化方向发展。总结起来,现有调度问题的研究方法大体上可以分为以下几种类别(1)数学规划方法即运筹学(OR)方法,将生产调度问题简化为数学规划模型,采用基于枚举思想的分枝定界法解决调度最优化或近似优化问题,属于精确方法。这类方法虽然从理论上能求得最优解,但由于其计算复杂的原因而难以真正实用。对于复杂调度问题,这种纯数学方法由于存在模型提取困难、运算量大、算法难以实现的弱点,仅适合较小规模的调度问题15。(2)基于启发式规则的调度方法从实用角度来看,启发式算法因其易于实现、计算复杂度低等原因,在实际中得到了比较广泛的应用,并且不断涌现出许多新的调度规则,可将其分为三类简单规则、复杂规则、启发式规则。虽然启发式规则常被用于实际当中,但它们一般不具有全局优化的特点16。(3)基于人工智能AI的方法AI方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。单一的数学方法和工具不足以解决实际的调度问题,AI和专家系统(ES)的出现对解决调度的实时性和智能性提供了新的辅助手段17。(4)基于仿真的方法由于制造系统的复杂性,以致于很难用精确的解析模型对其进行描述分析。但仿真却能提供理想模型,且可以定量地进行评估,从而对实际系统采用合适的调度方法18。仿真方法用于调度的优点有实验时间短,不受时空限制;可以测试不同调度决策的性能,从而选择较优的调度决策;能够用分析方法解决问题并寻求可行解。其不足之处是由于仿真具有实验的特点,很难从特定的实验中提炼出一般的规律性;生产调度成本高;仿真结果的价值和可信度严重依赖仿真模型、仿真方法及仿真实验输入数据;仿真的准确性受程序员判断能力和技能的限制。(5)计算智能方法近年来,一些高级局域搜索法由于具有普遍适用性和较低的经验复杂性等优点,得到了广泛的重视和应用。主要有以下几种方法遗传算法GAGOLDBERG首次将GA应用到实际工程系统的优化当中。由于GA原理和操作简单,通用性强,不受限制条件的约束,且具有隐含并行性和全局空间搜索能力,尤其适用于处理传统搜索方法难以解决的复杂的非线性问题。在机器学习、模式识别、控制工程等领域,尤其在生产调度领域都得到了广泛地应用。然而遗传算法对于大规模的组合优化问题,搜索空间大,搜索时间较长,往往会出现早收敛的现象;对初始种群很敏感,初始种群选择不好会影响解的质量和算法效率。目前,人们主要从两方面入手一是对遗传算法本身进行改进;一是与其他算法结合,取长补短。神经网络NN优化法用于车间调度,主要有三类方式利用其并行计算能力,求解优化调度,以克服调度的NP难题。利用其学习能力,从优化轨迹中提取调度知识。用NN来描述调度约束或调度策略,以实现对生产过程的可行或次优调度。(6)组合调度方法由于各种调度算法都不同程度地存在不足之处,所以学者们开始关注各种近似算法的组合研究,以弥补各自的缺点,发挥各自的优势,达到高度优化的目标。目前,各种算法的组合应用己成为解决优化调度问题很有前途的方法。7基于DEDS的解析模型方法对于车间类型的DEDS,同样可用其解析模型与方法来解决车间调度问题。如7QN、极大代数法、动态规划法。但它们都只是适合于制造系统的性能分析。PETRI网除具有并基于混合遗传算法的车间调度方法研究与应用发、动态、直观等优点外,还有能够准确快速地反映制造系统适时调度的离散性与随机性等特点,所以它与其它方法相结合在调度问题中得到了广泛的应用。目前,PETRI网用于制造系统调度存在以下问题节点语义的单义性,使得所携带的系统信息不够丰富。重用性差。当调度规则或方法复杂时,建模困难。8禁忌搜索TSTS是解决复杂组合优化问题的一种搜索策略和方法,由GLOVER等人提出、完善和发展1羽。目前,TS已在调度、交通运输、TSP问题、电子电路设计等诸多领域中得到应用。9模拟退火SASA可求得组合优化问题的最优或次最优解,首次将SA用于优化领域的是KIRKPATRICK,他尝试了将SA用于TSP问题的求解,此外,SA在JOBSHOP和FLOWSHOP问题中也得到了一定的应用。10拉氏松弛法拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的次优解,并能对解的次优性进行定量的评估,近年来已经成为解决复杂车问调度问题的一种重要方法,但不可避免的是,拉氏松弛法对其对偶问题存在搜索效率低、可行调度的构造有待进一步研究等问题。11基于模糊数学理论的方法客观现象具有确定性与不确定性两个基本方面,经典数学表达的是现象的确定性,不确定性一方面表现为随机性,另一方面表现为模糊性。正是利用此特点,许多学者把它引入调度领域11引,但与专家系统相似,这种方法同样存在开发周期长。需要丰富的调根据以上优化方法的分析比较,采用遗传算法进行调度,计算复杂度低,调度全面,并在实际中得到了比较广泛的应用。所以最终确定采用遗传进行优化,获得最终的调度方案,使得加工路径能够完成优化。24遗传算法基本理论遗传算法(GENETICALGORITHM,GA)相对于古典的启发式算法具有更好的性能1,它可以适应不同的问题形式,对搜索问题的限制少,减少了要解决的问题的复杂性。遗传算法可以同时搜索解空间内的许多点,有效地防止了搜索过程中收敛到局部最优解的情况。并且因其在搜索的过程中有目标性和方向性,相对于其它搜索方法,在计算时间上更有优势【19、20】。遗传算法(GENETICALGORITHM,GA)是一种模拟生物自然进化现象的优化算法,其核心思想是借用遗传学中的思想以及达尔文进化论的“物竞天择,适者生存”,最早由美国密歇根大学(UNIVERSITYOFMICHIGAN)的JOHNHOLLAND教授于1975年提出的,1989年GOLDBERG67在其著作中对遗传算法进行了更为全面和系统的总结,并由此奠定了遗传算法的基础。遗传算法将问题的解表示为“染色体”,通过模拟自然界中物种的选择、复制、交叉和变异等操作,以实现个体适应度的提高,并通过不断的迭代和对个体的评价选择,逐步寻找最优解(或次优解)【21、22】。MICHALEWICZ对遗传算法的五个基本要素做了总结,这五个基本要素包括编码解码,种群初始化,构造适应度函数,构造遗传算子8(包括选择、复制、交叉、变异等)和遗传参数设置(包括种群的规模、遗传算子的概率等)。下面给出一般遗传算法基本求解的步骤,其流程框图如图21所示。步骤1随机产生一个初始种群,并令其规模为P。步骤2对种群中的每个个体评价其适应度值。步骤3如果满足算法终止条件,则输出结果;如果不满足,则继续下一步骤。步骤4按照一定的策略和规则进行交叉、变异和选择等操作。步骤5产生下一代种群并返回到步骤2。对问题进行编码产生初始种群PT计算种群个体适应度进行遗传操作选择、交叉、变异产生种群PT1最佳个体是否满足优化准则初始种群PT种群PT1开始NY图21遗传算法流程图遗传算法具有(1)不受限制性条件的约束,设计简单且适应性广;(2)隐含并行搜索能力,能够在复杂空间进行全局优化搜索;(3)较高的搜索效率;(4)较强的鲁棒性,易得到全局最优解的同时减小陷入局部极小的可能性;(5)编码技术和遗传操作比较简单,优化算法通用性强等特点。相对于其他传统算法,遗传算法更能适用于不确定条件下的柔性作业车间调度问题的求解【24】。925遗传算法基本概念由于遗传算法是因进化论和遗传学机理而产生的直接搜索优化方法,故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下1串它是个体的形式,在算法中称为字符串,并且对应于遗传学中的染色体。2群体个体的集合称为群体,串是群体中的元素。3群体大小在群体中个体的数量称为群体的大小。4基因基因是串中的元素,基因用于表示个体的特征。例如有一个串S1001,则其中的1、0、0、1这4个元素分别称为基因。它们的值称为等位基因。5基因位置一个基因在串中的位置称为基因位置,有时也简称基因位。基因位置由串的左侧向右侧计算,例如在串S1101中,O的基因位置是3。基因位置对应于遗传学中的地点。6基因特征值在用串表示整数时,基因的特征值与二进制数的权一致。例如在,S1011中,基因位置3中的1,它的基因特征值为2,基因位置1中的L,它的基因特征值为8。7串的结构空间在串中,基因任意组合构成了串的集合。基因操作是在串结构空间中进行的。串结构空间对应于遗传学中的基因型的集合。8参数空间SR这是串空间在物理系统中的映射,它对应于遗传学中的表现型的集合。9适应度表示某一个体对于环境的适应程度。26遗传算法主要步骤遗传算法的主要步骤如下所示1编码遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合便构成了不同的点。编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。2初始群体的生成随机生成一定数目的初始群体,以此群体为基础,开始迭代运算。3确定适应度函数适应度函数基本上依据优化问题的目标函数而定,其作用是表明个体的优劣性。4选择当适应度函数确定以后,计算群体中各个个体的适应度。自然选择规律是以适应度函数值的大小决定的概率分布来确定哪些染色体适应生存,哪些被淘汰,生存下来的染色体组成种群,形成一个可以繁殖下一代的群体。5交叉交叉操作是遗传算法种最主要的遗传操作。父代的遗传基因结合是通10过父代染色体之间的交叉并到达下一代个体的。子代的产生是一个生殖过程,它产生了一个新解。6变异新解产生过程中可能发生基因变异,变异使某些解的编码发生变化,使解有更大的遍历性,变异运算后得到下一代群体。7终止条件判断在所有新一代群体中,是否存在满足条件的最优个体。如果存在,则停止迭代运算,输出最优解,否则继续迭代运算。27适应度函数遗传算法遵循自然界优胜劣汰的原则,在进行搜索中基本上不用外部信息,而用适应度表示个体的优劣,作为遗传算法操作的依据。个体的适应度高,被选择的概率就高,反之,被选择的概率就低。适应度函数是用来区分群体中个体好坏的标准,是算法演化过程的驱动力,是进行自然选择的唯一依据。改变群体内部结构的操作都是通过适应值加以控制。在具体应用中,适应度函数的设计要结合求解问题本身的要求而定【25】。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数的唯一要求是,针对输入可计算出能加以比较的非负结果。这一特点使得遗传算法的应用范围很广。1目标函数映射成适应度函数对于求解效能函数和利润函数UX的最大值问题,一种最自然的想法就是将目标函数作为适应度函数。但是许多优化问题是求取费用函数占GX的最小值,而遗传算法的要求适应度函数取正值,而且适应度越大,个体越好。因此,在不少场合采用问题的目标函数作为个体的适应性度量时,必须将目标函数转化为求最大值形式,而且保证适应度函数非负。一般可采用以下的方法进行转换MAX0GCXF显然,存在多种方式选择系数MAX。A可以是一个合适的输入值,也可采用迄今为止进化过程中GX的最大值或当前群体中GX的最大值。当然MAXC最好与群体无关。还有一种较常用的方法是将适应度函数取为目标函数的倒数。即1XGF28遗传操作算子选择、交叉和变异算子是遗传算法“优胜劣汰”思想的主要体现,也是构成算法具备很强的全局搜索能力的核心,利用遗传操作算子能够产生新一代种群,实现种群向更优方向进化。11281选择算子选择算子又称繁殖或者再生,是对群体中的个体按照优胜劣汰的方式选取,并遗传到下一代的操作,它是建立在群体中个体的适应度评价基础上,并选择适应值高的个体进行复制。通过选择机制可以避免优秀基因的流失,能够提高全局收敛性和算法的效率【26】。比例选择法比例选择法是基本的选择方法,也叫轮盘赌选择法。它的基本思想是个体被选中的概率与其适应度大小成正比。设群体大小为M,个体I的适应度为FI,选择概率PI为31FIPI1,2,IMI1式中PI体现了个体I在整个群体的个体适应度总和中所占的比例,个体适应度值越大,其被选中的概率就越大。但是,采用比例选择法会因为随机数的产生而有可能使适应度高的个体没有被选中的,而适应度低的个体反而被选中。期望值法期望值方法的基本思想是根据每个个体在下一代群体中的生存期望概率值来进行随机选择运算。个体在下一代群体中生存的期望数目NI为(32)FMFIINI1,2,MIAVGII1最佳个体保存法此方法的思想是把群体中最优的个体挑选出来,直接复制到下一代种群中去,故这种方法又称为精英保护法。最优保存策略成功地改善了遗传算法的局部收敛特性,能够防止优秀个体由于复制、交叉和变异中偶然因素而被破坏,也是一种增强算法稳定性和收敛性的有效方法【27】。但是,应用最优保存法时,应避免使进化计算陷入局部极值,以至于丧失了全局寻优的机会。以上几种选择方法均以适应度为基础进行选择,这就可能在进化过程中导致遗传算法的早期收敛的问题,可采用适应度函数尺度变换的方法来解决,此外还可采用部分个体的替换选择法、自适应变异概率选择法等选择方法来提高遗传算法性能。比例选择法是最基础的选择方法,且易于实现,但是因为这种方法有可能使适应度高的个体没有被选中,而适应度低的个体反而被选中。所以本文将采用比例选择法与最佳个体保存法相结合的选择方法,既避免了最优个体被漏选又能保证算法在全局中寻优。282交叉算子遗传算法中的所谓交叉操作,是指对两个相互配对的个体按某种方式相互交换其部分基因,从而形成两个新的个体。交叉运算是遗传算法区别于其它进化计算的重要特征,它在遗传算法中起着关键的作用,是产生新个体的主要方法。目前有如下几种基本交叉方法【28】。1单点交叉12在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进行互换,并生成两个新的个体。例如图22所示。父体A11OL111011011O01子体A父体B101110011011LL10子体B图22单点交叉2两点交叉两点交叉的操作与单点交叉类似,只是设置了两个交叉点依然是随机设定。两个交叉点之间的码串相互交换,如图23所示。父体A10L11L110010LL子体A父体B000L00000L1100子体B图23两点交叉3多点交叉将单点交叉与二点交叉的概念加以推广,可得到多点交叉的概念。多点交叉是指在个体编码串中随机设置多个交叉点,然后进行基因交换。多点交叉又称广义交叉,其操作过程与二点交叉相类似。一般来讲,多点交叉较少使用,因为不能有效地保存重要的模式,影响了遗传算法性能。283变异算子遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换,从而形成一个新的个体。从遗传运算过程中产生新个体的能力方面来说,交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力,而变异运算只是产生新个体辅助方法,但它也是必不可少的一个步骤,因为它决定了遗传算法的局部搜索能力【29】。交叉算子与变异算子的相互配合,共同完成对搜索空间的全局搜索和局部搜索,从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。在遗传算法中使用变异算子的目的有两个一是改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找一些较好的个体,它们己接近或有助于接近问题最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时若再使用变异算子来调整个体编码串中的部分基因值,就可以从局部的角度出发使个体更加逼近最优解,从而提高了遗传算法的局部搜索能力。二是使遗传算法可维持群体的多样性,以防止出现未成熟收敛现象。下面介绍在二进制编码常用的几个变异算子1基本变异算子基本变异算子是指对群体中的个体码串随机挑选一个或多个基因并对这些基因座的基因值作变动依变异概率作变动,0,1二值码串中基本变异操作如图24所示。13变异前11010011001011变异后图24基本变异算子2逆转变异算子在个体码串中随机挑选二个逆转点,然后将两个逆转点间的基因值逆向排列,逆转操作如图25所示。变异前11010011100101变异后图25基本变异算子3自适应变异算子该算子与基本变异算子的操作内容类似,唯一不同的是变异概率不是固定不变而是随群体中个体的多样性程度而自适应调整。一般是根据交叉所得两个新个体的海明距离进行变化。海明距离越小,变异概率越大,反之变异概率越小。29遗传算法参数的选择遗传算法参数主要包括染色体位串长度、群体规模N、交叉概率PC和变异概率PM。由于这组参数的选择对遗传算法的性能有很大影响,所以在初始阶段或进化过程中需要合理地选择和控制,使算法以最佳的轨迹接近最优解【30】。许多学者经过大量地实验研究,给出了最优参数选择的建议(1)染色体位串长度L取决于特定问题解的精度。要求精度越高,位串就越长,但需要很长的计算时间。为了提高效率,变长度位串或者在当前所达到的较小可行域内重新编码,是一种可行的方法,并显示了其良好的性能。但在实际中,要根据具体问题选择具有针对性的位串长度。如本文中将采用基于工序的实数编码,染色体的每个基因位代表一道工序,染色体长度表示所有待加工工序数的总和。(2)群体规模POPSIZE大群体含有较多的模式,为遗传算法提供了足够的模式采样容量,可以改进GA搜索质量,防止早熟现象的产生。但大的群体增加了个体适应度评价的计算量,从而使收敛速度降低。一般情况下专家建议POPSIZE20200。本文实例是针对较小批量和较大批量的零件加工,故取群体规模POPSIZE20100。(3)交叉概率PC交叉概率控制着交叉算子的应用频率。交叉概率越高,群体中新结构的引入就愈快,优良基因结构的破坏速度也响应上升;交叉概率越低,则可能导致搜索停滞不前。一般取PC061。自适应遗传算法能够在进化中根据个体优劣和群体分散度对控制参数进行自动调节,可较好地解决标准遗传算法在应用中遇到的收敛性差和早熟问题,所以本文将采用自适应交叉、变异概率作为参数的选择方法,即当群体中新个体产生的速度较小时就增大PC和PM,以产生多个新的模式结构;否则就取较小的PC和PM,以保证优良的个体不被破坏。(4)变异概率PM变异操作是保持群体多样性的有效手段。在交叉操作后产生的新群体中全部个体位串上的每位等位基因按变异概率PM随机改变,PM太小可能使某些基因位过早丢失的信息无法恢复,过高则遗传搜索将变成随机搜索,一般取PM0005001。14实际上,遗传参数的选择很大程度上与问题的类型有着直接的关系,问题的目标函数越复杂,参数选择就越困难。从理论上说,不存在一组适应于所有问题的最佳参数值,随着问题特征的变化,有效参数的差异往往就非常显著。所以如何设定控制参数以使遗传算法的性能得到改善,还需要结合实际问题深入研究,以及依赖遗传算法理论研究的新进展。210遗传算法的应用与发展趋势遗传算法提供了一种求解复杂系统优化问题的框架,它不依赖于问题的具体领域,且具有很强的鲁棒性,在许多工程领域都有成功的应用【31】。遗传算法的主要应用领域有组合优化计划调度问题、TSP问题、图的划分问题、运输问题函数优化多峰函数优化、多目标函数优化、不稳定函数的优化控制模糊控制器的设计、机器人控制、过程控制、系统辨识规划01整数规划、生产规划、并行任务处理图象处理模式识别、特征提取、分类设计结构、布局设计,参数选择优化目前,遗传算法的发展趋势主要有以下几个方面(1)算法的数学基础包括算法的收敛性,收敛速度估计,早熟机理的探索与预防,交叉算子的几何意义与统计解释,参数设置对算法的影响等方面。(2)算法与其他优化技术的组合充分利用遗传算法的大空间群体搜索性能与快速收敛的局部优化方法混合产生有效的全局优化方法,从而从根本上提高遗传算法的计算性能。(3)遗传算法的改进根据具体应用领域对遗传算法进行改进和完善。(4)算法的并行化研究遗传算法的群体、适应度评价、随机搜索等特征使其具有明显的并行性。因此,设计各种并行进化策略,建立相应的并行化算法的数学基础,有着非常重要的意义。15第三章基于遗传算法进行机床调度31静态车间调度静态车间调度是指所有待安排加工的工件均处于待加工状态,因而进行一次调度后,各作业的加工被确定,在以后的加工过程中就不再改变。故静态车间调度不考虑零件在加工过程中出现的意外情况,如机床突然损坏、零件的交货期提前,有更紧迫的零件要求被加工等等【32】。由以下实例说明。32问题的描述研究N个工件在M台机床的加工,已知各个工件的各个工序的加工时间和在各机床上的加工次序约束,调度开始时间为0,并且开始时刻各机器上没有任何的任务安排,调度的目标是确定与工艺约束条件相容的各机器上所有工件加工开始时间和加工结束时间,使得完成全部加工的总时间最少,同时还应该满足下面的条件1同一设备在某一时刻只能处理一个任务2每个任务不能同时在两台设备上被处理3每一任务的各个操作之间有确定的技术顺序约束4工序的处理一旦开始就不能被打断。33基本遗传算法的构造331编码编码问题是设计遗传算法的首要和关键问题,遗传算法的编码技术必须考虑染色体0的合法性、可行性、有效性以及问题解空间表征的完全性。其中编码方式包括有基于操作的编码基于工件的编码、基于先后表的编码、基于工件对关系的编码和基于机器的编码等等。本文采用基于机器的编码,下面以典型的作业车间调度问题FT06为例说明编码的过程FT06为6个工件6台机床的作业调度问题,各工件的技术约束和加工时间如表31所示,为方便起见把各工件的编码从05改为16。表31FT06的加工工艺约束和加工时间16第I道工序所在的加工机床号加工时间工件号I1I2I3I4I5I61311326476356228355106101104433544681921574251535435869539235564134162343691105431由上述表格可以很简单的建立一个基于机器的工件加工顺序表如表32所示。表32工件加工顺序第I道工序所在的加工机床号加工时间工件号I1I2I3I4I5I6134122564425522135524113613664311512231414442662325652316456553366462463335415表32第一行指机器1上首先加工工件3的第4道工序,然后加工工件1的第二道工序,以此类推。FT06基于机器的编码就是建立长度为66的染色体如表33所示表中每个数字含义和表32相同表33染色体341225644255213552411361664311512231144426623256231645655336462463335415332解码解码过程包括两部分,首先对随机产生的调度方案进行机器工件队列之间的冲突消解,然后在进行解码计算最终调度时间。1基于机器编码的机器工件队列之间的冲突消解NM的JOBSHOP调度问题就包含有NM个调度方案,当采用基于机17器的编码时,调换各机器上加工工件顺序就可以得到不同的调度方案,但是这种通过随机调换工件顺序而产生的调度方案不一定符合工件的实际加工要求和加工技术路线的约束,当产生的调度方案和实际加工要求约束不符合时就有必要对该调度方案进行冲突消除。下面以FT06为例说明该冲突消解的过程表32为一种随机产生的调度方案,现在分析其中的工件3和工
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
提示  人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:毕业设计(论文)-柔性制造系统中机床调度优化研究
链接地址:https://www.renrendoc.com/p-9744381.html

官方联系方式

2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

网站客服QQ:2881952447     

copyright@ 2020-2024  renrendoc.com 人人文库版权所有   联系电话:400-852-1180

备案号:蜀ICP备2022000484号-2       经营许可证: 川B2-20220663       公网安备川公网安备: 51019002004831号

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知人人文库网,我们立即给予删除!