毕业设计（论文）-柔性制造系统中机床调度优化研究
收藏
资源目录
压缩包内文档预览：
编号：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,MATHEMATICALEXPECTATIONOFCHROMOSO
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号