Description Usage Arguments Details Value Note Author(s) References See Also Examples
The function implements the Threshold Accepting algorithm.
1 |
OF |
The objective function, to be minimised. Its first argument
needs to be a solution |
algo |
A list of settings for the algorithm. See Details. |
... |
other variables passed to |
Threshold Accepting (TA) changes an initial solution
iteratively; the algorithm stops after a fixed number of
iterations. Conceptually, TA 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
as long
as the difference in ‘quality’ between the two solutions is
less than a threshold tau
; more precisely, as long as
OF(xn,...) - tau <= OF(xc,...)
. Thus, we also accept a new
solution that is worse than its predecessor; just not too much
worse. The threshold is typically decreased over the course of the
optimisation. For zero thresholds TA becomes a stochastic local
search.
The thresholds can be passed through the list algo
(see
below). Otherwise, they are automatically computed through the
procedure described in Gilli et al. (2006). When the thresholds are
created automatically, the final threshold is always zero.
The list algo
contains the following items.
nS
The number of steps per threshold. The default is 1000; but this setting depends very much on the problem.
nT
The number of thresholds. Default is 10; ignored if
algo$vT
is specified.
nD
The number of random steps to compute the threshold
sequence. Defaults to 2000. Only used if algo$vT
is NULL
.
q
The highest quantile for the threshold
sequence. Defaults to 0.5. Only used if algo$vT
is
NULL
. If q
is zero, TAopt
will run with
zero-thresholds (ie, like a Local Search).
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.
vT
The thresholds. A numeric vector. If NULL
(the
default), TAopt
will compute algo$nT
thresholds.
Passing threshold can be useful when similar problems are
handled. Then the time to sample the objective function to compute
the thresholds can be saved (ie, we save algo$nD
function
evaluations). If the thresholds are computed and
algo$printDetail
is TRUE
, the time required to
evaluate the objective function will be measured and an estimate for
the remaining computing time is issued. This estimate is often
very crude.
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
TRUE
.
scale
The thresholds are multiplied by
scale
. Default is 1.
stepUp
Defaults to 0
. If an integer greater
than zero, then the thresholds are recycled, ie, vT
is
replaced by rep(vT, algo$stepUp + 1)
(and the number of
thresholds will be increased by algo$nT
times
algo$stepUp
). This option works for supplied as well as
computed thresholds. Practically, this will have the same effect
as restarting from a returned solution. (In Simulated Annealing,
this strategy goes by the name of ‘reheating’.)
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)]]
.
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$stepUp + 1)
times algo$nS
(plus possibly
algo$nD
).
TAopt
returns a list with four components:
|
the solution |
|
objective function value of the solution, ie,
|
|
if |
|
if |
|
the value of |
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 thresholds of size 0 makes TA run as a Local Search. The
function LSopt
may be preferred then because of smaller
overhead.
Enrico Schumann
Dueck, G. and Scheuer, T. (1990) Threshold Accepting. A General Purpose Optimization Algorithm Superior to Simulated Annealing. Journal of Computational Physics. 90 (1), 161–175.
Dueck, G. and Winker, P. (1992) New Concepts and Algorithms for Portfolio Choice. Applied Stochastic Models and Data Analysis. 8 (3), 159–178.
Gilli, M., Kellezi, E. and Hysi, H. (2006) A Data-Driven Optimization Heuristic for Downside Risk Minimization. Journal of Risk. 8 (3), 1–18.
Gilli, M., Maringer, D. and Schumann, E. (2011) Numerical Methods and Optimization in Finance. Elsevier. http://www.elsevierdirect.com/product.jsp?isbn=9780123756626
Moscato, P. and Fontanari, J.F. (1990). Stochastic Versus Deterministic Update in Simulated Annealing. Physics Letters A. 146 (4), 204–208.
Schumann, E. (2011) The NMOF Manual. http://enricoschumann.net/NMOF.htm
Winker, P. (2001). Optimization Heuristics in Econometrics: Applications of Threshold Accepting. Wiley.
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
## *Threshold Accepting*
algo$nT <- 10L
algo$nS <- ceiling(algo$nS/algo$nT)
sol <- TAopt(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/TA
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", "TA"),
lty = 1, lwd = 2,col = c("black", "blue"))
|
[1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[13] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[25] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[37] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[49] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[61] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[73] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE FALSE TRUE TRUE
[85] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
[97] TRUE TRUE TRUE TRUE
[1] -0.01282244
[1] -0.05102445
Local Search.
Initial solution: -0.01282244
Finished.
Best solution overall: -0.9640783
[1] -0.9640783
Threshold Accepting
Computing thresholds ... OK
Estimated remaining running time: 0.1905 secs
Running Threshold Accepting ...
Initial solution: -0.01282244
Finished.
Best solution overall: -1.030897
[1] -1.030897
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.