DEoptim: Differential Evolution Optimization

Description

Performs evolutionary global optimization via the Differential Evolution algorithm.

Usage

DEoptim(fn, lower, upper, control = DEoptim.control(), ..., fnMap=NULL)

Value

The output of the function DEoptim is a member of the S3 class DEoptim. More precisely, this is a list (of length 2) containing the following elements:

optim, a list containing the following elements:

bestmem: the best set of parameters found.
bestval: the value of fn corresponding to bestmem.
nfeval: number of function evaluations.
iter: number of procedure iterations.

member, a list containing the following elements:

lower: the lower boundary.
upper: the upper boundary.
bestvalit: the best value of fn at each iteration.
bestmemit: the best member at each iteration.
pop: the population generated at the last iteration.
storepop: a list containing the intermediate populations.

Members of the class DEoptim have a plot method that accepts the argument plot.type.

plot.type = "bestmemit" results in a plot of the parameter values that represent the lowest value of the objective function each generation. plot.type = "bestvalit" plots the best value of the objective function each generation. Finally,

plot.type = "storepop" results in a plot of stored populations (which are only available if these have been saved by setting the control argument of DEoptim appropriately). Storing intermediate populations allows us to examine the progress of the optimization in detail. A summary method also exists and returns the best parameter vector, the best value of the objective function, the number of generations optimization ran, and the number of times the objective function was evaluated.

Arguments

fn: the function to be optimized (minimized). The function should have as its first argument the vector of real-valued parameters to optimize, and return a scalar real result. NA and NaN values are not allowed.
lower, upper: two vectors specifying scalar real lower and upper bounds on each parameter to be optimized, so that the i-th element of lower and upper applies to the i-th parameter. The implementation searches between lower and upper for the global optimum (minimum) of fn.
control: a list of control parameters; see DEoptim.control.
fnMap: an optional function that will be run after each population is created, but before the population is passed to the objective function. This allows the user to impose integer/cardinality constraints. See the the sandbox directory of the source code for a simple example.
...: further arguments to be passed to fn.

Author

David Ardia, Katharine Mullen mullenkate@gmail.com, Brian Peterson and Joshua Ulrich.

Details

DEoptim performs optimization (minimization) of fn.

The control argument is a list; see the help file for DEoptim.control for details.

The R implementation of Differential Evolution (DE), DEoptim, was first published on the Comprehensive R Archive Network (CRAN) in 2005 by David Ardia. Early versions were written in pure R. Since version 2.0-0 (published to CRAN in 2009) the package has relied on an interface to a C implementation of DE, which is significantly faster on most problems as compared to the implementation in pure R. The C interface is in many respects similar to the MS Visual C++ v5.0 implementation of the Differential Evolution algorithm distributed with the book Differential Evolution -- A Practical Approach to Global Optimization by Price, K.V., Storn, R.M., Lampinen J.A, Springer-Verlag, 2006. Since version 2.0-3 the C implementation dynamically allocates the memory required to store the population, removing limitations on the number of members in the population and length of the parameter vectors that may be optimized. Since version 2.2-0, the package allows for parallel operation, so that the evaluations of the objective function may be performed using all available cores. This is accomplished using either the built-in parallel package or the foreach package. If parallel operation is desired, the user should set parallelType and make sure that the arguments and packages needed by the objective function are available; see DEoptim.control, the example below and examples in the sandbox directory for details.

Since becoming publicly available, the package DEoptim has been used by several authors to solve optimization problems arising in diverse domains; see Mullen et al. (2011) for a review.

To perform a maximization (instead of minimization) of a given function, simply define a new function which is the opposite of the function to maximize and apply DEoptim to it.

