Evolutionary Algorithms For One Special Class Of Nonlinear Bilevel Programming Problem

Evolutionary algorithms are new kinds of modern optimization algorithms which are inspired by the principle of nature evolution. As new kinds of random search algorithms, they have some advantages such as global search ability, implicit parallelism, robustness, simple operation and so on.Bilevel programming problems (BLPPs) are nonconvex optimization problems with hierarchical 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. Since in real life we often encounter problems related to the ratio, especially the study of fractional bilevel programming problems is relatively rare, so the fractional bilevel programming research is of great practical significance.In this paper, considering the complexity of bilevel programming and the advantages of evolutionary algorithms, we apply evolutionary algorithms to solve a class of special nonlinear bilevel programming problems, and mainly focus is on the upper level problem being the linear fractional bilevel programming problem.Firstly, a genetic algorithm based on the simplex method is constructed to solve the linear fractional-linear bilevel programming(LFBP). By using the Kuhn-Tucker conditions of lower-level programming, the LFBP is transformed into a single-level programming. A new constraint-handling method and an objective-handling method are proposed. Thus, in our proposed genetic algorithm, only the linear programming is solved by the simplex method.Secondly, as a generalization of LFBP problem, we study a class of linear fractional-quadratic bilevel programming problem(LFQP), and apply the same idea to solve this kind of problem.Finally, numerical experiments are made and the results show that the proposed algorithms in this paper for a class of linear fractional programming problem are very effective.