求解特殊双层规划问题的遗传算法

摘要

对双层规划问题进行算法研究具有现实意义和应用前景，近年来受到众多领域的广泛关注。双层规划问题是一类具有递阶结构的非凸优化问题，双层规划的非凸性和不可微性给其数值求解带来了极大的困难，特别是求解非线性双层规划问题的全局最优解更加困难。遗传算法是一种解决复杂非线性优化问题的新型的有效方法，它不受目标函数的可微性、凸性、连续性等限制。具有全局优化、隐并行性、鲁棒性强、操作简单等特点。
　　 本文主要分析了双层规划的复杂性和遗传算法的优点，用遗传算法来求解双层规划问题。主要研究两种类型的双层规划问题，一类是下层为凸二次规划的双层规划，一类是灰色双层线性规划。
　　 首先，对下层是凸二次规划这一特殊结构的非线性双层规划问题，将下层的最优解用上层的决策变量或者Lagrange乘子来表示，并将下层的最优解带入到上层，把双层规划问题转化为含上层决策变量和Lagrange乘子的单层规划问题，设计一个改进的变异算子和一个局部搜索算子，提出一种混合遗传算法。大量的数值实验结果验证了算法的有效性。
　　 其次，对灰色双层线性规划进行了研究。提出了定位区间的概念和满意度计算的新方法，并对其性质进行了研究，根据灰色双层线性规划的特性，改进了种群初始化方法和适应度值计算方法，对灰色双层线性规划解的情况进行了初始判断，设计一个新的遗传算法求解。最后给出一个例子，说明算法的可行性。