Chinese Journal of Computers   Full Text
Title	An Interpolation Based Genetic Algorithm for Solving Nonlinear Bilevel Programming Problems
Authors	LI He-Cheng1),2) WANG Yu-Ping1)
Address	1)(School of Computer Science and Technology, Xidian University, Xi’an 710071) 2)(Department of Mathematics Science, Xidian University, Xi’an 710071)
Year	2008
Issue	No.6(910—918)
Abstract &   Background	Abstract Nonlinear bilevel programming problems are hierarchical optimization problems. For each fixed value of leader’s variables the existing algorithms are required to solve the follower’s optimization problem to obtain a feasible point for the whole problem, which results in a large amount of computation. Note that in the existing research works, the condition that the follower’s optimal solution is unique for each leader’s variable value is usually adopted. This condition means that each follower’s variable can be seen as a function of the leader’s variables although this function is unknown. Based on this observation and to avoid solving the follower’s problem frequently, a different skill from that of the existing works is used to tackle this difficulty, i.e., the interpolation functions are adopted to approximate these unknown functions. First, the values of the interpolation function are gotten by solving the follower’s problem for some given leader’s variable values (i.e., the interpolation points), and the interpolation polynomials (functions) are calculated by using these interpolation points. Then, the follower’s variables can be replaced by the corresponding interpolation polynomials in the leader’s problem. As a result, the original nonlinear bilevel programming can be approximated by a single-level programming. Finally, a specifically designed genetic algorithm is proposed for the single-level programming, and the interpolation points and the corresponding interpolation functions are adaptively modified and updated during the evolution so that the optimal solutions of the single-level programming can well approach to those of original nonlinear bilevel programming. Moreover, the computation amount will be decreased. The simulations on 25 test problems indicate the proposed algorithm can find the best solutions with a relatively small amount of computation for these test problems. Keywords nonlinear bilevel programming; interpolation polynomials; genetic algorithm; optimal solutions Background The bilevel programming problem(BLPP) can be viewed as a static version of the noncooperative, two-person game introduced by von Stackelberg in the context of unbalanced economic markets. It has a wide variety of applications, such as network design, transport system planning, and management and economics. As an optimization problem with hierarchical structure, bilevel programming problem is intrinsically hard. It is therefore no surprise that most algorithmic research to date has focused on the linear version of the problem. For nonlinear BLPP, most of the existing algorithms can yield a local minimum only. For some specific nonlinear BLPP, for example, all functions in BLPP are twice differential and convex, etc, a few procedures have been proposed to find a global minimum. In recent years, evolutionary algorithm has been developed to solve nonlinear BLPPs with nondifferential and nonconvex objective functions, but in order to obtain feasible points in the populations, for each value of leader’s variable, one has to optimize the follower’s problem. The process causes a large computational amount. In this paper, authors proposed a new genetic algorithm based on interpolation polynomials, in which the follower’s solution functions are given approximately by the interpolation polynomials with respect to leader’s variables. It means one can obtain follower’s approximately optimal solution only by computing the values of interpolation polynomials at leader’s variable value given. As a result, the computational amount is decreased. The experimental results also show that the proposed algorithm can find the best solution with less computation and evolving time. This work was supported by the National Natural Science Foundations of China (60374063).