To integrate additional constraints (other than box constraints) on the parameters x of fn(x), for instance x[1] + x[2]^2 < 2, integrate the constraint within the function to optimize, for instance:


    fn <- function(x){
      if (x[1] + x[2]^2 >= 2){
        r <- Inf
      else{
        ...
      }
      return(r)
    }

This simplistic strategy usually does not work all that well for gradient-based or Newton-type methods. It is likely to be alright when the solution is in the interior of the feasible region, but when the solution is on the boundary, optimization algorithm would have a difficult time converging. Furthermore, when the solution is on the boundary, this strategy would make the algorithm converge to an inferior solution in the interior. However, for methods such as DE which are not gradient based, this strategy might not be that bad.

Note that DEoptim stops if any NA or NaN value is obtained. You have to redefine your function to handle these values (for instance, set NA to Inf in your objective function).

It is important to emphasize that the result of DEoptim is a random variable, i.e., different results may be obtained when the algorithm is run repeatedly with the same settings. Hence, the user should set the random seed if they want to reproduce the results, e.g., by setting set.seed(1234) before the call of DEoptim.

DEoptim relies on repeated evaluation of the objective function in order to move the population toward a global minimum. Users interested in making DEoptim run as fast as possible should consider using the package in parallel mode (so that all CPU's available are used), and also ensure that evaluation of the objective function is as efficient as possible (e.g. by using vectorization in pure R code, or writing parts of the objective function in a lower-level language like C or Fortran).

Further details and examples of the R package DEoptim can be found in Mullen et al. (2011) and Ardia et al. (2011a, 2011b) or look at the package's vignette by typing vignette("DEoptim"). Also, an illustration of the package usage for a high-dimensional non-linear portfolio optimization problem is available by typing vignette("DEoptimPortfolioOptimization").

Please cite the package in publications. Use citation("DEoptim").

References

Ardia, D., Boudt, K., Carl, P., Mullen, K.M., Peterson, B.G. (2011) Differential Evolution with DEoptim. An Application to Non-Convex Portfolio Optimization. R Journal, 3(1), 27-34. tools:::Rd_expr_doi("10.32614/RJ-2011-005")

Ardia, D., Ospina Arango, J.D., Giraldo Gomez, N.D. (2011) Jump-Diffusion Calibration using Differential Evolution. Wilmott Magazine, 55 (September), 76-79. tools:::Rd_expr_doi("10.1002/wilm.10034")

Mitchell, M. (1998) An Introduction to Genetic Algorithms. The MIT Press. ISBN 0262631857.

Mullen, K.M, Ardia, D., Gil, D., Windover, D., Cline,J. (2011). DEoptim: An R Package for Global Optimization by Differential Evolution. Journal of Statistical Software, 40(6), 1-26. tools:::Rd_expr_doi("10.18637/jss.v040.i06")

Price, K.V., Storn, R.M., Lampinen J.A. (2006) Differential Evolution - A Practical Approach to Global Optimization. Berlin Heidelberg: Springer-Verlag. ISBN 3540209506.

Storn, R. and Price, K. (1997) Differential Evolution -- A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 11:4, 341--359.

Examples

Run this code

  ## Rosenbrock Banana function
  ## The function has a global minimum f(x) = 0 at the point (1,1).  
  ## Note that the vector of parameters to be optimized must be the first 
  ## argument of the objective function passed to DEoptim.
  Rosenbrock <- function(x){
    x1 <- x[1]
    x2 <- x[2]
    100 * (x2 - x1 * x1)^2 + (1 - x1)^2
  }

  ## DEoptim searches for minima of the objective function between
  ## lower and upper bounds on each parameter to be optimized. Therefore
  ## in the call to DEoptim we specify vectors that comprise the
  ## lower and upper bounds; these vectors are the same length as the
  ## parameter vector.
  lower <- c(-10,-10)
  upper <- -lower
 
  ## run DEoptim and set a seed first for replicability
  set.seed(1234)
  DEoptim(Rosenbrock, lower, upper)

  ## increase the population size
  DEoptim(Rosenbrock, lower, upper, DEoptim.control(NP = 100))

  ## change other settings and store the output
  outDEoptim <- DEoptim(Rosenbrock, lower, upper, DEoptim.control(NP = 80,
                        itermax = 400, F = 1.2, CR = 0.7))
  
  ## plot the output
  plot(outDEoptim)

  ## 'Wild' function, global minimum at about -15.81515
  Wild <- function(x)
    10 * sin(0.3 * x) * sin(1.3 * x^2) +
       0.00001 * x^4 + 0.2 * x + 80

  plot(Wild, -50, 50, n = 1000, main = "'Wild function'")

  outDEoptim <- DEoptim(Wild, lower = -50, upper = 50,
                        control = DEoptim.control(trace = FALSE))
  
  plot(outDEoptim)

  DEoptim(Wild, lower = -50, upper = 50,
          control = DEoptim.control(NP = 50))
 
  ## The below examples shows how the call to DEoptim can be
  ## parallelized.
  ## Note that if your objective function requires packages to be
  ## loaded or has arguments supplied via \code{...}, these should be
  ## specified using the \code{packages} and \code{parVar} arguments
  ## in control.  
  if (FALSE) { 

  Genrose <- function(x) {
     ## One generalization of the Rosenbrock banana valley function (n parameters)
     n <- length(x)
     ## make it take some time ... 
     Sys.sleep(.001) 
     1.0 + sum (100 * (x[-n]^2 - x[-1])^2 + (x[-1] - 1)^2)
  }

  # get some run-time on simple problems
  maxIt <- 250                     
  n <- 5

  oneCore <- system.time( DEoptim(fn=Genrose, lower=rep(-25, n), upper=rep(25, n),
                   control=list(NP=10*n, itermax=maxIt)))

  withParallel <-  system.time( DEoptim(fn=Genrose, lower=rep(-25, n), upper=rep(25, n),
                   control=list(NP=10*n, itermax=maxIt, parallelType=1)))

  ## Compare timings 
  (oneCore)
  (withParallel)
 }

Run the code above in your browser using DataLab