Empirical evaluation of distributed Differential Evolution on standard benchmarks

Empirical evaluation of distributed Differential Evolution on standard benchmarks Javier Apolloni a, ⇑ , José García-Nieto b , Enrique Alba b,c , Guillermo Leguizamón a a LIDIC, Departamento de Informática, Universidad Nacional de San Luis, Ejército de los Andes 950, 5700 San Luis, Argentina b Lenguajes y Ciencias de la Computación, University of Málaga, Campus de Teatinos s/n, 29071 Málaga, Spain c Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, Czech Republic Keywords: Distributed Differential Evolution Non-parametric tests Benchmarking abstract This paper presents a new distributed Differential Evolution (dDE) algorithm and provides an exhaustive evaluation of it by using two standard benchmarks. One of them was proposed in the special session of Real-Parameter Optimization of CEC’05, and the other was proposed in the special session of Large Scale Global Optimization of CEC’08. We statistically validate and compare our results versus all other techniques presented in these special sessions. This means that more than 25 problems, with different dimensions: 30, 50, 100, and 500 variables, are evaluated; and 15 algorithms are compared in the experiments. Our dDE is simple, accurate, and competitive when applied to a wide variety of problems, with scaling dimensions, and different function features: noisy, non-separable, multimodal, rotated, etc. 1. Introduction Metaheuristics [1,2] are optimization algorithms that allow experts to tackle complex problems by iteratively trying to improve a candidate solution, with regard to a given measure of quality (fitness). Possibly, the main feature of metaheuristics is that they make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, although metaheuristics do not guarantee an optimal solution is ever found, they are usually able to obtain high quality solutions with moderate computational cost. In the last decade, Differential Evolution (DE) [3,4] has emerged as a prominent metaheuristic for multidimensional realvalued functions. This technique was designed by Storn and Price in 1997 and has attracted a great attention from the research community since, it is simple and easy to understand, and it shows a special ability to deal with non-differentiable and multimodal optimization problems. In addition, there exists a number of works on theoretical and practical aspects of DE (multiobjective, constrained, dynamic, parallel, etc.) and has been applied on a wide range of real-world problems [4]. Besides the temporal complexity of some (NP-Hard) problems, they can be handled by canonical sequential metaheuristics (including DE), although the exploration procedure (of the search space) performed by them is also time-consuming. In addition, the size of the problem solution space, as well as its complexity, turn increasingly larger with the number of decision variables. As a result, more efficient search strategies are required to explore all the promising regions with limited computational resources. ⇑ Corresponding author. E-mail addresses: [email protected] (J. Apolloni), [email protected] (J. García-Nieto). Parallel distributed models are very useful tools to improve the performance of such techniques during the search process. In particular, DE methods can be easily distributed in a parallel model, since they are based in the evolution of a population of individuals. This population can be partitioned into small subsets known as islands, each subset evolving independently from each other, usually exploring different regions. These islands are spatially structured and exchange information among them to hopefully increase the accuracy and efficiency of the resulting algorithm. When run in a parallel computer, the time reduction is an additional advantage [5]. Furthermore, the latest advances in computing architectures and telecommunication networks allow us to link computers to create a powerful tool for low-cost computing. According to this, the parallel DE algorithm we are proposing here could be used at any granularity, i.e., at the computer, core, or thread levels. For instance, each core could process an island whose set of individuals is evolved by a DE algorithm. In this work, our main motivation is to develop and evaluate a set of distributed versions of Differential Evolution (dDE) with the aim of empirically assess whether these kinds of optimizers are competitive with the current state of the art, or not. Our conjecture is that, a periodical migration of individuals in a given topology leads to a high exploration ability in DE, since the foreign solutions could provide diversity to the island population. We are also interested to analyze the behavior of dDE versions on a set of many problems with different properties: separable/non-separable, unimodal/multimodal, shifted, rotated, hybrid/composed, and on a scaling benchmark with large dimension landscapes. Therefore, in this work we perform a thorough experimentation with our distributed versions of Differential Evolution (dDE) by following the standard procedures applied in two well-known special sessions: Real-Parameter Optimization of CEC’05 [6] and Large Scale Global Optimization of CEC’08 [7]. We statistically assess and compare our results against all the other techniques presented in these sessions, summing up 15 efficient algorithms in the top of the state of the art. The resulted distributions lead us to claim the competitive performance of our dDE, even on specially hard problems with intricate shapes and deceptive landscapes. The contributions of this work can be enumerated as follows: 1. We have analyzed the performance of several distributed versions of DE, and considered also a sequential canonical one. Aversion with two populations seems to show the best results. 2. Our proposed dDE has been evaluated in the CEC’05 experimental framework and compared with the eight proposed algorithms in this benchmark, for problem dimensions of 30 and 50 variables. These comparisons show the competitive performance of our distributed approach, statistically better than other DE versions, and similar to G-CMA-ES (the winner in this special session). 3. In an extensive experimentation, we have evaluated our dDE in the scope of CEC’08 test suite. In this benchmark, a number of 7 large scale problem functions with dimensions 100 and 500 variables are optimized. After statistical comparisons with regards to all presented algorithms in this special session, we can observe that our dDE is again located in the top level of techniques with the best performances. 4. Further analysis concerning the problem function properties show the ability of our dDE to obtain an excellent behavior on non-separable and multimodal functions. The remaining of this paper is organized as follows. Next section offers a review of distributed DE approaches found in the current literature. In Sections 3 and 4, the Canonical DE and the parallel distributed model proposed in this study are described, respectively. Experiments, comparisons, and analysis are presented in Section 5. Finally, concluding remarks and future work are provided in Section 6. 2. Literature overview: distributed DE approaches This section presents a brief overview of the main existing works dealing with distributed population DE algorithms in the literature. Practically all of them consist on island distributed models, with different topologies, and trying to induce diversification/intensification search mechanisms by means of the migration policy of solutions. It is worth mentioning that the use of parallel resources to improve the computational cost is an additional advantage only exploded in some of these works. A first approach was proposed by Zaharie and Petcu [8] consisting on a distributed DE, in which the population is divided into several sub-populations and one DE algorithm is executed in parallel on each sub-population. The motivation of this work was to tackle each optima in multimodal problems with different DE islands, following a random topology for solution exchange. A number of 6 functions were solved by this method. After this, Tasoulis et al. [9] proposed a dDE with islands physically assigned to different processors. In this proposal, a ring topology is established to connect islands and different mutation strategies were also analyzed in the scope of 7 optimization functions and few dimensions (2 to 30). Following this parallel scheme Kozlov and Samsonov [10] used a dDE approach to optimize segment determination gene network, although making a slight adaptation to the migration policy. A modified version of distributed DE was developed by De Falco et al. [11,12] for the registration of 2-D satellite images and for determining the optimal mapping of resource on grid computing, respectively. This proposal used slave processors to execute DE instances and one master processor to collect the information concerning each island. After this, Apolloni et al. [13] made a first preliminary analysis on a bi-population DE with encouraging results that were however partial and need a clear extension on the benchmark used and the algorithms studied to confirm their initial findings. In the above cases, the islands execute identical instances of algorithms with identical parameter setting, then it is said that is an homogeneous distributed model. On the contrary, the following proposals use different parameter setting for each DE island, so the distributed model is featured as heterogeneous. A generic parallelization framework, with several DE mutation strategies, for global optimization was introduced by Izzo et al. [14]. In this approach, the distribution model consisted on up to 5 islands connected by an asynchronous ring topology. The experiments in the scope of 5 well-known problem functions revealed the high performance of the proposal with regards to sequential DE. A novel heterogeneous dDE strategy was proposed by Weber et al. [15], where the population is also partitioned to constitute bi-population models. The sub-populations of the two groups evolve using an island-based DE algorithm, but one of them is used as external archive to keep the population diversity. In particular, at the end of the process, the best solutions are exchanged to incorporate diversity in these foreign sub-populations. In [16] an heterogeneous ring topology island DE model was introduced. In this algorithm, each island was configured with its own mutation factor parameter that may be perturbed as consequence of the migration process. The authors argued that this adaption method can be used for improving the exploration and exploitation of the search space, and tested it on a well-grounded experimental framework. Tasgetiren et al. [17] proposed an ensemble of distributed DE where each island has its own crossover operator and its own parameter values. After each evolutionary step, all of the sub-populations are merged in a single population from which are selected the solutions of the next step. In [18], a different way to perturb the mutation parameter and to improve the exploration and exploitation of the search space was proposed. More specifically, this proposal employs a mechanism that collects all of the sub-populations into a single population and then, divides randomly the population into new sub-populations. More recently, in [19] athorough experimentation was carried out to evaluate and compare a number of different DE versions. In this study, distributed DE versions resulted with a better performance than panmictic ones, as well as other DE approaches in the state of the art. The influence of specific mutation operators were also investigated in this work. A pool of strategies was used by Bujok and Tvrdík [20] to develop a competitive island-based DE. In this approach, the islands are connected into a star topology, each of them executing an instance of DE algorithm. A series of new solutions were generated from operators selected from the pool of strategies. A parallel self-adaptive proposal was introduced by Xie et al. [21], where islands are connected through a ring topology. In this last work, each island uses a DE algorithm to self-adapt the parameter values and avoid getting trapped into local optimal solution. From a different point of view, some authors introduced proposals that modify the topological connection during the evolutionary process. The goal is again to preserve population diversity and avoid premature convergence. In this regard, Biazzini and Montresor [22] proposed a dynamic topology of islands, where DE algorithms are randomly linked anew after each migration operation. The agents attempt to establish which sub-population contributes the most to the evolution, and employ this information to dynamically adapt the connection between islands. A recent strategy in this sense was presented by Sun et al. [23]. In this proposal, a parallel dDE is enhanced with an ensemble of different topologies that automatically adapt the connections among islands during the evolutionary process. The above studies propose several interesting approaches focused on different design aspects of the DE distribution/ parallelization. In the present work, an extensive experimentation is performed with the aim of shedding light on how competitive our dDE is, with regards to other outstanding DE versions, as well as other different metaheuristics in the state of the art. In concrete, the following features can be mentioned that make our work different to other distributed DE studies in the literature: 1. They tackled limited sets of functions with few scaling dimensions. Practically all of them used around 6 well-known functions (Ackley, Rastrigin, Rosenbrock, etc.) with up to 50 problem variables. We use here an extensive benchmark (more than 25 functions) with scaling number of variables: 30, 50, 100, and 500. 2. They where compared against other new and existing versions of DE. In our work, experimental comparisons are addressed in the scope of prominent competitors in special sessions (CEC’05 and CEC’08), where sophisticated versions of DE and other metaheuristics were also tested. 3. They analyzed the performance induced by adapting parameters and/or operators, mostly focused on migration strategies. In the present work, a specific analysis concerning the different function properties is carried out. Then, the possible advantage of using distributed DE populations on: non-separable, multimodal, shifted, and rotated functions is investigated. 3. Differential Evolution: background In the next section, our island model dDE will be described. Before, in this section, background concepts of canonical Differential Evolution algorithm are explained. Differential Evolution (DE) [4] is a stochastic population-based algorithm initially designed to solve optimization problems in continuous domains. In DE, the population is a set of individuals (tentative solutions) which evolve simultaneously through the search space of a given problem to optimize. The individuals are real-value vectors that, by combinations with others from the population, generate new individuals. DE tackles an optimization problem by maintaining a population of candidate solutions and updating them according to a scoring function or fitness. This function provides each solution with a quality measure relative to the optimization problem at hand. In this way, the optimization problem is treated as a black box and additional gradient information is not needed, as happens with classic optimization techniques such as gradient descent and quasi-newton methods [24]. Formally, the population P¼fx 1 ;x 2 ;...;x N gis a set of Nindividuals represented by means of real-valued vectors: x t i ¼ðx t i ð1Þ;x t i ð2Þ;...;x t i ðDÞÞ; where x t i ðjÞ2½x low ;x upp with x low ,x upp 2Rthe lower and upper bound of the domain of the variable j(1 6j6D). The current generation is represented by t(1 6t6t max ), and t max is the maximum number of generations in the iterative evolutionary process. In DE, the task of generating new individuals (real-valued vectors) is performed by operators such as the differential mutation (also known as ‘‘perturbation’’) and crossover. A mutant individual w tþ1 i is generated by a perturbation scheme that is selected when the algorithm is constructed. Storn and Price [3] originally proposed four perturbation schemes: DE/rand/1: w tþ1 i x t r1 þFx t r2 x t r3  :ð1Þ DE/best/1: w tþ1 i b t þFx t r1 x t r2  :ð2Þ DE/best/2: w tþ1 i b t þFx t r1 þx t r2 x t r3 x t r4  :ð3Þ DE/rand-to-best/1: w tþ1 i x t i þkb t x t i  þFx t r1 x t r2  ;ð4Þ where r1;r2;r3;r42f1;2;...;i1;iþ1;...;Ngare random integers mutually different, and also different from index i. Individual b t represents the best solution found so far. The mutation constant F>0 stands for the amplification of the difference between the individuals x r 0 s and it avoids the stagnation of the search process. Parameter kcontrols the greediness of the fourth scheme. To reduce the number of control variables, these two last parameters are usually set to the same value (F¼k). Algorithm 1. Pseudocode of Canonical DE 1: initialize(P) 2: while t<t max do 3: for each individual iof Pdo 4: choose mutually different r s values 5: w tþ1 i mutationðx t r s ;FÞ// Eq. (1) or Eq. (2) or Eq. (3) or Eq. (4) 6: u tþ1 i crossoverðx t i ;w tþ1 i ;CrÞ// Eq. (5) 7: evaluate(u tþ1 i ) 8: x tþ1 i selectionðx t i ;u tþ1 i Þ// Eq. (6) 9: end for 10: end while In order to increase even more the diversity in the population, each mutated individual undergoes a crossover operation with the target individual x t i , by means of which a trial individual u tþ1 i is generated. A randomly chosen position is taken from the mutant individual to prevent that the trial individual replicates the target one. u tþ1 i ðjÞw tþ1 i ðjÞif rðjÞ6Cr or j¼j r ; x t i ðjÞotherwise: (ð5Þ As shown in Eq. (5), the crossover operator randomly chooses a uniformly distributed integer value j r and a random real number r2½0;1,also uniformly distributed for each component jof the trial individual u tþ1 i . Then, the crossover probability Cr, and rare compared just like jand j r .Ifris less or equal to Cr (or jis equal to j r ) then the jth element of the mutant individual is selected to be allocated in the jth element of the trial individual u tþ1 i . Otherwise, the jth element of the target individual x t i becomes the jth element of the trial individual. Finally, a selection operator decides on the acceptance of the trial individual for the next generation if and only if it yields areduction (assuming minimization) in the value of the fitness function fðÞ, as shown by the following Eq. (6): x tþ1 i u tþ1 i if fðu tþ1 i Þ6fðx t i Þ; x t i otherwise: (ð6Þ Algorithm 1 shows the pseudocode of DE. After initializing the population, the individuals evolve during a number of iterations (t max ). Each individual is then mutated (Line 5) and recombined (Line 6). The new individual is selected (or not) following the operation of Eq. (6) (Lines 7 and 8). Although in the literature, up to the authors’ knowledge, there is no precise indication of which scheme is the best (it seems to depend to the tackled problem), nor there is a definitive indication of which values to use for parameters, Price et al. [4] proposed a series of empirically tested values. For instance, crossover probability Cr 2½0;1must be considerably lower than 1, e.g., 0.3, in spite of that, if no convergence can be achieved, a value in ½0;0:8should be used. For many applications, a population size of P¼10 Dis a good choice, being Dthe problem dimension. However, we have to note that this relation for Pis usually set when no restrictions concerning the maximum number of evaluations exist. Unfortunately, in this paper we deal with functions that belong at benchmarking competitions in which a bounded number of function evaluations are allowed. As a consequence, the algorithms dealing with these functions commonly set Pto an value in the interval 10 to 200 [25–39], in order to avoid consuming all of the allowed function evaluations in an early evolution phase of the algorithm. For this reason, we set Pto 20 individuals for all of the experiments/problems/dimensions, thus we achieve that our proposals perform a large number of evolution steps. Regarding mutation constant F, its value is usually chosen in [0.5,1], in such a way that, the higher the population size, the lower the weighting factor F. Clearly, in spite of having DE a few parameters to tune, the success of this algorithm is highly dependent to the complex interaction of them, especially Fand Cr. In this work, a systematic tuning of this two parameters has been carried out for each optimization problem. Then, a series of Fand Cr combinations will be presented in Section 5.2 for the sake of a well-grounded parameter setting. 4. Parallel Differential Evolution As commented before, like almost all the evolutionary algorithms, Differential Evolution suffers from some drawbacks such as risking of stagnation of searching process, because it does not progress for finding any better solution, and related to this, premature convergence to sub-optimal solutions due to a quick lost population diversity. A way of alleviating these problems is to find a balance in the explorative and exploitative capabilities of the algorithm [19].In consequence, some components of DE must be modified for helping to keep the balance. It is known that modifying the original structure of the population leads to improve the performance of the evolutionary algorithms, as well as other population-based metaheuristics [5]. In the literature, there exist several ways of structuring the population, e.g., cellular and island models, that, in certain complex problems, have proven to find better solutions [5,40]. Specifically, in the island model, the population is divided into small disjoint sub-populations and each sub-population is assigned to an island. This model defines a distributed algorithm since, the islands are independent and executes its own evolutionary algorithm. Besides, the island model uses a mechanism of exchanging of information during the evolutionary process. A topological structure of connecting islands, e.g., a ring, a star or randomly (see Fig. 1), is employed to send/receive solutions to/from other islands with certain frequency. It is worth noting this migration process becomes in an effective mechanism to keep the population diversity. Our work is focused on the optimization of continuous complex functions by using a parallel distributed DE based on an implementation suggested by Tasoulis et al. [9]. We use an island connection model where the population is partitioned in small groups of individuals. The individuals inside each island evolve independently from the rest of islands, although making each island occasional communication operations with the others islands to interchange solutions. The interchange of solutions is determined by the migration rate, that defines the number of individuals that are sent to (received from) other islands. A topology neighborhood is defined in the migration policy in order to carry out a guided exchange of solutions between subpopulations. For this migration of solutions, we fix it every certain number of steps of the evolution process of each island. For updating the islands, synchronous and asynchronous modes can be performed. Our dDE Fig. 1. Island based distribution topologies in population EAs. has been configured as asynchronous updating since individuals are received whenever they arrive, with no stops in the execution. 4.1. Island based model of dDE In Algorithm 2, the pseudocode of our island model distributed DE is shown. In this algorithm, the whole population Pis structured in msmaller subpopulations P i of n i individuals where N¼P m i¼1 n i . Each subpopulation is randomly (uniform) initialized, and it evolves in parallel independently and relatively isolated from the others performing periodical exchanges of solutions. The migration policy is determined by a five-tuple M¼h c ; q ;/ s ;/ r ; s iwhere c 2Ndenotes the migration gap between two successive exchanges of individuals, q 2Ndenotes the migration rate in every exchange, functions / s and / r decide how to select the individuals involved in the exchange. The selection function / s , decides what individuals select to migrate, and the individuals that arrive substitute those local individuals previously determined by the replacement function / r . The topological model is denoted by the function s :P!2 P , which selects what subpopulations can send to (or receive from) individuals. Algorithm 2. Pseudocode of the Distributed DE 1: DO IN PARALLEL for each i2f1;...;mg 2: initialize(P i ) 3: while t<t max do 4: perform a step of canonical DE// as in Algorithm 1 5: for each of the q individuals to send do 6: v t / s ðP i Þ 7: send v t to P j chosen by s // being P j the neighbor subpopulation 8: end for 9: while individuals are arriving do 10: receive v t /*asynchronous communication*/ 11: replace individual chosen from / r ðP j Þby v t 12: end while 13: end while In our algorithm, the individuals to be migrated are uniform randomly chosen by the selection function / s (line 6 in Algorithm 2). If the incoming individuals from other islands have higher performance than local ones chosen by the replacement function / r (line 11 in Algorithm 2), then the latter are substituted by the former. The topology is a unidirectional ring in which the individuals are exchanged with the nearest neighbor subpopulation. 5. Experimental study We now analyze the behavior of our dDE by performing a set of experiments plus a statistical validation with the reported results. We have used the skeleton architecture in C++ of the MALLBA Library [41] to easily develop our dDE algorithm. The underlying communication platform is implemented with the MPICH library (v.1.5.2) deployed on machines with O.S. Linux SUSE. For the experimental comparisons, we have used non-parametric statistical tests, since some times the numerical distributions of results did not follow the conditions of normality and homoscedasticity [42]. Therefore, our analyses are mainly focused on the whole distribution errors, although paying special attention on the mean errors, out of 25 independent runs. In particular, we have considered the application of Wilcoxon’ Pairwise, Friedman’s ranking, and Holm’s multicompare tests, this last as post hoc procedure [43], to know which algorithms are statistically worse than the reference algorithm (the one with the best ranking). We include in this study a series of comparisons with the canonical version of DE, as well as the algorithms of the state of the art (reference techniques for the tackled problems) in order to clarify how competitive our proposal is. Before, the set of benchmarking test functions and the parameter settings are detailed. 5.1. Test functions As commented in Section 1,we have used two different sets of functions to tests our dDE algorithm: the benchmark proposed in special session on Real-Parameter Optimization of CEC’05 [6], and the benchmark proposed in the special session on Large Scale Global Optimization of CEC’08 [7]. The test suite CEC’05 includes 25 optimization functions with different properties. The first 5 functions are unimodal and the remaining (20) are multimodal ones. In this work, we are mainly interested on multimodal functions with high complexities. The CEC’08 test suite includes 2 unimodal and 5 multimodals. The first 6 are basic and composed functions and the seventh one has been taken from an external benchmark of fractal functions whose global optimum is unknown so far. Table 1 shows the set of functions used in this study. A total number of 27 functions with heterogeneous landscapes and complexities, which are indexed as: f 6 to f 25 corresponding to CEC’05 functions, and g 1 to g 7 the ones of CEC’08. In terms of function structure, they can be featured as: single shifted structure (f 6 to f 12 ), expanded (f 13 to f 14 ), hybrid composed (f 15 to f 25 ), and large scale (g 1 to g 7 ). In this table, their most interesting properties are also highlighted: unimodal (U), multimodal (M), separable (Sep.), non-separable, shifted to biased optimum, rotated (Rot.), and hybrid composed. The respective bounds of search ranges (S.R.) and biases to optima (f  ) are also indicated. In this regard, all functions except for g 7 (which optimum is unknown) have the global optimum shifted to a value different from zero named bias. A shifted function to a bias is useful to avoid a symmetry on the search space that DE could exploit in its benefit. In two functions (f 8 and f 20 ), the optima cannot be found within the initialization range, and the domain of search is not limited (the optimum is out of the range of initialization). The complete descriptions of all these functions can be found in [7,6]. With the aim of illustrating the hardness of the tackled problems, Fig. 2shows the fitness landscapes of functions: f 15 ;f 19 ;g 6 , and g 7 . All these functions, excepting g 6 , show intricate landscapes with a great number of basins of attraction to local optima, with multi-funnel regions, and with rotated structures to the axis of coordinates. In the case of g 6 , the landscape is equally complex, since it consists on a great plateau area (where is difficult to search) with a narrow and shifted basin of attraction near to the borders. We have to note that these fitness landscapes were plotted for just two problem variables (dimension 2), although we have dealt with: 30, 50, 100, and 500 variables in our experiments. Following the specifications of the two benchmarks used, we have applied as stop conditions a maximum number of 10;000 Dfitness evaluations for CEC’05 functions, with scaling dimensions D¼30 and D¼50; and 5000 Dfitness evaluations for CEC’08 functions, with D¼100 and D¼500. We have performed 25 independent runs for each investigated DE version, problem function, and problem scale, summing up 25 327 4¼8100 experimental executions. We report the error values of the best solution (x) found defined as: fðxÞf  , where f  is the optimum fitness of function f. Error values lower than 10 14 (0-threshold) are approximated to zero. 5.2. Parameter setting The set of parameters used to tune our dDE were selected after preliminary experiments as follows: the population Pwas set to 20 individuals and was partitioned in msubpopulations (islands), each one having nindividuals where P m n¼20. The Table 1 CEC’05 and CEC’08 benchmarks with functions’ features: unimodal (U), multimodal (M), separable (Sep.) and non-separable, rotated (Rot.) and non-rotated. Problem search ranges (S.R.) and biases to optima values fare specified. RHC stands for Rotated Hybrid Composed. f Name U/M Sep. Rot. S.R. f  f 6 Shif. Rosenbrock’s Function M N N [100, 100] 390 f 7 Shif. Rot. Griewank’s. Opt. Out. Bounds M N R [0, 600] 180 f 8 Shif. Rot. Ackley’s Opt. on Bounds M N R [32, 32] 140 f 9 Shif. Rastrigin’s Function M S N [5, 5] 330 f 10 Shifted Rotated Rastrigin’s M N R [5, 5] 330 f 11 Shifted Rotated Weierstrass M N R [0.5, 0.5] 90 f 12 Schwefel’s Problem 2.13 M N N [ p ; p ]460 f 13 Shif. Exp. Griewank’s aRosenbrock’s MNN[3, 1] 130 f 14 Shif. Rot. Expanded Scaffer’s F6 M N R [100, 100] 300 f 15 HC (f1-f2,f3-f4,f5-f6,f7-f8,f9-f10) M N N [5, 5] 120 f 16 RHC f15 M N R [5, 5] 120 f 17 F16 with Noise in Fitness M N R [5, 5] 120 f 18 RHC (f1-f2,f3-f4,f5-f6,f7-f8,f9-f10) M N R [5, 5] 10 f 19 RHC Narrow Basin Global Optimum M N R [5, 5] 10 f 20 RHC Global Optimum on Bounds M N R [5, 5] 10 f 21 RHC (f1-f2,f3-f4,f5-f6,f7-f8,f9-f10) M N R [5, 5] 360 f 22 RHC High Condition Number Matrix M N R [5, 5] 360 f 23 Non-Continuous Rot. Hybr. Comp. M N R [5, 5] 360 f 24 RHC (f1,f2,f3,f4,f5,f6,f7,f8,f9,f10) M N R [5, 5] 260 f 25 RHC Global Optimum Outside Bounds M N R [2, 5] 260 g 1 Shifted Sphere Function U S N [100, 100] 450 g 2 Shifted Schwefel’s Problem 2.21 U N N [100, 100] 450 g 3 Shifted Rosenbrock’s Function M N N [100, 100] 390 g 4 Shifted Rastrigin’s Function M S N [5, 5] 330 g 5 Shifted Griewank’s Function M N N [600, 600] 180 g 6 Shifted Ackley’s Function M S N [32, 32] 140 g 7 FastFractal ‘‘DoubleDip’’ Function M N N [1, 1] Unknown Fig. 2. Complex fitness landscapes of functions: f 15 ;f 19 ;g 6 , and g 7 . Table 2 Parameters Fand Cr of dDE for each problem function of CEC’05 benchmark. F/D 30 50 FCrFCr f 6 5.0E01 4.0E01 5.0E01 4.5E01 f 7 5.0E01 5.0E01 5.0E01 5.0E01 f 8 5.0E01 5.0E01 5.0E01 5.0E01 f 9 9.0E01 1.0E02 9.0E01 1.0E02 f 10 5.0E01 2.0E01 4.0E01 5.0E01 f 11 9.0E01 5.0E01 9.0E01 1.0E01 f 12 5.0E01 1.0E01 5.0E01 1.0E01 f 13 9.0E01 1.0E03 9.0E01 1.0E03 f 14 9.0E01 1.0E03 9.0E01 1.0E03 f 15 1.0E01 1.0E03 9.0E01 1.0E03 f 16 9.0E01 1.0E02 9.0E01 2.0E01 f 17 9.0E01 5.0E01 9.0E01 5.0E01 f 18 5.5E01 4.0E01 5.5E01 4.0E01 f 19 5.0E01 5.0E01 5.0E01 5.0E01 f 20 5.5E01 5.0E01 5.5E01 5.0E01 f 21 5.0E01 1.0E02 5.0E01 1.0E01 f 22 5.0E01 5.0E01 5.0E01 5.0E01 f 23 5.0E01 1.0E01 5.0E01 1.0E02 f 24 9.0E01 9.0E01 9.0E01 9.0E01 f 25 9.0E01 9.0E01 9.0E01 9.0E01 migration gap and migration rate were set to c ¼100 and q ¼1, respectively. As previously mentioned, one randomly selected individual is sent from an island to another one in a non-blocking policy of migration. Concerning the DE specific parameters, Table 2shows the values of Fand Cr. These values have arisen from a systematic adjust that we performed for each function and dimension of the benchmark suite CEC’05. In the case of CEC’08, parameters have been set to F= 5.0E01 and Cr = 1.0E02 for all functions and dimensions, in order to following the competition rules of this benchmark [7]. It is worth noting that all of these values have been fixed for all our DE versions, including the canonical one. In this way, we look for applying the same learning procedure to our Differential Evolution strategy, with the aim of discovering the underlying benefits of using different distribution models. 5.3. Comparative study This section presents a comparative study of our different dDE versions. Later, a series of analyses in terms of function’s properties will be also given. 5.3.1. Comparative study of dDE versus Canonical DE As a first analysis, we compare here the canonical version of DE (seqDE) with two different versions of our island model DE (dDE). In the former, a whole population of 20 individuals evolves without separated structures. In the first island model, dDE 2 , the population of 20 individuals is split into two subpopulations (islands) of 10 individuals each one. In the second island model, dDE 4 , the whole population is divided into four subpopulations of 5 individuals. For these comparisons, we have applied the Wilcoxon Signed-Rank test [44] to compare each possible pair of DE models (seqDE, dDE 2 , dDE 4 ) on CEC’05 functions and for dimensions with 30 and 50 problem variables. As shown in Table 3, the statistical test calculates the differences between two distributions, and these differences are split into groups of positive and negative values. In this table, column R+ represents the sum of ranks with positive differences, and Ris the respective sum of negative differences, which gives us information about the algorithm with better performance. For example, in the comparison of seqDE versus dDE 2 for dimension 30, the sum of positive ranks (105) is greater than the sum of negative ones (48), meaning that seqDE distributions are higher than the ones of dDE 2 . Since we are dealing with minimizing functions, we can claim that our distributed DE with 2 islands is better ranked than the Canonical DE (seqDE), for CEC’05. With the aim of showing whether statistical differences exist (or not) between these distributions, we have also calculated the p-values of these tests with a confidence level of 95%. In this way, we can assure that significant differences exist when resulted p-values are lower than 0.05. As we can observe in the Table 3, our distributed DE model with two island (dDE 2 ) achieves higher ranks than the canonical model (seqDE) for the two dimensions: 30 and 50. A similar observation can be made when comparing the Canonical DE and the distributed model with four islands (dDE 4 ) for dimension 50. Although in the case of dimension 30, the sum of the positive ranks of seqDE is lower than the sum negative ones, then seqDE outperforms the performance of dDE 4 . However, the most interesting results are the ones concerning the comparison of the two distributed models, since for all dimensions, dDE 2 shows better ranks than dDE 4 , and resulted p-values are in both cases lower than 0.05 (2.00E03 for dimension 30 and 1.80E02 for dimension 50). From a graphical point of view, Fig. 3shows the trace progress performed by the three DE versions: seqDE, dDE 2 , and dDE 4 , for functions f 6 ;f 12 ;f 17 , and f 22 with dimension 30 variables. In this plot, we can observe that the distributed versions of DE show, in general, a delayed convergence with regards to the canonical one, probably induced by the migration policy in the formers. We suspect that the migration of fresh individuals from the other island in dDE 2 could enhance the local diversity of subpopulations, then improving the global results in terms of solution quality. However, an excessive diversity together with a low number of individuals in subpopulations could degrade the final results, as observed in dDE 4 . We now will face the last analysis of this section, where a comparison involves the dDE approach proposed in [9] since, as we commented before, we have based on this algorithm to design our own distributed Differential Evolution. For the reproduction of this approach (Tasoulis et al. [9]), we have followed the specifications as described in the referenced work, where the authors used a similar island-distribution scheme to our dDE 2 . For the sake of a fair comparison, we use two population and set Pto 20 individuals, i.e., 10 individual in each population, and the parameter values for Fand Cr are taken from Table 2. However, in Tasoulis’ proposal we use the differential mutation DE/best/1 (Eq. (2)) because it was Table 3 Signed-Rank test of seqDE, dDE 2 and dDE 4 in terms of the mean of the error value at a significance level of 95% (p-value = 0.05). Lowest signed-ranks are shown in bold. Algorithm Dimension R+ Rp-value seqDE versus dDE 2 30 105 48 1.85E01 50 110 61 2.95E01 seqDE versus dDE 4 30 66 105 4.08E01 50 107 103 9.56E01 dDE 2 versus dDE 4 30 15 156 2.00E03 50 31 140 1.80E02 [42] S. García, D. Molina, M. Lozano, F. Herrera, A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005, J. Heuristics 15 (2009) 617–644. [43] D.J. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures, Chapman & Hall/CRC, 2007. [44] R. Wilcox, New Statistical Procedures for the Social Sciences, Hillsdale, 1987. [45] N. Hansen, R. Ros, N. Mauny, M. Schoenauer, A. Auger, Impacts of invariance in search: when CMA-ES and PSO face ill-conditioned and non-separable problems, Appl. Soft Comput. 11 (2011) 5755–5769.