Genetic Algorithms For Two Classes Of Linear Fractional Bilevel Programming Problems With Interval Coefficients

In many practical problems, because of uncertain factors, some indices are not clear or difficult to determine except for range or rule of values, which means that the problems are often uncertain. This kind of problems is called uncertainty optimization problems, and the optimization problem with interval coefficients is typical one of all uncertainty optimization problems. Bilevel programming is a kind of hierarchical optimization problem, consisting of upper level and lower level programs. Both the upper level and the low level problems have their own constraint conditions, decision variables and objective function. The upper level problem is decided by both the upper level variables and the lower variables, and the lower level problem is determined by the lower level variables with upper level variables as parameters. Because of the inherent complexity, the bilevel programming problem with interval objective coefficients is rarely considered in existing literature. This thesis discusses two types of linear fractional bilevel programs with interval coefficients, and designs genetic algorithms to solve the optimal solutions to corresponding problems, respectively.1.For a class of bilevel programming problems with interval coefficients, in which the upper-level problem is linear, whereas the lower-level problem is a linear fractional program, we present a genetic algorithm by taking the coefficient intervals as the search space. Firstly, individuals can be gotten by encoding the lower-level objective coefficients such that the original problem can be transformed into certain bilevel programs for each encoded individual; In addition, the optimality results are used to solve these certain problems; Finally, the best and the worst solutions can be obtained by evolving the coefficients of the lower level objective. The simulation results show that the proposed algorithm is feasible and efficient.2.For a class of bilevel programming problems, in which the upper-level problem is a linear fractional program with interval objective coefficients, whereas the lower-level problem is linear, a genetic algorithm with four fitness functions is presented. Firstly, four certain programs can be gotten by taking upper-lower bounds of the coefficient intervals of the upper level objective; In addition, the characteristics of these four problems as well as the optimality conditions of linear programming are used to design a genetic algorithm which takes four objective functions as evaluation, and the best and the worst optimal solutions can be obtained by using the proposed algorithm. Finally, the simulation results show that the proposed algorithm is feasible and efficient.