In general, xnew = x1 + F*(x2-x3) where x2 and x3 are randomly selected. If x2 and x3 are ordered so that the difference vector is applied on a downward slope (for a minimization problem), convergence can be faster, but it can also cause premature convergence which can lead to worse overall performance.
This is the summary of the general discussion I've heard, but I can't find any specific references to people who have done these studies. Can anyone point me to work with "directional" difference vectors -- in both single objective and multi-objective problem domains?
Thanks!
Dear Prof. Chen,
Two papers I'm aware of and should be relevant to your question, are as follows:
1. http://www.sciencedirect.com/science/article/pii/S1568494610001134
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.3921&rep=rep1&type=pdf
The first is studying the optimal choice of the base vector (x1 in the equation xnew=...) by comparing all three of them (x1, x2 and x3) in terms of fitness, in order to speed up the convergence rate.
The second is published by James Montgomery, an author who has conducted extensive studies on the movements of DE solution vectors within the search space. The paper listed herein talks specifically about difference vectors and solution vector movements in search space.
Dear prof. Chen.
There are several papers that probably help you related to your question. The scheme proposed is called Trigonometric Mutation Operator and can be consulted, among others, in
A Trigonometric Mutation Operation to Differential Evolution by Hui-Yuan Fan, Jouni Lampinen, Journal of Global Optimization, September 2003, Volume 27, Issue 1, pp 105-129.
Regards.
In the same vein with the post from Prof. Hernández-Díaz, Hui-Yuan Fan and Jouni Lampinen have issued a paper on the directed mutation operation for the Differential Evolution algorithm.
Hui-Yuan Fan, Jouni Lampinen, "A Directed Mutation Operation for the Differential Evolution Algorithm", International Journal of Industrial Engineering 10(1) (2003) 6-15.
Hi all,
The following is a summary of the studies I know about "directed" mutation in DE. I classified them into three categories: (1) use of classical directed mutation (2) proposal of new directed mutation (3) directed mutation in multiobjective DE.
(1) ===== Use of classical directed mutation =====
For "classical directed mutation," here I mean DE/rand-to-best/, DE/current-to-best/, and DE/current-to-rand/ strategies.
SaDE adaptively controls the use of four mutation strategies, including DE/rand-to-best/2/bin and DE/current-to-rand/1. DE/current-to-rand/1 was shown to be effective in solving rotated problems. You may be interested in Fig. 7 in the paper to see the change of utilization percentage of these mutation strategies with respect to the generation number and different problem instances. Similar observations can be found in the paper about SspDE. jDE-2 algorithm uses three mutation strategies, including DE/current-to-best/1/bin. However, there is no result about its particular effect on the performance.
SaDE: http://dx.doi.org/10.1109/TEVC.2008.927706
SspDE: http://dx.doi.org/10.1016/j.cor.2010.06.007
jDE-2: http://dx.doi.org/10.1109/CEC.2006.1688311
(2) ===== Proposal of new directed mutation =====
(2.1) SDE arranges individuals in the population in a ring topology and takes the best individual in the ring neighborhood as the base vector. It is called the DE/lbest/1 strategy.
SDE: http://dx.doi.org/10.1016/j.ejor.2006.10.020
(2.2) DERL/DELB: Like the DE/rand/1 strategy, DERL selects three random individuals. The difference is in that DERL takes the best among the three individuals as the base vector and uses the other two to form the perturbation vector. DELB does a local search after generating the trial vector. It may search toward the trial vector (contraction) or search in the opposite direction (reflection), depending on whether the solution is improved.
DERL/DELB: http://dx.doi.org/10.1016/j.ejor.2004.08.047
(2.3) JADE revises the DE/current-to-best/1 strategy to the DE/current-to-"p"best/1 strategy, which selects one of the best 100p% individuals. It also uses an inferior archive to store the deleted parent individuals and considers the archival members in the perturbation vector. The authors also proposed DE/rand-to-pbest strategies in another paper. These strategies are used in SaJADE and GaDE, and the idea on inferior archive is also seen in LMDEa.
JADE: http://dx.doi.org/10.1109/TEVC.2009.2014613
SaJADE: http://dx.doi.org/10.1109/TSMCB.2010.2056367
GaDE: http://link.springer.com/content/pdf/10.1007%2Fs00500-010-0643-6.pdf
LMBEa: http://dx.doi.org/10.1109/CEC.2012.6252911
(2.4) DEGL generates the donor vector by the weighted sum of a local donor vector and a global donor vector. The global donor vector is generated in the same way as the DE/current-to-best/1 strategy. The local donor vector is generated in a similar way, but the global best individual is replaced by a local best individual in the defined ring neighborhood. DEGL also proposes several methods to control the weight to combine the two donor vectors.
DEGL: http://dx.doi.org/10.1109/TEVC.2008.2009457
(2.5) IMDE seperates the individuals in the population into a better half and a worse half. It generates the donor vector in different groups in different ways. It may generate a donor vector for one group by taking two random members in the same group to calculate the perturbation vector and one random member from the other group as the base vector. Please check the original paper for more details.
IMDE: http://dx.doi.org/10.1016/j.asoc.2012.08.014
(2.6) LMDE detects the landscape and uses DE/pbest/1/exp for unimodal problems and DE/rand/1/exp otherwise.
LMDE: http://dx.doi.org/10.1109/CEC.2012.6256613
(3) ===== Directed mutation in multiobjective DE =====
(3.1) The "Best" individual: To choose the "best" individual for the DE/best/ strategy becomes not trivial in dealing with multiobjective optimization problems. MOSaDE selects one from the archive of non-dominated solutions randomly. JADE2 selects one based on the Pareto rank and crowding distance in their current-to-pbest strategy. MODEA follows the strategy of DERL and selects one of the non-dominated solutions among the three random solutions randomly as the base vector. NSDE-DC revises the DE/current-to-rand/1 strategy by moving toward the individual with a better Pareto rank.
MOSaDE: http://dx.doi.org/10.1109/CEC.2007.4424939
JADE2: http://dx.doi.org/10.1109/CEC.2008.4631174
MODEA: http://dx.doi.org/10.1016/j.ejor.2011.09.025
NSDE-DC: http://dx.doi.org/10.1145/1143997.1144119
(3.2) Some algorithms put restrictions on the candidates for the base vector or for calculating the perturbation vector. For better solution distribution, NSDE-DS revises the DE/current-to-rand/1 strategy by taking two individuals with the same Pareto rank to form the perturbation vector. In MOEA/D-DE, each individual can serve as the target vector, and only individuals in the neighborhood of the target vector can be used to generate the donor vector. In MODE-LD+SS, only individuals that are non-dominated in the neighborhood can be used to generate the donor vector. For the definitions of the neighborhood in MOEA/D and MODE-LD+SS, please refer to the original papers.
NSDE-DS: http://dx.doi.org/10.1145/1143997.1144119
MOEA/D-DE: http://dx.doi.org/10.1109/TEVC.2008.925798
MODE-LD+SS: http://dx.doi.org/10.1109/CEC.2010.5586137
Hope this information is useful. Any comments and corrections are welcome. :)
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication