I think of SHADE, which stands for Success-History based Adaptive Differential Evolution, as one of the most effective refinements built on top of classic Differential Evolution. The problem I always ran into with plain DE was that its performance depended heavily on manually choosing good values for F (scale factor) and CR (crossover rate), and the best values often differed not just between problems but between different phases of the same optimization run. SHADE solves this by making F and CR self-adaptive, learning good parameter values from the algorithm’s own successful history as the search progresses. I find it valuable because it removes a large chunk of the manual tuning burden while consistently ranking among the top performers in optimization competitions.
History and Background
I attribute SHADE to Ryoji Tanabe and Alex Fukunaga, who introduced it in their 2013 paper “Success-History Based Parameter Adaptation for Differential Evolution,” presented at the IEEE Congress on Evolutionary Computation (CEC). SHADE built directly on an earlier adaptive DE variant called JADE (Zhang and Sanderson, 2009), which introduced the idea of adapting F and CR based on recent successful values, along with the “current-to-pbest” mutation strategy and an external archive of inferior solutions. SHADE refined this idea by replacing JADE’s single adaptively-updated mean parameter with a historical memory of multiple successful parameter sets, drawn from over the course of the run, giving it a richer and more robust adaptation mechanism. A later variant, L-SHADE (2014), added linear population size reduction and became one of the most consistently winning algorithms in the CEC real-parameter optimization competitions, which is a big part of why I consider the SHADE family a benchmark reference point in evolutionary optimization research.
Problem Statement
I use SHADE for the same class of problems as Differential Evolution — continuous, real-valued, potentially non-differentiable, noisy, or black-box global optimization — but specifically in situations where I don’t want to hand-tune F and CR myself, or where the ideal parameter values likely differ across different regions or phases of the search. The problem SHADE solves is: how do I let an evolutionary algorithm learn its own good control parameters from experience, on the fly, rather than relying on a fixed or manually scheduled parameter setting that may be well-suited to only part of the optimization process?
Core Concepts
- Historical memory (M_F, M_CR): Two arrays of size H that store successful F and CR values (or their weighted means) collected from previous generations.
- Success: A trial vector is considered “successful” if it produces an improvement over its target vector (i.e., it gets selected into the next generation).
- Lehmer mean: A weighted mean used to update the F memory, which is more sensitive to larger successful F values than a simple arithmetic mean.
- Current-to-pbest/1 mutation: A mutation strategy where the mutant vector is generated using the target vector, one of the top p% best individuals, and two randomly chosen vectors (one possibly from an external archive).
- External archive: A set storing recently replaced (inferior) individuals, used to add diversity to the mutation process without expanding the active population.
- p-best: A parameter controlling how many of the top-ranked individuals are eligible to be chosen as the “best” vector in mutation, adding controlled greediness.
How It Works
I run SHADE through this process for each generation:
- I initialize a population of NP vectors randomly, and initialize the historical memory arrays $M_F$ and $M_{CR}$, each of size H, typically all set to 0.5.
- For each individual $i$, I randomly select an index $r$ from the memory and generate $F_i$ and $CR_i$ by sampling from distributions centered on $M_F[r]$ and $M_{CR}[r]$ (Cauchy distribution for F, normal distribution for CR).
- I generate a mutant vector using the current-to-pbest/1 strategy, involving the target vector, a randomly chosen top-performing vector, and vectors from the population and archive.
- I perform binomial crossover using $CR_i$ to produce a trial vector.
- I evaluate the trial vector and compare it to the target: if it’s better, the trial replaces the target in the next generation, and the target is added to the archive; if worse or equal, the target survives.
- I record all F and CR values that led to successful trials, weighted by how much fitness improvement they achieved.
- At the end of the generation, I update one slot of the historical memory using the Lehmer-weighted mean of the successful F values and the weighted mean of successful CR values.
- I repeat this process across generations, with the memory index cycling and old archive entries pruned when the archive exceeds its size limit.
Working Principle
I see SHADE’s core logic as a feedback loop between the algorithm’s performance and its own parameter settings. Whenever a particular (F, CR) pair produces a successful trial vector — meaning it moved the search forward — that pair’s “signature” gets folded back into the historical memory, making similar values more likely to be sampled in future generations. Because the memory holds H different slots rather than just one running average, the algorithm can retain diverse successful parameter regimes simultaneously, which is useful because different problems, or different stages of the same problem, often benefit from different exploration/exploitation trade-offs. The Lehmer mean specifically weights larger successful F values more heavily, reflecting empirical findings that slightly more aggressive mutations tend to correlate with bigger fitness improvements, so the memory doesn’t simply average toward mediocrity.
Mathematical Foundation
For each individual $i$, parameters are sampled as:
$$ CR_i \sim \mathcal{N}(M_{CR}[r_i], 0.1), \quad F_i \sim \text{Cauchy}(M_F[r_i], 0.1) $$
with values truncated/resampled to stay within valid ranges (CR in $[0,1]$, F in $(0,1]$).
The current-to-pbest/1 mutation is defined as:
$$ v_i = x_i + F_i \cdot (x_{pbest} – x_i) + F_i \cdot (x_{r1} – \tilde{x}_{r2}) $$
where $x_{pbest}$ is randomly chosen among the top $p \cdot NP$ individuals, $x_{r1}$ is from the current population, and $\tilde{x}_{r2}$ is chosen from the union of the population and the external archive.
At the end of a generation, given a set $S_F$ and $S_{CR}$ of successful parameter values and their corresponding fitness improvements $\Delta f_k = |f(u_k) – f(x_k)|$, the memory update uses weights:
$$ w_k = \frac{\Delta f_k}{\sum_{j=1}^{|S_F|} \Delta f_j} $$
The CR memory slot is updated with a weighted arithmetic mean:
$$ M_{CR}[idx] = \sum_{k=1}^{|S_{CR}|} w_k \cdot S_{CR,k} $$
The F memory slot is updated with the weighted Lehmer mean:
$$ M_F[idx] = \frac{\sum_{k=1}^{|S_F|} w_k \cdot S_{F,k}^2}{\sum_{k=1}^{|S_F|} w_k \cdot S_{F,k}} $$
Diagrams
flowchart TD
A[Initialize population and memory M_F, M_CR] --> B[Sample F_i, CR_i for each individual from memory]
B --> C[Generate mutant via current-to-pbest/1 strategy]
C --> D[Crossover to form trial vector]
D --> E[Evaluate trial vector]
E --> F{Trial better than target?}
F -- Yes --> G[Replace target, store F_i, CR_i as successful, add old target to archive]
F -- No --> H[Keep target unchanged]
G --> I{Generation complete?}
H --> I
I -- No --> B
I -- Yes --> J[Update memory M_F, M_CR using weighted means]
J --> K{Stopping condition met?}
K -- No --> B
K -- Yes --> L[Return best solution found]Pseudocode
function SHADE(f, D, NP, H, max_evaluations):
population = initialize_random_population(NP, D)
M_F = array of size H filled with 0.5
M_CR = array of size H filled with 0.5
archive = empty set
memory_index = 1
while evaluations < max_evaluations:
S_F = []; S_CR = []; deltas = []
for i in 1 to NP:
r = random_index(1, H)
CR_i = sample_normal(M_CR[r], 0.1)
F_i = sample_cauchy(M_F[r], 0.1)
pbest = pick_random_from_top_p_percent(population)
r1 = random_index_from_population(exclude=i)
r2 = random_index_from_population_union_archive(exclude=i, r1)
mutant = population[i] + F_i*(pbest - population[i]) + F_i*(population[r1] - archive_or_pop[r2])
trial = binomial_crossover(population[i], mutant, CR_i)
if f(trial) <= f(population[i]):
add population[i] to archive
S_F.append(F_i); S_CR.append(CR_i)
deltas.append(|f(trial) - f(population[i])|)
population[i] = trial
// else: keep target unchanged
if S_F is not empty:
weights = normalize(deltas)
M_CR[memory_index] = weighted_mean(S_CR, weights)
M_F[memory_index] = weighted_lehmer_mean(S_F, weights)
memory_index = (memory_index mod H) + 1
trim_archive_to_size(archive, NP)
return best_individual(population)
Step-by-Step Example
I will sketch this with a small illustration on minimizing $f(x)=x_1^2+x_2^2$, with H=3, memory initially all 0.5.
For an individual $x_i = (3, -2)$, fitness 13:
- I sample $r=2$ from memory, get $CR_i \approx 0.55$, $F_i \approx 0.62$ (sampled from distributions centered at the memory values).
- $x_{pbest}$ is one of the current best individuals, say $(0.5, 0.3)$.
- I compute the mutant using current-to-pbest/1: $v_i = (3,-2) + 0.62\cdot((0.5,0.3)-(3,-2)) + 0.62\cdot(x_{r1}-x_{r2})$, which pulls the vector strongly toward the good region near the best individual.
- After crossover with $CR_i=0.55$, I get a trial vector, evaluate it, and suppose its fitness is 6.2 — better than 13.
- Since it’s an improvement, $x_i$ is replaced by the trial, the old $x_i=(3,-2)$ goes into the archive, and $(F_i, CR_i) = (0.62, 0.55)$ is recorded as a successful pair with weight proportional to the improvement $|13-6.2|=6.8$.
- At the end of the generation, this and other successful pairs are combined (weighted more toward large improvements) to update one memory slot, say $M_F[2]$ and $M_{CR}[2]$, nudging future sampling toward similarly effective parameter values.
Time Complexity
Each generation costs $O(NP \cdot D)$ for generating mutants and trial vectors, plus $O(NP \cdot C)$ for evaluating trial fitness, where $C$ is the cost of one objective evaluation. Selecting the p-best individual requires a partial sort of the population, costing $O(NP \log NP)$ per generation if I resort each time (though this can be maintained incrementally). Memory updates cost $O(NP)$ per generation for computing the weighted means. Across $G$ generations, total time is roughly $O(G \cdot NP \cdot (D + C + \log NP))$, which is very close to plain DE’s complexity with a modest constant-factor overhead for the adaptive components.
Space Complexity
Beyond the population’s $O(NP \cdot D)$ storage, SHADE needs space for the historical memory arrays $M_F$ and $M_{CR}$, each of size $H$ (small, often 5–100), and the external archive, which is typically capped at size $NP$, adding another $O(NP \cdot D)$. So overall space complexity remains $O(NP \cdot D)$, with the memory arrays contributing only a negligible constant amount on top.
Correctness Analysis
I evaluate SHADE’s correctness the same way I evaluate DE’s: it inherits DE’s greedy selection, so the best fitness found in the population is monotonically non-increasing (for minimization) across generations — it never regresses. The adaptive parameter mechanism does not change this guarantee; it only changes how F and CR are sampled, which affects search efficiency, not the correctness of the selection step itself. As with DE, a formal proof of convergence to the global optimum requires idealized assumptions (unbounded generations, nonzero probability of sampling any point in the space), but SHADE’s strong empirical track record across CEC benchmark competitions — where it has repeatedly ranked among top-performing algorithms — is the primary evidence I rely on for its practical effectiveness, alongside its inheritance of DE’s theoretical properties.
Advantages
- It removes most of the manual burden of tuning F and CR, letting the algorithm adapt these parameters from its own search history.
- It consistently ranks among top performers in standardized optimization benchmarks (CEC competitions).
- The historical memory retains diverse successful parameter regimes rather than collapsing to a single average, helping it adapt to different search phases.
- It builds on DE’s simplicity and greedy selection, inheriting DE’s monotonic improvement guarantee.
- The external archive adds diversity to mutation without inflating the active population size.
Disadvantages
- It is more complex to implement correctly than plain DE, with more moving parts (memory, archive, p-best selection).
- It introduces its own meta-parameters (memory size H, archive size, p value) that, while less sensitive than F/CR themselves, still require reasonable defaults.
- The added bookkeeping (archive management, memory updates) increases implementation overhead and slightly increases per-generation computation.
- Like DE, it’s primarily designed for continuous spaces and needs adaptation for discrete or combinatorial problems.
- Performance gains over well-tuned plain DE can be modest on very simple problems, where the adaptation machinery adds complexity without much benefit.
Applications
- Numerical benchmark optimization and algorithm competitions (its original proving ground).
- Engineering design problems where good F/CR settings are unknown in advance.
- Machine learning hyperparameter tuning, especially when search budgets are limited and manual tuning of the optimizer’s own parameters isn’t practical.
- Chemical and process engineering optimization with complex, poorly understood objective landscapes.
- Power system and control engineering optimization problems.
- Any large-scale continuous optimization task where an off-the-shelf, low-maintenance, high-performing optimizer is valuable.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define NP 30
#define D 2
#define H 5
#define MAX_GEN 100
#define LOWER -10.0
#define UPPER 10.0
#define ARCHIVE_MAX NP
double M_F[H], M_CR[H];
double population[NP][D];
double archive[ARCHIVE_MAX][D];
int archive_size = 0;
double objective_function(double *x) {
double sum = 0.0;
for (int i = 0; i < D; i++) sum += x[i] * x[i];
return sum;
}
double random_uniform(double lo, double hi) {
return lo + (hi - lo) * ((double) rand() / RAND_MAX);
}
// simple Cauchy sample via inverse CDF
double sample_cauchy(double loc, double scale) {
double u = (double) rand() / RAND_MAX;
return loc + scale * tan(M_PI * (u - 0.5));
}
double sample_normal(double mean, double std) {
double u1 = (double) rand() / RAND_MAX;
double u2 = (double) rand() / RAND_MAX;
double z = sqrt(-2.0 * log(u1)) * cos(2.0 * M_PI * u2);
return mean + std * z;
}
void add_to_archive(double *vec) {
if (archive_size < ARCHIVE_MAX) {
for (int j = 0; j < D; j++) archive[archive_size][j] = vec[j];
archive_size++;
} else {
int idx = rand() % ARCHIVE_MAX; // random replacement
for (int j = 0; j < D; j++) archive[idx][j] = vec[j];
}
}
int main() {
srand((unsigned) time(NULL));
double fitness[NP];
for (int i = 0; i < H; i++) { M_F[i] = 0.5; M_CR[i] = 0.5; }
for (int i = 0; i < NP; i++) {
for (int j = 0; j < D; j++)
population[i][j] = random_uniform(LOWER, UPPER);
fitness[i] = objective_function(population[i]);
}
int mem_idx = 0;
for (int gen = 0; gen < MAX_GEN; gen++) {
double S_F[NP], S_CR[NP], deltas[NP];
int success_count = 0;
// find best individual for pbest selection (simplified: use global best)
int best_idx = 0;
for (int i = 1; i < NP; i++)
if (fitness[i] < fitness[best_idx]) best_idx = i;
double new_population[NP][D];
double new_fitness[NP];
for (int i = 0; i < NP; i++) {
int r = rand() % H;
double CR_i = sample_normal(M_CR[r], 0.1);
double F_i = sample_cauchy(M_F[r], 0.1);
if (CR_i < 0) CR_i = 0; if (CR_i > 1) CR_i = 1;
if (F_i <= 0) F_i = 0.01; if (F_i > 1) F_i = 1;
int r1 = rand() % NP;
while (r1 == i) r1 = rand() % NP;
double *r2_vec;
if (archive_size > 0 && rand() % 2 == 0)
r2_vec = archive[rand() % archive_size];
else
r2_vec = population[rand() % NP];
double mutant[D], trial[D];
for (int j = 0; j < D; j++) {
mutant[j] = population[i][j]
+ F_i * (population[best_idx][j] - population[i][j])
+ F_i * (population[r1][j] - r2_vec[j]);
}
int j_rand = rand() % D;
for (int j = 0; j < D; j++) {
double r_val = (double) rand() / RAND_MAX;
trial[j] = (r_val <= CR_i || j == j_rand) ? mutant[j] : population[i][j];
if (trial[j] < LOWER) trial[j] = LOWER;
if (trial[j] > UPPER) trial[j] = UPPER;
}
double trial_fitness = objective_function(trial);
if (trial_fitness <= fitness[i]) {
add_to_archive(population[i]);
S_F[success_count] = F_i;
S_CR[success_count] = CR_i;
deltas[success_count] = fabs(trial_fitness - fitness[i]);
success_count++;
for (int j = 0; j < D; j++) new_population[i][j] = trial[j];
new_fitness[i] = trial_fitness;
} else {
for (int j = 0; j < D; j++) new_population[i][j] = population[i][j];
new_fitness[i] = fitness[i];
}
}
for (int i = 0; i < NP; i++) {
for (int j = 0; j < D; j++) population[i][j] = new_population[i][j];
fitness[i] = new_fitness[i];
}
// update memory using weighted means (Lehmer mean for F)
if (success_count > 0) {
double weight_sum = 0;
for (int k = 0; k < success_count; k++) weight_sum += deltas[k];
double mean_cr = 0, lehmer_num = 0, lehmer_den = 0;
for (int k = 0; k < success_count; k++) {
double w = deltas[k] / weight_sum;
mean_cr += w * S_CR[k];
lehmer_num += w * S_F[k] * S_F[k];
lehmer_den += w * S_F[k];
}
M_CR[mem_idx] = mean_cr;
M_F[mem_idx] = lehmer_num / lehmer_den;
mem_idx = (mem_idx + 1) % H;
}
int cur_best = 0;
for (int i = 1; i < NP; i++)
if (fitness[i] < fitness[cur_best]) cur_best = i;
printf("Generation %d: best fitness = %f\n", gen, fitness[cur_best]);
}
return 0;
}
Sample Input and Output
For the sphere function over $[-10,10]^2$, a typical run produces output like:
Generation 0: best fitness = 1.842213
Generation 20: best fitness = 0.001204
Generation 50: best fitness = 0.0000021
Generation 99: best fitness = 0.00000003
I usually notice SHADE converging at least as fast as, and often faster and more reliably than, plain DE with a fixed F and CR, especially on more complex multimodal benchmark functions not shown in this simplified sphere example.
Optimization Techniques
- Linear population size reduction (L-SHADE): Gradually shrinking NP over the course of the run focuses computational effort on refinement in later generations.
- Careful p-best selection: Using a small p (like top 10-20%) balances greediness (fast convergence) against diversity (avoiding premature convergence).
- Archive size tuning: Keeping the archive roughly the same size as the population is a common default, but tuning it can help on specific problem classes.
- Memory size H tuning: A moderate memory size (commonly around 5-10) balances responsiveness to recent success against long-term stability of the parameter distribution.
- Boundary handling refinement: Using reflection-based repair instead of simple clipping when trial vectors exceed bounds preserves more useful search direction information.
Common Mistakes
- Forgetting to weight the memory update by fitness improvement, which turns it into an unweighted average and loses the benefit of favoring more impactful parameter values.
- Using the arithmetic mean instead of the Lehmer mean for updating $M_F$, which changes the adaptation’s bias and can hurt performance.
- Allowing the archive to grow unbounded instead of capping and pruning it, which increases memory use and slows down mutation vector selection.
- Not resampling or clipping F and CR values that fall outside valid ranges after sampling from Cauchy/normal distributions.
- Selecting p-best too small (effectively always using the single global best), which can cause premature convergence similar to DE/best/1’s known weaknesses.
Further Reading
- Tanabe, R., Fukunaga, A. “Success-History Based Parameter Adaptation for Differential Evolution.” IEEE Congress on Evolutionary Computation (CEC), 2013: https://ieeexplore.ieee.org/document/6557555
- Tanabe, R., Fukunaga, A. “Improving the Search Performance of SHADE Using Linear Population Size Reduction.” IEEE CEC, 2014: https://ieeexplore.ieee.org/document/6900380
- Zhang, J., Sanderson, A. C. “JADE: Adaptive Differential Evolution with Optional External Archive.” IEEE Transactions on Evolutionary Computation, 2009: https://ieeexplore.ieee.org/document/5208221
- Das, S., Mullick, S. S., Suganthan, P. N. “Recent Advances in Differential Evolution – An Updated Survey.” Swarm and Evolutionary Computation, 2016: https://www.sciencedirect.com/science/article/pii/S2210650216000146
- Wikipedia overview of Differential Evolution (covers adaptive variants): https://en.wikipedia.org/wiki/Differential_evolution
