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