A bespoke implementation of the ‘NCDE’ (neighborhood based crowding DE) algorithm by Qu et al. (2012) tools:::Rd_expr_doi("10.1109/TEVC.2011.2161873"), assisted with the dynamic archive mechanism of Epitropakis et al. (2013) tools:::Rd_expr_doi("10.1109/CEC.2013.6557556").
NCDEoptim(lower, upper, fn,
constr = NULL, meq = 0, eps = 1e-5,
crit = 1e-5, niche_radius = NULL, archive_size = 100,
reinit_if_solu_in_arch = TRUE,
NP = 100, Fl = 0.1, Fu = 1, CRl = 0, CRu = 1.1,
nbngbrsl = NP/20, nbngbrsu = NP/5,
tau_F = 0.1, tau_CR = 0.1, tau_pF = 0.1,
tau_nbngbrs = 0.1,
jitter_factor = 0.001,
maxiter = 2000,
add_to_init_pop = NULL,
trace = FALSE, triter = 1,
...)A list with the following components:
a matrix whose columns are the
local and global minima stored in the archive of feasible solutions
in ascending order of the objective function values.
the values of \(\mathrm{fn}(X_i)\) for the
corresponding columns of solution_arch.
a matrix whose columns are the
local and global minima stored in the final population
in ascending order of the objective function values;
feasible solutions come first followed by the infeasible ones.
the values of \(\mathrm{fn}(X_i)\) for the
corresponding columns of solution_pop.
the number of iterations used.
and if there are general constraints present:
numeric vectors, the lower and upper bounds of the
search space (box constraints); must be finite
(is.finite).
a function to be minimized that takes a
numeric vector \(X_i\) as first argument and returns the value of the
objective.
a vector function specifying the
left-hand side of equality constraints defined to equal zero
(\(h_j(X_i) = 0,\; j = 1,\ldots,\mathrm{meq}\)),
followed by inequality constraints defined as lesser than zero
(\(g_j(X_i) \le 0,\; j = \mathrm{meq}+1,\ldots\)). This function takes
\(X_i\) as its first argument and returns a numeric vector with the same
length of the total number of constraints. It defaults to NULL,
which means that bound-constrained minimization is used.
an integer, the first meq constraints are
equality constraints whereas the remaining ones are
inequality constraints. Defaults to 0
(inequality constraints only).
the maximal admissible constraint violation for
equality constraints. A numeric vector of small positive tolerance values
with length meq used in the transformation of equalities into
inequalities of the form \(|h_j(X_i)| - \epsilon \le 0\). A scalar value
is expanded to apply to all equality constraints. Default is 1e-5.
a numeric, the acceptance threshold on the archive strategy. If
isTRUE(all.equal(fn(X_best_so_far_in_archive), fn(X_i), tolerance = crit)),
a solution \(X_i\) is checked for possible insertion into the
dynamic archive. Defaults to 1e-5.
a numeric, the absolute tolerance used to decide whether
the solution \(X_i\) is identical to an already existing
local or global solution in the archive. It defaults to NULL,
meaning that the niche radius is adaptively chosen during the search.
Results are much better if one is able to provide
a reasonable value.
an integer, the maximum number of solutions that
can be kept in the archive; entries above this limit are discarded.
Default is 100.
a logical, if TRUE, any solution
\(X_i\) already in the archive reinitializes its nearest neighbor
in the population within the range
\([\mathrm{lower}, \mathrm{upper}]\). Default is TRUE.
an integer, the population size. Defaults to 100.
a numeric, the minimum value that the
scaling factor F could take. It defaults to 0.1.
a numeric, the maximum value that the
scaling factor F could take. It defaults to 1.
a numeric, the minimum value to be used for the
crossover constant CR. It defaults to 0.
a numeric, the maximum value to be used for the
crossover constant CR. It defaults to 1.1.
an integer, the lower limit for the
neighborhood size nbngbrs.
It defaults to 1/20 of the population size.
an integer, the upper limit for the
neighborhood size nbngbrs.
It defaults to 1/5 of the population size.
a numeric, the probability that the
scaling factor F is updated. Defaults to 0.1.
a numeric, the probability that the
crossover constant CR is updated. Defaults to 0.1.
a numeric, the probability that the
mutation probability \(p_F\) in the mutation strategy
DE/rand/1/either-or is updated. Defaults to 0.1.
a numeric, the probability that the
neighborhood size nbngbrs is updated. Defaults to 0.1.
a numeric, the tuning constant for jitter.
If NULL only dither is used. Default is 0.001.
an integer, the maximum number of iterations allowed which is
the stopping condition. Default is 2000.
numeric vector of length length(lower) or
column-wise matrix with length(lower) rows specifying
initial candidate solutions which are appended to the randomly generated
initial population. Default is NULL.
a logical, determines whether or not to monitor the
iteration process. Default is FALSE.
an integer, trace output is printed at every
triter iterations. Default is 1.
additional arguments passed to fn and constr.
Eduardo L. T. Conceicao mail@eduardoconceicao.org
This implementation differs mainly from the original ‘NCDE’ algorithm
of Qu et al. (2012) by employing the archiving procedure proposed
in Epitropakis et al. (2013) and the adaptive ‘jDE’ strategy
instead of canonical Diferential Evolution. The key reason for archiving
good solutions during the search process is to prevent them from being lost
during evolution. Constraints are tackled through the
\(\varepsilon\)-constrained method as proposed
in Poole and Allen (2019). The ‘jDE’ and
\(\varepsilon\)-constrained mechanisms are applied in the same way
as in JDEoptim, but with synchronous mode of
population update. In contrast, the reinitialization in the current
population triggered by already found solutions is done asynchronously.
Each line of trace output follows the format of:
iteration : < value of niche radius > population>> ( value of best solution ) best solution { index of violated constraints } archive>> [ number of solutions found ] ( value of best solution ) best solution
Epitropakis, M. G., Li, X. and Burke, E. K. (2013) A dynamic archive niching differential evolution algorithm for multimodal optimization; in 2013 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp. 79--86. tools:::Rd_expr_doi("10.1109/CEC.2013.6557556").
Poole, D. J. and Allen, C. B. (2019) Constrained niching using differential evolution. Swarm and Evolutionary Computation 44, 74--100. tools:::Rd_expr_doi("10.1016/j.swevo.2018.11.004").
Qu, B. Y., Suganthan, P. N. and Liang, J. J. (2012) Differential evolution with neighborhood mutation for multimodal optimization. IEEE Transactions on Evolutionary Computation 16, 601--614. tools:::Rd_expr_doi("10.1109/TEVC.2011.2161873").
# \donttest{
# NOTE: Examples were excluded from testing
# to reduce package check time.
# Use a preset seed so test values are reproducible.
set.seed(1234)
# Warning: the examples are run using a very small number of
# iterations to decrease execution time.
# Bound-constrained optimization
# Vincent function
#
# f(x) = -mean(sin(10*log(x)))
#
# 0.25 <= xi <= 10, i = {1, 2, ..., n}
# The function has 6^n global minima without local minima.
NCDEoptim(c(0.25, 0.25), c(10, 10),
function(x) -mean(sin(10*log(x))),
niche_radius = 0.2,
maxiter = 200, trace = TRUE, triter = 20)
# Nonlinear constrained optimization
# Function F10 of Poole and Allen (2019)
#
# f(x) = -sin(5*pi*x)^6 + 1
# subject to:
# g(x) = -cos(10*pi*x) <= 0
#
# 0 <= x <= 1
# The 10 global optima are
# (x1*, ..., x10*; f*) = ((2*(1:10) - 1)/20; 0.875).
NCDEoptim(0, 1,
function(x) -sin(5*pi*x)^6 + 1,
function(x) -cos(10*pi*x),
niche_radius = 0.05,
maxiter = 200, trace = TRUE, triter = 20)
# }
Run the code above in your browser using DataLab