Particle Swarm Hybridized with Differential Evolution: Black-Box Optimization Benchmarking for Noisy Functions

Particle Swarm Hybridized with Differential Evolution: Black-Box Optimization Benchmarking for Noisy Functions José García-Nieto Dept. de Lenguajes y Ciencias de la Computación University of Málaga, ETSI Informática, Málaga - 29071, Spain [email protected] Enrique Alba Dept. de Lenguajes y Ciencias de la Computación University of Málaga, ETSI Informática, Málaga - 29071, Spain [email protected] Javier Apolloni LIDIC - Departamento de Informática University of San Luis, Ejército de los Andes 950, 5700, Argentina javier[email protected] ABSTRACT In this work we evaluate a Particle Swarm Optimizer hybridized with Differential Evolution and apply it to the Black- Box Optimization Benchmarking for noisy functions (BBOB 2009). We have performed the complete procedure established in this special session dealing with noisy functions with dimension: 2, 3, 5, 10, 20, and 40 variables. Our pro-posal obtained an accurate level of coverage rate, despite the simplicity of the model and the relatively small number of function evaluations used. Keywords Benchmarking, Black-box optimization, Noisy Functions, Hy-brid Algorithms, Particle Swarm, Differential Evolution 1. INTRODUCTION Particle Swarm Optimization (PSO) [8] and Differential Evolution (DE) [9] have been successfully used on real parameter function optimization since they are two well adapted algorithms for continuous solution encoding. Real parameter optimization problems consist basically in this: find x∗ such that ∀ x f(x∗) ≤ f(x) (minimization). Here, f(.) is a function in a real space domain that models an opti-mization problem, x = {x1, x2, . . . , xDIM } is a solution for such problem, and DIM is the number of variables with xi∈[xlow i, xupp i] (1 ≤i≤DIM). Finally, xlow i,xupp i∈R correspond to lower (low) and upper (upp) limits of the variable domain, respectively. Swagatam Das et al. [3] proposed an initial hybridization of PSO and DE for continuous optimization. Based on this first idea, in this work we propose a PSO algorithm which basically uses the differential variation scheme employed in DE for adjusting the velocity of particles. In this way, by combining search strategies, parameter adaptation, and differential operators present in PSO and DE we expect to improve the performance of the resulting technique. Our proposal, called DEPSO, is evaluated by means of the Black- Box Optimization Benchmarking for noisy functions (BBOB 2009) [4, 7] according to the experimental design from [6]. We have performed the complete procedure established in this GECCO’09 workshop dealing with noisy functions with dimension: 2, 3, 5, 10, 20, and 40 variables. Our proposal will be shown to obtain an accurate level of coverage rate, even for the higher dimensions, and despite the relatively small number of function evaluations used (1000 ×DIM). The remaining of the paper is organized as follows. In Section 2 the DEPSO algorithm is briefly described. Sections 3 and 4 presents the experimentation procedure and the results obtained, respectively. In Section 5, a brief analysis of the CPU Timing experiment is reported. Finally, conclusions and remarks are given in Section 6. 2. THE ALGORITHM: DEPSO Our proposal, DEPSO, is basically running a PSO algorithm in which we incorporate ideas of DE. For each particle p(with velocity and position vectors vand x, respectively) the velocity is updated according to two main influences: social and differential variation factors. The social factor concerns the local or global best position gof a given neighborhood of particles (being global when this neighborhood is the entire swarm). The differential variation factor is composed by using two randomly selected particle positions as made in DE. This way, for each particle xiof the swarm, a differential vector w=xr1−xr2is generated where particles xr1and xr2are randomly (uniformly) selected (with xi6=xr16=xr2). Then, the new velocity v0of a particle iis calculated by means of the following equation: v0 i←ω·vi+µ·w+ϕ·(gi−xi),(1) where ωis the inertia weight of the particle that con- trols the trade-off between global and local experience and µis a scaling factor applied to the differential vector (µ= UN(0,1)). The third component corresponds to the social factor which is influenced by the global best gof the swarm and directly proportional to the social coefficient ϕ(in this case ϕ=UN(0,1)). Therefore, in the velocity calculation, the standard historical influence used in PSO is replaced in our proposal by the differential vector w. Similarly to DE, the update of each jcomponent of the velocity vector of a given particle iis carried out by means of the Equation 2 as follows: v0 i(j) = (v0 i(j) if r≤Cr, vi(j) otherwise. (2) Here, r∈[0,1] is a uniformly distributed value which determines if the jth component is selected from the new velocity or is selected from the current velocity, based on the crossover probability Cr ∈[0,1]. This mechanism is used to increase the exploitation ability of the algorithm through the search space [9]. Finally, a particle ichanges its position (moves) only if the new one x0 iis lower or equal than the current position xi(minimizing in this work). In other case, the particle keeps its current position (equations 3 and 4). x00 i=(x0 iif f(x0 i)≤f(xi) xiotherwise, (3) being x0 i←xi+v0 i(4) Additionally, with certain probability pmut, a mutation operation is made on each particle in order to avoid an early convergence to a local optimum. The new mutated position x0is generated by means of the Equation 5. x00 ←xlow +UN(0,1) ·(xupp −xlow) (5) Vectors xlow and xupp correspond to lower and upper limits of each dimension of the function to optimize, respectively. Algorithm 1 shows pseudocode of the hybrid DEPSO algorithm developed for this work. First, an initialization process of all particles in the swarm S(as stated in [6]), and their initial evaluation (line 1) are carried out. After this, each evolution step the particle’s positions are updated following the differential variation model of the equations previously explained (lines 4 to 18). In addition, the global best position reached at the moment is updated in order to guide the rest of the swarm. Eventually, a mutation operation is made (lines 20 to 24). Finally, the algorithm returns the best solution found during the whole process. 3. EXPERIMENTAL PROCEDURE The experimentation procedure has been carried out according to [6] on the benchmark of 30 noisy functions given in [4, 7]. The DEPSO algorithm was implemented in C++ using the MALLBA library [1] of metaheuristics. The noisy functions were tackled connecting the C-code of the Black- Box Optimization Benchmarking to our implementation of DEPSO. Each candidate solution was sampled uniformly in [−5,5]DIM , where DIM represents the search space dimension. The maximal number of function evaluation was set to 1000 ×DIM. Algorithm 1 Pseudocode of DEPSO 1:initialize(S) 2: while not stop condition is met do 3: for each particle position xiof the swarm Sdo 4: /* Differential Variation */ 5: for each dimension jof the particle position xido 6: w(j)←xr1(j)−xr2(j) 7: if r≤Cr then 8: v0 i(j)←ω·vi(j) + µ·w(j) + ϕ·(g(j)−xi(j)) 9: end if 10: end for 11: for each dimension jof the particle position xido 12: x0 i(j)←xi(j) + v0 i(j) 13: end for 14: if f(x0 i)≤f(xi)then 15: x00 i←x0 i 16: else 17: x00 i←xi 18: end if 19: /* Mutation */ 20: if UN(0,1) < pmut then 21: for each dimension jof the particle position xido 22: x00 i(j)←xinf (j) + UN(0,1) ·(xsup(j)−xinf (j)) 23: end for 24: end if 25: end for 26: end while 27: Output: Best solution found Our proposal was tested performing 15 independent runs for each noisy function and each dimension. Table 1 shows the parameter setting used to configure DEPSO. These parameters were tuned in the context of the special session of CEC’05 for real parameter optimization [11, 5] reaching results statistically similar to the best participant algorithms (G-CMA-ES [2] and K-PCX [10]) in that session. This parameterization was kept the same for all the experiments, and therefore the crafting effort [6] is zero. Table 1: Parameter setting used in DEPSO Description Parameter Value Swarm size Ss 20 Crossover probability Cr 0.9 Inertia weight ω0.1 Differential mutation µ UN(0,1) Social coefficient ϕ1·UN(0,1) Mutation probability pmut 1 DIM 4. RESULTS AND DISCUSSION In this section, the results are presented and some discussions are made in terms of the number of successful trials (fopt + ∆f≤10−8) reached for each kind of noisy function: moderate (f101-f106), severe (f107-f121), and severe multimodal (f122-f139). Figure 1 shows the Expected Running Time (ERT, •) to reach fopt + ∆fand median number of function evaluations of successful trials (+). As we can observe, our proposal obtains the highest number of successful trials in moderate noise functions, specifically in dimensions 2, 3, 5 and 10, in f101 and f102. With regards to severe noise functions, the target function is reached in 9 out of 15 trials for the lower dimensions. In severe noise multimodal functions, DEPSO obtains successful trials in f125 and f130 for dimension 2, and in f128 for dimensions 2, 3 and 5. As a summary, in Table 2 the functions are ranked by means of the number of successful trials that DEPSO has obtained with them (with the best ranked functions in the top). For higher dimensions (20 and 40), the best behavior of our proposal can be observed when facing moderate noise functions as shown in Table 3, concretely in functions f101 and f102 where error precisions slightly higher than 10−5 were reached. Secondly, for severe noise and severe noise multimodal functions (tables 3 and 4 DIM=20), the best achieved ∆fprecisions (of the median trials) are always close to e+ 0, although being some of them close to e−2 as in f109, f125, and f127. We suspect that the relative low convergence rate in severe noise functions (for the higher dimensions) can be due to the small number of maximal function evaluations employed (1000 ×DIM). Concerning this last issue, the empirical cumulative distribution function (ECDF) of the running time (in terms of function evaluations) is shown in Figure 2 left. We can easily observe that the ECDF tends to get reduced with the number of functions evaluation for all noisy functions. Specifically for severe noise and severe noise multimodal functions, the ECDF of the best achieved ∆f(Figure 2 right) tends to reduce the difference to the optimal function value noticeably (with the proportion of trials). Table 2: Noisy Functions ranked by the number of successful trials obtained by DEPSO. Columns indicate dimensions 23 5 10 20 40 f101 f101 f101 f101 - - f102 f102 f102 f102 - - f113 f107 f107 - - - f128 f113 f113 - - - f107 f128 f128 - - - f103 f103 - - - - f115 f115 - - - - f125 - - - - - f130 - - - - - f116 - - - - - f105 - - - - - 5. CPU TIMING EXPERIMENT For the timing experiment, the same DEPSO algorithm was run on f8 until at least 30 seconds had passed (according to the exampletiming procedure available in BBOB 2009 [6]). These experiments have been conducted with an Intel(R) Corel(TM)2 CPU processor with 1.66 GHz and 1GB RAM; O.S Linux Ubuntu version 8.10 using the C-code provided. The results were 1.1, 0.9, 1.3, 2.3, 3.9, and 7.1× e-06 seconds per function evaluation in dimensions 2, 3, 5, 10, 20, and 40, respectively. 6. CONCLUSION In this work we have experimentally studied DEPSO, a simple and easy to implement optimization algorithm constructed by hybridizing the Particle Swarm Optimizer with Differential Evolution operations. The experiments have been made in the context of the special session of real parameter Black-Box Optimization Benchmarking (GECCO BBOB 2009), performing the complete procedure previously established, and dealing with noisy functions with dimension: 2, 3, 5, 10, 20, and 40 variables. Our proposal obtained an accurate level of coverage rate for dimensions 2, 3, 5, and 10, specifically with moderate noise and severe noise multimodal functions. Successful trials were found for 11 out of 30 functions. The fact of using the same parameter setting for all functions (and dimensions), together with the relatively small number of function evaluations used (1000 ×DIM), leads us to think that DEPSO can be easily improved for better covering noise functions with higher dimensions. Future experiments with different parameter settings depending of each family of noisy functions, and performing larger number of evaluations can be made in this sense. 7. ACKNOWLEDGMENTS Authors acknowledge funds from the Spanish Ministry of Sciences and Innovation European FEDER under contract TIN2008-06491-C04-01 (M* project, available in URL http://mstar.lcc.uma.es) and CICE, Junta de Andaluc´ıa under contract P07-TIC-03044 (DIRICOM project, available in URL http://diricom.lcc.uma.es). 8. REFERENCES [1] E. Alba, G. Luque, J. Garc´ıa-Nieto, G. Ordonez, and G. Leguizam´on. Mallba: a software library to design efficient optimisation algorithms. Int. J. of Innovative Computing and Applications 2007 (IJICA), 1(1):74–85, 2007. [2] A. Auger and N. Hansen. A restart cma evolution strategy with increasing population size. IEEE Congress on Evolutionary Computation, 2:1769–1776, 2005. [3] S. Das, A. Abraham, and A. Konar. Particle swarm optimization and differential evolution algorithms: Technical analysis, applications and hybridization perspectives. In Advances of Computational Intelligence in Industrial Systems, 2008. [4] S. Finck, N. Hansen, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Presentation of the noisy functions. Technical Report 2009/21, Research Center PPE, 2009. [5] J. Garcia-Nieto, E. J. Apolloni, Alba, and G. Leguizam´on. Algoritmo Basado en C´umulos de Part´ıculas y Evoluci´on Diferencial para la Resoluci´on de Problemas de Optimizaci´on Continua. In VI Congreso Espa˜nol sobre Metaheur´ısticas, Algoritmos Evolutivos y Bioinspirados (MAEB’09), page 433.440, M´alaga, 11 a 13 de Febrero, 2009. [6] N. Hansen, A. Auger, S. Finck, and R. Ros. Real-parameter black-box optimization benchmarking 2009: Experimental setup. Technical Report RR-6828, INRIA, 2009. [7] N. Hansen, S. Finck, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Noisy functions definitions. Technical Report RR-6869, INRIA, 2009. [8] J. Kennedy and R. Eberhart. Particle swarm optimization. Neural Networks, Piscataway, NJ., 2 3 510 20 40 0 1 2 3 4 5 6 7101 Sphere moderate Gauss +1 +0 -1 -2 -3 -5 -8 2 3 510 20 40 0 1 2 3 4 5 6 7104 Rosenbrock moderate Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7 11 107 Sphere Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7110 Rosenbrock Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7 14 12 4 113 Step-ellipsoid Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7102 Sphere moderate unif 2 3 510 20 40 0 1 2 3 4 5 6 7 1 105 Rosenbrock moderate unif 2 3 510 20 40 0 1 2 3 4 5 6 7108 Sphere unif 2 3 510 20 40 0 1 2 3 4 5 6 7111 Rosenbrock unif 2 3 510 20 40 0 1 2 3 4 5 6 7114 Step-ellipsoid unif 2 3 510 20 40 0 1 2 3 4 5 6 7 10 6 103 Sphere moderate Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7106 Rosenbrock moderate Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7109 Sphere Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7112 Rosenbrock Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7 84 115 Step-ellipsoid Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7 2 116 Ellipsoid Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7119 Sum of different powers Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7122 Schaffer F7 Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7 3 125 Griewank-Rosenbrock Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7 14 9 4 128 Gallagher Gauss 2 3 510 20 40 0 1 2 3 4 5 6 7117 Ellipsoid unif 2 3 510 20 40 0 1 2 3 4 5 6 7120 Sum of different powers unif 2 3 510 20 40 0 1 2 3 4 5 6 7123 Schaffer F7 unif 2 3 510 20 40 0 1 2 3 4 5 6 7126 Griewank-Rosenbrock unif 2 3 510 20 40 0 1 2 3 4 5 6 7129 Gallagher unif 2 3 510 20 40 0 1 2 3 4 5 6 7118 Ellipsoid Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7121 Sum of different powers Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7124 Schaffer F7 Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7127 Griewank-Rosenbrock Cauchy 2 3 510 20 40 0 1 2 3 4 5 6 7 3 130 Gallagher Cauchy +1 +0 -1 -2 -3 -5 -8 Figure 1: Expected Running Time (ERT,•) to reach fopt + ∆fand median number of function evaluations of successful trials (+), shown for ∆f= 10,1,10−1,10−2,10−3,10−5,10−8(the exponent is given in the legend of f101 and f130) versus dimension in log-log presentation. The ERT(∆f)equals to #FEs(∆f)divided by the number of successful trials, where a trial is successful if fopt + ∆fwas surpassed during the trial. The #FEs(∆f)are the total number of function evaluations while fopt +∆fwas not surpassed during the trial from all respective trials (successful and unsuccessful), and fopt denotes the optimal function value. Crosses (×) indicate the total number of function evaluations #FEs(−∞). Numbers above ERT-symbols indicate the number of successful trials. Annotated numbers on the ordinate are decimal logarithms. Additional grid lines show linear and quadratic scaling. f101 in 5-D, N=15, mFE=3600 f101 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 8.2e1 6.6 e1 9.9 e1 8.2e1 15 1.3 e3 1.2 e3 1.4e3 1.3 e3 115 4.0e2 3.7 e2 4.2 e2 4.0e2 15 3.6 e3 3.4 e3 3.8e3 3.6 e3 1e−115 7.3e2 7.0 e2 7.5 e2 7.3e2 15 7.9 e3 7.6e3 8.2e3 7.9 e3 1e−315 1.4e3 1.4 e3 1.5 e3 1.4e3 15 2.3 e4 2.1e4 2.4e4 2.3 e4 1e−515 2.1e3 2.1 e3 2.2 e3 2.1e3 77.9 e4 5.9e4 1.2e5 3.7 e4 1e−815 3.2e3 3.2 e3 3.3 e3 3.2e3 027e–6 29e–8 12e–5 4.0 e4 f102 in 5-D, N=15, mFE=3480 f102 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 8.6e1 6.5 e1 1.1 e2 8.6e1 15 1.5 e3 1.4 e3 1.5e3 1.5 e3 115 3.2e2 2.7 e2 3.6 e2 3.2e2 15 3.5 e3 3.4 e3 3.6e3 3.5 e3 1e−115 6.5e2 6.0 e2 7.0 e2 6.5e2 15 7.5 e3 7.3e3 7.8e3 7.5 e3 1e−315 1.3e3 1.2 e3 1.4 e3 1.3e3 13 3.0 e4 2.5e4 3.7e4 2.5 e4 1e−515 2.1e3 2.0 e3 2.1 e3 2.1e3 32.0 e5 1.2e5 6.0e5 4.0 e4 1e−815 3.2e3 3.1 e3 3.3 e3 3.2e3 046e–6 61e–7 14e–4 4.0 e4 f103 in 5-D, N=15, mFE=10040 f103 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.3e2 1.0 e2 1.6 e2 1.3e2 15 1.3 e3 1.3 e3 1.4e3 1.3 e3 115 3.9e2 3.5 e2 4.3 e2 3.9e2 15 3.8 e3 3.6 e3 3.9e3 3.8 e3 1e−115 7.4e2 7.0 e2 7.9 e2 7.4e2 12 2.4 e4 1.8e4 3.1e4 2.0 e4 1e−315 2.2e3 1.9 e3 2.5 e3 2.2e3 034e–3 16e–3 12e–2 3.2 e4 1e−581.4e4 1.1 e4 2.0 e4 8.4e3 .. . . . 1e−8033e–7 79e–8 16e–5 7.9e3 .. . . . f104 in 5-D, N=15, mFE=10040 f104 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 7.7e2 7.0 e2 8.4 e2 7.7e2 019e+0 18e+0 82e+0 3.5 e4 110 8.1e3 6.5 e3 1.0 e4 6.8e3 .. . . . 1e−127.1e4 3.7 e4 >1 e5 1.0e4 .. . . . 1e−3053e–2 60e–3 19e–1 8.9e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f105 in 5-D, N=15, mFE=10040 f105 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 8.9e2 8.0 e2 9.8 e2 8.9e2 020e+0 15e+0 84e+0 3.5 e4 152.3e4 1.6 e4 4.1 e4 8.8e3 .. . . . 1e−127.2e4 3.7 e4 >1 e5 1.0e4 .. . . . 1e−3017e–1 87e–3 30e–1 7.9e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f106 in 5-D, N=15, mFE=10040 f106 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 8.7e2 7.9 e2 9.5 e2 8.7e2 025e+0 18e+0 83e+0 3.5 e4 161.8e4 1.3 e4 3.1 e4 7.5e3 .. . . . 1e−111.5e5 7.3 e4 >1 e5 1.0e4 .. . . . 1e−3014e–1 18e–2 31e–1 8.9e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f107 in 5-D, N=15, mFE=10040 f107 in 20-D, N=15, mFE=40040 ∆f# ERT 10% 90% RTsucc # ERT 10% 90% RTsucc 10 15 1.3e2 9.4 e1 1.6 e2 1.3e2 038e+0 18e+0 71e+0 1.4 e4 115 7.2e2 6.2 e2 8.1 e2 7.2e2 .. . . . 1e−115 1.6e3 1.5 e3 1.8 e3 1.6e3 .. . . . 1e−315 3.5e3 3.2 e3 3.8 e3 3.5e3 .. . . . 1e−513 7.1e3 5.8 e3 9.0 e3 5.6e3 .. . . . 1e−811 1.2e4 9.6 e3 1.5 e4 8.3e3 .. . . . f108 in 5-D, N=15, mFE=10040 f108 in 20-D, N=15, mFE=40040 ∆f# ERT 10% 90% RTsucc # ERT 10% 90% RTsucc 10 15 2.0e2 9.4 e1 3.2 e2 2.0e2 081e+0 59e+0 14e+1 1.1 e4 134.8e4 2.8 e4 1.5 e5 8.3e3 .. . . . 1e−1019e–1 74e–2 47e–1 2.8e3 .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f109 in 5-D, N=15, mFE=10040 f109 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.1e2 8.9 e1 1.3 e2 1.1e2 15 2.4 e3 2.0 e3 2.8e3 2.4 e3 115 3.8e2 3.4 e2 4.2 e2 3.8e2 86.1 e4 4.6 e4 9.0e4 3.3 e4 1e−115 1.2e3 1.0 e3 1.5 e3 1.2e3 099e–2 67e–2 28e–1 3.2 e4 1e−327.2e4 3.6 e4 >1 e5 9.0e3 .. . . . 1e−5051e–4 97e–5 44e–3 7.1e3 .. . . . 1e−8.. . . . .. . . . f110 in 5-D, N=15, mFE=10040 f110 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.6e3 1.4 e3 1.9 e3 1.6e3 072e+2 14e+2 22e+3 2.5 e4 143.4e4 2.2 e4 7.0 e4 9.1e3 .. . . . 1e−1020e–1 38e–2 31e–1 7.1e3 .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f111 in 5-D, N=15, mFE=10040 f111 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 1 1.5 e5 7.4e4 >1e5 1.0 e4 077e+3 42e+3 14e+4 3.2e3 1031e+0 12e+0 94e+0 5.0e3 .. . . . 1e−1.. . . . .. . . . 1e−3. . . . . . . . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f112 in 5-D, N=15, mFE=10040 f112 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 7.9e2 7.4 e2 8.4 e2 7.9e2 037e+0 24e+0 13e+1 3.2 e4 126.7e4 3.6 e4 >1 e5 1.0e4 .. . . . 1e−111.5e5 7.4 e4 >1 e5 1.0e4 .. . . . 1e−3 0 25e–1 31e–2 30e–1 7.1 e3 . . . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f113 in 5-D, N=15, mFE=10040 f113 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 4.1e2 3.3 e2 5.0 e2 4.1e2 014e+1 91e+0 29e+1 1.6 e4 115 1.9e3 1.5 e3 2.2 e3 1.9e3 .. . . . 1e−112 8.1e3 6.5 e3 1.0 e4 6.4e3 .. . . . 1e−343.4e4 2.1 e4 7.0 e4 8.8e3 .. . . . 1e−543.4e4 2.2 e4 7.0 e4 8.8e3 .. . . . 1e−843.4e4 2.2 e4 7.0 e4 9.0e3 .. . . . f114 in 5-D, N=15, mFE=10040 f114 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 13 3.6e3 2.1 e3 5.4 e3 2.7e3 049e+1 44e+1 83e+1 2.5 e4 1042e–1 15e–1 15e+0 5.0e3 .. . . . 1e−1.. . . . .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f115 in 5-D, N=15, mFE=10040 f115 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 3.1e2 2.7 e2 3.6 e2 3.1e2 94.5 e4 3.6 e4 6.1e4 3.1 e4 113 2.7e3 1.6 e3 4.0 e3 2.5e3 093e–1 64e–1 24e+0 3.2 e4 1e−181.2e4 8.6 e3 1.7 e4 7.0e3 .. . . . 1e−3058e–3 11e–3 10e–1 6.3e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f116 in 5-D, N=15, mFE=10040 f116 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 9 1.1 e4 7.8e3 1.5e4 6.5 e3 016e+3 94e+2 38e+3 1.4e4 126.9e4 3.6 e4 >1 e5 1.0e4 .. . . . 1e−127.1e4 3.6 e4 >1 e5 1.0e4 .. . . . 1e−3073e–1 45e–3 26e+0 7.9e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f117 in 5-D, N=15, mFE=10040 f117 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 0 15e+1 61e+0 29e+1 3.2 e3 026e+3 18e+3 43e+3 7.1e3 1.. . . . .. . . . 1e−1.. . . . .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f118 in 5-D, N=15, mFE=10040 f118 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 11 7.1e3 5.3 e3 9.5 e3 5.2e3 055e+1 38e+1 73e+1 3.5 e4 134.6e4 2.6 e4 1.4 e5 7.7e3 .. . . . 1e−111.5e5 7.5 e4 >2 e5 1.0e4 .. . . . 1e−3037e–1 21e–2 19e+0 7.9e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f119 in 5-D, N=15, mFE=10040 f119 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.8e1 1.0 e1 2.6 e1 1.8e1 10 3.5 e4 2.6 e4 4.9e4 2.4 e4 115 6.8e2 5.8 e2 8.0 e2 6.8e2 083e–1 56e–1 15e+0 1.8 e4 1e−114 3.1e3 2.4 e3 4.0 e3 2.9e3 .. . . . 1e−371.9e4 1.4 e4 2.8 e4 9.7e3 .. . . . 1e−5019e–4 17e–5 29e–3 7.9e3 .. . . . 1e−8.. . . . .. . . . f120 in 5-D, N=15, mFE=10040 f120 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 3.7e1 1.6 e1 6.0 e1 3.7e1 031e+0 21e+0 42e+0 3.5 e3 171.4e4 9.6 e3 2.4 e4 5.9e3 .. . . . 1e−1010e–1 60e–2 23e–1 2.8e3 .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . Table 3: Shown are, for functions f101-f120 and for a given target difference to the optimal function value ∆f: the number of successful trials (#); the expected running time to surpass fopt + ∆f(ERT, see Figure 1); the 10%-tile and 90%-tile of the bootstrap distribution of ERT; the average number of function evaluations in successful trials or, if none was successful, as last entry the median number of function evaluations to reach the best function value (RTsucc ). If fopt + ∆fwas never reached, figures in italics denote the best achieved ∆f-value of the median trial and the 10% and 90%-tile trial. Furthermore, N denotes the number of trials, and mFE denotes the maximum of number of function evaluations executed in one trial. See Figure 1 for the names of functions. D=5D= 20 all functions 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f101-130 +1:29/30 -1:20/30 -4:7/30 -8:5/30 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f101-130 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f101-130 +1:14/30 -1:3/30 -4:2/30 -8:0/30 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f101-130 moderate noise 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f101-106 +1:6/6 -1:6/6 -4:3/6 -8:2/6 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f101-106 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f101-106 +1:3/6 -1:3/6 -4:2/6 -8:0/6 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f101-106 severe noise 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f107-121 +1:14/15 -1:9/15 -4:2/15 -8:2/15 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f107-121 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f107-121 +1:4/15 -1:0/15 -4:0/15 -8:0/15 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f107-121 severe noise multimod. 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f122-130 +1:9/9 -1:5/9 -4:2/9 -8:1/9 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f122-130 012 3 log10 of FEvals / DIM 0.0 0.2 0.4 0.6 0.8 1.0 proportion of trials f122-130 +1:7/9 -1:0/9 -4:0/9 -8:0/9 012 3 4 5 678 9 10 11 12 13 14 log10 of Df / Dftarget f122-130 Figure 2: Empirical cumulative distribution functions (ECDFs), plotting the fraction of trials versus running time (left) or ∆f. Left subplots: ECDF of the running time (number of function evaluations), divided by search space dimension D, to fall below fopt + ∆fwith ∆f= 10k, where kis the first value in the legend. Right subplots: ECDF of the best achieved ∆fdivided by 10k(upper left lines in continuation of the left subplot), and best achieved ∆fdivided by 10−8for running times of D, 10 D, 100 D . . . function evaluations (from right to left cycling black-cyan-magenta). Top row: all results from all functions; second row: moderate noise functions; third row: severe noise functions; fourth row: severe noise and highly-multimodal functions. The legends indicate the number of functions that were solved in at least one trial. FEvals denotes number of function evaluations, Dand DIM denote search space dimension, and ∆fand Df denote the difference to the optimal function value. f121 in 5-D, N=15, mFE=10040 f121 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 3.9e1 2.8 e1 5.1 e1 3.9e1 15 1.9 e3 1.5 e3 2.3e3 1.9 e3 115 3.2e2 2.7 e2 3.7 e2 3.2e2 51.0 e5 6.8 e4 1.9e5 3.3 e4 1e−115 1.6e3 1.4 e3 1.8 e3 1.6e3 011e–1 71e–2 28e–1 2.8 e4 1e−3014e–3 68e–4 32e–3 5.6e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f122 in 5-D, N=15, mFE=10040 f122 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 3.4e1 2.2 e1 4.6 e1 3.4e1 15 2.1 e3 1.4 e3 2.8e3 2.1 e3 112 5.0e3 3.6 e3 6.6 e3 4.2e3 063e–1 49e–1 77e–1 1.0 e4 1e−1057e–2 35e–2 12e–1 5.6e3 .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f123 in 5-D, N=15, mFE=10040 f123 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 2.8e1 1.7 e1 4.0 e1 2.8e1 22.9 e5 1.5 e5 >6e5 4.0 e4 111.5e5 7.2 e4 >1 e5 1.0e4 012e+0 95e–1 17e+0 2.0 e4 1e−1026e–1 13e–1 39e–1 2.8e3 .. . . . 1e−3. . . . . . . . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f124 in 5-D, N=15, mFE=10040 f124 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 2.0e1 1.2 e1 2.9 e1 2.0e1 15 6.9 e2 6.0 e2 7.9e2 6.9 e2 115 2.0e3 1.6 e3 2.5 e3 2.0e3 028e–1 22e–1 45e–1 2.8 e4 1e−1027e–2 14e–2 60e–2 7.1e3 .. . . . 1e−3. . . . . . . . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f125 in 5-D, N=15, mFE=10040 f125 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.0e0 1.0 e0 1.0 e0 1.0e0 15 1.2 e0 1.1 e0 1.3e0 1.2 e0 115 3.5e1 2.2 e1 5.0 e1 3.5e1 14 7.8 e3 4.5 e3 1.2e4 7.3 e3 1e−181.2e4 8.7 e3 1.9 e4 6.1e3 081e–2 70e–2 96e–2 1.8 e4 1e−3098e–3 74e–3 17e–2 2.5e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f126 in 5-D, N=15, mFE=10040 f126 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.1e0 1.0 e0 1.3 e0 1.1e0 15 1.1 e0 1.0 e0 1.1e0 1.1 e0 115 5.1e1 3.6 e1 6.8 e1 5.1e1 013e–1 11e–1 16e–1 7.9 e3 1e−111.4e5 6.6 e4 >1 e5 1.0e4 .. . . . 1e−3021e–2 10e–2 27e–2 2.8e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f127 in 5-D, N=15, mFE=10040 f127 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 1.3e0 1.1 e0 1.4 e0 1.3e0 15 1.1 e0 1.0 e0 1.1e0 1.1 e0 115 3.6e1 2.6 e1 4.8 e1 3.6e1 15 9.5 e2 7.9 e2 1.1e3 9.5 e2 1e−181.5e4 1.2 e4 2.1 e4 9.1e3 065e–2 58e–2 75e–2 2.2 e4 1e−3096e–3 35e–3 14e–2 6.3e3 .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f128 in 5-D, N=15, mFE=10040 f128 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 3.2e2 2.1 e2 4.3 e2 3.2e2 066e+0 62e+0 71e+0 2.2 e4 161.9e4 1.3 e4 3.0 e4 8.6e3 .. . . . 1e−143.0e4 2.0 e4 6.1 e4 1.0e4 .. . . . 1e−343.1e4 2.0 e4 6.2 e4 1.0e4 .. . . . 1e−543.2e4 2.1 e4 6.5 e4 1.0e4 .. . . . 1e−843.3e4 2.1 e4 6.7 e4 1.0e4 .. . . . f129 in 5-D, N=15, mFE=10040 f129 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 3.7e2 2.0 e2 5.7 e2 3.7e2 072e+0 69e+0 77e+0 1.3 e4 111.5e5 7.5 e4 >2 e5 1.0e4 .. . . . 1e−1024e–1 14e–1 67e–1 4.0e3 .. . . . 1e−3.. . . . .. . . . 1e−5.. . . . .. . . . 1e−8.. . . . .. . . . f130 in 5-D, N=15, mFE=10040 f130 in 20-D, N=15, mFE=40040 ∆f#ERT 10% 90% RTsucc #ERT 10% 90% RTsucc 10 15 2.5e2 1.9 e2 3.1 e2 2.5e2 11 3.1 e4 2.4 e4 4.0e4 2.3 e4 189.9e3 6.6 e3 1.5 e4 5.7e3 15.8 e5 2.8 e5 >6e5 4.0 e4 1e−161.7e4 1.2 e4 3.0 e4 7.5e3 062e–1 22e–1 19e+0 3.2 e4 1e−343.3e4 2.0 e4 6.9 e4 8.3e3 .. . . . 1e−511.5e5 7.4 e4 >1 e5 1.0e4 .. . . . 1e−8094e–2 16e–5 20e–1 7.1e3 .. . . . Table 4: Shown are, for functions f121-f130 and for a given target difference to the optimal function value ∆f: the number of successful trials (#); the expected running time to surpass fopt + ∆f(ERT, see Figure 1); the 10%-tile and 90%-tile of the bootstrap distribution of ERT; the average number of function evaluations in successful trials or, if none was successful, as last entry the median number of function evaluations to reach the best function value (RTsucc ). If fopt + ∆fwas never reached, figures in italics denote the best achieved ∆f-value of the median trial and the 10% and 90%-tile trial. Furthermore, N denotes the number of trials, and mFE denotes the maximum of number of function evaluations executed in one trial. See Figure 1 for the names of functions. Proceedings of IEEE International Conference on, pages 1942–1948, 1995. [9] K. V. Price, R. Storn, and J. Lampinen. Differential Evolution: A practical Approach to Global Optimization. Springer-Verlag, London, UK, 2005. [10] A. Sinha, S. Tiwari, and K. Deb. A population-based, steady-state procedure for real-parameter optimization. IEEE Congress on Evolutionary Computation, 1:514–521, 2005. [11] P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y.-P. Chen, A. Auger, and S. Tiwari. Problem definitions and evaluation criteria for the cec 2005 special session on real-parameter optimization. Technical report, Nanyang Technological University 2005.