GAopt {NMOF}

Optimisation with a Genetic Algorithm

Description

A simple Genetic Algorithm for minimising a function.

Usage

GAopt (OF, algo = list(), ...)

Arguments

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.

Details

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:

nB

number of bits per solution. Must be specified.

nP

population size. Defaults to 50. Using default settings may not be a good idea.

nG

number of iterations (‘generations’). Defaults to 300. Using default settings may not be a good idea.

crossover

The crossover method. Default is "onePoint"; also possible is “uniform”.

prob

The probability for switching a single bit. Defaults to 0.01; typically a small number.

pen

a penalty function. Default is NULL (no penalty).

repair

a repair function. Default is NULL (no repairing).

initP

optional: 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).

loopOF

logical. Should the OF be evaluated through a loop? Defaults to TRUE.

loopPen

logical. Should the penalty function (if specified) be evaluated through a loop? Defaults to TRUE.

loopRepair

logical. Should the repair function (if specified) be evaluated through a loop? Defaults to TRUE.

methodOF

loop (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).

cl

a cluster object or the number of cores. See documentation of package parallel.

mc.control

a list of named elements; optional settings for mclapply (for instance,

list(mc.set.seed = FALSE))

printDetail

If TRUE (the default), information is printed.

printBar

If TRUE (the default), a txtProgressBar is printed.

storeF

If TRUE (the default), the objective function values for every solution in every generation are stored and returned as matrix Fmat.

storeSolutions

If 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.

classify

Logical; 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.

Value

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 algo$storeF is TRUE, a matrix of size algo$nG times algo$nP containing the objective function values of all solutions over the generations; else NA

xlist

if algo$storeSolutions is TRUE, a list that contains a list P of matrices and a matrix initP (the initial solution); else NA.

initial.state

the value of .Random.seed when the function was called.

Author(s)

Enrico Schumann

References

Gilli, M., Maringer, D. and Schumann, E. (2019) Numerical Methods and Optimization in Finance. 2nd edition. Elsevier. doi:10.1016/C2017-0-01621-X

Schumann, E. (2023) Financial Optimisation with R (NMOF Manual). http://enricoschumann.net/NMOF.htm#NMOFmanual

See Also

DEopt, PSopt

Examples

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