Optimisation with Differential Evolution
The function implements the standard Differential Evolution algorithm.
DEopt(OF, algo = list(), ...)
OF |
The objective function, to be minimised. See Details. |
algo |
A list with the settings for algorithm. See Details and Examples. |
... |
Other pieces of data required to evaluate the objective function. See Details and Examples. |
The function implements the standard Differential Evolution (no jittering or other features). Differential Evolution (DE) is a population-based optimisation heuristic proposed by Storn and Price (1997). DE evolves several solutions (collected in the ‘population’) over a number of iterations (‘generations’). In a given generation, new solutions are created and evaluated; better solutions replace inferior ones in the population. Finally, the best solution of the population is returned. See the references for more details on the mechanisms.
To allow for constraints, the evaluation works as follows: after a new
solution is created, it is (i) repaired, (ii) evaluated through the
objective function, (iii) penalised. Step (ii) is done by a call to
OF; steps (i) and (iii) by calls to algo$repair and
algo$pen. Step (i) and (iii) are optional, so the respective
functions default to NULL. A penalty is a positive number added
to the ‘clean’ objective function value, so it can also be
directly written in the OF. Writing a separate penalty function
is often clearer; it can be more efficient if either only the objective
function or only the penalty function can be vectorised. (Constraints
can also be added without these mechanisms. Solutions that violate
constraints can, for instance, be mapped to feasible solutions, but
without actually changing them. See Maringer and Oyewumi, 2007, for an
example.)
Conceptually, DE consists of two loops: one loop across the
generations and, in any given generation, one loop across the solutions.
DEopt indeed uses, as the default, two loops. But it does not
matter in what order the solutions are evaluated (or repaired or
penalised), so the second loop can be vectorised. This is controlled by
the variables algo$loopOF, algo$loopRepair and
algo$loopPen, which all default to TRUE. Examples are
given in the vignettes and in the book. The respective
algo$loopFun must then be set to FALSE.
All objects that are passed through ... will be passed to the
objective function, to the repair function and to the penalty function.
The list algo collects the the settings for the
algorithm. Strictly necessary are only min and max (to
initialise the population). Here are all possible arguments:
CRprobability for crossover. Defaults to 0.9. Using default settings may not be a good idea.
FThe step size. Typically a numeric vector of length
one; default is 0.5. Using default settings may not be a good
idea. (F can also be a vector with different values for
each decision variable.)
nPpopulation size. Defaults to 50. Using default settings may not be a good idea.
nGnumber of generations. Defaults to 300. Using default settings may not be a good idea.
min, max
vectors of minimum and maximum
parameter values. The vectors min and max are used
to determine the dimension of the problem and to randomly
initialise the population. Per default, they are no constraints: a
solution may well be outside these limits. Only if
algo$minmaxConstr is TRUE will the algorithm repair
solutions outside the min and max range.
minmaxConstrif TRUE, algo$min and
algo$max are considered constraints. Default is
FALSE.
pena penalty function. Default is NULL (no penalty).
initPoptional: the initial population. A matrix of size
length(algo$min) times algo$nP, or a function that
creates such a matrix. If a function, it should take no arguments.
repaira repair function. Default is NULL (no
repairing).
loopOFlogical. Should the OF be evaluated
through a loop? Defaults to TRUE.
loopPenlogical. Should the penalty function (if
specified) be evaluated through a loop? Defaults to TRUE.
loopRepairlogical. Should the repair function (if
specified) be evaluated through a loop? Defaults to TRUE.
printDetailIf TRUE (the default), information
is printed. If an integer i greater then one, information
is printed at very ith generation.
printBarIf TRUE (the default), a
txtProgressBar is printed.
storeFif TRUE (the default), the objective
function values for every solution in every generation are stored
and returned as matrix Fmat.
storeSolutionsdefault is FALSE. If
TRUE, the solutions (ie, decision variables) in every
generation are stored and returned as a list P in list
xlist (see Value section below). To check, for instance,
the solutions at the end of the ith generation, retrieve
xlist[[c(1L, i)]]. This will be a matrix of size
length(algo$min) times algo$nP. (To be consistent
with other functions, xlist is itself a list. In the case
of DEopt, it contains just one element.)
classifyLogical; default is FALSE. If
TRUE, the result will have a class attribute TAopt
attached. This feature is experimental: the supported
methods may change without warning.
dropIf FALSE (the default), the dimension is
not dropped from a single solution when it is
passed to a function. (That is, the function will
receive a single-column matrix.)
A list:
|
the solution (the best member of the population), which is a numeric vector |
|
objective function value of best solution |
|
a vector. The objective function values in the final population. |
|
if |
|
if |
|
the value of |
Enrico Schumann
Gilli, M., Maringer, D. and Schumann, E. (2019) Numerical Methods and Optimization in Finance. 2nd edition. Elsevier. https://www.elsevier.com/books/numerical-methods-and-optimization-in-finance/gilli/978-0-12-815065-8
Maringer, D. and Oyewumi, O. (2007). Index Tracking with Constrained Portfolios. Intelligent Systems in Accounting, Finance and Management, 15(1), pp. 57–71.
Schumann, E. (2012) Remarks on 'A comparison of some heuristic optimization methods'. http://enricoschumann.net/R/remarks.htm
Schumann, E. (2019) Financial Optimisation with R (NMOF Manual). http://enricoschumann.net/NMOF.htm#NMOFmanual
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), pp. 341–359.
## Example 1: Trefethen's 100-digit challenge (problem 4)
## http://people.maths.ox.ac.uk/trefethen/hundred.html
OF <- tfTrefethen ### see ?testFunctions
algo <- list(nP = 50L, ### population size
nG = 300L, ### number of generations
F = 0.6, ### step size
CR = 0.9, ### prob of crossover
min = c(-10, -10), ### range for initial population
max = c( 10, 10))
sol <- DEopt(OF = OF, algo = algo)
## correct answer: -3.30686864747523
format(sol$OFvalue, digits = 12)
## check convergence of population
sd(sol$popF)
ts.plot(sol$Fmat, xlab = "generations", ylab = "OF")
## Example 2: vectorising the evaluation of the population
OF <- tfRosenbrock ### see ?testFunctions
size <- 3L ### define dimension
x <- rep.int(1, size) ### the known solution ...
OF(x) ### ... should give zero
algo <- list(printBar = FALSE,
nP = 30L,
nG = 300L,
F = 0.6,
CR = 0.9,
min = rep(-100, size),
max = rep( 100, size))
## run DEopt
(t1 <- system.time(sol <- DEopt(OF = OF, algo = algo)))
sol$xbest
sol$OFvalue ### should be zero (with luck)
## a vectorised Rosenbrock function: works only with a *matrix* x
OF2 <- function(x) {
n <- dim(x)[1L]
xi <- x[seq_len(n - 1L), ]
colSums(100 * (x[2L:n, ] - xi * xi)^2 + (1 - xi)^2)
}
## random solutions (every column of 'x' is one solution)
x <- matrix(rnorm(size * algo$nP), size, algo$nP)
all.equal(OF2(x)[1:3],
c(OF(x[ ,1L]), OF(x[ ,2L]), OF(x[ ,3L])))
## run DEopt and compare computing time
algo$loopOF <- FALSE
(t2 <- system.time(sol2 <- DEopt(OF = OF2, algo = algo)))
sol2$xbest
sol2$OFvalue ### should be zero (with luck)
t1[[3L]]/t2[[3L]] ### speedupPlease choose more modern alternatives, such as Google Chrome or Mozilla Firefox.