Genetic Algorithms For Solving Two Types Of Linear Fractional Bilevel Programming Problems

Bilevel programming problems are hierarchical optimization problems, whichcontains one upper level optimization problem and one or more lower level opti-mization problems. The upper and lower levels have their own objective functionsand constraints, the objective function and constraints of the upper level not on-ly relate to the upper level decision variables, but also depend on the optimalsolution to the lower level problem. In the past decades, the theories, methodsand applications of bilevel programming have made great development, and ithas become a new important branch to mathematical programming problems.Genetic algorithm has been developed by simulating the biological evolutionand the principles of genetics as an optimization algorithm, which does not playany restriction on the continuity and the diferentiability of functions. In addition,genetic algorithm has implicit parallelism and global search capability, which canautomatically obtain and adjust the search direction and has strong robustnessto various optimization problems.Firstly, the basic conceptions of the bilevel programming and genetic algo-rithm are described in detail, including the background, characteristics, algo-rithms and applications of bilevel programming problems, the development andframe of the genetic algorithm.One of the main results of this thesis is that a class of bilevel programmingproblems is discussed, in which the leader is fractional whereas the follower hasmore than one linear programing. To solve this problem, a genetic algorithmbased on a new encoding scheme is proposed. Firstly, the dual theory is appliedto convert the original problem to a single level program; Secondly, all individ-uals are encoded by considering potential vertices of the feasible region of thefollower’s dual problem. Further, for each individual given, the values of dualvariables can be obtained, which makes the nonlinear constraints removed fromall constraints; Finally, the resulting linear fractional programming is solved andthe value of the objective function is taken as the fitness of this At first, based onthe optimality of the linear fractional programming problem, that is, the optimal solution can arrive on some extreme point of the constraint domain, a discreteencoding scheme is adopted. In addition, for each individual, the follower vari-able can be represented as a function of the leader’s variables; further, in theleader’s problem all follower’s variable is replaced by this function. When theleader’s problem simply involving the leader’s variables is solved, the objectivevalue is taken as the fitness evaluation of the individual. Finally, all individualsin populations are sorted according to fitness values, and the feasibility of thebest one is verified by solving a linear programming. If the best is not feasible,then the second one is considered until the feasible individual is found. When thetermination criterion is satisfied, the best feasible point is output. The simulationresults show that the proposed algorithm is feasible and efcient. individual.The other main result is that an efcient genetic algorithm for linear frac-tional bilevel programming problem is developed.