改进蜜蜂进化型遗传算法引导的nsga2两阶段优化算法及应用 70页

学校代号10532学号S130210089分类号O232密级公开硕士学位论文改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用学位申请人姓名张丽科培养单位机械与运载工程学院导师姓名及职称邓乾旺教授学科专业机械工程研究方向生产与服务系统设计与优化论文提交日期2016年05月10日 湖南大学学位论文原创性声明的指导下独立进行研究所取得的本人郑重声明：所呈交的论文是本人在导师引用的内容外，本论文不包含任何其他个人或研巧成果。除了文中持别加站标注品的个人和集体，巧集体己经发表或撰写的成果作。对本文的研究做出重要贡献果由本人承担。已在文中臥明确方式标明。本人完全意识到本声明的法律后日期：户化年＾月５曰作者签名：夸长＾矛钟学位论文版权使用授权书关保留，同意学校保本学位论文作者完全了解学校有、使用学位论文的规定论文被查阅和借阅。留并向国家有关部口或机构送交论文的复印件和电子版’允许从将本学位论文的全部或部分内容编入有关数据库进行检索，本人授权鄉南大学可汇编本学位论文。可臥采用影印、缩印或扫描等复制手段保存和本学位ｉ仑文属于密□年解密后适用本授权书。，在１、保＾２、不保密巧＾＂上相应方框内打）（请在臥日期６年《月：＾日；＞ｏ＾作者签名＝巧和ｔ日期：扭年ｆ月日导师签名；古片（ａＯ／叮 学校代号：10532学号：S130210089密级：公开湖南大学硕士学位论文改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用学位申请人姓名：张丽科导师姓名及职称：邓乾旺教授培养单位：机械与运载工程学院专业名称：机械工程论文提交日期：2016年05月10日论文答辩日期：2016年05月28日答辩委员会主席：程军圣教授 Atwo-stageoptimizationalgorithmofNSGA2guidedbytheimprovedbeeevolutionarygeneticalgorithmanditsapplicationbyZHANGLikeB.E.(NorthChinaUniversityofWaterResourcesandElectricPower)2013AthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofScienceinMechanicalEngineeringintheGraduateSchoolofHunanUniversitySupervisorProfessorDENGQianwangMay,2016 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用摘要现代工程的研究问题日益复杂，且往往具有多个相互制约的设计目标，使得传统的多目标优化问题的理论和方法不断受到挑战。多目标优化算法作为求解这类问题的主要方法，应具备鲁棒性强、求解效率高、求解精度优等特点。近年来，许多优秀的多目标优化算法及理论相继被提出。本文通过分析优化算法的研究现状，深入研究了多种优化算法的优劣。针对经典NSGA2(Non-dominatedsortinggeneticalgorithm2)在求解复杂问题时的不足，结合蜜蜂进化型遗传算法的优点，提出了改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法，并对该算法的应用进行了研究。主要工作及创新点概括如下：1）通过优化选择算子γ、根据交叉父代的相似度采用不同的交叉方式及根据个体父代性能选择变异方式，改进蜜蜂进化型遗传算法，提高第一阶段的寻优效率。然后，通过深入探究经典NSGA2在求解复杂苛刻优化问题时存在的问题，在采用改进交叉方式和变异方式的基础上，提出删除重复个体、引入新个体、精英种群代替父代种群等改进措施，提高第二阶段的种群多样性、算法的求解效率和精度。针对约束条件苛刻的多目标问题，构造外部辅助种群，将满足规定条件的不可行解复制到外部种群并参与下一代操作，引导其它不可行解向可行解边界靠拢，加快算法求解速度。基于以上改进及两阶段优化算法思想，针对约束条件苛刻的多目标问题和无约束条件的多目标问题分别设计相应的算法求解流程。2）从绿色绩效的角度出发，建立了废旧产品的回收与再制造VRPSPD路径规划问题模型，然后利用本文算法求解该优化模型。通过对比分析算法改进前后求解不同客户规模下的运行结果，验证了本文算法的高效性。3）利用改进算法求解以最小化最大完工时间、最大机器负荷和机器总负荷为目标的多目标柔性作业车间调度问题，通过对几种经典案例的求解及与其它优化算法求解结果对比分析，验证了本文算法的有效性。关键词：多目标优化；NSGA2；蜜蜂进化型遗传算法；两阶段优化算法；回收与再制造；柔性作业车间II 硕士学位论文AbstractTheresearchissuesofmodernengineeringareincreasinglycomplex,andtheyoftenhavemultipleinter-constraintdesigngoals,whichmakethetheoryandmethodofthetraditionalmulti-objectiveoptimizationproblemscontinuetobechallenged.Asthemainmethodtosolvethiskindofproblems,themulti-objectiveoptimizationalgorithmsshouldhavethecharacteristicsofstrongrobustness,highefficiencyandhighaccuracy.Inrecentyears,manyexcellentmulti-objectiveoptimizationalgorithmsandtheorieshavebeenproposed.Inthepaper,theadvantagesanddisadvantagesofvariousoptimizationalgorithmsaredeeplystudiedthroughtheanalysisoftheresearchstatusoftheoptimizationalgorithms.FortheshortagesofclassicNSGA2insolvingcomplexproblems,combinedwiththeadvantagesofbeeevolutionarygeneticalgorithm,amulti-objectiveevolutionaryalgorithmcalledNSGA2guidedbytheimprovedbeeevolutionarygeneticalgorithmisdesignedtoexecutetwo-stageoptimization,andtheapplicationoftheproposedalgorithmisstudied.Themainworkandinnovationpointsaresummarizedasfollows:1)Byoptimizingtheselectionoperatorγ,accordingthesimilarityofcrossparentstoselectcrossmethodsandaccordingtheperformanceofindividual’sparenttoselectmutationmethods,thebeeevolutionarygeneticalgorithmandthesearchingefficiencyofthefirstphaseareimproved.Then,throughtheanalysisoftheshortagesofclassicalNSGA2insolvingcomplexanddemandingoptimizationproblems,basedontheimprovedcross-wayandmutationmethods,thispaperproposestodeleteduplicateindividuals,introducenewindividuals,useelitepopulationinsteadoftheparentpopulationandotherimprovementmeasurestoimprovethepopulationdiversity,algorithmefficiencyandaccuracyinthesecondphase.Fortheoptimizationproblemswithdemandingconstraints,thispaperintroducesanexternalauxiliarypopulation.Theinfeasiblesolutionswhichtheconstraintviolationdegreearesmallerthanagivenvaluearecopiedtotheexternalsetandparticipateinthenextgenerationofevolutiontoimprovethepopulationdiversityandguideotherinfeasiblesolutionsrapidlyapproachingthefeasiblesolutionboundary.Basedontheaboveimprovementsandthethoughtofthetwostageoptimizationalgorithm,thecorrespondingdetailedalgorithmflowsaredesignedtorespectivelysolvethemulti-objectiveproblemwithdemandingconstrainedconditionsandthemulti-objectiveproblemwithnoconstraint.III 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用2)Fromthepointofgreenperformance,aVRPSPDmodelofrecyclingandremanufacturingofwasteproductsisestablished,andtheproposedalgorithmisusedtosolvetheoptimizationmodel.Comparedtheresultsofdifferentcustomersizecalculatedbytheproposedalgorithmwiththeresultscalculatedbythealgorithmimprovedbefore,theefficiencyoftheproposedalgorithmisverified.3)Usetheproposedalgorithmtosolvethemulti-objectiveflexiblejobshopschedulingproblemwiththeobjectivesofminimizingthemaximumcompletiontime,themaximummachineloadandthetotalloadofthemachines.Thevalidityoftheproposedalgorithmisillustratedbythecalculationofthebasicexamplesandthecomparisonoftheresultscalculatedbyothersixclassicalgorithms.KeyWords:Multi-objectiveOptimization;NSGA2;BeeEvolutionaryGeneticAlgorithm;Two-stageOptimizationAlgorithm;RecyclingandRemanufacturing;FlexibleJobShopIV 硕士学位论文目录学位论文原创性声明和学位论文版权使用授权书...................................................I摘要........................................................................................................................IIAbstract...................................................................................................................III插图索引.................................................................................................................VII附表索引................................................................................................................VIII第1章绪论...........................................................................................................11.1研究背景及意义...........................................................................................11.2多目标算法的研究现状...............................................................................21.2.1传统多目标优化算法............................................................................21.2.2进化多目标优化算法............................................................................31.3蜜蜂进化型遗传算法...................................................................................51.4NSGA2算法概述.........................................................................................51.4.1快速非支配排序....................................................................................61.4.2拥挤度及拥挤度比较算子.....................................................................71.5论文主要工作及组织安排...........................................................................81.5.1主要工作................................................................................................81.5.2组织安排................................................................................................8第2章改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法......................102.1改进蜜蜂进化型遗传算法.........................................................................102.1.1参数的改进..........................................................................................102.1.2数据分析..............................................................................................102.1.3改进蜜蜂进化型遗传算法的交叉和变异操作....................................122.2改进NSGA2算法......................................................................................132.2.1经典NSGA2优点及不足....................................................................132.2.2结构改进..............................................................................................132.2.3改进NSGA2算法的交叉和变异操作.................................................142.3两阶段优化算法.........................................................................................142.3.1约束条件苛刻的多目标优化问题.......................................................142.3.2无约束条件的多目标优化问题...........................................................162.4本章小结....................................................................................................19第3章改进算法在逆向物流路径规划中的应用.....................................................20V 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用3.1逆向物流VRPSPD路径研究概况.............................................................203.2回收与再制造逆向物流网络模型..............................................................213.3回收与再制造逆向物流路径的多目标优化模型.......................................223.3.1油耗模型..............................................................................................223.3.2等待时间模型......................................................................................233.3.3行驶距离模型......................................................................................233.3.4目标函数..............................................................................................233.4算法实例仿真.............................................................................................253.4.1仿真实例及结果..................................................................................263.4.2结果分析..............................................................................................333.5本章小结....................................................................................................34第4章改进算法在柔性作业车间调度中的应用...................................................354.1柔性作业车间调度问题概述......................................................................354.1.1柔性作业车间调度问题描述...............................................................354.1.2柔性作业车间调度的研究方法...........................................................364.1.3柔性作业车间的研究现状...................................................................374.1.4目标函数..............................................................................................384.1.5参数说明..............................................................................................404.2改进算法在FJSP上的设计.......................................................................404.2.1FJSP的编码..........................................................................................404.2.2FJSP的解码..........................................................................................414.3算法实例仿真.............................................................................................434.3.1仿真实例及结果..................................................................................434.3.2结果分析..............................................................................................484.4本章小结....................................................................................................49结论与展望...............................................................................................................50参考文献...................................................................................................................52致谢.......................................................................................................................58附录A攻读硕士学位期间发表的学术论文...........................................................59VI 硕士学位论文插图索引图1.1蜜蜂进化型遗传算法进化机制模型...............................................................5图1.2蜜蜂进化型遗传算法流程图...........................................................................6图1.3论文框架图......................................................................................................9图2.1平均最大适应度与γ占比的关系.................................................................11图2.2平均进化代数与γ占比的关系.....................................................................11图2.3多种变异.......................................................................................................12图2.4约束条件苛刻时的改进算法流程图.............................................................16图2.5无约束条件时的改进算法流程图.................................................................18图3.1回收与再制造物流网络结构.........................................................................21图3.2单点交叉.......................................................................................................25图3.3双点交叉.......................................................................................................26图3.4目标值：油耗................................................................................................28图3.5目标值：行驶距离........................................................................................28图3.6目标值：顾客等待时间................................................................................28图3.7车辆配送路径图............................................................................................29图3.8车辆经过各服务点时载货量变化情况.........................................................29图3.922客户最优解...............................................................................................32图3.1042客户最优解.............................................................................................32图3.11重复个体数..................................................................................................32图4.1染色体结构....................................................................................................41图4.2染色体编码示例............................................................................................41图4.3动态式调度(a)...............................................................................................42图4.4动态式调度(b)...............................................................................................43图4.5染色体解码甘特图........................................................................................43图4.6算例4×5(f1=12,f2=8,f3=32).........................................................................44图4.7算例8×8(f1=14,f2=12,f3=77)......................................................................44图4.8算例10×10(f1=7,f2=5,f3=43)......................................................................45图4.9算例10×10(f1=8,f2=7,f3=41)......................................................................45图4.10算例15×10(f1=12,f2=11,f3=91).................................................................45图4.11目标f1的收敛迭代图..................................................................................48VII 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用附表索引表3.1汽车引擎能耗模型参数................................................................................22表3.2各服务点信息................................................................................................26表3.3改进前后算法运行结果比较.........................................................................27表3.422客户各服务点信息...................................................................................30表3.542客户各服务点信息...................................................................................30表4.1柔性调度4×5算例........................................................................................36表4.2算法参数设置................................................................................................44表4.3算例4×5算法求解结果对比........................................................................46表4.4算例8×8算法求解结果对比........................................................................46表4.5算例10×10算法求解结果对比....................................................................46表4.6算例15×10算法求解结果对比....................................................................46表4.7相关算法求解结果及运行时间对比分析.....................................................47VIII 硕士学位论文第1章绪论1.1研究背景及意义[1]现实生活中任何控制和决策问题都可以归结于优化问题。我们总是希望用最少的资源消耗、人力投入等获得最大收益，如产品实用性能、安全性能及舒适[25]性能都最佳，这明显是相互矛盾的多目标规划问题~，然而这些问题遍布于物[6]流规划、生产调度、工业制造及航天工程、生物信息等各个领域。优化算法就是以数学知识为基础，研究各种系统的优化途径和方案，为决策者提供科学决策依据的技术方法。因此，高效的优化方法一直是各领域研究学者探索的重点。优化方法根据决策变量是否连续，分为连续优化问题和组合优化问题。优化方法根据是否有约束条件，分为无约束优化问题和有约束优化问题。实际的优化问题往往存在多个约束条件，如何处理好约束条件对提高优化方法的求解效率也是至关重要。优化方法按求解精度分为精确方法和近似方法，精确方法经过严格的数学推到、计算，能够获得全局最优解，但是对约束条件苛刻、规模庞大的优化问题却无能为力，近似方法是利用迭代的原理在合理的时间内求出近似最优解，对优化问题要求较低，通常只需要一个决策向量和目标向量，是现实情况下经常采用的方法。优化方法按求解的优化目标个数分为单目标优化方法和多目标优化方法[7]。虽然求解单目标的优化方法已经相当成熟，但在求解多目标问题前显得无所适从。然而科学研究和实际生产通常存在多个优化目标，这些优化目标相互制约，一个优化目标的增加往往会导致其它至少一个优化目标的退化。在兼顾其它优化目标的前提下，决策者需要根据变化的研究背景或生产背景侧重某一个或几个优化目标。因此，研究高效的、具有一组互不占优的最优解的多目标优化方法更具有重要的实际意义。多目标优化算法是近30年来发展最迅猛的一门学科，从传统的多目标优化方法，如加权法、约束法、目标规划法等，到后面学者根据自然界的进化现象提出[8]的比较经典的多目标优化算法，如多目标遗传算法（MOGA）、向量评估遗传[9][10]算法（VEGA）、小生境pareto遗传算法（NPGA）、非支配排序遗传算法（NSGA）[11]等。这些算法相对简单，将多目标问题转换成单目标问题或基于非支配排序选择个体、基于共享函数和小生境技术保持种群多样性等方法解决多目标优化问题。随着各个学科的快速发展、研究问题的不断深入和复杂，很多优化问题不断挑战多目标优化方法的理论成果。随着现代计算机性能的不断提升，在前人的基础上，为了更有效的求解高维多目标优化问题，很多学者不断尝试、改进、提出新型的1 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用搜索算子和多目标优化方法，取得了很多优秀成果，如粒子群优化算法（PSO）[12][13][14]、NSGA2算法、人工免疫系统（AIS）等。近年来兴起的NSGA2算法，因其高效率的求解多目标问题，获得越来越多的重视。NSGA2相对于NSGA最大的优势是根据产生的各种非劣前端，采用更好的记帐策略（精英策略），从而减少算法整体运算时间，并采用密度估计算子和[15]拥挤比较算子取代原来的共享机制以保证种群多样性和pareto解分布均匀性，能够有效解决各领域内多目标规划问题，特别是离散型问题。然而，随着工程实践、科学研究问题的日益复杂、约束条件的苛刻、增多、不确定性、目标的多元化及人们对时效性的注重，在对优化问题的多个目标特别是相互冲突的子目标进行求解时，多目标优化问题的理论和方法也显现出不足之处。不同的多目标优化方法具有不同的优劣，即面临着鲁棒性不强的短板。NSGA2算法在管理经营、工业生产等方面的求解应用也受到很大限制，如收敛精度不高、pareto前沿分布不均、收敛速度慢等。如何快速的求解且得到令人满意的解决方案，对提升企业竞争力、提高企业形象具有十分重要的意义。因此，改进NSGA2，扩展其应用领域，提高其收敛速度、求解精度是十分迫切和必要的。本文通过改进NSGA2在求解问题时的不足之处，及利用蜜蜂进化型遗传算法的求解优势，构造了改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法，有效的提高了NSGA2算法的求解性能并拓展了其应用范围。1.2多目标算法的研究现状多目标优化问题广泛存在于社会各学科领域，第一个真正用于解决多目标优化问题的多目标优化算法是Schaffer于1985年提出的向量评估遗传算法（VEGA）。在此之前，人们是将多目标问题归一化成单目标问题，利用传统的优化方法解决，如加权法、约束法、目标规划法、分层分析法等。自Schaffer基于pareto排序提出VEGA以后，不少学者基于pareto排序提出很多新型算法，如Fonseca和Fleming于1993年提出的MOGA、Nafpliotis和Horn于1994年提出的小生境Pareto遗传算法（NPGA）、Zitzler和Thiele于1999年提出的强度Pareto进化算法（SPEA）[16]、Srinivas和Deb于2000年提出的非支配排序算法（NSGA）等，以及在此基[17][18]础上引入精英保留机制提出的第二代算法，如NPGA2、SPEA2、NSGA2等，还有学者基于仿生机制提出的智能进化算法，如差分进化算法、人工免疫算法、模拟退火算法、粒子群算法、蚁群算法等。下面对以上部分算法做简单介绍。1.2.1传统多目标优化算法1）加权法为事先要优化的每个目标fi(x)分配一个权重ωi，然后由公式（1.1）将多目标2 硕士学位论文问题转化成单目标问题。加权法构造简单，操作容易，但不足的是需要为每个目标合理分配权重，且每次优化只能求得一个结果。mmfifxi，满足i=1(1.1)ii112）约束法决策者根据自己的偏重，选择多目标中的一个目标fk(x)作为优化目标，并将其余优化目标由公式（1.2）转化成约束条件，进而将多目标优化问题转变成带约[19]束的单目标优化问题。其中εi是决策者对优化目标fi(x)的估值上限。约束法在兼顾其余优化目标的前提下，能够保证决策者偏重的目标取得很好的解，但缺点是决策者需要合理估算εi。st.fxii,1im且ik(1.2)3）目标规划法目标规划法需要决策者事先根据经验为每个优化目标预计一个目标值，并将[20]该目标值添加到执行过程中。它能够很好地求解线性规划问题，但一个很严重的缺点是它要求决策者合理估算目标值。1.2.2进化多目标优化算法随着工程实践、科学研究问题的日益复杂、约束条件的苛刻、增多、不确定性、目标的多元化及人们对时效性的注重，传统的优化方法已不能高效率地解决这些多目标优化问题。人们通过探索、观察自然界的进化现象提出了很多有效的多目标进化算法，根据多目标进化算法的特点和发展历程将其分成第一代多目标进化算法、第二代多目标进化算法和智能多目标进化算法。1）第一代多目标进化算法从Schaffer于1985年提出向量评估遗传算法至90年代末，这之间的多目标进化算法被人们称作第一代多目标进化算法。该阶段算法特点是简单，基于共享适应度和非支配排序来保持种群的多样性，典型的算法有MOGA、NPGA和NSGA。MOGA是Fonseca和Fleming基于非支配排序的思想提出的多目标进化算法。在每一代，每个个体p的rank等级等于它在种群中被支配的个体数n_p加1，等级为1的个体就是最优非劣个体。所有个体rank等级确定后依据rank等级升序排序，并采用Goldberg的线性或非线性插值的方法分配适应度，等级相同的个体具有相同的适应度。最后通过共享机制选择操作个体，保证种群的多样性。MOGA执行简单，但由于需要设置共享参数，易受小生境策略影响，有可能导致早熟收敛。NPGA也是基于非支配排序思想提出的，相比其它算法其突出特点是算法采3 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用用竞争选择机制。具体操作：在每一代，随机从种群中选择两个个体及一个种群子集，将这两个个体与子集基于目标值比较，若只有一个个体不被子集支配，则将该个体选入下一代，若两个体均非支配或被支配，则基于小生境机制选择最优个体进入下一代。这使得种群优秀个体能够很大程度上被保留到下一代，有助于收敛到比较优的非劣解。竞争规模不同、小生境半径不同，算法的收敛效果和收敛速度也不同。由于设置合理的竞争规模和小生境半径比较困难，这影响到算法的使用效果。NSGA是Deb于1994年在进化算法的基础上基于非支配排序的思想设计的。每一代，种群个体之间根据目标解的优劣支配关系进行排序，将当代种群中的非劣解归类为最高等级1，并分配一个很大的适应度值。然后，移除这些非劣解，从余下的个体中继续进行支配关系排序，将获得的非劣解归为等级2，并分配一个次于上一个等级的适应度。重复这样的操作，直到所有的个体等级分配完毕并被赋予适应度值。同时为了保证种群多样性，对同一等级的个体采用共享机制。NSGA算法具有以下优点：优化目标个数任选，对任意目标个数都表现出良好的性能；等级越高，适应度值越大，有利于当代最优个体尽可能的遗传至下一代；采用共享机制保证种群多样性，有助于最优pareto前沿分布均匀。但是NSGA算法还存在以下不足：计算复杂度高，计算时间长；无精英保留制，不能保证当代最优pareto前沿个体一定遗传到下一代；共享参数需要事先确定。2）第二代多目标进化算法自90年代末至21世纪初，以精英保留制为特征的多目标进化算法成为第二代多目标进化算法。精英保留制的引入使得每一代种群中的最优个体都能够保留至下一代，加快了算法的收敛速度和收敛结果。典型的算法有SPEA、SPEA2、NSGA2、PAES、NPGA2等。Zitzler于1999年提出SPEA算法，通过引入外部种群N´实现精英保留制。将每一代的非支配个体转移至外部种群N´中，剩余个体构成种群N，并利用聚类方法删除N´中多余个体。N´中的个体适应度与其在N中支配的个体数成正比，N中的个体适应度等于N´中支配它的个体的适应度之和。在N中和N´中利用二元锦标赛机制选择较优个体，适应度越小，个体越优。算法缺点是效率低，进化结果与N´的规模有关。Zitzler基于SPEA的缺点于2001年提出了SPEA2。[21]PESA是Corne等人于2000年基于空间网格的思想提出的经典算法，它有一个内部种群和一个外部种群构成。进化过程中每一代，将内部种群中的非支配个体加入到外部种群中，清空内部种群并根据拥挤度删除外部种群中相同数量的个体。下一代内部种群个体一部分按新方法产生，一部分由部分外部种群个体交叉变异产生。该算法有效的保持了种群的多样性，但在优化运算时间上有所欠缺。4 硕士学位论文1.3蜜蜂进化型遗传算法遗传算法（GeneticAlgorithm，GA）是由美国的Holland教授于1975年首次提出，它是人们受自然界的遗传进化机制启发提出来的一种高度并行、随机搜索的算法。它模拟生物进化过程中自然选择、优胜劣汰、遗传变异的生存法则，将实际问题按照某种指标朝向人们希望的解前进，直达满足某种收敛条件为止。该算法操作简单，无须人机交互，但是局部搜索能力差、收敛速度慢和收敛精度低。蜜蜂进化型遗传算法（BeeEvolutionaryGeneticAlgorithm，BEGA）是根据自然[22]界中蜜蜂独有的繁殖方式－具有共同的母亲蜂王，提出的一种改进遗传算法，其进化机制模型如图1.1。在每一代进化前，选取种群中最优的个体作为蜂王，它能够充分利用蜂王的最优基因带动种群向更优的方向进化，迅速提升种群水平，同时引入外来种群以增加种群多样性，保证种群收敛到全局最优解。这使得BEGA在收敛速度及收敛精度上均优于一般的遗传算法。蜜蜂进化型遗传算法的具体流程图如图1.2。雄峰新蜂王外界引入雄峰上一代蜂王比较适应度优者为新蜂王交配交配新一代蜂群最优个体图1.1蜜蜂进化型遗传算法进化机制模型1.4NSGA2算法概述NSGA2是Deb等人于2002年在非支配排序遗传算法（NSGA）的基础上，针对NSGA算法的不足，提出的改进型算法，主要表现在以下三个方面：1）提32出快速非支配排序方法，使得算法的计算复杂度由O(MN)降到O(MN)，其中M为目标个数，N为种群规模；2）引入精英保留制，将父代种群与子代种群合并，从中选取较优的N个个体作为子代种群，确保当代最优pareto前沿个体遗传到下一代，从而引导种群快速良好的向前进化；3）引入拥挤度概念，利用拥挤度比较算子代替原有的通过设定共享半径的适应度共享策略，使得算法更加方面实用，且pareto前沿面上的个体能够均匀的扩展到整个pareto域，有效的保证了种群多样性。这些改进使得NSGA2成为最为优秀的多目标优化算法之一，Deb等人的这篇文献是多目标优化领域内被SCI引用次数最多的文献。5 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用开始初始种群Nt=1染色体适应度计算最优个体标记为QueenY是否满足收敛准则输出最优解N轮盘赌输法选择γ个个体随机生成N/2-γ个新个体最优个体的适应度和Queen的适应度比较Queen与这两部分个体交叉产生N个个体获胜者为新的Queen（首代不比较）变异操作计算染色体适应度最优个体进化代数t加1子代种群图1.2蜜蜂进化型遗传算法流程图NSGA2也是应用最广泛的算法之一。如倪昂修等人用NSGA2优化了多段翼[23]型的设计，通过对父代种群进行精英筛选，提高算法的求解效率。张利将NSGA2[24]运用于电力系统稳定器的参数优化中，通过引入模糊优选模型，改进算法的求[25]解精度。徐慧英等人将NSGA2用于车辆路径的多目标优化中，并对算法进行[26]改进。Chatterjee等人利用NSGA2研究AISI-304不锈钢钻削参数的影响。Huang[27]利用改进的NSGA2优化了混流泵叶轮的多目标模型。Martínez-Vargas等人运[28]用NSGA2研究了频谱共享网络的频谱分配问题。虽然NSGA2应用广泛，但在求解不同问题时学者们大都对其进行改进，以提高算法的求解效率和精度。正对绪论1.1所述，面对日益复杂的现代工程优化问题，提高NSGA2的鲁棒性、求解效率和精度具有十分重要的意义。1.4.1快速非支配排序首先，在每一代对每个染色体即解决方案进行两参数的计算。其中一个是n_p用于存放种群中支配p的染色体个数，另一个是s_p用于存放被p支配的染色体集合。然后，找到n_p=0的个体，把它们放入集合F1中，并将他们的等级设置为1，则他们属于第一个非支配面。之后，依次对每一个F1中成员的s_p中的k执行n_k减1，如果成员k的n_k减1结果为0，则将k的等级设置为2，属于第二个非支配面，并把它放到另一个集合H中。接着对第二个非支配面中每个个体p的s_p采取同样的操作确定第三非支配面，依次类推，知道所有的个体都被确定6 硕士学位论文2完毕。通过这种方式，使得NSGA2算法的复杂度降为O(MN)。对于种群P，其快速非支配排序伪代码如下：函数sort(P)对于每一个p∈P对于每一个q∈P若（p≺q）则%p支配qs_p=s_p∪{p}%把p放入s_p中或者（q≺p）则%p被q支配n_p=n_p+1若n_p=0，则F1=F1∪{q}i=1%i为非支配层数当F1≠∅时H=∅对于每一个p∈F1对于每一个q∈s_pn_q=n_q-1若n_q=0，则H=H∪{q}i=i+1,F1=H1.4.2拥挤度及拥挤度比较算子NSGA2是利用拥挤度概念代替原有NSGA中需人为指定共享半径的共享函数方法，来保证种群的多样性。拥挤度用于描述个体所处环境的拥挤程度，可以通过计算染色体i最邻近的两点所构成的矩形的长与宽之和，估算染色体i的拥挤度，这个矩形包括染色体i，但是不能包括其它个体。对于多目标问题，若用di表示第i个染色体的拥挤度距离，fim（m=1,2，…，M）表示染色体i第m个目标函数值，则其计算方法如下：1）初始化，另di=0；2）基于每个目标函数对所有个体进行升序排列，对于排在第一位和最后一位的个体，我们设置它们的di=∞；3）对于其它个体，我们由公式（1.3）计算其拥挤度。Mdifi1.mfi1.m(1.3)m1由上可知，对于拥挤度计算的复杂性与参与排序的个体数相关，在最极端的情况下，即所有的个体都在同一个非支配集里，其计算复杂度为O(MNlgN)。在计算完拥挤度距离后，算法设置了拥挤度比较算子，以便更好的选择个体7 改进蜜蜂进化型遗传算法引导的NSGA2两阶段优化算法及应用进行后续运算，确保算法收敛的pareto结果均匀分布。Deb通过定义一个≺