R based tabu search algorithm for binary configurations

Share:

Description

A tabu search algorithm for optimizing binary strings. It takes a user defined objective function and reports the best binary configuration found throughout the search i.e. the one with the highest objective function value. The algorithm can be used for variable selection.

The results can be plotted and summarized using plot.tabu and summary.tabu.

Usage

1
2
tabuSearch(size = 10, iters = 100, objFunc = NULL, config = NULL, neigh = size, 
listSize = 9, nRestarts = 10, repeatAll = 1, verbose = FALSE)

Arguments

size

the length of the binary configuration.

iters

the number of iterations in the preliminary search of the algorithm.

objFunc

a user supplied method that evaluates the objective function for a given binary string. The objective function is required to take as an argument a vector of zeros and ones.

config

a starting configuration.

neigh

a number of neighbour configurations to check at each iteration. The default is all, which is the length of the string. If neigh < size, the neighbours are chosen at random.

listSize

tabu list size.

nRestarts

the maximum number of restarts in the intensification stage of the algorithm.

repeatAll

the number of times to repeat the search.

verbose

if true, the name of the current stage of the algorithm is printed e.g. preliminary stage, intensification stage, diversification stage.

Value

A tabu object which is a list giving:

configKeep

a matrix of configurations chosen at each iteration of the algorithm.

eUtilityKeep

value of the objective function for the above configurations.

iters

the number of iterations in the preliminary search of the algorithm.

neigh

a number of neighbour configurations checked at each iteration.

listSize

tabu list size.

repeatAll

the number of times the search was repeated.

Author(s)

K. Domijan

References

Glover, F., 1977. Heuristics for integer programming using surrogate constraints. Decision Sciences 8, 156-166.

Glover, F., 1986. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13, 533-549.

Fouskakis, D., Draper, D., 2002. Stochastic optimization: a review. International Statistical Review 70, 315-349.

See Also

plot.tabu summary.tabu

Examples

 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
# A simple example


evaluateSimple <- function(th)return(1)

result <- tabuSearch(size = 20, iters = 100, objFunc = evaluateSimple) 



# simulate 10-d data: 150 samples from 3 bivariate normals and 8 noise variables. 
# Variable selection should recover the first two variables


## Not run: 
library(MASS)
NF <- 10
G <- 3
NTR <- 50
NTE <- 50

muA <- c(1,3)
SigmaA <- matrix(c(0.2, 0.04, 0.04, 0.2), 2, 2)
muB <- c(1.2,1)
SigmaB <- matrix(c(0.1, -0.06, 0.004, 0.2), 2, 2)
muC <- c(3,2)
SigmaC <- matrix(c(0.2, 0.004, 0.004, 0.2), 2, 2)

train <- rbind(mvrnorm(NTR, muA, SigmaA), mvrnorm(NTR, muB, SigmaB), mvrnorm(NTR, muC, SigmaC))
test <- rbind(mvrnorm(NTE, muA, SigmaA), mvrnorm(NTE, muB, SigmaB), mvrnorm(NTE, muC, SigmaC))

train <- cbind(train, matrix(runif(G * NTR * (NF - 2), 0, 4), nrow = G * NTR, ncol = (NF-2)))
test <- cbind(test, matrix(runif(G * NTE * (NF - 2), 0, 4), nrow = G * NTE, ncol = (NF-2)))

wtr <-  as.factor(rep(1:G, each = NTR))
wte <-  as.factor(rep(1:G, each = NTE))
pairs(train, col = wtr)




library(e1071)

evaluate <- function(th){ 
    if (sum(th) == 0)return(0)             
    model <- svm(train[ ,th==1], wtr , gamma = 0.1)
    pred <- predict(model, test[ ,th==1])
    csRate <- sum(pred == wte)/NTE 
    penalty <- (NF - sum(th))/NF 
    return(csRate + penalty)
}  
 
res <- tabuSearch(size = NF, iters = 50, objFunc = evaluate, config = matrix(1,1,NF),
listSize = 5, nRestarts = 4) 


plot(res)
plot(res, "tracePlot")

summary(res, verbose = TRUE)


## End(Not run)