A Hybrid Genetic Algorithm for Solving Nonlinear Bilevel Programming Problems Based on the Simplex Method

In this paper, a hybrid genetic algorithm is proposed for solving nonlinear bilevel programming problems (BLPPs). In order to improve the feasibility of the individuals, for each fixed leader-level variable x, the follower´s problem is solved to get its optimal solution y. Then, based on the simplex method, a new crossover operator is designed, in which the best individuals generated so far are employed to yield a good direction of evolvement. Furthermore, a penalty method is developed to deal with the leader-level constraints, in which the penalty parameter can be adjusted by considering the status of the individuals in the population. At last, when the follower´s problem has more than one optimal solutions for a fixed x, a selection scheme is given by solving a constructed single-level programming problem. The simulation on 20 benchmark problems demonstrates the effectiveness of the proposed algorithm.