Optimisation with a Genetic Algorithm
A simple Genetic Algorithm for minimising a function.
GAopt (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 a simple Genetic Algorithm (GA). A
GA evolves a collection of solutions (the so-called
population), all of which are coded as vectors containing only zeros
and ones. (In GAopt, solutions are of mode logical.)
The algorithm starts with randomly-chosen or user-supplied population
and aims to iteratively improve this population by mixing solutions
and by switching single bits in solutions, both at random. In each
iteration, such randomly-changed solutions are compared with the
original population and better solutions replace inferior
ones. In GAopt, the population size is kept constant.
GA language: iterations are called generations; new solutions
are called offspring or children (and the existing solutions, from which
the children are created, are parents); the objective function is called
a fitness function; mixing solutions is a crossover; and randomly
changing solutions is called mutation. The choice which solutions remain in
the population and which ones are discarded is called selection. In
GAopt, selection is pairwise: a given child is compared with a
given parent; the better of the two is kept. In this way, the best
solution is automatically retained in the population.
To allow for constraints, the evaluation works as follows: after new
solutions are created, they are (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 can also be directly written
in the OF, since it amounts to a positive number added to the
‘clean’ objective function value; but a separate function is
often clearer. A separate penalty function is advantagous if either only
the objective function or only the penalty function can be vectorised.
Conceptually a GA consists of two loops: one loop across the
generations and, in any given generation, one loop across the solutions.
This is the default, controlled by the variables algo$loopOF,
algo$loopRepair and algo$loopPen, which all default to
TRUE. But it does not matter in what order the solutions are
evaluated (or repaired or penalised), so the second loop can be
vectorised. The respective algo$loopFun must then be set to
FALSE. (See also the examples for DEopt and
PSopt.)
The evaluation of the objective function in a given generation can even
be distributed. For this, an argument algo$methodOF needs to be
set; see below for details (and Schumann, 2011, for examples).
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 contains the following items:
nBnumber of bits per solution. Must be specified.
nPpopulation size. Defaults to 50. Using default settings may not be a good idea.
nGnumber of iterations (‘generations’). Defaults to 300. Using default settings may not be a good idea.
crossoverThe crossover method. Default is
"onePoint"; also possible is “uniform”.
probThe probability for switching a single bit. Defaults to 0.01; typically a small number.
pena penalty function. Default is NULL (no
penalty).
repaira repair function. Default is NULL (no
repairing).
initPoptional: the initial population. A logical
matrix of size length(algo$nB) times algo$nP, or a
function that creates such a matrix. If a function, it must take
no arguments. If mode(mP) is not logical, then
storage.mode(mP) will be tried (and a warning will be
issued).
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.
methodOFloop (the default), vectorised,
snow or multicore. Setting vectorised is
equivalent to having algo$loopOF set to FALSE (and
methodOF overrides loopOF). snow and
multicore use functions clusterApply and
mclapply, respectively. For snow, an object
algo$cl needs to be specified (see below). For
multicore, optional arguments can be passed through
algo$mc.control (see below).
cla cluster object or the number of cores. See
documentation of package parallel.
mc.controla list of named elements; optional settings
for mclapply (for instance,
list(mc.set.seed = FALSE))
printDetailIf TRUE (the default), information
is printed.
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.
storeSolutionsIf TRUE, the solutions (ie,
binary strings) 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 algo$nB times algo$nP.
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.
A list:
xbest |
the solution (the best member of the population) |
OFvalue |
objective function value of best solution |
popF |
a vector. The objective function values in the final population. |
Fmat |
if |
xlist |
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
Schumann, E. (2019) Financial Optimisation with R (NMOF Manual). http://enricoschumann.net/NMOF.htm#NMOFmanual
## a *very* simple problem (why?):
## match a binary (logical) string y
size <- 20L ### the length of the string
OF <- function(x, y) sum(x != y)
y <- runif(size) > 0.5
x <- runif(size) > 0.5
OF(y, y) ### the optimum value is zero
OF(x, y)
algo <- list(nB = size, nP = 20L, nG = 100L, prob = 0.002)
sol <- GAopt(OF, algo = algo, y = y)
## show differences (if any: marked by a '^')
cat(as.integer(y), "\n", as.integer(sol$xbest), "\n",
ifelse(y == sol$xbest , " ", "^"), "\n", sep = "")
algo$nP <- 3L ### that shouldn't work so well
sol2 <- GAopt(OF, algo = algo, y = y)
## show differences (if any: marked by a '^')
cat(as.integer(y), "\n", as.integer(sol2$xbest), "\n",
ifelse(y == sol2$xbest , " ", "^"), "\n", sep = "")Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.