Reseach On Algorithms For Solving Nonlinear Bilevel Programming Problems

The optimization problems exist in various fields of daily life such aseconomics, management, policy development, engineering design and etc, in whichthe decision-making optimization problem is one of the most attractive problems.The bilevel programming problem, an important class of optimization problem, is ofgreat significance and can be applied in a wide range of fields. The BLPP isnon-convex and non-differentiable, so it is very difficult to solve. As the simplestkind of BLPP, the linear bilevel programming has been proven to be NP-hardproblem. It has a lot of limitations when we use traditional algorithms to solve thiskind of problem, however, for some complex and high-dimensional problems, it ismore difficult to solve by using traditional algorithms. Without requiring thegradation information of objective functions, thus, it is more convenient to solvethese complex problems by using heuristic algorithm. The Biogeography-basedoptimization (BBO) algorithm is a heuristic algorithm which is based onbiogeographic habitat equilibrium theory. This algorithm, without the requirement ofthe differentiability of the objective function, the convexity of the search space andsome other conditions, has been widely applied to single-level optimization problem.So far, BBO algorithm is rarely used for solving BLPPs.For two specific types of the BLPPs, we designed hybrid BBO algorithms byusing the complex method and coordinate rotation method, respectively.The main work is summarized as follows:1. When the lower level problem is a liner programming problem on the lowervariables and the objective function of the upper level is non-convex andnon-differentiable, first, we transform the original bilevel programming problem intoa single-level optimization problem by replacing the lower-level linear programmingproblem by optimility conditions, so that solving the problem becomes much easier;then we designed a hybrid BBO algorithm based on simplex method and fourdifferent migration models. The proposed algorithm overcomes the low ability oflocal search of the original BBO algorithm, we implemented a complex method inorder to enhance the local search ability, increase the accuracy of solution, speed upthe rate of convergence. Moreover, the global cobvergence of the proposed algorithmwith probability one is proved. At last, the experimental results indicate that BBOalgorithm is an efficient and stable approach, and outperforms the compared algorithms.2. When the lower level is convex differentiable about the lower variable and theobjective function and constraint functions of the upper level are non-convex andnon-differentiable, first, the original BLPP is transformed into a single-leveloptimization problem by using optimility conditions (KKT conditions) to lower levelproblem. Then, using uniform design to generate the initial population, designingcrossover and selection operators, combining coordinate rotation method, andapplying a random mobility model, we put forward an improved BBO algorithm.Furthermore, we prove the global convergence of the proposed algorithm withprobability one. Finally, a great number of experimental results show that theproposed algorithm is efficient and stable, and performs better than the comparedalgoeirhms.