GAopt: Optimisation with a Genetic Algorithm
In NMOF: Numerical Methods and Optimization in Finance
Description
Usage
Arguments
Details
Value
Author(s)
References
See Also
Examples
Description
A simple Genetic Algorithm for minimising a function.
Usage
1
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:
nBnumber of bits per solution. Must be specified.
nPpopulation size. Defaults to 50. 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 snow.
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.
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; 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. (2011) Numerical
Methods and Optimization in Finance. Elsevier.
http://www.elsevierdirect.com/product.jsp?isbn=9780123756626
Schumann, E. (2013) The NMOF Manual.
http://enricoschumann.net/NMOF.htm
See Also
Examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
## 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,
printBar = TRUE)
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 = "")
Example output
[1] 0
[1] 9
Genetic Algorithm.
|
| | 0%
|
|= | 1%
|
|= | 2%
|
|== | 3%
|
|=== | 4%
|
|==== | 5%
|
|==== | 6%
|
|===== | 7%
|
|====== | 8%
|
|====== | 9%
|
|======= | 10%
|
|======== | 11%
|
|======== | 12%
|
|========= | 13%
|
|========== | 14%
|
|=========== | 15%
|
|=========== | 16%
|
|============ | 17%
|
|============= | 18%
|
|============= | 19%
|
|============== | 20%
|
|=============== | 21%
|
|================ | 22%
|
|================ | 23%
|
|================= | 24%
|
|================== | 25%
|
|================== | 26%
|
|=================== | 27%
|
|==================== | 28%
|
|===================== | 29%
|
|===================== | 30%
|
|====================== | 31%
|
|======================= | 32%
|
|======================= | 33%
|
|======================== | 34%
|
|========================= | 35%
|
|========================= | 36%
|
|========================== | 37%
|
|=========================== | 38%
|
|============================ | 39%
|
|============================ | 40%
|
|============================= | 41%
|
|============================== | 42%
|
|============================== | 43%
|
|=============================== | 44%
|
|================================ | 45%
|
|================================= | 46%
|
|================================= | 47%
|
|================================== | 48%
|
|=================================== | 49%
|
|=================================== | 51%
|
|==================================== | 52%
|
|===================================== | 53%
|
|===================================== | 54%
|
|====================================== | 55%
|
|======================================= | 56%
|
|======================================== | 57%
|
|======================================== | 58%
|
|========================================= | 59%
|
|========================================== | 60%
|
|========================================== | 61%
|
|=========================================== | 62%
|
|============================================ | 63%
|
|============================================= | 64%
|
|============================================= | 65%
|
|============================================== | 66%
|
|=============================================== | 67%
|
|=============================================== | 68%
|
|================================================ | 69%
|
|================================================= | 70%
|
|================================================= | 71%
|
|================================================== | 72%
|
|=================================================== | 73%
|
|==================================================== | 74%
|
|==================================================== | 75%
|
|===================================================== | 76%
|
|====================================================== | 77%
|
|====================================================== | 78%
|
|======================================================= | 79%
|
|======================================================== | 80%
|
|========================================================= | 81%
|
|========================================================= | 82%
|
|========================================================== | 83%
|
|=========================================================== | 84%
|
|=========================================================== | 85%
|
|============================================================ | 86%
|
|============================================================= | 87%
|
|============================================================== | 88%
|
|============================================================== | 89%
|
|=============================================================== | 90%
|
|================================================================ | 91%
|
|================================================================ | 92%
|
|================================================================= | 93%
|
|================================================================== | 94%
|
|================================================================== | 95%
|
|=================================================================== | 96%
|
|==================================================================== | 97%
|
|===================================================================== | 98%
|
|===================================================================== | 99%
|
|======================================================================| 100%
Best solution has objective function value 0 ;
standard deviation of OF in final population is 0 .
10010101010000011000
10010101010000011000
Genetic Algorithm.
|
| | 0%
|
|= | 1%
|
|= | 2%
|
|== | 3%
|
|=== | 4%
|
|==== | 5%
|
|==== | 6%
|
|===== | 7%
|
|====== | 8%
|
|====== | 9%
|
|======= | 10%
|
|======== | 11%
|
|======== | 12%
|
|========= | 13%
|
|========== | 14%
|
|=========== | 15%
|
|=========== | 16%
|
|============ | 17%
|
|============= | 18%
|
|============= | 19%
|
|============== | 20%
|
|=============== | 21%
|
|================ | 22%
|
|================ | 23%
|
|================= | 24%
|
|================== | 25%
|
|================== | 26%
|
|=================== | 27%
|
|==================== | 28%
|
|===================== | 29%
|
|===================== | 30%
|
|====================== | 31%
|
|======================= | 32%
|
|======================= | 33%
|
|======================== | 34%
|
|========================= | 35%
|
|========================= | 36%
|
|========================== | 37%
|
|=========================== | 38%
|
|============================ | 39%
|
|============================ | 40%
|
|============================= | 41%
|
|============================== | 42%
|
|============================== | 43%
|
|=============================== | 44%
|
|================================ | 45%
|
|================================= | 46%
|
|================================= | 47%
|
|================================== | 48%
|
|=================================== | 49%
|
|=================================== | 51%
|
|==================================== | 52%
|
|===================================== | 53%
|
|===================================== | 54%
|
|====================================== | 55%
|
|======================================= | 56%
|
|======================================== | 57%
|
|======================================== | 58%
|
|========================================= | 59%
|
|========================================== | 60%
|
|========================================== | 61%
|
|=========================================== | 62%
|
|============================================ | 63%
|
|============================================= | 64%
|
|============================================= | 65%
|
|============================================== | 66%
|
|=============================================== | 67%
|
|=============================================== | 68%
|
|================================================ | 69%
|
|================================================= | 70%
|
|================================================= | 71%
|
|================================================== | 72%
|
|=================================================== | 73%
|
|==================================================== | 74%
|
|==================================================== | 75%
|
|===================================================== | 76%
|
|====================================================== | 77%
|
|====================================================== | 78%
|
|======================================================= | 79%
|
|======================================================== | 80%
|
|========================================================= | 81%
|
|========================================================= | 82%
|
|========================================================== | 83%
|
|=========================================================== | 84%
|
|=========================================================== | 85%
|
|============================================================ | 86%
|
|============================================================= | 87%
|
|============================================================== | 88%
|
|============================================================== | 89%
|
|=============================================================== | 90%
|
|================================================================ | 91%
|
|================================================================ | 92%
|
|================================================================= | 93%
|
|================================================================== | 94%
|
|================================================================== | 95%
|
|=================================================================== | 96%
|
|==================================================================== | 97%
|
|===================================================================== | 98%
|
|===================================================================== | 99%
|
|======================================================================| 100%
Best solution has objective function value 5 ;
standard deviation of OF in final population is 0 .
10010101010000011000
10000100010001010001
^ ^ ^ ^ ^
NMOF documentation built on May 2, 2019, 6:39 p.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Description Usage Arguments Details Value Author(s) References See Also Examples
Description
A simple Genetic Algorithm for minimising a function.
Usage
1 |
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:
nBnumber of bits per solution. Must be specified.
nPpopulation size. Defaults to 50. 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)timesalgo$nP, or a function that creates such a matrix. If a function, it must take no arguments. Ifmode(mP)is notlogical, thenstorage.mode(mP)will be tried (and a warning will be issued).loopOFlogical. Should the
OFbe evaluated through a loop? Defaults toTRUE.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,snowormulticore. Settingvectorisedis equivalent to havingalgo$loopOFset toFALSE(andmethodOFoverridesloopOF).snowandmulticoreuse functionsclusterApplyandmclapply, respectively. Forsnow, an objectalgo$clneeds to be specified (see below). Formulticore, optional arguments can be passed throughalgo$mc.control(see below).cla cluster object or the number of cores. See documentation of package
snow.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), atxtProgressBaris printed.storeFIf
TRUE(the default), the objective function values for every solution in every generation are stored and returned as matrixFmat.storeSolutionsIf
TRUE, the solutions (ie, binary strings) in every generation are stored and returned as a listPin listxlist(see Value section below). To check, for instance, the solutions at the end of theith generation, retrievexlist[[c(1L, i)]]. This will be a matrix of sizealgo$nBtimesalgo$nP.
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 |
xlist |
if |
|
the value of |
Author(s)
Enrico Schumann
References
Gilli, M., Maringer, D. and Schumann, E. (2011) Numerical Methods and Optimization in Finance. Elsevier. http://www.elsevierdirect.com/product.jsp?isbn=9780123756626
Schumann, E. (2013) The NMOF Manual. http://enricoschumann.net/NMOF.htm
See Also
Examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ## 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,
printBar = TRUE)
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 = "")
|
Example output
[1] 0
[1] 9
Genetic Algorithm.
|
| | 0%
|
|= | 1%
|
|= | 2%
|
|== | 3%
|
|=== | 4%
|
|==== | 5%
|
|==== | 6%
|
|===== | 7%
|
|====== | 8%
|
|====== | 9%
|
|======= | 10%
|
|======== | 11%
|
|======== | 12%
|
|========= | 13%
|
|========== | 14%
|
|=========== | 15%
|
|=========== | 16%
|
|============ | 17%
|
|============= | 18%
|
|============= | 19%
|
|============== | 20%
|
|=============== | 21%
|
|================ | 22%
|
|================ | 23%
|
|================= | 24%
|
|================== | 25%
|
|================== | 26%
|
|=================== | 27%
|
|==================== | 28%
|
|===================== | 29%
|
|===================== | 30%
|
|====================== | 31%
|
|======================= | 32%
|
|======================= | 33%
|
|======================== | 34%
|
|========================= | 35%
|
|========================= | 36%
|
|========================== | 37%
|
|=========================== | 38%
|
|============================ | 39%
|
|============================ | 40%
|
|============================= | 41%
|
|============================== | 42%
|
|============================== | 43%
|
|=============================== | 44%
|
|================================ | 45%
|
|================================= | 46%
|
|================================= | 47%
|
|================================== | 48%
|
|=================================== | 49%
|
|=================================== | 51%
|
|==================================== | 52%
|
|===================================== | 53%
|
|===================================== | 54%
|
|====================================== | 55%
|
|======================================= | 56%
|
|======================================== | 57%
|
|======================================== | 58%
|
|========================================= | 59%
|
|========================================== | 60%
|
|========================================== | 61%
|
|=========================================== | 62%
|
|============================================ | 63%
|
|============================================= | 64%
|
|============================================= | 65%
|
|============================================== | 66%
|
|=============================================== | 67%
|
|=============================================== | 68%
|
|================================================ | 69%
|
|================================================= | 70%
|
|================================================= | 71%
|
|================================================== | 72%
|
|=================================================== | 73%
|
|==================================================== | 74%
|
|==================================================== | 75%
|
|===================================================== | 76%
|
|====================================================== | 77%
|
|====================================================== | 78%
|
|======================================================= | 79%
|
|======================================================== | 80%
|
|========================================================= | 81%
|
|========================================================= | 82%
|
|========================================================== | 83%
|
|=========================================================== | 84%
|
|=========================================================== | 85%
|
|============================================================ | 86%
|
|============================================================= | 87%
|
|============================================================== | 88%
|
|============================================================== | 89%
|
|=============================================================== | 90%
|
|================================================================ | 91%
|
|================================================================ | 92%
|
|================================================================= | 93%
|
|================================================================== | 94%
|
|================================================================== | 95%
|
|=================================================================== | 96%
|
|==================================================================== | 97%
|
|===================================================================== | 98%
|
|===================================================================== | 99%
|
|======================================================================| 100%
Best solution has objective function value 0 ;
standard deviation of OF in final population is 0 .
10010101010000011000
10010101010000011000
Genetic Algorithm.
|
| | 0%
|
|= | 1%
|
|= | 2%
|
|== | 3%
|
|=== | 4%
|
|==== | 5%
|
|==== | 6%
|
|===== | 7%
|
|====== | 8%
|
|====== | 9%
|
|======= | 10%
|
|======== | 11%
|
|======== | 12%
|
|========= | 13%
|
|========== | 14%
|
|=========== | 15%
|
|=========== | 16%
|
|============ | 17%
|
|============= | 18%
|
|============= | 19%
|
|============== | 20%
|
|=============== | 21%
|
|================ | 22%
|
|================ | 23%
|
|================= | 24%
|
|================== | 25%
|
|================== | 26%
|
|=================== | 27%
|
|==================== | 28%
|
|===================== | 29%
|
|===================== | 30%
|
|====================== | 31%
|
|======================= | 32%
|
|======================= | 33%
|
|======================== | 34%
|
|========================= | 35%
|
|========================= | 36%
|
|========================== | 37%
|
|=========================== | 38%
|
|============================ | 39%
|
|============================ | 40%
|
|============================= | 41%
|
|============================== | 42%
|
|============================== | 43%
|
|=============================== | 44%
|
|================================ | 45%
|
|================================= | 46%
|
|================================= | 47%
|
|================================== | 48%
|
|=================================== | 49%
|
|=================================== | 51%
|
|==================================== | 52%
|
|===================================== | 53%
|
|===================================== | 54%
|
|====================================== | 55%
|
|======================================= | 56%
|
|======================================== | 57%
|
|======================================== | 58%
|
|========================================= | 59%
|
|========================================== | 60%
|
|========================================== | 61%
|
|=========================================== | 62%
|
|============================================ | 63%
|
|============================================= | 64%
|
|============================================= | 65%
|
|============================================== | 66%
|
|=============================================== | 67%
|
|=============================================== | 68%
|
|================================================ | 69%
|
|================================================= | 70%
|
|================================================= | 71%
|
|================================================== | 72%
|
|=================================================== | 73%
|
|==================================================== | 74%
|
|==================================================== | 75%
|
|===================================================== | 76%
|
|====================================================== | 77%
|
|====================================================== | 78%
|
|======================================================= | 79%
|
|======================================================== | 80%
|
|========================================================= | 81%
|
|========================================================= | 82%
|
|========================================================== | 83%
|
|=========================================================== | 84%
|
|=========================================================== | 85%
|
|============================================================ | 86%
|
|============================================================= | 87%
|
|============================================================== | 88%
|
|============================================================== | 89%
|
|=============================================================== | 90%
|
|================================================================ | 91%
|
|================================================================ | 92%
|
|================================================================= | 93%
|
|================================================================== | 94%
|
|================================================================== | 95%
|
|=================================================================== | 96%
|
|==================================================================== | 97%
|
|===================================================================== | 98%
|
|===================================================================== | 99%
|
|======================================================================| 100%
Best solution has objective function value 5 ;
standard deviation of OF in final population is 0 .
10010101010000011000
10000100010001010001
^ ^ ^ ^ ^
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.