Informatica 39 (2015) 459-460 459
Evolutionary Multiobjective Optimization Based on Gaussian Process Modeling
Miha Mlakar
Department of Intelligent Systems, Jožef Stefan Institute Jamova 39, Ljubljana, Slovenia
Keywords: multiobjective optimization, evolutionary algorithms, surrogate models, relations under uncertainty Received: October 16, 2015
This paper presents a summary of the doctoral dissertation of the author, which addresses the task of evolutionary multiobjective optimization using surrogate models.
Povzetek: Prispevek predstavlja povzetek doktorske disertacije avtorja, ki obravnava večkriterijsko evolucijsko optimizacijo z uporabo nadomestnih modelov.
1 Introduction
The optimization problems where simultaneous optimization of multiple, often conflicting criteria (or objectives) is needed, are present in everyday life and can be found in various fields. One of the most effective ways of solving multiobjective optimization problems is to use multiobjective evolutionary algorithms (MOEAs) [1]. MOEAs are population-based algorithms that draw inspiration from optimization processes that occur in nature. In order to find a Pareto-optimal set, a lot of different solutions have to be assessed (evaluated) during the optimization process. For some optimization problems these solution evaluations can be computationally expensive and a single solution evaluation takes a lot of time. In order to obtain the results of such an optimization problem more quickly (or obtain them in a reasonable amount of time), we can use surrogate models in the optimization process. A surrogate model is constructed based on modeling the response of the simulator from a limited number of previously exactly evaluated solutions. Then instead of using a time-consuming exact evaluation, a solution can be approximated with the surrogate model. Since an individual solution approximation is (much) faster, the whole optimization process can be accelerated.
However, the use of the surrogate models in optimization can also have a drawback. If the optimization problem is very complex and therefore hard to model, the surrogate models can be imprecise and the solutions approximated with these models can be inaccurate. As a consequence, this can slow the optimization process or even prevent the algorithm from finding the best solutions.
When approximating solutions, some surrogate models, in addition to the approximated values, provide also a confidence interval of the approximation. This confidence interval indicates the region in which the exactly evaluated solution should appear. The confidence interval width indicates the certainty of the approximation. If the confidence interval is narrow, we
can be more certain about the approximation and vice versa.
The solutions represented with confidence intervals, where exact objective values are unknown, are called solutions under uncertainty. Since the uncertainty offers additional information, it can be effectively used when comparing solutions. In the doctoral dissertation [2], we defined new relations under uncertainty that consider also the confidence intervals to reduce the possibility of incorrect comparisons due to the inaccurate approximations. The relations under uncertainty are described in more details in Section 2.
Based on the relations under uncertainty, we proposed a new surrogate-model-based multiobjective evolutionary algorithm called Differential Evolution for Multiobjective Optimization based on Gaussian Process modeling (GP-DEMO). The algorithm and its comparison to other algorithms is described in Chapter 3.
2 Relations for comparing solutions under uncertainty
If the solutions are represented with the approximated values and confidence intervals for each approximation, the standard Pareto dominance relations are not suitable and must be adapted to accommodate the uncertainty. In order to be able to compare the solutions represented in this way, the relations between the solutions under uncertainty are defined on the bounding boxes (BBs) of their objective values [3]. From the vectors of the approximated values (z) and the confidence intervals (e), the bounding box is designed as shown in Figure 1.
The relations under uncertainty were defined for constrained and unconstrained optimization problems and they cover all possible cases that can occur when comparing solutions under uncertainty.
460 Informática 39 (2015) 459-460
M. Mlakar
Figure 1: The bounding box of an objective vector.
To check, if the use of the proposed relations under uncertainty reduces the possibility of incorrect comparisons due to the inaccurate approximations, we compare them with Pareto dominance relations. The comparison was performed with various surrogate models and on different benchmark problems. The results shower that relations under uncertainty reduce the possibility of incorrect comparisons.
3 The GP-DEMO algorithm
As shown in the previous chapter, the use of new relations under uncertainty reduces the possibility of incorrect comparisons of inaccurately approximated solutions. So we decided to design a new surrogate-model-based optimization algorithm called GP-DEMO with relations under uncertainty used for comparing solutions [4]. This algorithm is an extension of the Differential Evolution for Multiobjective Optimization (DEMO) algorithm [5], which uses differential evolution to effectively solve numerical multiobjective optimization problems. As a surrogate model Gaussian Process modeling is employed to find approximate solution values together with their confidence intervals. As GP-DEMO works on the same principles as DEMO, the quality of its results is expected to be similar to the results of DEMO, but with fewer exact solution evaluations. To thoroughly test the GP-DEMO algorithm, we compare it with another surrogate-modelbased algorithm (GEC) and with DEMO on several benchmark and two real-world optimization problems.
The results showed that GP-DEMO and DEMO obtain similar results, but GP-DEMO needs less exact evaluations and thus has shorter optimization time on real-world problems. In comparison to GEC, GP-DEMO obtained better results. Which algorithm needs less exact evaluations depends on the type of optimization problem.
In order to determine when to use GP-DEMO instead of DEMO, we calculate border times. The border time for a specific optimization problem tells us how long a single exact solution evaluation should last, in order for the optimization times of GP-DEMO and DEMO to be equal. Depending on the appraised complexity of the problem, the border time can be estimated. Therefore, if a single exact solution evaluation takes more than the
estimated border time and the quality of the results is important, we can conclude that for this problem GP-DEMO is a more appropriate choice than DEMO.
4 Conclusion
This paper summarized the doctoral dissertation [2] and presents its main ideas and findings. We defined new relations for comparing solutions under uncertainty and confirmed that they reduce the possibility of incorrect comparisons due to the inaccurate approximations.
We then used these relations in the new surrogate-model-based multiobjective evolutionary algorithm GP-DEMO. We thoroughly tested the algorithm and the results show that GP-DEMO in comparison to other MOEAs produces comparable results with fewer exact evaluations of the original objective functions.
References
[1]	Deb, K.. Multi-objective optimization using evolutionary algorithms. Wiley, New York, 2001.
[2]	Mlakar, M. Evolutionary multiobjective optimization based on Gaussian process modeling, PhD Thesis, IPS Jožef Stefan, Ljubljana, Slovenia, 2015.
[3]	Mlakar, M., Tušar, T., Filipič, B. Comparing solutions under uncertainty in multiobjective optimization. Mathematical Problems in Engineering, 2014. doi:10 .1155/2014/817964.
[4]	Mlakar, M., Petelin, D., Tušar, T., Filipič, B. GP-DEMO: Differential evolution for multiobjective optimization based on Gaussian process models. European Journal of Operational Research, 2015, 243 (2), 347-361.
[5]	Robič T., Filipič B., DEMO: Differential evolution for multiobjective optimization, in Proc. of 3rd Int. Conf. Evol. Multi-Criterion Optimization - EMO 2005, pp. 520-533.