Research On Algorithms For Solving Two Special Classes Of Bilevel Programming Problems

Bilevel programming is a nested optimization problem, and it has very importantpractical significance and application value. Since bilevel programming problem(BLPP) is non-convex and non-differential, thus, it is very difficult to solve. The linearbilevel programming, as the simplest kind of BLPP, has been proved to be NP-hardproblem, and the traditional algorithms are not good at solving this kind of problem.Without requiring differentiability of the objective functions, gradient information andsome other conditions, evolutionary algorithms, such as, genetic algorithm, ant colonyalgorithm, particle swarm optimization algorithm, have attracted a lot of attention forsolving BLPPs. As a novel evolutionary algorithm, estimation of distribution algorithm(EDA) combines the evolutionary algorithms and statistical learning, and it not onlyinherits the advantage of evolutionary algorithm, but it also improves someshortcomings of evolutionary algorithm itself by statistical learning, which has been animportant method for solving complex and non-differential problems. Up till now,EDAis seldom used for solving BLPPs.Based on the original EDA, introducing uniform design, crossover operator andorthogonal crossover operator, we propose two classes of improved EDA method tostudy the solution of two special classes of BLPPs. The main research works can besummarized as follows:1. For the quadratic-linear BLPP, first, we transform the original BLPP into asingle-level optimization problem by using the simplex optimal equivalent conditions.Then, based on the original EDA, using uniform design to generate the initialpopulation, introducing a kind of crossover operator which uses the optimal individualpopulations to cross, we put forward an improved EDA method, and the convergenceof the proposed algorithm is also proved. Using uniform design to generate initialpopulation, it guarantees the population diversity. Introducing crossover operator, itenhances the local convergence of the algorithm, ensures the evolution of population ina good direction and speeds up the rate of convergence. Processing the new generatedindividual beyond the boundary, it ensures the quality of the individual. Finally, theexperimental results indicate that the proposed algorithm is effective. Moreover, incontrast to the original EDA, the improved EDA is more stable and its convergencespeed is faster.2. For the fractional-fractional BLPP, first, we change the original problem into a BLPP that lower level problem is a liner programming problem on the lower variablesvia equivalent deformation. Then, using uniform design to generate initial population,introducing orthogonal crossover operator, processing the new generated individualbeyond the boundary, we propose a novel improved EDA method. The proposedalgorithm overcomes the low ability of local search of the original EDA method,enhances the local search ability and speeds up the rate of convergence. Furthermore,we prove the convergence of the proposed algorithm. Finally, the experimental resultsshow that the proposed algorithm is effective. Compared with the original EDA, theimproved EDAis more stable and its convergence speed is faster.