A New Evolutionary Algorithm for a Class of Nonlinear Bilevel Programming Problems and Its Global Convergence

When the leader's objective function of a nonlinear bilevel programming problem is nondifferentiable and the follower's problem of it is nonconvex, the existing algorithms cannot solve the problem. In this paper, a new effective evolutionary algorithm is proposed for this class of nonlinear bilevel programming problems. First, based on the leader's objective function, a new fitness function is proposed that can be easily used to evaluate the quality of different types of potential solutions. Then, based on Latin squares, an efficient crossover operator is constructed that has the ability of local search. Furthermore, a new mutation operator is designed by using some good search directions so that the offspring can approach a global optimal solution quickly. To solve the follower's problem efficiently, we apply some efficient deterministic optimization algorithms in the MATLAB Toolbox to search for its solutions. The asymptotically global convergence of the algorithm is proved. Numerical experiments on 25 test problems show that the proposed algorithm has a better performance than the compared algorithms on most of the test problems and is effective and efficient.