带精英策略NSGA的研究及其在区域水资源优化配置中的应用

中北大学硕士学位论文带精英策略NSGA的研究及其在区域水资源优化配置中的应用姓名：房好帅申请学位级别：硕士专业：计算机应用技术指导教师：孔令德20080520带精英策略NSGA的研究及其在区域水资源优化配置中的应用作者：房好帅学位授予单位：中北大学相似文献(10条)1.学位论文鞠海华基于NSGA-Ⅱ算法的作业车间调度研究2008车间调度方法与优化技术的研究已经成为先进制造技术的基础和关键。在制造业车间，调度问题的规模巨大，所涉及的对象复杂，系统动态性强。调度问题本身是一类组合优化问题，也是典型的NP(NP-complete)问题。车间作业调度问题具有计算复杂性、动态约束性、多目标性等特点。多目标优化问题在科学和工程等领域是一个热点问题，同时也是研究的一个难点。传统的多目标优化方法在某些复杂的多目标优化问题中存在不足，因此渐渐地被一些优越的多目标优化算法所替代。第一代非劣前沿分级遗传算法NSGA在多目标领域中显示出比较大的优势，但是随着应用范围的不断拓宽，其缺点就不断暴露出来。为了更好地解决多目标优化问题，在NSGA的基础上，研究人员提出了带精英策略的非劣前沿分级遗传算法NSGA-II。国外关于NSGA-II的理论和应用研究都比较深入，而国内目前还比较少。本文通过对该算法的研究，将其应用于实际的作业车间调度问题。利用NSGA-II在多目标优化领域强大的优势，很好地解决了多目标作业车间调度的问题。本文主要的工作为：(1)研究了车间调度的背景、研究现状、意义和发展趋势；对车间调度的各种研究方法进行了系统的分析和比较；对课题研究的意义和内容作了阐述。(2)详细研究和分析了非劣前沿分级遗传算法(NSGA)在解决多目标优化问题中的优缺点，并在NSGA的基础上重点研究了其改进算法--带精英策略的非劣前沿分级遗传算法(NSGA-II)的思想、流程、小生境和精英策略，对二者进行详细的比较，总结出NSGA-II在解决多目标优化问题中的优势；并针对遗传算法收敛速度慢和易陷入局部最优的问题，在总结已有经验的基础上提出改进：对交叉概率和变异概率的计算提出了改进方法，避免遗传算法产生无用解或陷入局部优化，以提高效率。(3)针对多目标作业车间调度优化无法找到唯一最优解的问题，建立了带约束条件的多目标车间调度的数学优化模型。用MATLAB语言编写了基于多目标优化的带精英策略的非劣前沿分级遗传算法程序，并给出了非劣前沿分级、Pareto最优解、小生境等的MATLAB程序代码。程序在MATLAB7.0.1中调试通过，说明了用MATLAB实现基于多目标优化的NSGA-Ⅱ算法的可行性，且从数据上表明带精英策略的非劣前沿分级遗传算法在解决多目标优化问题时优于普通多目标优化算法。(4)通过采用带精英策略的非劣前沿分级遗传算法解决多工艺路线与多目标调度集成的问题，在考虑了交货期最短、生产成本最低和设备负载平衡的条件下，构建了相应的多工艺路线与调度集成模型，将多工艺路线和车间调度相结合，实现了最优工艺路线与调度结果的同时生成。通过算例分析，证明NSGA-Ⅱ算法能够有效地实现多工艺路线与多目标车间调度的集成。2.期刊论文李莉.史仲平.潘丰.LILi.SHIZhong-ping.PANFeng基于NSGA-Ⅱ算法的BP神经网络优化研究-微计算机信息2009,25(4)针对BP(BackPropagation)网络训练时,会遇到陷入局部极小点、收敛速度慢等问题,提出将BP训练看成多目标寻优过程,以网络输出节点的误差最小作为并行搜索的多个目标,通过带精英策略的非支配排序遗传算法(NSGA-Ⅱ,Non-DominatedSortingGeneticAlgorithmⅡ)对BP网络的初始权值和阈值进行优化,给出了应用该方法的步骤.通过仿真验证,这种NSGA-Ⅱ&BP算法时一个单输入双输出非线性系统进行逼近,能克服BP网络训练的缺陷,且所建模型对检测样本的拟合程度比单独BP网络的效果要好.3.期刊论文张晓菲.张火明精英策略的改进非支配遗传算法-中国计量学院学报2010,21(1)在研究NSGA-Ⅱ算法的基础上,提出了一种新的精英策略.它既可以使种群中优良个体保持到下一代,又可以维护种群的多样性,避免算法陷入局部最优解.此外,对NSGA-Ⅱ算法的交叉算子和变异算子进行了重新选择,交叉算子采用模拟二进制交叉算子,变异算子采用非均匀变异算子.将它们引入INSGA-Ⅱ算法中,在优化前期可以进行大范围搜索,而后期可以集中搜索某个重点区域,从而可以提高解的精确性.通过经典函数测试,并将INSGA-Ⅱ算法与NSGA-Ⅱ算法的结果进行比较.结果表明,基于精英策略的改进算法INSGA-Ⅱ不仅取得了较好的结果,而且分布性也得到了有效的提高.4.学位论文王鲁基于遗传算法的多目标优化算法研究2006解决现实世界中的许多问题会遇到两种类型的难度：Ⅰ)多个相互冲突的目标，Ⅱ)高维复杂的搜索空间。就第一点而言，与单目标优化不同的是，多个相互竞争目标的优化结果是得到一组可行解，一般被称作Pareto最优解集。由于缺少喜好信息，在折中解中找不到一个解比另一个解更好。就第二点而言，若使用精确的方法解决多目标优化问题，搜索空间太大而且很复杂。因此，需要设计高效的优化策略来解决这两个问题。非劣分类算法Ⅱ(NSGAⅡ)是近几年发展起来的一种多目标遗传算法。它采用了非劣分类算法以及精英策略。它具有很多优点：(1)将时间复杂度降低到(GMN2)，其中G是代数，M是目标个数，N是种群规模；(2)采用精英策略，使得先前各代中搜索到的精英解得以保留；(3)不需要确定共享参数，因此算法对于用户来说是透明的。本文对遗传算法进行了介绍，讨论了多目标演化算法的相关重要策略，并介绍了SPEA2算法和NSGAⅡ算法。在对NSGAⅡ实验发现，大概在20代以后，种群中的所有解都是精英，随后各代的操作都将在精英解中进行，非精英解无法参与其中，当前种群也就不能再接纳一些新的解参与下一代的操作，降低了解的多样性。搜索过程将中止并过早的收敛到局部的Pareto解。为了确保搜索向全局Pareto优解收敛，一种确保解的多样性的改进精英策略的多目标遗传算法(IENSGAⅡ)被提出，在改进的多目标优化算法中，精英策略保存从上一代至今最优的非劣解，使得精英解的作用代数得以延续。同时提出一种分布函数，通过调节参数r以及改进精英策略的应用代数gener在遗传操作中控制精英解的选取范围，使得一部分非精英解按照等级的不同公平参与到遗传操作中，增加了解的多样性。将IENSGAⅡ算法和NSGAⅡ算法在六个多目标测试问题(ZDT1，ZDT2，ZDT3，ZDT4，ZDT6，KUR)上作了比较，并引入Deb所提出的两个性能度量值r和△进行测试。通过性能度量值及最终优化后的Pareto优解的组成图示均可看出在所有的六个测试问题上改进的多目标演化算法无论在解的多样性还是解的收敛性方面都有较大改观，在多样性及收敛性之间达到了一个较好的平衡，避免了解过早收敛到局部Pareto解集。性能明显优于NSGAⅡ算法。5.期刊论文冯士刚.艾芊.王伟.徐伟华.凌晓波.刘蓓.王冲.FENGShi-gang.AIQian.WANGWei.XUWei-hua.LINGXiao-bo.LIUBei.WANGChong基于伪并行NSGA-Ⅱ算法的火电站多目标负荷调度-上海交通大学学报2008,42(3)为了克服以往负荷调度模型及优化算法存在的缺陷,提出了多目标负荷调度模型,同时考虑最小化燃料费用和污染排放量,并将带精英策略的快速非支配排序遗传算法(NSGA-Ⅱ)与并行遗传算法(PGA)相结合对其求解.利用该方法对一电厂进行多目标负荷调度,获得了分布良好的Pareto最优解,为经济性和环保性的权衡分析提供了有效的工具,分析结果验证了其思路的有效性和可行性.6.学位论文樊纪山ε-dominance多目标演化算法在优化问题中的应用研究2006在现实生活中，人们遇到的大多数优化问题是多目标优化问题，而且这些目标之间大多数是相互冲突的。在优化过程中所获得的解集就称为Pareto优化解集。大多数的多目标优化算法是用来寻找Pareto近似优化解集。算法所获得的解不但要分布均匀，而且还要尽量地接近Pareto优化阵面。但是目前存在的多数优化算法在这方面却存在着一定缺陷。比如有些算法可能花费大量的时间获得分布均匀的优化解；有些算法虽然时间短些，但获得的优解分布不是很均匀。在这篇论文中提出一种快速稳定的多目标演化算法(Ⅰ-MOEA)，同时又改进了目前一种比较好的算法-NSGA-Ⅱ算法。Ⅰ-MOEA算法是基于Deb.在2002年提出的ε-dominance的概念，算法还应用了精英策略、归档更新、超网格分割法和G向量支配策略。精英策略是目前公认的一种保持个体多样性的有效策略。归档更新策略分为在线归档和离线归档，算法中应用了在线归档。本文中提出的超网格分割法和G向量支配策略是用来解决个体多样性的问题。网格分割方法是将目标空间分割成许多超网格，同时保证每一个超网格只能被一个非支配的个体所占用，这样做的目的是便于个体之间的ε支配关系的比较，可以解决维持解的多样性的问题。G向量支配策略用来选择非支配的精英个体，可以保证选出的精英最具有代表性，从而很好地解决个体的多样性问题。用Pareto支配和ε支配来选择非支配个体，选择出具有代表性的精英个体，这样就可以减少候选解的Pareto优化区域。归档的大小没有预先设值，而是根据协调参数λ和ε的乘积而定，这样能缩短归档的更新时间，且能获得理想的Pareto优化解，从而减少了整个算法的计算时间。从模拟实验的结果来看，该算法具有很好的通用性，且算法的效率也很高。在改进的NSGA-Ⅱ算法(Ⅰ-NASG-Ⅱ算法)中，首先分析了NSGA-Ⅱ算法所存在的缺陷，即在保持解的多样性方面存在着缺陷。于是用SPEA2中的Clustering方法来代替NSGA-Ⅱ算法中Crowding方法。从测试结果看，Ⅰ-NSGA-Ⅱ算法获得解分布比NSGA-Ⅱ算法所获得解均匀些；而Ⅰ-MOEA算法无论是在无约束的两个目标、有约束限制的两个目标还是三个目标上的测试，获得优化解都比较理想。从模拟结果上看，这两种算法都取得了良好的效果。7.学位论文石红玉NSGA-Ⅱ在卫星星座优化设计的应用研究2007在实际应用中人们经常遇到多目标优化问题，如投资问题。投资者一般希望投入的资金量最少，风险最小，且获得的收益最大。多目标优化问题的多个目标通常是相互冲突，相互竞争的，对其中一个目标优化必须以其他目标作为代价。多目标优化是近30年来迅速发展起来的一门新兴学科，一直是科学和工程研究领域的难题和热点问题。多年来许多研究者的工作就是寻找一些重要技术来处理多目标优化问题。传统的解多目标优化问题的方法通常存在许多缺陷，如各目标加权值的分配带有较大的主观性，优化过程中各目标的优度进展不可操作等，在处理高维数、多模态等复杂问题上存在许多不足。遗传算法是模拟自然界生物进化过程与机制，求解优化与搜索问题的一类自组织、自适应的人工智能技术。由于遗传算法是对整个群体进行的进化运算操作，它着眼于个体的集合，而多目标优化问题的非劣解一般也是一个集合，遗传算法的这个特性表明遗传算法非常适合求解多目标优化问题。国内外研究学者在简单遗传算法的基础上，发展出了多种多目标优化遗传算法，如SPEA、MOGA、NSGA、NSGA-Ⅱ、PAES、MEES等。本文研究的非支配排序遗传算法(Non-dominatedSortingGeneticAlgorithm,NSGA)及其改进算法NSGA-Ⅱ就是其中发展较快、优化效果较好的一种方法。本文对NSGA-Ⅱ算法的基本原理进行了系统的学习和研究，在算法的应用研究方面作了大胆的尝试。NSGA-Ⅱ是NSGA算法的改进，在NSGA的基础上加上了精英策略、密度值估计策略和快速非支配排序策略，在很大程度上改善了NSGA的缺点。但NSGA-Ⅱ采用的SBX交叉算子和变异算子性能相对较弱，从而在一定程度上限制了算法的搜索性能，使得NSGA-Ⅱ在种群的多样