NMOF (version 0.20-0)

LSopt: Stochastic Local Search

Description

Performs a simple stochastic local search.

Usage

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

Arguments

OF

the objective function, to be minimised. Its first argument needs to be a solution; ... arguments are also passed.

algo

list of settings. See Details.

...

other variables to be passed to the objective function and to the neighbourhood function. See Details.

Value

• Returns a list.
• xbest
  best solution found.
• OFvalue
  objective function value associated with best solution.
• Fmat
  a matrix with two columns. Fmat[ ,1L] contains the proposed solution over all iterations; Fmat[ ,2L] contains the accepted solutions.

concept

Local Search

acronym

LS

code

FALSE

Details

Local Search (LS) changes an initial solution for a number of times, accepting only such changes that lead to an improvement in solution quality (as measured by the objective function OF). More specifically, in each iteration, a current solution xc is changed through a function algo$neighbour. This function takes xc as an argument and returns a new solution xn. If xn is not worse than xc, ie, if OF(xn,...)<=of(xc,...)< code="">, then xn replaces xc. The list algo contains the following items: [object Object],[object Object],[object Object],[object Object],[object Object]

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. (2011) Examples and Extensions for the NMOF Package. http://ssrn.com/abstract=1886522

See Also

TAopt

Examples

## Aim: find the columns of X that, when summed, give y

## random data set
nc <- 25L; nr <- 5L; howManyCols <- 5L
X <- array(runif(nr*nc), dim = c(nr, nc))
xTRUE <- sample(1L:nc, howManyCols)
Xt <- X[ , xTRUE, drop = FALSE]
y <- rowSums(Xt)

## a random solution x0 ...
makeRandomSol <- function(nc) {
    ii <- sample.int(nc, sample.int(nc, 1L))
    x0 <- numeric(nc); x0[ii] <- 1L
    x0
}
x0 <- makeRandomSol(nc)

## ... but probably not a good one
sum(y - rowSums(X[ , as.logical(x0), drop = FALSE]))
sum(y - rowSums(X[ , xTRUE, drop = FALSE]))


## a neighbourhood function: switch n elements in solution
neighbour <- function(xc, data) {
    xn <- xc
    p <- sample.int(data$nc, data$n)
    xn[p] <- abs(xn[p] - 1L)
    if (sum(xn) < 1L) xn <- xc 
    xn
}
## a greedy neighbourhood function
neighbourG <- function(xc, data) {
    of <- function(x)
        abs(sum(data$y - rowSums(data$X[,as.logical(x), drop = FALSE])))
    xbest <- xc
    Fxbest <- of(xbest)
    for (i in 1L:data$nc) {
        xn <- xc; p <- i
        xn[p] <- abs(xn[p] - 1L)
        if (sum(xn) > 1L) {
            Fxn <- of(xn) 
            if (Fxn <= Fxbest) {
                xbest <- xn; FXbest <- Fxn
            }
        }
    }
    xbest
}

## an objective function
OF <- function(xn, data)
    abs(sum(data$y - rowSums(data$X[ ,as.logical(xn), drop = FALSE])))


## (1) *greedy search*
## note: this could be done in a simpler fashion. but the 
##       redundancies/overhead here are small; and the example is to
##       show how LSopt can be used for such a search
data <- list(X = X, y = y, nc = nc, nr = nr, n = 1L)
algo <- list(nS = 500L, neighbour = neighbourG, x0 = x0,
             printBar = FALSE, printDetail = FALSE)

sol <- LSopt(OF, algo = algo, data = data)
sort(which(as.logical(sol$xbest)))
sort(xTRUE)
sol$OFvalue
par(ylog = TRUE)
plot(sol$Fmat[ ,2L],type = "l", log = "y", 
     ylim = c(1e-4, max(pretty(sol$Fmat[ ,2L]))), 
     xlab = "iterations", ylab = "OF value")

## (2) *Local Search*
algo$neighbour <- neighbour
sol <- LSopt(OF, algo = algo, data = data)
sort(which(as.logical(sol$xbest)))
sort(xTRUE)
sol$OFvalue
lines(sol$Fmat[ ,2L], type = "l", lty = 2)

## (3) *Threshold Accepting*
algo$nT <- 10L
algo$nS <- ceiling(algo$nS/algo$nT)
sol2 <- TAopt(OF, algo = algo, data = data)
sort(which(as.logical(sol2$xbest)))
sort(xTRUE)
sol2$OFvalue
lines(cummin(sol2$Fmat[ ,2L]),type = "l", lty = 3)