SAopt: Optimisation with Simulated Annealing In enricoschumann/NMOF: Numerical Methods and Optimization in Finance

Description

The function implements a Simulated-Annealing algorithm.

Usage

 `1` ```SAopt(OF, algo = list(), ...) ```

Arguments

 `OF` The objective function, to be minimised. Its first argument needs to be a solution `x`; it will be called as ```OF(x, ...)```. `algo` A list of settings for the algorithm. See Details. `...` other variables passed to `OF` and `algo\$neighbour`. See Details.

Details

Simulated Annealing (SA) changes an initial solution iteratively; the algorithm stops after a fixed number of iterations. Conceptually, SA consists of a loop than runs for a number of iterations. In each iteration, a current solution `xc` is changed through a function `algo\$neighbour`. If this new (or neighbour) solution `xn` is not worse than `xc`, ie, if `OF(xn,...) <= OF(xc,...)`, then `xn` replaces `xc`. If `xn` is worse, it still replaces `xc`, but only with a certain probability. This probability is a function of the degree of the deterioration (the greater, the less likely the new solution is accepted) and the current iteration (the longer the algorithm has already run, the less likely the new solution is accepted).

The list `algo` contains the following items.

`nS`

The number of steps per temperature. The default is 1000; but this setting depends very much on the problem.

`nT`

The number of temperatures. Default is 10.

`nI`

Total number of iterations, with default `NULL`. If specified, it will override `nS` with `ceiling(nI/nT)`. Using this option makes it easier to compare and switch between functions `LSopt`, `TAopt` and `SAopt`.

`nD`

The number of random steps to calibrate the temperature. Defaults to 2000.

`initT`

Initial temperature. Defaults to `NULL`, in which case it is automatically chosen so that `initProb` is achieved.

`finalT`

Final temperature. Defaults to 0.

`alpha`

The cooling constant. The current temperature is multiplied by this value. Default is 0.9.

`mStep`

Step multiplier. The default is 1, which implies constant number of steps per temperature. If greater than 1, the step number `nS` is increased to `m*nS` (and rounded).

`x0`

The initial solution. If this is a function, it will be called once without arguments to compute an initial solution, ie, `x0 <- algo\$x0()`. This can be useful when the routine is called in a loop of restarts, and each restart is to have its own starting value.

`neighbour`

The neighbourhood function, called as `neighbour(x, ...)`. Its first argument must be a solution `x`; it must return a changed solution.

`printDetail`

If `TRUE` (the default), information is printed. If an integer `i` greater then one, information is printed at very `i`th iteration.

`printBar`

If `TRUE` (default is `FALSE`), a `txtProgressBar` (from package utils) is printed. The progress bar is not shown if `printDetail` is an integer greater than 1.

`storeF`

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

`storeSolutions`

Default is `FALSE`. If `TRUE`, the solutions (ie, decision variables) in every generation are stored and returned in list `xlist` (see Value section below). To check, for instance, the current solution at the end of the `i`th generation, retrieve ```xlist[[c(2L, i)]]```.

`classify`

Logical; default is `FALSE`. If `TRUE`, the result will have a class attribute `SAopt` attached.

`OF.target`

Numeric; when specified, the algorithm will stop when an objective-function value as low as `OF.target` (or lower) is achieved. This is useful when an optimal objective-function value is known: the algorithm will then stop and not waste time searching for a better solution.

At the minimum, `algo` needs to contain an initial solution `x0` and a `neighbour` function.

The total number of iterations equals `algo\$nT` times `algo\$nS` (plus possibly `algo\$nD`).

Value

`SAopt` returns a list with five components:

 `xbest` the solution `OFvalue` objective function value of the solution, ie, `OF(xbest, ...)` `Fmat` if `algo\$storeF` is `TRUE`, a matrix with one row for each iteration (excluding the initial `algo\$nD` steps) and two columns. The first column contains the objective function values of the neighbour solution at a given iteration; the second column contains the value of the current solution. Since SA can walk away from locally-optimal solutions, the best solution can be monitored through `cummin(Fmat[ ,2L])`. `xlist` if `algo\$storeSolutions` is `TRUE`, a list; else `NA`. Contains the neighbour solutions at a given iteration (`xn`) and the current solutions (`xc`). Example: `Fmat[i, 2L]` is the objective function value associated with `xlist[[c(2L, i)]]`. `initial.state` the value of `.Random.seed` when the function was called.

