Double Multi-objective Optimization Evolutionary Algorithm Problem

Bilevel programming problems are a class of hierarchical optimization problems,which are used in many areas extensively, such as economy and management andmilitary, etc. The problem is characterized by the fact that the constraint region ofone optimization problem is determined by the optimality of another, and isstrongly-NP. For a multi-objective optimization problem, there is more than oneobjective in the objective function and these objectives usually contradict with eachother. Bilevel multi-objective optimization involves at least one multi-objectivefunction in the leader’s and the follower’s objectives, with bilevel hierarchicalstructure as well as features of multi-objective optimization, making the problemhave important theoretic and practice values. However, on the other hand, the featuremakes the problem harder to solve. At present, there exist some transformingapproaches, such as K-K-T conditions, they convert bilevel model into a single-levelcase, and use single-level multi-objective optimization methods to deal withtransformed one. The shortcoming is that the efficiency of algorithms is alwaysdecreased due to adding too many variables. In this thesis, two classes of bilevelmulti-objective programming problems are discussed and the evolutionaryalgorithms are designed based on the feature of the problems.1. For bilevel programming problems with multi-objective function simply inleader’s level, following the assumption that the follower has a uniquesolution for each fixed leader’s variable value, an evolutionary algorithm isproposed based on NSGA-II and the interpolation technique. Firstly, somesample points are selected and the follower’s solution functions areapproximated by corresponding interpolation functions; Secondly, NSGA-IIis used to evolve the leader’s variable, and for each leader’s variable theoptimal solution of the follower can be obtained using interpolationfunctions. In order to obtain better approximation of the follower’s solutions,at each iteration a small number of better individuals are selected andmodified. The modified points are taken as new sample points to improvethe interpolation functions. Finally, in order to decrease the amount ofcomputation, a multi-criterion evolving process is given, which makes themodification of multiple points finished in one run of evolutionary algorithm.2. For bilevel programming problems with multi-objective functions in bothleader’s and follower’s levels, we deal with the follower’s objective byweighting all objective functions, in which the values of weight coefficientsare taken by the uniform design. Hence, the original follower’s problem isconverted into several single objective problems. In addition, The leadervariables is evolved by NSGA-II, and for each leader’s variable value, agroup of weights are taken and the corresponding optimization problem issolved. As a result, individuals in populations can be obtained. Thesimulation results show the proposed algorithm is feasible and efficient.