Research On Estimation Of Distribution Algorithms For Bilevel Programming Problems

Bilevel programming problems(BLPPs)are a class of hierarchy optimization models with nested upper and lower level problems.In this model,both levels have their own objective functions and constraint conditions.In the process of optimization,the leader first makes its decisions and then the follower reacts under the decisions given by the leader.On one hand,the decisions made by the leader influence the optimization of the follower;On the other hand,the lower's response affects the upper's decision in return.Plentiful applications of this model in engineering problems enrich research results.However,it is non-convex and non-differentiable feature makes BLPPs extremely difficult to solve.Up to now,researches for BLPP mainly focus on some special small-scale problems,and there are few efficient algorithms for largescale ones.Estimation of distribution algorithm(EDA)takes distribution information of selected superior points into account sufficiently,requiring less computational cost,and it is easy to operate especially for discrete optimization.In this thesis,discretizing the search space by using optimality conditions,we design EDAs to deal with two types of bilevel programming problems,linear bilevel programming and linear fractional bilevel programming.Linear bilevel programming problem(LBP)is a simple bilevel program whose objective functions and constraints involved in the model are linear.However,there still lacks efficient algorithms for larger scale problems since it is non-convex and nondifferentiable with respect to leader's variables.The optimality conditions of the linear programming are adopted to design an EDA for solving this problem.Firstly,considering the features of the follower's program,we take the bases of the follower as individuals and search the base space with finite elements.Secondly,for each individual(base),we make use of the optimal and feasible conditions to obtain a solution function of the follower's program.By replacing the follower's variables in the leader's level,one can get a linear program associated with the leader's variables only.The optimal objective of the resulting linear program is taken as evaluation of this individual.Finally,we get the probability distribution of the individuals through a perturbation scheme,and new individuals are sampled from the distribution.Numerical computational results on examples illustrate the feasibility and efficiency of the proposed approach.Linear fractional bilevel programming(LFBP)is a kind of nonlinear bilevel optimization model,consisting of linear fractional objective functions and linear constraints.We design an EDA to solve this type of problems by means of the optimality features of the follower's problem.Firstly,we regard each base of the follower as an individual to search the base space having finite elements.Secondly,for each base fixed,we utilize the optimal conditions of the linear fractional program to achieve the solution expression of the follower's variables.As done in linear case,one can obtain a linear fractional program.The resulting problem is solved and the objective value is taken as the fitness of the individual.Finally,the distributed function is determined by a probability perturbation method and a local search method is presented when new individuals are generated.Numerical experiments illustrate the efficiency of the proposed algorithm.