The paper deals with the application of evolu- eral days to several weeks of time and costs several to tionary algorithms to black-box optimization, frequently en- many thousands of euros. countered in biology, chemistry and engineering. In those The usual way of dealing with a time-consuming areas, however, the evaluation of the black-box tness is of- and costly evaluation of an objective function is to ten costly and time-consuming. Such a situation is usually evaluate such a function only sometimes, and tackled by evaluating the original tness only sometimes, evaluate its suitable response-surface model othearnwdiseev,alcuaallteidngs uitrsroagpaptreopmroiadteel roefstphoenset-nseusrsf.acSeevmeroadlelkiontdhs- erwise [19, 25]. In the context of evolutionary optiof models have been successful in surrogate modelling, and mization, such a model is commonly called surrogate a variety of models of each kind can be obtained through model of the tness, and the approach is called surparametrization. Therefore, real-world applications of sur- rogate modelling [10, 29, 32, 37] (occasionally also outrogate modelling entail the problem of assessing the suit- side that context [3, 23]). Because tness is typically ability of di erent models for the optimization task being assumed to be highly nonlinear, nonlinear models are solved. The present paper attempts to systematically inves- used as surrogate models. So far most frequently entigate this problem. It surveys available methods to assess countered have been Gaussian processes [7, 28, 37] model suitability and reports the incorporation of several (inspired by their success in response surface modsuch methods in our recently proposed approach to surro- elling [20, 21, 23, 35]), radial basis function (RBF) netgate modelling based on radial basis function networks. In works [2, 37] and other kinds of feedforward neural netiatdpdaityisonmtuochthaettceonmtimononallysoutsoeditgslolobcaallssuuiittaabbiilliittyyofofraamgoidveenl, works [16, 18]. input. Finally, it shows some results of testing several of Due to the applicability of di erent kinds of models the surveyed methods in two real-world applications. to surrogate modelling, as well as due to the possibility to construct a variety of models of each kind through an appropriate parametrization, a large number of var1 Introduction ious surrogate models can always be employed. Therefore, real-world applications of surrogate modelling enAn important application area of evolutionary opti- tail the problem of assessing the suitability of di erent mization algorithms [8, 31] is black-bock optimization, models for the optimization task being solved. Unfori.e., optimization of an objective function (in evolu- tunately, no systematic attention seems to have been tionary terms called tness) that cannot be described paid to that problem so far in the area of surrogate explicitly, but is known only from its evaluations in modelling, the research in this area being focused on a nite number of points in the input space. the integration of surrogate models with evolutionary Frequently, the tness is evaluated in some empirical optimization algorithms, their adaptation to the optiway, through measurements or testing. This is typical mization tasks, and on increasing the accuracy of the for applications in biology, chemistry, or materials sci- constructed models [11, 14, 17, 26]. The present paper ence [1]. In those domains, however, the fact that evo- is an attempt to change the situation. We survey availlutionary algorithms rely solely on tness evaluations able methods to assess model suitability, concentratcan be quite disadvantageous because the evaluation of ing in particular on local suitability of the model for empirical functions encountered there is usually time- a given input. Moreover, we give some results of testconsuming and costly. For example in the evolution- ing several of the surveyed methods on two real-world ary optimization of catalytic materials [1, 12], where applications of surrogate modelling. a tness describes the suitability of the material for In the following section, the principles of surrogate a particular chemical reaction, its evaluation in one modelling are recalled and their usefulness for evolugeneration of the evolutionary algorithm needs sev- tionary optimization is documented. The key section of the paper is Section 3, in which the most important ? The research reported in this paper has been sup- methods for assessing model suitability are explained ported by the Czech Science Foundation (GA CR) grant and results of their testing are presented. P202/11/1368.
Surrogate modelling in evolutionary optimization (iv) The EA is run with the original tness for a prescribed number ge of generations with populations Pgm+1; : : : ; Pgm+ge (frequently, ge = 1). (v) The set E is replaced by E [ Pgm+1 [ [
Pgm+ge and the algorithm returns to (ii).
In evolutionary optimization, surrogate modelling is an approach in which the evaluation of the original black-box tness is restricted to points considered to be most important in the search for its global maximum, The fact that surrogate modeling is employed in and its appropriate response-surface model is evalu- the context of costly or time-consuming objective funcated otherwise. Important for searching the global ma- tions e ectively excludes the possibility to use those ximum of a tness function are on the one hand the functions for tuning surrogate modeling methods, and highest values found so far, on the other hand the di- for comparing di erent models and di erent ways of versity of current population. Therefore, the selection their combining with evolutionary optimization. To of points in which the original tness is evaluated is get around this di culty, arti cial benchmark funcalways based on some combination of those two crite- tions can be used, computed analytically but expected ria. to behave in evolutionary optimization similarly to the
The di erent ways of interaction between the sys- original tness. As an example, Fig. 1 shows the applitem input/output interface, the generated evolution- cation of surrogate modelling to a benchmark function ary algorithm (EA) and the surrogate model can basi- proposed in [34] for the application area of optimizacally be assigned to one of the following two strategies: tion of catalytic materials (cf. [1]). The benchmark function was optimized using the system GENACAT A. The individual-based strategy consists in choosing [13, 15], one of several evolutionary optimization sysbetween the evaluation of the original tness and tems developed speci cally for that application area. the evaluation of its surrogate model individual- The evolutionary algorithm employed by GENACAT wise, for example, in the following steps: is a genetic algorithm (GA) taking into account the (i) An initial set E of individuals is collected in composition and properties of catalytic materials. As which the original tness was evaluated surrogate model, a RBF-network trained with data (e.g., individuals forming several rst genera- from all previous generations was used, combined with tions of the EA). the GA according to the individual-based strategy. (ii) The model is trained using pairs f(x; (x)) : The results shown in Fig. 1 clearly document that surx 2 E g. rogate modelling substantially accelerates the search (iii) The EA is run with the tness replaced for the maximum of a tness function. by the model for one generation with a poppuloaptuiolantiQonosfizseizfeorq Pth,ewohpetrimeiPzatisiotnhoefde,siarnedd 3 Assessing the suitability of di erent q is a prescribed ratio (e.g., q = 10 or q = 100). models (iv) A subset P Q of size P is selected so as to contain those individuals from Q that are most Instead of a single surrogate model, a whole set of modimportant according to the considered criteria els F an be used. Then it is necessary to decide how for the progress of optimization. suitable each of them is to be evaluated instead of the (v) For x 2 P, the original tness is evaluated. original tness . Typically, the suitability of a model
F 2 F is assumed to be indirectly proportional to
(vi)riTthhme sreettuErniss rteop(laiic)e.d by E [ P and the algo- saogmiveenersreoqru"e(nFce),odfedantaednootnuFsedanfodr cthalecucolantsetdruuctsiionng
B. The generation-based strategy consists in choosing of F . Consequently, the most suitable surrogate model
between both kinds of evaluation generation-wise, is the one ful lling
for example, in the following steps:
(i) An initial set E of individuals in which the F^ = arg min "(F ): (
X (F (x)
jDij x2Di
construction of F : single split and cross-validation, the Observe that the most suitable model F^ in (
Let us exemplify the calculation of "(F ) by recall- suitable with respect to the given sequence of data. Its ing the de nition of the root mean squared error on obvious advantage is that it needs to be found only an input data sequence D: once, and then it can be used for all evaluations, as long as the set F does not change.
RMSE(F ) = RMSED(F ) = (
the original tness.
2. For each of the considered 78 architectures, one
surrogate model was trained using all the available
data from the 1st{6th generation.
3. The RMSE of each surrogate model on the data
from the 1st{6th generation was estimated using (i) Kendall's rank correlation coe cient between
leave-one-out cross-validation, according to (
surrogate model on the data from the 7th
generation was calculated according to (
namely for the 21 MLP architectures that, in addition
to (
Figure 2 visualizes the results of comparisons in step 8 for a subset of the considered surrogate models, which clearly con rm a strong correlation between the rank of the model suitability and the rank of model RMSE on test data. Needless to say, the fact that a globally most suitable model achieves the least value of an error " calculated using a given sequence of data does not at all mean that it yields the most suitable prediction for every x in which tness can be evaluated. Therefore, we introduce the model F^x locally most suitable for x as
F^x = arg min (F; x):
F 2F
(
Like " in (
Recall that a surrogate model is evaluated in points x 2 X in which has not been evaluated yet. Hence, the calculation of the error (F; x) must not depend on the value of (x). Though in the context of surrogate modelling, using such errors has not been reported yet, a number of error measures exist that could be used to this end, most importantly: { widths of con dence intervals [33]; { transductive con dence [9, 27, 36]; { estimation of prediction error relying on density
estimation [4]; { sensitivity analysis [5]; { several heuristics based on the nearest neighbours
of the point of evaluation [4, 30]; { heuristic based on the variance of bagged models [6];
We are currently extending the surrogate model
presented in [2], which is based on RBF-networks, with
three of the above error measures:
(i) Width of prediction intervals for x 2 X , i.e., of
con dence intervals for F^x(x) in (
Hence, F is replaced with
F LIN = fF LIN : F 2 F g: Then for each considered x 2 X , the element F^MLE
x
of F LIN corresponding to the maximum-likelihood
estimate of the d + 1 parameters is found using
a given training sequence of input-output pairs
(x1; y1); : : : ; (xp; yp). That allows to calculate for
each F 2 F the error in (
F1
p X(yj j=1 [1; p p d
F^MLE(xj ))2
x d]
p X(yj j=1
F (xj ))2 ; (
Pk j=1 ynj
k (ii)(F; x) =
F (x) :
(
nal set of considered surrogate models is de ned as
F = 8 <F : F = : m X BjF & B1F ; : : : ; BmF 2 B j=1 and the bagged variance is calculated according to (iii)(F; x) =
m 0 1 X @BjF (x) m j=1 1 m
X BjF (x)A :
m j=1
12
9
= ;
;
(
Because the extension of the surrogate model
from [2] with those three error measures has been
implemented very recently, it is now in the course of
test(
using the original tness.
2. For each of the 5 possible numbers of hidden
neurons, one surrogate model was trained using all the
available data from the 1st{6th generation.
3. The RMSE of each surrogate model on the data
from the 1st{6th generation was estimated using
10-fold cross-validation, according to (
4. Based on the result of step 3, the globally most
suitable model was determined. 5. The 7th generation G7 of the genetic algorithm
was produced. 6. The models obtained in step 2 were used to predict
the tness of x 2 G7. 7. For F 2 F and x 2 G7, the errors (i)(F; x); (ii)(F; x); (iii)(F; x) were calculated. 8. The surrogate models locally most suitable for x 2 G7 according to (i); (ii) and (iii) were determined. 9. For x 2 G7, the original tness was evaluated. 10. For x 2 G7, the absolute errors of the considered surrogate models were calculated from the results of steps 6 and 9.
Figure 3 visualizes the locally most suitable models determined in step 8 for a subset of 30 randomly selected catalytic materials from the 7th generation. The fact that for those catalysts the absolute errors of all
ve RBF networks were calculated in step 10 allows to juxtapose the choices of the locally most suitable models and the globally most suitable model (model with 2 hidden neurons) with the achieved absolute errors. The juxtaposition shows that the model with the lowest absolute error was nearly always assessed as the locally most suitable by some of the three implemented error measures. Unfortunately, no one of them could be relied on in a majority of all cases. 4
Conclusion This paper is, to our knowledge, a rst attempt to systematically investigate available methods for assessing the suitability of surrogate models in evolutionary optimization. In addition to the commonly used global suitability of a model, it paid much attention also to its local suitability for a given input. We have incorporated three methods for assessing local suitability into our recently proposed approach to surrogate modelling based on RBF networks. The paper not only surveyed available methods for assessing suitability, but also described their testing and presented some of the testing results.
The presented results clearly con rm the usefulness of methods for assessing the suitability of surrogate models: there is a strong correlation between the ranks of models according to the RMSE-based global suitability estimated by means of leave-one-out crossvalidation on data from the 1st{6th generation and according to the RMSE on the data from the 7th generation, and for nearly every unseen input, the model with the lowest absolute error is indeed assessed as the locally most suitable by some of the implemented methods. Unfortunately, none of the methods is able to correctly assess the locally most suitable model for a majority of the 7th generation, which shows that further research in this area is needed. We want to take active part in such research, pursuing the following three directions: (i) Implement and test further methods for assessing local suitability, listed above in Subsection 3.1. We consider particularly interesting the transductive con dence machine [9, 27, 36] because it is a novel method and has solid theoretical fundamentals. (ii) Investigate whether the success of some of the tested methods for assessing local suitability depends on the kind of dataset (in terms of the number of nominal attributes, number of continuous attributes, etc.) on which the surrogate models have been trained, or on their descriptive statistics. To this end, we want to make use of the GAME system [22], which collects a large amount of meta-data about the kind of the processed dataset and about its descriptive statistics. (iii) Modify and combine the tested methods, using the results obtained in (ii), to increase their success in assessing the local suitability of surrogate models.