Genetic Algorithms For Two Special Classes Of Bilevel Programming Problems

With the fast development of science and technology in recent years, more and more decision making problems with the hierarchical structure have arisen in many fields. These problems finally become bilevel programming problems and result in more difficulty for decision makers. Bilevel programming problems are widely used in our life. Much attention has been paid to this field in recent years. However, the solution of bilevel programming is very difficult to get because of its non-convexity, NP-hard characteristic and non-differentiability. In particular, it is more difficult to get its global optimal solution. Genetic algorithms are a new kind of effective algorithms for complex optimization problems. They have no much restriction on related functions, such as differentiability, convexity, continuation and so on. Especially, for some large-scale complex nonlinear optimization problems, they are usually superior to traditional optimization approaches.Considering the difficulty of bilevel programming and the good performance of genetic algorithm, Genetic algorithms are applied to solve bilevel programming. The structure characteristic of bileve programming is fully considered in the process of solving the bilevel programming by adopting proper skills, such as decreasing the problem dimensions and search space. As a result, the speed of the genetic algorithms will be more quickly.In this thesis, first, for two special classes of bilevel programming problems, the optimal solution of the lower-level problem is represented by the upper-level variables or Lagrange multipliers, i.e., the lower-level variables are a function of upper-level variables. Then the bilevel programming problem can be transformed into a single-level optimization problem only containing the upper-level variables or Lagrange multipliers through replacing the lower-level variables by this function. Second, an improved convex crossover operator and a novel mutation operator are designed, respectively. Based on these, two new genetic algorithms are proposed for these two classes of bilevel programming problems, respectively. Moreover, the global convergence of the proposed algorithms is proved. At last, the experimental simulations are made and the results indicate the proposed algorithms are effective.