# A Stigmergy-Based Differential Evolution
## 1 Introduction
In the multiple kernel version, the least parallelizable is the update mass kernel. At a given moment, all threads could be trying to write the global best to the same memory location. With respect to DE, several proposals have been made to parallelize this algorithm, such as the one presented in [24], where opposition-based learning and Differential Evolution are programmed with CUDA to optimize 19 benchmark functions. The authors cannot perform the fittest selection in parallel, and they propose a reduction approach to find the best individual at each iteration. A similar approach is found in [25], where only four functions are tested up to 100 dimensions. In this case, the authors propose the use of an adaptive scaling factor and an adaptive crossover probability; even though the authors utilize the DE/rand/1/bin version, they also keep track of the best individual so far. To represent DE variants, a general pattern DE/\(x\)/\(y\)/\(z\) is used, where \(x\) describes the base vector selection type, \(y\) represents the number of differentials and \(z\) is the type of crossover operator, and if there is an asterisk symbol (*) it means that any valid operator can be used for that process. Thus, for DE/rand/1/bin, \"rand\" indicates that the individuals are randomly chosen, \"1\" specifies that only one vector difference is used to form the mutated population and \"bin\" means that a binomial crossover is applied. A survey of DE parallelized on GPGPU is found in [26], tracking the research efforts to parallelize DE from computer networks since 2004, passing through the use of GPGPU with first (and therefore, with a lack of features) CUDA SDKs and ending with a brief exploration of DE and GPU-based frameworks. It is worth mentioning that, in most of the articles, the original operators are preserved and only the parallel implementation is performed using one kernel for each process. To have a general idea about the implementation of DE on GPUs, Table 1 shows some proposals highlighting the implemented DE version, whether any operator was modified or not, the number and type of test functions and the maximum dimensionality. It can be observed that the idea of proposing modifications to differential evolution operators has not been widely investigated. Some metaheuristics utilize two methods to update the global best (individual and fitness) by: (a) comparing it against the corresponding values of every individual in the population and (b) sorting the corresponding values of the entire population. In the first approach, parallelization implies that \(N_{p}-1\) individuals will be trying to update the best fitness value in the actual iteration and the best individual to the same memory's positions: this is the worst-case scenario. This could produce race conditions, which are undesirable because they could produce a loss of information. A better method is the sorting-based approach which can only be partially parallelized, in fact, this DE algorithm version is the one used for comparisons in this research. This paper considers a modification, based on the stigmergy concept, to Differential Evolution (version best/1/bin, in this case the best individual solution of the DE population is selected as the target vector) to eliminate the global best utilization. For this purpose, the mutation and crossover operators are modified. Such adjustment, which we called Stigmergic Differential Evolution (SDE), has a similar performance to the original DE with a lower computational cost in some cases when programmed into GPGPU: mainly, it preserves a good convergence behavior as the dimensionality grows. Therefore, we consider that other metaheuristics that utilize the global best to guide the optimization process could benefit from the proposed methodology. The remaining paper is as follows: Section 2 explains the concept of stigmergy and explores some of its applications to solve engineering problems. Section 3 gives an account of our proposal and the benchmark of optimization problems for the comparisons.