GP-DEMO: Differential Evolution for Multiobjective Optimization based on Gaussian Process models

Highlights

• New surrogate-model-based evolutionary multiobjective algorithm GP-DEMO is proposed.

• New relations for comparing solutions under uncertainty are defined.

• Comparing solutions under uncertainty prevents wrongly performed comparisons.

• GP-DEMO in comparison to DEMO obtained similar results with less exact evaluations.

Abstract

This paper proposes a novel surrogate-model-based multiobjective evolutionary algorithm called Differential Evolution for Multiobjective Optimization based on Gaussian Process models (GP-DEMO). The algorithm is based on the newly defined relations for comparing solutions under uncertainty. These relations minimize the possibility of wrongly performed comparisons of solutions due to inaccurate surrogate model approximations. The GP-DEMO algorithm was tested on several benchmark problems and two computationally expensive real-world problems. To be able to assess the results we compared them with another surrogate-model-based algorithm called Generational Evolution Control (GEC) and with the Differential Evolution for Multiobjective Optimization (DEMO). The quality of the results obtained with GP-DEMO was similar to the results obtained with DEMO, but with significantly fewer exactly evaluated solutions during the optimization process. The quality of the results obtained with GEC was lower compared to the quality gained with GP-DEMO and DEMO, mainly due to wrongly performed comparisons of the inaccurately approximated solutions.

Introduction

Optimization problems are present in our everyday life and come in a variety of forms, e.g. the task to optimize certain properties of a system by correctly choosing the system parameters. Many of these optimization problems require the simultaneous optimization of multiple, often conflicting, criteria (or objectives). These problems are called multiobjective optimization problems. The solution to such problems is not a single point, but a family of points, known as the Pareto-optimal set. This set of solutions gives the decision maker an insight into the characteristics of the problem before a single solution is chosen.

One of the most effective ways to solve problems with more objectives is to use multiobjective evolutionary algorithms (MOEAs). MOEAs are population-based algorithms that draw inspiration from optimization processes that occur in nature. During the optimization process, in order to find a Pareto-optimal set, a lot of different solutions have to be assessed (evaluated). These solution evaluations can be costly, dangerous or computationally expensive. In such cases the goal is to minimize the number of exactly evaluated solutions, but still find the best solutions. In this paper we focus on computationally expensive problems, where one solution evaluation takes a lot of time.

In order to obtain the results of such an optimization problem more quickly (or even be able to obtain them in reasonable amount of time), we can use surrogate models in the optimization process to approximate the objective functions of the problem. To evaluate a solution, instead of using a time-consuming exact evaluation, a solution can be approximated with the surrogate model. Since one solution approximation is (much) faster, the whole optimization process can be accelerated. However, note that the time needed to create and update the surrogate models during the optimization process has to be considered and included in the whole duration of the optimization process. So, in the case where the exact solution evaluations are quick, it can happen that the surrogate-model-based optimization takes longer than the optimization without surrogates.

In surrogate-model-based multiobjective optimization, approximated values are often inappropriately used in the solution comparison. As a consequence, exactly evaluated good solutions can be discarded from the population because they appear to be dominated by the inaccurate and over-optimistic approximations. This can slow the optimization process or even prevent the algorithm from finding the best solutions.

Some surrogate models provide a distribution, from which the approximated value and also the confidence interval of the approximation can be calculated. Using this confidence interval, we define new dominance relations that take into account this uncertainty and propose a new concept for comparing solutions under uncertainty that requires exact evaluations only in cases where more certainty is needed. This minimizes the mistakes made in comparisons of inaccurately approximated solutions.

Based on this concept we propose a new surrogate-model-based multiobjective evolutionary algorithm, called Differential Evolution for Multiobjective Optimization based on Gaussian Process modeling (GP-DEMO). This algorithm is an extension of the Differential Evolution for Multiobjective Optimization (DEMO) algorithm (Robič & Filipič, 2005), which uses differential evolution to effectively solve numerical multiobjective optimization problems and, in addition, emphasizes the variation operators. In GP-DEMO, Gaussian Process (GP) modeling is employed to find approximate solution values together with their confidence intervals. Then, instead of comparing the solutions using the Pareto dominance relation, GP-DEMO uses the new uncertainty-based dominance relations, requiring exact evaluations of solutions as needed. The efficiency of GP-DEMO is assessed on several benchmark and two real-world optimization problems.

The structure of this paper is as follows. In Section 2, we overview the work done in the field of surrogate-model-based optimization, especially in multiobjective optimization. In Section 3, we describe the Gaussian Process modeling that is used to build the surrogate models in GP-DEMO. Then, in Section 4, we describe the new relations and methods for comparing solutions (presented with and without uncertainty). The GP-DEMO algorithm is presented in Section 5. In Section 6, we test and compare GP-DEMO with two other algorithms on benchmark and real-world multiobjective optimization problems. Finally, Section 7 concludes the paper with a summary of the work done and our ideas for future work.