复杂双层规划问题的高性能可信进化算法研究

双层规划问题是一类具有主从递阶结构的优化问题，其特点是一个优化问题的约束域由另一个优化问题决定.当双层规划问题含有非凸不可微函数或问题规模较大时，求解难度极大，称之为复杂双层规划问题.这类问题在工程实践和经济管理领域广泛出现，但现有的算法大部分只对小规模且凸的简单双层规划有效，对复杂问题往往很难找到全局最优解或根本无法求解.因此研究这类问题，寻找高效可信的算法是十分必要的.. 本项目研究求解复杂双层规划的高效且收敛可控的进化算法，即高性能可信进化算法.首先对复杂问题进行分类研究，利用该类问题本身的特点设计算法.通过挖掘并利用问题解的特点，特别是最优性结果，减少算法的计算量；其次在算子的设计中融入统计和近似计算技术，提高算法的搜索效率；最后利用随机过程理论对提出的进化算法进行收敛性分析，给出算法的可靠性度量，使计算过程和计算结果可信.这些研究结果将有效弥补目前双层规划问题算法的不足.

双层规划是一类具有主从递阶结构的非凸不可微优化问题，广泛出现于工程实践和经济管理领域。当双层规划问题中含有非凸不可微函数、整数变量或问题的规模较大时，求解难度很大。存在的大部分算法对该类问题最优解的搜索效率不高。为了探索这类复杂问题的有效解法，我们选择以具有全局搜索性能的进化算法为框架，针对问题的不同类型，设计了基于问题结构特征的有效算法。首先，对于含有非凸不可微函数的非线性双层规划问题，设计了一个递阶协同进化算法，该算法对上下层函数均无可微和凸性要求；针对下层问题是线性、二次等类型，分别给出了基于上层变量和下层基混合编码的进化算法。这些算法对上层函数无可微和凸性要求。其次，对于大规模双层规划问题，研究了线性、线性—二次、凸二次、分式—多线性下层等类型的双层规划问题，利用单纯形算法的最优性条件、K-K-T转化和强对偶定理，设计了基于下层问题可行基编码的进化算法，并给出了部分算法的收敛性分析。这类算法的设计方式使得搜索空间变为有限集，从而使得算法能有效求解较大规模问题。第三，对于含有整数变量的双层规划问题，提出了递阶式搜索的协同进化算法。对于下层为混合整数线性规划的情形，给出了基于下层最优性条件验证的遗传算法，并证明了算法的收敛性。除了上述类型外，还讨论了多目标双层规划、弱双层规划和区间系数双层规划问题，分别设计了基于插值近似技术、对偶条件和区间系数编码的进化算法。项目研究的问题基本涉及双层规划问题的大部分常见类型，在算法设计中，对问题最优性条件及问题结构的利用，有效地提高了算法的计算效率。研究结果不仅补充了双层规划问题的算法体系，而且对解决相关实践问题有一定的促进作用。