Research On Bilevel Optimization Methods Based On Both Evolutionary Algorithms And Approximate Solution Techniques

Bilevel programming involves two optimization problems with a hierarchical nested structure,which are located at different levels.The constraint domain of the upperlevel optimization problem is implicitly determined by the lower-level optimization problem.The optimization of the upper-level objective plays a dominant role,however,the lower-level objective must be optimal with respect to the lower-level variables.Due to the hierarchical structure of the problem,the lower-level optimization problem needs to be frequently solved,which can accumulate a large amount of calculation.As a result,most of the present research only focus on linear,quadratic and other special types of bilevel programming problems.In order to overcome the shortcomings of current research,for the general bilevel programming problems,the thesis aims at reducing the calculation amount of the lower-level optimization procedure,and based on the problem characteristics,present evolutionary algorithms based on approximate solution technology.The proposed schemes efficiently improve the performance of evolutionary algorithm for bilevel programs,the main research achievements are as follows:For the general nonlinear bilevel programming problem,an evolutionary algorithm based on the approximation technique of the lower-level solution is developed.Firstly,a multi-population co-evolution mechanism is designed,and both the crossover and mutation operators are considered to balance the exploration and exploitation capabilities of the algorithm,respectively;Then,under the guidance of sensitivity analysis theory,an approximate evaluation method for new individuals is presented;In addition,according to the predetermined similarity threshold,only a few offspring individuals are selected to endure further accurate fitness evaluation,thus avoiding a large number of lower-level optimization procedures.Finally,the proposed algorithm is tested on widely used examples and compared with similar algorithms,the experimental results and analysis show that the algorithm can get better solutions than those in compared literatures.In transportation networks,the mathematical model of the toll setting problem can usually be expressed as a bilevel programming problem.The computational difficulty of this model is that the lower-level program is an integer programming problem,and there exist few efficient approaches among classical hierarchical optimization methods for this discrete optimization problems.In order to overcome the shortcomings,a new optimization method for the toll setting problem is presented by combining the evolutionary algorithm and the lower-level integer solution approximation technique.Firstly,for any offspring individuals generated by the upper-level variables,an approximate integer solution to the lower-level problem can be obtained by solving the relaxation problem as well as an additional constructed 0-1 program;Secondly,the fitness values of these offspring are approximately evaluated,and then only a few among these offspring need to be refined for the purpose of accurate evaluations according to a predetermined threshold of fitness,which can effectively reduces the number of solving the lower-level problem;In addition,the information of better individuals is used in the design of the crossover operator,which is expected to produce potential high-quality offspring.Finally,the performance of the algorithm is tested on a total of 10 cases from two transportation networks,and the experimental results show that the proposed algorithm can obtain a better toll revenue.