NCDEoptim function

Bound-Constrained and Nonlinear Constrained Multimodal Optimization via Differential Evolution

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

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 $pF$ 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 $epsilon$-constrained method as proposed in Poole and Allen (2019). The jDE and $epsilon$-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 bestsolution ) best solution { index of violated constraints } archive>> [number of solutions found ] ( value of best solution ) best solution

Returns

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.

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

Author(s)

Eduardo L. T. Conceicao mail@eduardoconceicao.org

Note

This function is in an experimental stage.

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)