基于近似技术的双层规划进化算法

双层规划涉及上层和下层两个最优化问题，上层规划问题的约束域由下层规划问题隐式确定，双层优化以上层目标为主，而下层目标在下层变量方面必须达到最优。双层规划问题的递阶结构使其具有很高的计算复杂度，特别是频繁计算下层问题会累计很大的计算量。为了有效求解这类问题，提出一种基于近似技术的进化算法。首先，采取多种群协同进化，分别利用交叉和变异算子平衡算法的开采和勘探能力；其次，基于灵敏度分析理论，设计了新个体的近似评价方式以减少算法的下层求解次数。一个算例的近似效果演示结果表明，由近似技术得到的近似后代个体与精确后代个体的位置大部分是重合的。除此之外，在10个常用算例上的结果显示，所提算法比多值映射算法获得了更好的最优解；并且根据CPU时间比较，说明近似技术有效地提高了找到最优解的速度，减少了运行时间，验证了所提算法采取的近似技术的有效性。

Evolutionary algorithm based on approximation technique for solving bilevel programming problems

Bilevel programming involves two optimization problems located at upper-level （leader） and lower-level （follower）. The constraint domain of the leader is determined by the follower implicitly， the leader objective dominates in a bilevel optimization procedure， and the follower objective must be optimized with respect of the follower variables. The hierarchical structure of the bilevel optimization problem causes large computational complexity. Especially， the frequent computations of the follower can accumulate a large amount of computational cost. In order to solve this kind of problem effectively， an evolutionary algorithm based on approximation technique was developed. Firstly， a multi-population co-evolution approach was applied， and the crossover and the mutation operators were used respectively to balance the exploitation and exploration capabilities of the algorithm. Secondly， based on the sensitivity analysis theory， an approximation evaluation method for new individuals was designed to reduce the computation frequency of the follower carried out by the algorithm. The demonstration results of the approximate effect of a numerical example show that most positions of the approximate offspring individuals and the exact offspring individual are mostly coincident. In addition， the results on 10 common examples show that the proposed algorithm can find better optimal solutions than the multi-valued mapping algorithm. CPU time comparison shows that the approximate technique improves the speed of finding the optimal solution effectively， thereby reducing the running time. Therefore， the effectiveness of the approximate technique adopted by the algorithm is demonstrated.