Research And Application Of Bilevel Optimization Based On Evolutionary Algorithms

Bilevel optimization has two levels of objectives which need to be optimized.The upper objective function determines the lower objective function,and the lower objective function affects the upper objective function.Every feasible solution of a bilevel optimization problem is determined,a lower optimization problem needs to be solved.Bilevel optimization models are used in many areas,such as economic,management,engineering,network and other large areas,or market management,stock trading,facility location,traffic planning and other small issues.However,due to the hierarchical structural features and its non-convex,non-differentiable functional properties,bilevel optimization is an NP-hard problem.At present,the difficulties and challenges in bilevel optimization are mainly focus on:(1)How to quickly pursue the optimal solution of the lower level optimization problem to reduce the computational complexity;(2)How to design an evolutionary algorithm for the upper level problem,which the convergence can be proved;(3)How to deal with the constraints of the bilevel optimization problem reasonably;(4)How to apply the existing bilevel optimization theory to specific practical problems.In order to overcome the difficulties,the research work in this paper is as follows:(1)A bi-level particle swarm optimization algorithm based on sphere mutation and dynamic constraint processing is proposed.The algorithm can quickly search for the optimal solution of the bilevel optimization problem with less function evaluation times and higher accuracy.Recently,with the improvement of computer performance,it has become more and more popular to solve bilevel optimization problems with evolutionary algorithms.Because evolutionary algorithms have no convex,differentiable and derivative requirements for bilevel optimization function,a bilevel particle swarm optimization algorithm is proposed in this paper.It combines some new operators and strategies to make the algorithm have better optimization effects.In order to ensure that the population has a priori advantage in the initial stage,a population preprocessing strategy based on quadratic poles is used to reduce the blindness of population initialization.In order to keep the diversity of the population,this paper designs a mutation strategy based on hypersphere,which makes the particle e-reach each position with probability.In order to reserve the particles which are close to the constraint boundary,a method combining dynamic constraint processing and fitness evaluation is designed to make the constraint processing smoother.In order to make the particle swarm optimization algorithm have a better search direction,this paper uses a local search strategy based on quadratic approximation function,which makes the current best particle more easily reaches the global optimal solution.In order to accelerate the lower level optimization,this paper designs a kind of RBF-guided particle swarm search strategy.The strategy can reduce the number of function evaluations for the lower particle swarm search.Finally,not only the convergence of the algorithm is analyzed,but also the corresponding comparative experiments are carried out.The experimental results show that the algorithm performs well for complex bilevel optimization problems with constraints.(2)The actual problem about video server deployment and traffic planning is fully studied,for which a bilevel optimization model is established and the new GA-based algorithm is designed.In an existing network topology,how to deploy video servers and plan the traffic paths from the servers to the consumer nodes to minimize the cost of server deployment and traffic bandwidth is a typical discrete bilevel optimization problem.The problem has a distinct hierarchical structure: each time a server deployment solution for upper-level problem is determined,its corresponding lower-level traffic path needs to be re-planned.For this practical problem,this paper establishes a bilevel optimization model and designs a new algorithm combining upper-level genetic algorithm and lower-level SPFA(Shortest Path Faster Algorithm)method.Finally,the experimental results show that the designed models and algorithms are effective for network topology of different scales.Through the algorithm design for continuous problems and the abstract modeling for discrete practical problems,this paper combines the theory of evolutionary algorithm to conduct a more in-depth study on the bilevel optimization problem and algorithm.These research results can provide some values for algorithm design and practical application of the bilevel optimization.