Several variants of DE using niching methods to extend the usability of the algorithm to multimodal optimization have been presented in the literature. Most of the methods fall in the category of explicit PN, but also the implicit PN concepts of sharing and crowding have been used. This section introduces different DE versions developed for multimodal optimization.
5.4.1 Sharing DE
The fitness sharing concept has been imported to DE by Thomsen [163]. The sharing DE (SHDE) uses the standard sharing function described by equations 3.1 and 3.2, using the Euclidean distance as the distance measure. The method allows the population to double each generation. After NP trials have been generated, the sharing function is used for calculating the fitness for each individual, and the worst half of the population is purged. The algorithm ensures elitism by always preserving the individual with best unscaled fitness. The algorithm suffers from the characteristic problems of sharing: the requirement to defineσradand the high CPT ofO(NP).
5.4.2 Crowding DE
Crowding-based DE (CRDE) presented by Thomsen [163] modifies the selection phase of DEGS (eq. 5.3) so that instead of~xi, the trial ~ui is compared to the most similar member from a random subset of population~xk
~xk=
~ui if f(~ui)≤f(~xk)
~xk otherwise , (5.12)
whose size is defined by theCF parameter. Also the replacement is done instantly to the main population instead of using a separate trial population. The similarity is measured by the Euclidean distance. To eliminate the additional parameter and URE, Thomsen uses CF = NP, which means that CPT is high O(NP). The advantage of CRDE is the lack of additional control parameters. Thomsen performed an experimental study between the sharing and crowding versions of DE. The results demonstrated CRDE to outperform SHDE in all tested cases in locating and maintaining multiple optima.
5.4.3 Speciation-based DE
Speciation-based DE (SDE) proposed by Li [85] is an explicit PN method. The DE population is classified into species according to their similarity measured by Euclidean distance. A procedure for determining species and the dominant individuals in these species is used as in [84]. Each species and its corresponding species seed (the dominant individual) form a separate subpopulation where DEGS is executed locally. To eliminate redundant individuals, a trial having fitness identical to the species seed is replaced by a randomly generated individual. Because species are adaptively formed around different optima, over successive iterations, multiple global optima can be found in parallel. The CPT ofO(c) for SDE is similar as in the clearing approach and thus lower compared to the SHDE and CRDE.
As with SHDE, theσrad parameter is required in order to define the size of a species, which is a major limitation for the method. Parametermdefines the minimum number of members in each species in addition to the species seed. If the species does not have enough members, new individuals are randomly generated withinσradand added to the species. Between generations, onlyNP fittest individuals are preserved. This includes a risk of losing some potential niches before they have enough time to converge, especially with small population sizes combined with large values ofmand smallσrad.
5.4.4 Multipopulation DE
Zaharie [184] proposes a multiresolution multipopulation DE (MMDE), which divides the population toc equally sized subpopulations. The search space is initially divided intocnon-overlapping subdomains, for which the subpopulations are initialized. While the DE algorithm is run independently for each subpopulation, the subpopulations are not restricted to the subdomains used in the initialization. The search is divided into epochs, between which the subpopulations are re-initialized using a finer discretization of the domain, so that the number of subdomains increases bycafter each epoch. The best solution in each subpopulation is stored in an archive after each epoch. To prevent redundant solutions from entering the archive, the Euclidean distance between each new entree is calculated for each existing solution in the archive, and too similar solutions are discarded. Additionally, hill-valley detection [169] is used to exclude solutions belonging to the same peak. For each subpopulation, a subdomain for re-initialization is randomly selected, but the sharing concept is used to exclude the subdomains for which the archive already contains solutions. MMDE does not require the definition of theσradparameter, but introduces a set of new parameters, the number and size of the subpopulations, as well as the number and length of the epochs. The added complexity of the method comes from the re-initialization and archive updating procedures performed between epochs. The complexity increase from the Euclidean distance calculations is affected by the length of an epoch as well as the size of the archive. Thus the CPT for MMDE is approximatelyO(n), wherendefines the number of optima the problem contains, which relates to the size of the archive. However, the hill-valley detection used in updating the archive also requires excess function evaluations, the number of which is related to the archive size andc.
In [183] Zaharie adds crowding to the multipopulation concept producing a multipopu-lation crowding DE (MCDE). The subpopumultipopu-lations are initialized using subdomains as in MMDE. For each subpopulation, the CRDE is used. As CRDE allows each subpopula-tion to locate several optima, the epochs and re-initializasubpopula-tion of MMDE are no longer needed.
5.4.5 Other approaches
Rigling and Moore [126] have implemented an explicit PN method for DE by tagging population members to belong to different subpopulations and implementing a mating re-striction, so that the variation operations are performed only inside each subpopulation.
Additionally, a penalty is applied to members of each subpopulation that are too close to members of different subpopulations to drive each subpopulation towards a different opti-mum. The method requires the definition of the number of subpopulations (c), a penalty term and the minimum spanning distance to be maintained between the subpopulation (effectively theσrad parameter), which are all problem-dependent parameters and thus form a major difficulty for the use of the method. Rumbler and Moore [131] have tried to overcome these limitations by suggesting aNewEDE method for determining the optimal values for these parameters. The idea is to simply run the algorithm repeatedly with different parameter setups to determine suitable values and at the same time keep record of the found solutions. While single values for the problematic parameters are no longer
needed, the problem of parameter selection still remains, as the ranges to be tested are still needed. Of course the repeated runs increase the computational complexity.
Hendershot [62] has further extended the NewEDE concept in an algorithm called Mul-tiDE. The algorithm is similarly run with varying values for thec andσradparameters and records the best found solutions. The method, however, does not use the penalty term and instead compares each trial to the elements in the recorded optimal solutions, and if it differs less than the value of a precision parameter defined by the user, the trial is discarded. Additionally, for each trial the Euclidean distances to the members of other subpopulations are calculated, and if the trial is within theσrad from any of these, it is moved away from that subpopulation. The process is repeated until the trial is not within theσradfrom any member of the other subpopulations. To increase the conver-gence speed, subpopulations which fail to locate new optima within the user-specified maximum number of computations, are eliminated. The main drawback of the MultiDE is the difficulty to tune the control parameters: while the penalty term is removed, the limits for σrad and c are still required. Additionally, the method adds the precision parameter and the maximum number of computations allowed before elimination of sub-population to the list of user defined-parameters. The complexity of the method is high, as for each trialn·(NP−NP/c) (allcsubpopulations are of equal size) Euclidean distance calculations are required, wherendefines the number of repetitions until a suitable trial is found. This gives the method the CPT ofO(NP).