Research On Genetic Algorithms For Nonlinear Bilevel Programming Problems

Bilevel programming problems (BLPPs) are nonconvex optimization problems with hierarchial structure. The vast majority of the existing research works on BLPPs is concentrated on linear BLPPs and some special nonlinear BLPPs in which all of the functions involved are convex and twice differentiable. Few works are concentrated on the BLPPs involving nondifferential and nonconvex functions. In this dissertation, based on the characteristics of problems involved, GAs are proposed for solving several classes of nonlinear BLPPs, and the convergence of these algorithms is verified. Unlike the optimization technologies based on gradients, most of these proposed GAs do not require the convexity and differentiability on the leader's function. Furthermore, based on the simplex method and the exponential distribution, new crossover operators are designed to improve the efficiency of GAs. The main contributions of this thesis are as follows:1. For BLPPs in which the follower's problems are linear, two classes of problems are studied. One is that the leader's problem is convex and differentiable, whereas the other is that the leader's problem is nonconvex and nondifferentiable. For the first class of problems, the different bases of the follower's problems are applied to encode individuals in the population, and the optimality conditions are applied to transform the BLPP into a single level programming where the optimal value is taken as the fitness. The advantage of designing GA in this way is that the large scale BLPPs can be solved efficiently. For BLPPs with nonconvex and nondifferentiable functions, based on the dual programming of the follower's problem and the dual theorem, the region of the leader's variables is divided into several subregions, such that for all values of leader's variables in each subregion, the follower's problem has the same solution expression. Furthermore, GA is used to solve the leader's problems, in which a new crossover operator is designed based on the simplex method. An advantage of the proposed GA is the optimal solutions to the follower's problem can be obtained very easily without solving the follower's problem. As a result, the efficiency of GA is greatly improved.2. Two classes of BLPPs are studied, one is that the follower's problem is convex quadratic, while the other is that the follower's functions are convex. Also, in the two classes of BLPPs the leader's problems involve nonconvex and nondifferentiable functions. GAs are proposed for solving the two classes of problems, respectively, and the K-K-T conditions are applied to transform the original BLPPs into single level programming. Furthermore, in order to improve the feasibility of individuals in populations, some special techniques are adopted. For the first class of BLPPs, Lemke algorithm is used to obtain the follower' solutions; for the second one, a new constraint-handling scheme is given which can make infeasible points satisfy all equality and inequality constraints. Also, a method which can judge whether an individual is a solution of follower's problem is presented.3. Three classes of BLPPs with nonconvex follower's functions are studied. In the first one the follower's functions are separable with respect to follower's variables. In the second one the follower's objective is a special compound function. In the last one the follower's problem is generalized concave. First, for these three classes of BLPPs, the solution methods to the follower's programming are presented. For the first class, the follower's solutions are obtained by decomposing the follower's programming into univariate optimization problem. For the second one, based on the characteristics of the follower's objective, the follower's programming is decomposed into several convex programming, and the optimal solutions can be obtained by solving at most two of these convex programming problems. Note that the solutions to a concave programming can be obtained at one of extreme points of the feasible region, the follower's problem of the last class can be solved by comparing the objective values at all extreme points. To solve the leader's problem, GAs are adopted and the best individuals are used to design new crossover operators.4. For the nonlinear BLPPs in which the follower's problems can be solved, an interpolation-based GA is proposed. The solution function of the follower's programming is approximated by its interpolating function, that is, the solutions to follower's programming can be approximately obtained by the interpolation. It avoids solving a large number of the follower's programming, as a result, the amount of computation is greatly decreased.5. Three classes of mixed-integer nonlinear bilevel programming problems are studied. In the first one, the follower's function is separable with respect to the follower's integral variables. In the second one, the follower's function is convex if the follower's variables are not restricted to integers. In the last one, the follower's function is polynomial with respect to integer variables. First, the solution methods are given for each follower's programming mentioned above, respectively. For the first one, the follower's problem is solved by making use of the convexity or concavity of the objective function. According to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower's programming for the second class of problems. For the last one, a continuity technique is used to transform the follower's mixed-integer problem into a linear programming(LP). Then, based on the exponential distribution, a new crossover operator is designed, and GAs are proposed for solving these three classes of BLPPs, respectively.6. For all of the proposed algorithms, the convergence is analyzed.