The paper deals with surrogate modelling, Indeed, the impossibility to compute analytically the a modern approach to the optimization of empirical ob- function values of such a function makes also an anajective functions. The approach leads to a substantial de- lytical computation of its gradient and second-order crease of time and costs of evaluation of the objective func- derivatives impossible, whereas measurement errors tion, a property that is particularly attractive in evolution- usually hinder obtaining su±ciently accurate estimaary optimization. In the paper, an extension of surrogate tes of the derivatives. modelling with regression boosting is proposed. Such an extension increases the accuracy of surrogate models, thus Like other methods relying solely on function valalso the agreement between results of surrogate modelling ues, evolutionary algorithms need the objective funcand results of the intended optimization of the original ob- tion to be evaluated in quite a large number of points. jective function. The proposed extension is illustrated on In the context of optimization of empirical objective a case study in the area of searching catalytic materials op- functions, this can be quite disadvantageous because timal with respect to their behaviour in a particular chem- the evaluation of such a function in the points formical reaction. A genetic algorithm developed speci¯cally for ing one generation of an evolutionary algorithm is ofthis application area is employed for optimization, multi- ten costly and time-consuming. Hence, the above menlayer perceptrons serve as surrogate models, and a method tioned advantages of using evolutionary algorithms for called AdaBoost.R2 is used for boosting. Results of the case the optimization of empirical objective functions are sgtautdeymcoledaerllliyngc.on¯rm the usefulness of boosting for surro- frequently counterbalanced by considerably high costs and time needed for the evaluation of such functions. An area, where the trade-o® between successful op1 Introduction timization and costly objective function evaluations plays a crucial role, is the computer-aided search for For more than two decades, evolutionary algorithms, new materials and chemicals optimal with respect to especially their most frequently encountered represen- certain properties [2]. Here, evolutionary algorithms tative { genetic algorithms, belong to the most suc- are used in more than 90 % of optimization tasks, cessful methods for solving di±cult optimization tasks and the rarely encountered alternatives are simulated [3, 11, 31, 32, 42]. The popularity of evolutionary algo- annealing [9, 22, 23], simplex method [17], and holorithms is to some extent due to their biological inspi- graphic search strategy [37, 38, 41], which also use soleration, which increases their comprehensibility out- ly function values, therefore needing a similarly high side computer science. Nevertheless, they share sev- number of objective function evaluations as evolutioneral purely mathematical properties of all stochastic ary algorithms. Testing a generation of materials or optimization methods, most importantly, the valuable chemicals typically needs hours to days of time and ability of to escape a local optimum and continue the costs hundreds to thousands euros. Therefore, the evosearch for a global one, and the restriction of the infor- lutionary optimization rarely runs for more than ten mation on which they rely to function values only. generations. Consequently, they do not need information about gra- The usual approach to decreasing the cost and dients or second-order partial derivatives, di®erently time of optimization of empirical objective functions to smooth optimization methods (such as steepest de- is to evaluate the objective function only sometimes scent, conjugate gradient methods, the popular Le- and to evaluate a suitable regression model of that venberg-Marquardt method, etc. ). This makes them function otherwise. The employed model is termed particularly attractive for the optimization of empiri- surrogate model of the empirical objective function, cal objective functions, the values of which cannot be and the approach is referred to as surrogate modelling. analytically computed, but have to be obtained ex- Needless to say, the time and costs needed to evaluperimentally, through some measurement or testing. ate a regression model are negligible compared to an ? The research reported in this paper has been supported empirical objective function. However, it must not be by the grant No. 201/08/1744 of the Grant Agency of forgotten that the ¯nal optimized function coincides the Czech Republic and partially supported by the Insti- with the original empirical objective function only in tutional Research Plan AV0Z10300504. some points, whereas in the remaining points it coin-
cides only with its surrogate model. Consequently, the that is known to be useful in general [
This paper suggests to increase the accuracy of sur- In the context of evolutionary optimization, surrorogate models by means of boosting. Boosting is a pop- gate modelling has the following main steps: ular approach to increasing the accuracy of classi¯ca- (i) Collecting an initial set of points in which the obtion, and due to the success of classi¯cation boosting, jective function has already been empirically evalalso several methods of regression boosting have al- uated. This can be the ¯rst generation or several ready been proposed. However, so far no attempt has ¯rst generations of the evolutionary algorithm, but been reported to combine regression boosting with sur- such points are frequently available in advance. rogate modelling. Hence, the purpose of the research (ii) Approximating the objective function by a surroreported in the paper is basically a proof of concept: to gate model, with the use of the set of all points in extend surrogate modelling through the incorporation which it has been empirically evaluated. of regression boosting, and to validate that extension (iii) Running the evolutionary algorithm for a popuon several su±ciently complex case studies. One of lation considerably larger than is the desired popthose case studies is described in the paper. ulation size, with the empirical objective function
In the following section, basic principles of surro- replaced by the surrogate model. gate modelling and its strategies in evolutionary opti- (iv) Forming the next generation of the desired size mization are recalled, and important surrogate models as a subset of the large population obtained in are listed. Section 3 recalls the principles of boosting the preceding step that includes points most imand explains a particular method of regression boost- portant according to considered criteria for the ing that will be employed later in a case study in mate- progress of optimization (such as indication of glorials science. That case study is sketched and its main bal optimum, diversity). results are presented in Section 4. (v) Empirically evaluating the objective function in all points that belong to the next generation of the desired size, and returning to step (ii). 2 Surrogate modelling Actually, the above steps (ii){(v) correspond to only one possible strategy of surrogate modelling in evolutionary optimization: the individual-based control, sometimes also referred to as pre-selection [40].
An alternative strategy to the steps (ii){(v) is to run the algorithm for only the desired population size, interleaving one generation/several generations in which the original objective function is empirically evaluated with a certain number of generations in which the surrogate model is evaluated. This is the generation-based control of surrogate modelling in evolutionary optimization.
For empirical objective functions, it is typical to be highly nonlinear. Therefore, nonlinear regression models should be used as surrogate models. They can be basically divided into two large groups according to whether the set of functions among which the surrogate model has to be chosen has an explicit ¯nite parametrization.
Surrogate modelling is a general approach to the
optimization of costly objective functions in which the
evaluation of the objective function is restricted to
points that are considered to be most important for
the progress of the employed optimization method [
Although surrogate modelling is a general
optimization approach (cf. its application in the context
of conventional optimization in [
(ii) Support vector regression based on positive
semi-de¯nite kernels [34, 36]. It is worth
mentioning that they generalize the above recalled
RBF networks, and also the historically ¯rst
kind of nonlinear regression { polynomial
regression.
(iii) Gaussian process regression [28] is listed here
also due to a relationship to radial basis
function networks, but most importantly due to
the fact that it has already been successfully
employed in surrogate modelling [
Boosting is a method of improving classi¯cation
accuracy that consists in developing the classi¯er
iteratively, and increasing the relative in°uence of the
training data that most contributed to errors in the
previous iterations on its development in the
subsequent iterations [33]. The usefulness of boosting for
classi¯cation has incited its extension to regression [
Both for classi¯cation and for regression, the basic approach to increasing the relative in°uence of particular training data is re-sampling the training data accord- The errors used to asses the quality of the boosting to a distribution that gives them a higher probabil- ing approximation are then called boosting errors, e.g., ity of occurrence. This is equivalent to re-weighting the boosting MSE, or boosting MAE, where MSE refers to contributions of the individual training pairs (xj ; yj ), the mean squared error between the computed and with higher weights corresponding to higher values of measured values, whereas MAE refers to the mean the error measure. absolute error, i.e., to the mean Euclidean distance
Since surrogate models are regression models, any between them. For simplicity, also the approximation
method for regression boosting (such as [
Similarly to other adaptive boosting methods, each iteration.
of the available pairs (x1; y1); : : : : : : ; (xp; yp) of input The above formulation of the method deals only
and output data is in the ¯rst iteration of with the case E¹i < 0:5. For E¹i ¸ 0:5, the original
AdaBoost.R2 used exactly once. This corresponds to formulation of the method in [
In the subsequent iterations (i ¸ 2), the following solely on the data employed to construct the
regressequence of steps is performed: sion model. A possible alternative for the case E¹i ¸ 0:5
is reinitialization, i.e., proceeding as in the 1st
itera1. A sample (»1; ´1); : : : ; (»p; ´p) is obtained through tion [
re-sampling (x1; y1); : : : ; (xp; yp) according to the In connection with using feed-forward neural
netdistribution Pi¡1. works as surrogate models, it is important to be aware
2. Using (»1; ´1); : : : ; (»p; ´p) as training data, a re- of the di®erence between the iterations of boosting
gression model Fi is constructed. and the iterations of neural network training.
Boost3. A [
(2) 5. Provided E¹i < 0:5 , the probability distribution for re-sampling (x1; y1); : : : ; (xp; yp) is for k = 1; : : : ; p updated according to
The extension of surrogate modelling with boosting will now be illustrated on a case study using data from the investigation of catalytic materials for the highPi(xk; yk) = temperature synthesis of hydrocyanic acid. That investigation and its results have been recently described = Pi¡1(xk; yk) ³ 1¡E³¹Ei¹iE¹´i(1´¡(E1i¡(kE)i)(k)) : (3) ienxp[2er4i]m.Ietnhtsasinbeaenciprceurfloarrm4e8d-cthharnonueglhrheaigcht-otrh.rIonugmhpoustt Pip=1 Pi¡1(xk; yk) 1¡E¹i of those experiments, the composition of the materials was designed by means of a genetic algorithm devel6. The boosting approximation in the i-th iteration is oped speci¯cally for heterogeneous catalysis [44]. More set to the median of the approximations F1; : : : ; Fi precisely, the algorithm was running for 7 generations with respect to the probability distribution of population size 92, and in addition 52 other cataµ 1 ¡E¹1E¹1 ; : : : ; 1 ¡E¹iE¹i ¶ : (4) ltayilgysattsticewdmi.taChtoemnriasaenlqsuuawelelnyrteldyg,easditaghtneaerdeadbc.ooumtpaolstiotgioenthwerer6e96invcaest-k=1
p E¹i = 1 X Pi(xk; yk)Ei(k): p 4
The composition and preparation of the investi- as test data was calculated, and averaged over all the
gated catalytic materials and the conditions in which 604 folds. The criterion according to which boosting is
they had been tested have been in detail described considered useful to an architecture was: the average
in [
These were the architectures (14,10,6,3), (14,14,8,3), (14,13,5,3), (14,10,4,3) and (14,11,3), for which the ¯nal iterations of boosting were 32, 29, 31, 19 and 3, respectively. For each of them, the validation proceeded as follows:
As the surrogate model, MLPs were employed, in
accordance with their leading role among nonlinear
regression models in the area of catalytic
materials [
The most appropriate MLP architectures were corresponding to the respective architecture, a sinsearched by means of cross-validation, using only data gle MLP was trained with data about the 604 catabout catalysts from the 1.{6. generation of the ge- alytic materials considered during the architecture netic algorithm and about the 52 catalysts with manu- search. ally designed composition, thus altogether data about 2. Each of those MLPs was employed to approximate 604 catalytic materials. Data about catalysts from the the conversions of CH4 and NH3 and the yield of 7. generation were completely excluded and left out HCN for the 92 materials from the 7. generation for validating the search results. To use as much in- of the genetic algorithm. formation as possible from the available data, cross- 3. In each iteration, the medians with respect to the validation was applied as the extreme 604-fold vari- probability distribution (4) of the approximations ant, i.e., leave-1-out validation. The set of architec- of the two conversions and of the HCN yield obtures within which the search was performed was de- tained up to that iteration were used as the boostlimited by means of the heuristic pyramidal condition: ing approximations. the number of neurons in a subsequent layer must not 4. From the conversions and the yield predicted by increase the number of neurons in a previous layer. the boosting approximations, and from the meaDenote nI , nh and nO the numbers of input, hidden sured values, the boosting MSE and MAE were and output neurons, respectively, and nH1 and nH2 calculated for each MLP. the numbers of neurons in the ¯rst and second hidden layer, respectively. Then the pyramidal condition The boosting errors (MSE and MAE) are sumreads: marized in Figure 2, whereas Figure 3 compares the (i) for MLPs with 1 hidden layer: nI ¸ nH ¸ nO, in boosting approximations of the conversions of CH4 our case 14 ¸ nH ¸ 3 (12 architectures); and NH3 and of the yield of HCN in the 1st and ¯nal (ii) for MLPs with 2 hidden layers: nI ¸ nH1 ¸ iteration with their measured values. The presented nH2 ¸ nO, in our case 14 ¸ nH1 ¸ nH2 ¸ 3 results clearly con¯rm the usefulness of boosting for (78 architectures). the ¯ve considered architectures. For each of them, To investigate the usefulness of boosting in our boosting led to an overall decrease of both considered case study, the same data were used and the same error measures, the MSE and MAE, on new data from set of architectures was considered as for architecture the 7th generation of the genetic algorithm. Moreover, search. In each iteration, a leave-1-out validation was the decrease of the MSE (which is the measure emperformed, in the way brie°y outlined in the preceding ployed during the investigation of the usefulness of section: The mean squared error of the performance of boosting) is uninterrupted or nearly uninterrupted till the catalytic materials serving in the individual folds the ¯nal boosting iteration. On the other hand, the scatter plots in Figure 3 do not indicate any apparent di®erence between the e®ect of boosting on the three properties employed as catalyst performance measures in our case study { conversion of CH4, conversion of NH3, and yield of HCN. Hence, the performed validation con¯rms the usefulness of boosting irrespectively of which of those performance measures is considered. 5
The paper dealt with surrogate modelling, a modern approach to the optimization of empirical objective functions, which is particularly attractive in evolutionary optimization. It proposed to extend surrogate modelling with regression boosting, to increase the accuracy of surrogate models, thus also the agreement between results of surrogate modelling and results of the intended optimization of the original objective function. Needless to say, regression boosting is not new, though it is less common than the popular classi¯cation boosting. However, novel is its combination with surrogate models, which adds the advantage of increased accuracy to the main advantage of surrogate modelling { decreasing the time and costs of optimization of empirical objective functions.
Theoretical principles of both surrogate modelling and boosting are known, therefore the main purpose of the reported research was to validate the feasibility of the proposed extension of surrogate modelling on several su±ciently complex case studies, one of which was sketched in this paper. The presented case study results clearly con¯rm the usefulness of boosting. For the ¯ve most promising architectures, boosting leads to an overall decrease of both considered error measures, MSE and MAE, on new data from the 7th generation of the genetic algorithm. Moreover, the decrease of the MSE (which is the boosting error employed during the investigation of the usefulness of boosting) is uninterrupted or nearly uninterrupted till the ¯nal boosting iteration. On the other hand, the scatter plots in Figure 3 do not indicate any apparent di®erence between the e®ect of boosting on the three catalyst properties considered as possible objective functions in our case study { conversion of CH4, conversion of NH3, and yield of HCN. Hence, the performed validation con¯rms the usefulness of boosting irrespectively of which of these objective functions is selected.