基于进化算法的双层优化问题研究及应用

论文摘要

双层优化有着上下两层目标需要去优化,上层决定下层,下层影响上层,每确定一个双层优化问题的可行解,都需要求解一个下层优化问题。无论是经济、管理、工程、网络等这些大领域,还是市场营销、股票买卖、设施选址、流量规划等这些小问题,都无不体现着双层优化的应用价值。然而由于双层优化层级化的结构特征,以及非凸、不可微等函数性质,导致其是一种NP-hard问题。目前双层优化存在的挑战主要有:（1）如何快速追寻下层优化问题的最优解以减少计算复杂度;（2）对于上层优化问题,能否设计一个收敛性可证的进化算法;（3）如何合理处理双层优化问题的约束条件;（4）能否将现存的双层优化理论应用到具体的实际问题中去。为了解决以上问题,本文的研究工作有:（1）提出了一种基于球变异和动态约束处理的双层粒子群算法,该算法能以较少的函数评估次数,较高的精度,快速追寻到双层优化问题的最优解。近来随着计算机性能的提升,使用进化算法来求解双层优化问题已成为学术研究热点。鉴于进化算法对于双层优化没有可微、可导等函数特性要求,本文提出了一种双层粒子群算法,并融合了一些新的算子和策略使得算法具有更好的寻优效果。为了种群在初始化阶段就有一定先验优势,本文使用了一种基于二次极点的种群初始化策略,减少了种群初始化的盲目性;为了保持种群的多样性,本文设计了基于超球面的变异算子,使得粒子到空间每一个位置以概率?可达;为了保证靠近约束边界的潜力不可行解在进化前期不被错过,本文把动态约束处理的策略与适应度评价相结合,使得约束的处理更加精细;为了让粒子群算法具有更好的寻优方向,本文使用了一种基于二次近似函数的局部搜索策略,使得当前最好粒子更容易到达全局最优解;为了加速下层优化,本文设计了一种RBF（Radial Basis Function）指导的下层搜索策略,其降低了下层粒子群搜索的函数评估次数。最后理论分析了算法的收敛性,并进行了实验,结果表明对于带约束的复杂双层优化问题,该算法寻优性能良好。（2）研究了视频服务器部署以及流量规划这类实际中存在的双层优化问题,建立了模型并设计算法进行求解。在一个现存的网络拓扑结构中,如何安置视频服务器,并规划服务器到消费节点的流量路径,使得服务器部署费用和带宽租赁费用最少,这是一个典型的离散性双层优化问题。该问题有着分明的层级结构:每确定一种上层服务器的部署方案,就需要重新规划其对应的下层流量路径。针对这一实际问题,本文建立了双层优化模型,并设计了一种上层遗传算法与下层SPFA（Shortest Path Faster Algorithm）增广路径扩流相结合的算法来求解。最终实验结果表明,对于不同规模的网络拓扑结构,所设计的模型和算法是有效的。通过连续性问题的算法设计和离散性实际问题的抽象建模,本文结合进化算法理论,对双层优化问题和算法展开了较为深入的研究。这些研究成果,能够为双层优化的算法设计和实际应用提供一定的参考价值。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 选题背景和意义
•   1.2 国内外研究现状
•     1.2.1 问题研究
•     1.2.2 算法研究
•   1.3 研究内容与创新
•   1.4 论文安排
•   1.5 本章小结
• 第二章 基础知识简介
•   2.1 双层优化模型
•   2.2 粒子群算法
•     2.2.1 PSO算法模型
•     2.2.2 PSO算法步骤
•     2.2.3 PSO在双层优化中的应用
•   2.3 遗传算法
•     2.3.1 编码
•     2.3.2 初始化种群
•     2.3.3 交叉
•     2.3.4 变异
•     2.3.5 选择
•     2.3.6 算法的终止
•     2.3.7 GA算法流程
•     2.3.8 GA在双层优化中的应用
•   2.4 本章小结
• 第三章 基于球变异和动态约束处理的双层PSO算法
•   3.1 新提出的算法（BPSO-QMDC）
•     3.1.1 算法框架
•     3.1.2 球变异PSO
•     3.1.3 基于极点的种群初始化策略
•     3.1.4 基于二次近似的局部搜索
•     3.1.5 约束处理以及适应度函数
•     3.1.6 RBF指导下的下层搜索改进策略
•   3.2 算法收敛性分析
•   3.3 实验以及结果分析
•     3.3.1 实验及参数设置
•     3.3.2 结果及分析
•   3.4 本章小节
• 第四章 基于遗传算法的视频服务器部署问题研究
•   4.1 背景知识介绍
•     4.1.1 问题背景
•     4.1.2 研究回顾
•   4.2 问题描述及建模
•     4.2.1 问题描述
•     4.2.2 双层优化模型的建立
•   4.3 算法设计
•     4.3.1 上层GA选址
•     4.3.2 下层SPFA流量规划
• SPFA算法流程'>    4.3.3 GA_SPFA算法流程
•   4.4 实验及总结
•   4.5 本章小节
• 第五章 总结和展望
•   5.1 研究总结
•   5.2 未来展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 赵龙

导师: 魏静萱

关键词: 粒子群算法,进化算法,遗传算法,双层优化,流量规划,最小费用最大流

来源: 西安电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 西安电子科技大学

分类号: TP18;O224

DOI: 10.27389/d.cnki.gxadu.2019.001670

总页数: 77

文件大小: 2188K

下载量: 157