NCDEoptim {DEoptimR}

Bound-Constrained and Nonlinear Constrained Multimodal Optimization via Differential Evolution

Description

A bespoke implementation of the ‘NCDE’ (neighborhood based crowding DE) algorithm by Qu et al. (2012) doi:10.1109/TEVC.2011.2161873, assisted with the dynamic archive mechanism of Epitropakis et al. (2013) doi:10.1109/CEC.2013.6557556.

Usage

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,
          ...)

Arguments

lower, upper

numeric vectors, the lower and upper bounds of the search space (box constraints); must be finite (is.finite).

fn

a function to be minimized that takes a numeric vector X_i as first argument and returns the value of the objective.

constr

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.

meq

an integer, the first meq constraints are equality constraints whereas the remaining ones are inequality constraints. Defaults to 0 (inequality constraints only).

eps

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.

crit

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.

niche_radius

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.

archive_size

an integer, the maximum number of solutions that can be kept in the archive; entries above this limit are discarded. Default is 100.

reinit_if_solu_in_arch

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.

NP

an integer, the population size. Defaults to 100.

Fl

a numeric, the minimum value that the scaling factor F could take. It defaults to 0.1.

Fu

a numeric, the maximum value that the scaling factor F could take. It defaults to 1.

CRl

a numeric, the minimum value to be used for the crossover constant CR. It defaults to 0.

CRu

a numeric, the maximum value to be used for the crossover constant CR. It defaults to 1.1.

nbngbrsl

an integer, the lower limit for the neighborhood size nbngbrs. It defaults to 1/20 of the population size.

nbngbrsu

an integer, the upper limit for the neighborhood size nbngbrs. It defaults to 1/5 of the population size.

tau_F

a numeric, the probability that the scaling factor F is updated. Defaults to 0.1.

tau_CR

a numeric, the probability that the crossover constant CR is updated. Defaults to 0.1.

tau_pF

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.

tau_nbngbrs

a numeric, the probability that the neighborhood size nbngbrs is updated. Defaults to 0.1.

jitter_factor

a numeric, the tuning constant for jitter. If NULL only dither is used. Default is 0.001.

maxiter

an integer, the maximum number of iterations allowed which is the stopping condition. Default is 2000.

add_to_init_pop

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.

trace

a logical, determines whether or not to monitor the iteration process. Default is FALSE.

triter

an integer, trace output is printed at every triter iterations. Default is 1.

...

additional arguments passed to fn and constr.

Details

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

Value

A list with the following components:

solution_arch

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.

objective_arch

the values of \mathrm{fn}(X_i) for the corresponding columns of solution_arch.

solution_pop

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.

objective_pop

the values of \mathrm{fn}(X_i) for the corresponding columns of solution_pop.

iter

the number of iterations used.

and if there are general constraints present:

constr_value_arch

a matrix whose columns contain the values of the constraints for solution_arch.

constr_value_pop

a matrix whose columns contain the values of the constraints for solution_pop.

Note

This function is in an experimental stage.

Author(s)

Eduardo L. T. Conceicao [e-mail]

References

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. 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. 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. doi:10.1109/TEVC.2011.2161873.

Examples

# 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)