Many today's engineering tasks use approx- both continuous and discrete variables [16, 7]. This imation of their expensive objective function. Surrogate paper describes a particular surrogate model based models, which are frequently used for this purpose, can save on radial basis function (RBF) networks and genersignificant costs by substituting some of the experimental alized linear models (GLMs). Most of the existevaluations or simulations needed to achieve an optimal ing works [22, 17, 9] deal with only continuous door near-optimal solution. This paper presents a surrogate mains or combination with integer variables, but the model based on RBF networks. In contrast to the most of the surrogate models in the current literature, it can be di- works dealing with mixed-variables surrogate models rectly used for problems with mixed continuous and discrete are rather few [21, 19]. variables - clustering and generalized linear models are em- In our model, multiple RBF networks are trained ployed for dealing with discrete covariates. The model has and discrete variables are used either for focusing been tested on a benchmark optimization problem and its training of the networks on the most appropriate data, approximation properties are presented on a real-world ap- or generalized linear model is constructed on this part plication data. of the data. The paper is organized as follows: in the next section, we recall principles of surrogate modelling, RBF 1 Introduction networks and GLMs. Section 3 describes our approach to constructing a surrogate models and using it in optimization. Finally, Section 4 provides the results of testing on a benchmark function and real-world data.
⋆ This work was supported by the Grant Agency of the Charles University (GA UK), grant number Surrogate modelling. Approximation of the fitness 278511/2011 (Luk´aˇs Bajer), and by the Czech Science function with some regression model is a common cure Foundation (GA CR), grant number 201/08/0802 (Mar- for tasks when empirical objective function has to be tin Holenˇa). used. These surrogate models simulate behaviour of the original function while being much cheaper and 3 Our strategy for using much less time consuming to evaluate. surrogate-assisted genetic
As a surrogate model, mainly nonlinear regression optimization models are used, for example gaussian processes [4] or artificial neural networks. In connection with evo- Our version of the surrogate-assisted genetic algorithm lutionary optimization, neural networks of the type including a detailed pseudo-code has been introduced multilayer perceptrons [10] and networks with radial in the previous article [1]. This section describes the basis functions [22, 17] have been particularly popular. construction and using of surrogate models based on The last mentioned kind of neural networks underlies RBF networks. also the model reported in this paper.
Combining of the original fitness function and the surrogate model is determined by evolution con- 3.1 Model construction trol (EC). In the literature [10], individual and generation based approaches are distinguished. While the individual-based EC chooses for evaluation by the original fitness only part of an enlarged population, the generation-based approach evaluates in different generations the whole population by either the original, or the model fitness.
RBF networks compute a mapping from the input space (typically a subspace of IRn) to IR (for simplicity we will focus on versions with scalar output) [5]. The mapping can be expressed as
g f (x) = X i=1 πifi(||x − ci||)
(
d η = X xj βj j=0
(3) to a linear predictor η, and (3) a link function g that connects the random and systematic components together: η = g(μ). The explanatory variables are usually supplemented with the constant vector of ones GLM model. Generalized linear model is used in its corresponding to an intercept parameter β0. continuous-response form and responses are supposed
GLMs are particularly useful for our work because from normal distribution Y ∼ N (μ, σ2). Even though they are able to express a relation between discrete the latter assumption generally does not hold, GLMs (integer or after a transformation of values even nom- still provide useful mean of regression expressed on the inal) input variables and a continuous response. basis of the discrete values.
RBF networks, which were defined in Section 2.1, enable us to use only continuous variables for their fitting. Construction of our first surrogate model [1] starts with clustering of the available training data according to their discrete values into several clusters in order to focus the RBF networks training on the most similar datapoints. Let us call this model RBF/discrete clustering, or shortly RBF/DSCL model. Subsequently, separate RBF networks are fitted with the data of each such a cluster using the datapoints’ continuous variables. The algorithm is the same as described on the Fig. 1 except the omitted steps (1)–(3), and the clustering which is made using discrete values from the training database D in the step (4).
This approach does not utilize relation between values of the discrete input variables and the response variable. As was stated in Section 2.1, such a relation can be expressed by generalized linear models, and these models form an important part of our new RBF/GLM surrogate model.
Training the RBF/GLM model starts with construction of two auxiliary models: the first, global RBF network fˆRBF : S(C) → IR is fitted on the continuous input variables while the second, GLM fˆGLM : S(D)→IR is built using the discrete variables. Both of them make use of all the available training data and regress the response-variable values.
Global RBF network. Training of the auxiliary RBF network works similarly to the training of the RBF networks in the previous RBF/DSCL model [1] – the same starting values for centers and weights, and cross-validation for choosing the best number of components g is used. However, instead of clusters, all the data in the database D are used at once.
Before using or fitting the GLM, the discrete values must be converted to a proper representation. Since we do not expect any ordering on the discrete values, we have chosen dummy coding [13] which establishes one binary indicating variable Iij ∈ {0, 1} for each nominal value from the value sets Vs(Xi(D)), i = 1, . . . , d, j = 1, . . . , |Vs(Xi(D))| of the original discrete variables.
Assignment between the original discrete values and the dummy coding dummy : S(D) → {0, 1}|Vs(X1)|+...+|Vs(Xd)|
(4) has to be recorded for evaluation with the surrogate model.
Final RBF clustered model. Having created the global RBF network fˆRBF and the GLM model fˆGLM, we can proceed with the construction of the final RBF clustered surrogate model fˆ : S(C) → IR. The process starts with clustering of the training data from the database D = {xi(D), xi(C), yi}iN=1 according to the difference between responses of the two auxiliary models on the corresponding input variables (for i = 1, . . . , N ) diff i = fˆRBF(xi(C)) − fˆGLM(dummy(xi(D))).
(5)
The sizes of the clusters have to be at least smin – the minimal number of data needed for fitting one RBF network. This number is provided by the user and its best value depends on a particular task. The higher the smin is, the more components can each RBF
FitTheModel(smin, D, e) Arguments: smin – min. size of clusters,
D – database, e – type of error estimate:
MSE, AIC, or BIC
Steps of the procedure:
(1) (fˆRBF, rbf GLOB) ← fit the global RBF
(
N (4) {Cj}jm=1 ← cluster D into clusters of size
N
at least smin according to {diff i}i=1
(5) for each cluster Cj,mja=x 1, . . . , m
(6) for gj = 1, . . . , gj
(
fitting RBF with gj components (8) gj⋆ ← the number of components
of the best RBF (9) rbf j ← retrained RBF network
with gj⋆ components (10) msej ← mse[j, gj⋆] Output: {rbf GLOB, glm, (rbf j , msej , diff j )jm=1}
Fig. 1. Pseudo-code of the fitting procedure. network have, but the more distinct discrete values are usually grouped together in one cluster.
One separate RBF network rbf j is trained on the data of each cluster Cj , j = 1, . . . , m. The maximal number of components of each network is upperbounded by gjmax = ⌊( k −k1 |Cj |)/ρ⌋. Training these networks is analogous to training of the global RBF network described in Section 3.1. The only difference is in the training data: only the data of individual clusters are used for each network. 3.2
Once the surrogate model is built, it can be used for evaluating individuals resulting from the evolution. The parameters of the model can be summarized as {rbf GLOB, glm, (rbf j , msej , diff j )jm=1}. Here, rbf GLOB are global RBF network parameters, glm = (β0, . . . , βr) are parameters of the GLM, rbf j global RBF network parameters, msej are the MSECV obtained from cross-validation, and diff j are the difference diff (5) averaged on the j-th cluster’s data.
Given a new individual (x˜(C), x˜(D)), evaluation with the surrogate model starts with computing the difference between responses of the global RBF network and GLM with corresponding parameters rbf GLOB and glm dgiff = fˆRBF(x˜(C); rbf GLOB)
−fˆGLM(dummy (x˜(D)); glm ).
Based on this value, the index c of the cluster with the average difference most similar to the individual’s difference is obtained c = arg
min j=1,...,m |diff j − dgiff |.
Finally, the response of the c-th final RBF network is
used as a return value of the surrogate model
(6)
(
(8) If more than one cluster is at the same distance from the individual, the RBF network with the lowest MSECV is chosen. 4
Implementation and results of testing Our algorithms were implemented in the MATLAB environment. We have been utilizing the Global Optimization Toolbox which provided us with a platform for testing the model on a benchmark optimization task. Similarly, our hierarchical clustering method extends the cluster analysis from the Statistical Toolbox which provide us with GLM fitting procedure, too, and we employ a nonlinear curve-fitting from the Optimization Toolbox for fitting RBF networks. 4.1
Our models have been tested on three different kinds of data. The first two datasets (Valero and HCN) are the same as in our last article [1], the third is the building1 dataset from Proben1 [18] collection.
Valero’s [20] benchmark fitness function was constructed to resemble empirical fitness functions from chemical engineering. The surrogate models have been 10-times trained on dataset with 2000 randomly generated data. Using the same settings for fitting, the average root of the MSE (RMSE) of the new RBF/GLM model has been only slightly decreased. (see Table 1 and the top graphs on Fig. 2).
Valero RRBBFF//DGSLCML 1144..044969 ±± 11..0541385 HCN RRBBFF//DGSLCML 1105..364200 ±± 11..581696 building1 RRBBFF//DGSLCML 00.0.163460178 ±± 00..0000449565
The second dataset is from a real application in Fig. 2. Scatter plots of the RBF/GLM (left column) and chemical engineering (cf. using RBF networks in this RBF/DSCL model (right column) on testing data. application area e.g. in the work of Jun [11]): the optimization of chemical catalysts for Hydrocyanic acid (HCN) synthesis [14]. Solutions of this task are com- the relation between discrete variables and the outposed of two discrete and 11 continuous variables, the put. Conversely, the results of the RBF/GLM model whole dataset has 696 items. Fitting results are sub- are at least comparable to the results reported stantially different from the benchmark problem (con- elsewhere [12, 2, 15]. sidering the average response in the dataset y¯ = 31.17, the measured RMSE’s are relatively much higher: see middle row of graphs on Fig. 2). RMSE of the 4.2 Genetic algorithm performance on the new RBF/GLM model has been decreased by nearly benchmark fitness 35 % comparing to the previous model’s error.
Prechelt’s Proben1 [18] is a popular collection of datasets for data mining, originally intended for neural The benchmark fitness enabled us to test the model networks benchmarking. We have tested our models on with the GA [1]. As shown in Table 2, the GA with the building1 dataset using the first response variable the surrogate model reaches on this function the same indicating electrical energy consumption in a building; fitness values as the non-surrogate GA using only less multiple-trained on the first 3156 and tested on the than 30 per cent of the original fitness function evalremaining 1052 data, as suggested by Prechelt. Aver- uations (generation-based EC), or it is able to find age results from ten trainings show that the former 1.1-times better solution with 80 per cent of the origRBF/DSCL model is not able to sufficiently express inal fitness evaluations (individual-based EC). Valero, RBF/GLM
Valero, RBF/DSCL 200
300 400 Original fitness 200
300 400
Original fitness HCN synthesis
HCN synthesis 20 40 60 Original fitness
80 building1 20 40 60 Original fitness
80 building1 0.3 0.4 0.5 0.6 0.7
Original fitness 0.3 0.4 0.5 0.6 0.7
Original fitness