进化多目标优化算法及其应用研究

论文摘要

多目标优化对于科学家和工程师来说无疑是一个非常重要的研究课题,因为现实问题大多具备多目标的特征,通常难以处理。传统的解决多目标的方法如:加权法、约束法、线性规划法等有很大的局限性。智能优化算法是通过模拟某一自然现象或过程而建立起来的,它们具有适于高度并行性、自组织、自学习与自适应等特征,为解决复杂问题提供了一种新途径。这类算法主要包括进化算法（EA）、粒子群算法（PSO）、人工免疫系统（AIS）和蚁群算法（ACO）等等。本文主要是研究用进化算法来解决多目标优化问题。进化算法也称演化算法,是一种模拟自然进化过程的随机优化方法。群体搜索策略和群体间个体之间的信息交换是它比传统优化算法优越的两大特点。随着对进化算法的研究的深入,国内外研究人员在简单遗传算法的基础上,提出了多种多目标遗传算法,其中非支配排序遗传算法NSGA经研究证实为效果最好的一种,但是在人们的不断使用过程中,发现这种算法有很多不尽如人意的地方,后来人们改进了NSGA算法的缺点,提出带精英策略的非支配排序遗传算法NSGAⅡ。目前来说,对于带精英策略的非支配排序遗传算法的研究,国外的理论研究与应用研究较为深入,相比在国内的研究较少。本文对算法的基本原理进行了系统的学习与研究,并将该算法用于解决一些实际的问题,利用NSGAⅡ在解决多目标优化问题方面有很多强大的优势,很好得解决了这些生活中的实际问题。本文主要进行了以下工作:（1）首先,介绍了进化多目标优化的产出背景和它的三个发展阶段;然后介绍了多目标优化的概念和相关术语,分析和总结了它目前常用的评价方法及其它的常用分类标准和分类方法;论述了常用的经典的多目标优化方法和进化多目标优化的基本框架。（2）论述了多目标优化遗传算法的研究现状,其中重点介绍了非支配排序遗传算法的情况。从多目标优化的理论与概念入手,论述了非支配排序遗传算法NSGA的基本原理和不足之处,并对其改进算法NSGA-Ⅱ提出的快速非支配排序法、拥挤度及其比较算子、精英策略和NSGA-Ⅱ的主要流程作了详细的研究。（3）设施选址问题作为现实中的多目标优化问题的典型,本文尝试用NSGA-Ⅱ算法去解决垃圾处理站设施选址问题和重大突发事件设施选址问题。对于前者,在分析了其多目标数学模型的基础上考虑了总成本最小和负效用最小两个目标函数,具体分析了并给出了NSGA-Ⅱ在设施选址中的具体运用过程,并给出了实例验证。对于后者,通过对重大突发事件特点的描述,以急救援设施服务需求区域的加权最大距离最小、权重越大的需求区域得到的应急服务最大化和应急救援设施服务需求点的加权距离最小化为三个目标函数,应用NSGA-Ⅱ算法求解,并给出了实例验证。实验表明,该算法能在短时间内得到Pareto最优解,具有很好的优化效果。仿真表明该算法是一种可行的、有效的解决多目标优化问题的方法。并探讨了NSGA-Ⅱ在其他方面的应用,此算法在解决多目标优化方面具有广阔的应用前景,希望能为决策部门提供决策依据。最后,总结了全文的工作,并对多目标进化算法的未来发展方向提出了一些设想。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 多目标优化问题综述
• 1.3 进化多目标优化算法的发展阶段
• 1.3.1 1985 年～1994 年的缓慢发展期
• 1.3.2 1994～2003 年的快速发展期
• 1.3.3 2003 年～现在的全面发展期
• 1.4 带精英策略的非支配排序遗传算法概述
• 1.5 本文的所做的工作及内容安排
• 第2章 进化多目标优化算法
• 2.1 多目标优化问题的产生与发展
• 2.2 多目标优化的基本概念和相关术语
• 2.2.1 多目标优化的定义
• 2.2.2 非支配解
• 2.3 进化多目标优化算法的性能评价
• 2.4 进化多目标优化算法的分类
• 2.5 经典的多目标优化方法
• 2.5.1 目标加权法
• 2.5.2 约束法
• 2.5.3 目标规划法
• 2.6 进化多目标优化算法的基本框架
• 2.7 本章小结
• 第3章 带精英策略的非支配排序遗传算法
• 3.1 进化算法概述
• 3.1.1 遗传算法的基本原理
• 3.1.2 遗传算法的主要步骤
• 3.2 非支配排序遗传算法（NSGA）
• 3.2.1 非支配排序原理
• 3.2.2 共享小生境技术（即NSGA 算法适应值计算）
• 3.2.3 算法流程
• 3.3 带精英策略的非支配排序遗传算法（NSGAⅡ）
• 3.3.1 上述非支配排序的伪代码如下
• 3.3.2 拥挤度
• 3.3.3 小生境和精英策略
• 3.3.4 NSGA-Ⅱ的算法流程
• 3.4 本章小结
• 第4章 NSGAⅡ在设施选址中的应用
• 4.1 选址问题
• 4.1.1 引言
• 4.1.2 选址问题的研究意义
• 4.1.3 选址问题的分类
• 4.2 NSGAⅡ在垃圾处理站选址问题中的应用
• 4.2.2 垃圾处理站选址的数学模型
• 4.2.3 垃圾处理站选址的NSGAⅡ的设计
• 4.3 NSGAⅡ在重大突发事件应急救援设施选址中的应用
• 4.3.1 常用的应急设施选址的模型
• 4.3.2 重大突发事件的特点
• 4.3.3 问题描述和模型建立
• 4.3.4 算法设计
• 4.3.5 算例验证
• 4.4 基于NSGAⅡ的其他设施选址方面的研究探讨
• 4.4.1 基于NSGAⅡ的物流配送中心设施选址问题的研究
• 4.4.2 基于NSGAⅡ的其他设施选址问题的研究
• 4.5 基于NSGAⅡ的其他方面的应用
• 4.6 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 攻读硕士期间（待）发表的论文
• 致谢