Research On Evolutionary Algorithms Using Approximate Evaluation Techniques For Bi-level Programming Problems And Its Application

Many optimization problems involve the hierarchical distribution of two levels of decision problems in a decision-making structure,such as investment portfolio,transportation management,national defense security problems,etc.Such problems with hierarchical conflict but interrelated relationship are called bi-level programming,which is a hierarchical optimization problem in essence.In a bi-level programming problem,one optimization task is nested in another optimization task,and this kind of hierarchical structure makes the problem difficult to solve.Such problems are strongly NP-hard.Most of the existing algorithms are only suitable for bi-level programming problems with a small number of variables or special types of functions such as linear,quadratic,convex and so on.As the development of big data technology,both the variable dimension and complexity of bi-level programming problems also increase.It is very difficult for most of existing methods to obtain the globally optimal solution to the problem,and these approaches always spend a lot of computational cost.In order to deal with these problems,in this thesis,a new hybrid optimization algorithm is developed based on the classical evolutionary algorithm framework,in which evolutionary operators are improved and some approximate evaluation technologies are combined.For the portfolio problem with cardinality constraints,the corresponding solution algorithm is given according to the characteristics of the problem.Main works are as follows:For general bi-level programming problems,a hybrid optimization algorithm is proposed by improving the operators of the evolutionary algorithm and designing a stepwise approximate evaluation technique.In the proposed algorithm,the priority principle as well as the inducible region is adopted,and a relaxation problem,composed of the upper-level objective function and all constraint functions,is solved based on a stepwise approximation scheme.During the procedure,only a small number of the relaxation solutions are selected and further updated by solving lower-level problems for updating,and the optimal solution can be obtained by the approximate evaluation technique.The proposed algorithm is simulated on two test sets,and the experimental results show that the algorithm can obtain the optimal solution of the bi-level optimization problem with less evaluation times.In the portfolio problem,a bi-level programming model is composed of Sharpe Ratio model and Mean-Variance portfolio model with cardinality constraints.The model involves hierarchical structure and integer constraints,which always causes a lot of computational cost.In this thesis,a bi-level optimization method based on the evolutionary algorithm and an approximate evaluation technology is proposed.Firstly,an approximate evaluation strategy is presented and applied to deal with the simplified lower-level problem,which can reduce the computational costs caused by lower-level optimizations.Secondly,crossover and mutation operators are designed by using heuristic information to improve the convergence and diversity of the populations.Finally,simulation experiments were carried out on five real data sets with different scales,and the experimental results verify the effectiveness and robustness of the proposed method.