Research On Evolutionary Algorithms For Solving Complex Bilevel Programming Problems

In the fields of engineering and economic management,there often exist optimization models with different levels of decision-making,such problems are known as multi-level optimization problems,or hierarchical optimization problems,duing to its hierarchical decision-making process.When the problem only involves two-level decision-making,the corresponding optimization problem is called bilevel(two-level)programming.Bilevel optimization is a typical representative of multi-level hierarchical optimization problems.Its extensive practical application background and algorithm challenges has made it an important research field of optimization problems.Different from multi-objective optimization models,the decision makers of bilevel programming are at two different levels and this hierarchical structure always leads to problems non-convex and non-differentiable.Even though a linear bilevel programming problem,it is strongly NP-hard.These characteristics contribute to computational difficulty for traditional gradient-based optimization algorithms to find the global optimal solutions to the problems.Having global convergence,without additional requirement on convexity or differentiability of functions,evolutionary algorithm and other swarm intelligent optimization algorithms are increasingly used to solve bilevel programming problems.However,when the bilevel model involves multimodal functions,integer constraints and multi-objective optimization,the problem becomes more difficult to solve than ever and there are very few effective algorithms for such problems.The thesis starts with model processing and operator designation,and develops effective evolutionary algorithms for four types of complex bilevel optimization problems.The specific work is as follows:1.For the linear integer bilevel programming problem,an evolutionary algorithm based on gradient information is proposed.Firstly,for each decision variable value of the leader's problem,the relaxation solution of the follower's problem is obtained by solving the follower's relaxation problem.Secondly,using the wheel selection method to select some individuals for updating the follower's solutions,in this process a simplified branch and bound method is adopted.Finally,combined with the negative gradient of the leader's objective function,a heuristic crossover operator is designed to generate offsprings as well as possible.The experimental results show that the algorithm pays less computational cost than other compared algorithms.2.Combining simplified branch and bound algorithm and interpolation method,a memetic algorithm is proposed for solving nonlinear integer bilevel programming problems.First,the leader's decision variable values are taken as individuals in the initial population,and the follower's optimal integer solution can be obtained for each individual by solving the follower's programming problem.In addition,in order to avoid too frequently solving the follower's problem,the interpolation method is used to approximate follower's solutions.Finally,in the evolution process,the optimal integer solutions of the original problem can be obtained by updating follower's solutions of potential better individuals.Simulation experiments illustrate the effectiveness of the proposed memetic algorithm in dealing with nonlinear integer bilevel programs.3.Aiming at the complex nonlinear bilevel programming problem,an evolutionary algorithm embedded with a surrogate model is designed by using Trust-Tech technology as well as correlation coefficients.Firstly,the Isodata method is used to divide the initial population into several subgroups,and the correlation coefficients of individuals in each subgroup are determined according to the rank of the leader's and follower's objective functions.Secondly,for the offspring individuals generated by the evolution operator,the surrogate model is used to approximate the solutions to the follower's programming problem,and some points in the population can be selected in combination with the correlation coefficient.Finally,the Trust-Tech technology is used to search for the best solution in different subgroups,which helps to speed up the convergence speed of the evolutionary algorithm.The simulation experiment results show that the algorithm can effectively obtain the optimal solutions.4.For the multi-objective bilevel programming problem,an evolutionary algorithm based on the surrogate model is developed.Firstly,the uniform design is used to generate the weight vector,and the dynamic weighted sum method is embedded to transform the follower's multi-objective problem into several single-objective optimization problems.Secondly,for each leader's decision variable given,a surrogate model is presented and used to solve the transformed follower's programming problems,and the surrogate model can be improved self-adaptively.Finally,the mentioned-above technologies are embedded into MOEA/D,and the hybrid algorithm is used to obtain the Pareto solution set of the leader's problem.Simulation results show that these schemes can effectively improve the performance of MOEA/D when solving multi-objective bilevel programs.