If `algo\$classify` was set to `TRUE`, the resulting list will have a class attribute `TAopt`.

Note

If the `...` argument is used, then all the objects passed with `...` need to go into the objective function and the neighbourhood function. It is recommended to collect all information in a list `myList` and then write `OF` and `neighbour` so that they are called as `OF(x, myList)` and ```neighbour(x, myList)```. Note that `x` need not be a vector but can be any data structure (eg, a `matrix` or a `list`).

Using an initial and final temperature of zero means that SA will be equivalent to a Local Search. The function `LSopt` may be preferred then because of smaller overhead.

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

Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983). Optimization with Simulated Annealing. Science. 220 (4598), 671–680.

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

`LSopt`, `TAopt`, `restartOpt`
 ``` 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 50 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``` ```## Aim: given a matrix x with n rows and 2 columns, ## divide the rows of x into two subsets such that ## in one subset the columns are highly correlated, ## and in the other lowly (negatively) correlated. ## constraint: a single subset should have at least 40 rows ## create data with specified correlation n <- 100L rho <- 0.7 C <- matrix(rho, 2L, 2L); diag(C) <- 1 x <- matrix(rnorm(n * 2L), n, 2L) %*% chol(C) ## collect data data <- list(x = x, n = n, nmin = 40L) ## a random initial solution x0 <- runif(n) > 0.5 ## a neighbourhood function neighbour <- function(xc, data) { xn <- xc p <- sample.int(data\$n, size = 1L) xn[p] <- abs(xn[p] - 1L) # reject infeasible solution c1 <- sum(xn) >= data\$nmin c2 <- sum(xn) <= (data\$n - data\$nmin) if (c1 && c2) res <- xn else res <- xc as.logical(res) } ## check (should be 1 FALSE and n-1 TRUE) x0 == neighbour(x0, data) ## objective function OF <- function(xc, data) -abs(cor(data\$x[xc, ])[1L, 2L] - cor(data\$x[!xc, ])[1L, 2L]) ## check OF(x0, data) ## check OF(neighbour(x0, data), data) ## plot data par(mfrow = c(1,3), bty = "n") plot(data\$x, xlim = c(-3,3), ylim = c(-3,3), main = "all data", col = "darkgreen") ## *Local Search* algo <- list(nS = 3000L, neighbour = neighbour, x0 = x0, printBar = FALSE) sol1 <- LSopt(OF, algo = algo, data=data) sol1\$OFvalue ## *Simulated Annealing* algo\$nT <- 10L algo\$nS <- ceiling(algo\$nS/algo\$nT) sol <- SAopt(OF, algo = algo, data = data) sol\$OFvalue c1 <- cor(data\$x[ sol\$xbest, ])[1L, 2L] c2 <- cor(data\$x[!sol\$xbest, ])[1L, 2L] lines(data\$x[ sol\$xbest, ], type = "p", col = "blue") plot(data\$x[ sol\$xbest, ], col = "blue", xlim = c(-3, 3), ylim = c(-3, 3), main = paste("subset 1, corr.", format(c1, digits = 3))) plot(data\$x[!sol\$xbest, ], col = "darkgreen", xlim = c(-3,3), ylim = c(-3,3), main = paste("subset 2, corr.", format(c2, digits = 3))) ## compare LS/SA par(mfrow = c(1, 1), bty = "n") plot(sol1\$Fmat[ , 2L],type = "l", ylim=c(-1.5, 0.5), ylab = "OF", xlab = "Iterations") lines(sol\$Fmat[ , 2L],type = "l", col = "blue") legend(x = "topright", legend = c("LS", "SA"), lty = 1, lwd = 2, col = c("black", "blue")) ```