from typing import Union
from .problem import Problem
from .tools.support import compute_statistics, print_info, Logbook, set_progress_bar, BestIndividualTracker, \
FinalResult
[docs]
class DE(object):
"""
Differential Evolution (DE) is a parallel direct search method designed for minimizing possibly nonlinear and
non-differentiable continuous space functions [1]. Starting from an initial random population, the evolutionary
cycle that creates a new population for the next generation consists of an appropriate perturbation of each individual.
In detail, for each target individual, a mutant individual is generated by adding a weighted difference between two or four
randomly chosen individuals to a third individual selected as best or randomly. At this point, a uniform crossover
is applied between the target and the mutant to obtain the trial individual. Lastly, the trial individual is compared
to the target individual to determine the best member of the next generation [2].
References:
[1] R. Storn and K. Price, “Differential evolution–a simple and efficient heuristic for global optimization over
continuous spaces,” Journal of global optimization, vol. 11, no. 4, pp. 341–359, 1997.
[2] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, "A comparison of evolutionary algorithms for
training variational quantum classifiers", Proceedings of 2023 IEEE Congress on Evolutionary Computation (CEC),
pp. 1–8, 2023.
Args:
variant: The variants are denoted as <selection>/<n_diffs>/<crossover>, where <selection> is `best` or `rand`,
<n_diffs> is `1` or `2`, and <crossover> is `bin`.
differential_weight: Differential weight is a hyperparameter that controls the amplification of the individuals
difference used to create the mutant. It must be in the range (0, 2).
If ``(min, max)`` tuple, dithering is employed. Dithering randomly changes the
differential weight in each generation so that it can help speed convergence significantly.
CR: The probability that a parameter of the trial individual is replaced with the corresponding one of the
mutant individual.
"""
def __init__(
self,
variant: str = 'best/1/bin',
differential_weight: Union[float, tuple] = 0.8,
CR: float = 0.9
):
self.variant = variant
self.differential_weight = differential_weight
self.CR = CR
[docs]
def evolve_population(self, problem: Problem, population, fitness, gen):
"""
Evolve the population by means of genetic operators.
Args:
problem : :class:`~.Problem` to be solved.
population: A population of individuals as array of real parameters with (`pop_size`, `n_params`)
shape.
fitness: A set of fitness values associated to the population as array of real values with (`pop_size`, )
shape.
gen: Current generation number.
Returns:
The offspring and fitness values obtained after evolution, and number of fitness evaluations completed
during the evolution.
"""
xp = problem.xp
pop_size, dim = population.shape
if isinstance(self.differential_weight, tuple):
F = xp.random.uniform(self.differential_weight[0],
self.differential_weight[1],
size=(pop_size, 1))
else:
F = self.differential_weight
r = xp.random.randint(0, pop_size, size=(pop_size, 5))
r0, r1, r2, r3, r4 = r.T
def fix(a, b):
return xp.where(a == b, (a + 1) % pop_size, a)
r1 = fix(r1, r0)
r2 = fix(r2, r1)
r3 = fix(r3, r2)
r4 = fix(r4, r3)
selection, n_diff, _ = self.variant.split('/')
if selection == "best":
best_idx = xp.argmin(fitness)
base = population[best_idx]
else:
base = population[r0]
if n_diff == '1':
mutants = base + F * (population[r1] - population[r2])
else:
mutants = base + F * (
population[r1] + population[r2]
- population[r3] - population[r4]
)
cross_mask = xp.random.random((pop_size, dim)) < self.CR
j_rand = xp.random.randint(0, dim, size=(pop_size, 1))
idx = xp.arange(dim)
forced_mask = idx == j_rand
cross_mask = cross_mask | forced_mask
trials = xp.where(cross_mask, mutants, population)
problem.check_bounds(trials)
trial_fitness = problem.evaluate_fitness(trials)
improve = trial_fitness < fitness
offspring = xp.where(improve[:, None], trials, population)
fit_offspring = xp.where(improve, trial_fitness, fitness)
return offspring, fit_offspring, pop_size
[docs]
def optimize(self, problem: Problem, pop_size: int, initial_pop=None,
max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) -> FinalResult:
"""
Optimize the parameters of the problem to be solved.
Args:
problem: :class:`~.Problem` to be solved.
pop_size: Population size.
initial_pop: Initial population of possible solutions as array of real parameters with (`pop_size`, `n_params`)
shape. If None, the initial population is randomly generated from `param_bounds`.
max_nfev: Maximum number of fitness evaluations used. If not None, this is considered as stopping criterion.
max_gen: Maximum number of generations. If `max_nfev` is None, this is considered as stopping criterion.
num_run: Independent execution number of the algorithm.
seed: Initialize the random number generator. If None, the current time is used.
verbose: If True, the statistics of fitness values is printed during the evolution.
Returns:
A :class:`~.FinalResult` containing the optimization result.
"""
xp = problem.xp
if seed is not None:
xp.random.seed(seed)
gen = 0
population = xp.array(initial_pop) if initial_pop is not None else problem.generate_random_pop(pop_size)
fitness = problem.evaluate_fitness(population)
tot_nfev = population.shape[0]
best_tracker = BestIndividualTracker(xp)
best_tracker.update(population, fitness)
pbar = set_progress_bar(max_gen, max_nfev)
if max_nfev is not None:
pbar.update(tot_nfev)
stats = compute_statistics(fitness, xp)
lg = Logbook()
lg.record(gen=gen, nfev=tot_nfev, **stats)
if verbose: print_info(n_run=num_run, gen=gen, nfev=tot_nfev, **stats, header=True)
for gen in range(1, max_gen + 1):
if max_nfev is not None and tot_nfev >= max_nfev:
break
offspring, fit_offspring, nfev = self.evolve_population(problem, population, fitness, gen)
tot_nfev += nfev
population[:] = offspring
fitness[:] = fit_offspring
best_tracker.update(population, fitness)
stats = compute_statistics(fitness, xp)
lg.record(gen=gen, nfev=nfev, **stats)
if verbose: print_info(n_run=num_run, gen=gen, nfev=nfev, **stats)
pbar.update(nfev if max_nfev else 1)
pbar.close()
return FinalResult(x=best_tracker.get_best(), fun=best_tracker.get_best_fit(),
nfev=tot_nfev, gen=gen, log=lg.get_log())