An adaptive evolutionary surrogate-based approach for single-objective bilevel optimisation

Authors

M. Antoniou,
P. Korošec,
G. Papa

Publication

Uncertainty Quantification and OPtimization UQOP 2019

Paris, France, 18-20 March, 2019

Abstract

Bilevel optimisation problem refers to a problem where one optimisation problem has another optimisation problem as constraint. The target of this problem is to find the optimum of the upper level problem, taking into consideration the optimality of the corresponding lower level. Despite this basic definition and idea, the problem introduces many challenges, as it is usually not following simplified properties such as convexity or continuity. Moreover, even the simplest case of a linear bilevel optimisation problems has been proved to be NP-hard.
<br/>
The research community so far was concentrated on tackling well-behaved bilevel problems with specific properties in order to be solved with classical methods. In recent years, hybrid and evolutionary approaches have become more popular. Metaheuristic and evolutionary algorithms do not need to make assumptions about the objective functions of the problem and therefore can become really useful for solving bilevel problems. On the other hand these algorithms require a large number of functions evaluations. The nested nature of the bilevel problems contributes even more in transforming the evolutionary approach in bilevel optimisation to a computationally expensive task. The cost worsens when the evaluations of the exact solution of the problems require calling time consuming tasks, e.g. Computation Fluid Dynamics (CFD) for engineering simulations.
<br/>
In this paper, we will attempt to approximate the upper level vector with the lower optimal solutions with Kriging as a surrogate model, an approach tested already in the some papers. The goal is to develop an adaptive Differential Evolution Algorithm (DE) in the upper level, where the parameter control will be done taking into consideration the evaluation of both levels. The population size of the upper level will be updated each time the expected approximation error is not acceptable and the model needs to be retrained. Moreover, a mutation and crossover adaptation strategy will be applied in the upper level optimisation algorithm. For the lower level optimisation, when exact solutions are needed to train the surrogate, a separate evolutionary algorithm (DE or Particle Swarm Optimisation) will be used. The expected outcome is to investigate the improvements that adaptive parameter control can bring to evolutionary surrogate assisted optimisation algorithm by finding good quality bilevel solutions with lower number of functions evaluations in a number of known benchmark test problems.

BIBTEX copied to Clipboard