Tabu search for a partial principal balance on grouped parts

Source: R/tabu_search.R

Finds a single grouped balance by tabu search over a partition of selected parts. The search is carried out on groups of parts defined by lI, using the variance criterion induced by the covariance matrix of the log-transformed composition.

partial_pb_tabu_search(X, lI, iter, tabu_size, ini = NULL, debug = FALSE)

Arguments

X

A numeric matrix with strictly positive finite entries. Rows are observations and columns are compositional parts.

lI

A list defining a partition of a subset of the columns of X. Each element of lI is an integer vector giving the indices of the parts belonging to the same group. Indices must be valid column positions of X, and no column may appear in more than one group.

iter

Integer. Maximum number of tabu search iterations.

tabu_size

Integer. Maximum size of the tabu list.

ini

Initial grouped split. If NULL (default), the initial solution is obtained from the constrained principal balance of the grouped subcomposition. Otherwise, ini must be an integer/numeric vector in \(\{-1,0,1\}\) of length length(lI) defining the initial grouped split. Negative entries indicate groups on the left side, positive entries indicate groups on the right side, and zeros indicate inactive groups.

debug

Logical. If TRUE, progress information is printed during the search.

Value

A list with the following elements:

iter_best

Iteration at which the best solution was found.

tabu_size

Effective tabu list size when the best solution was found.

steps

Objective values along the visited search path.

dim

Dimension of the grouped problem, equal to length(lI) - 1.

lI

The input grouping structure.

variance

Variance criterion of the best grouped balance found.

balance_raw

Integer vector in \(\{-1,0,1\}\) describing the best grouped split found. Negative entries indicate groups on the left side of the balance, positive entries indicate groups on the right side, and zeros indicate inactive groups.

balance

The corresponding one-column balance basis obtained from balance_raw using sbp_basis.

Details

The initial grouped split is obtained either from the constrained principal balance of the grouped subcomposition, or from a user-supplied grouped balance.

The objective function is the variance of the balance associated with a split between a left and a right set of active groups. At each tabu iteration, candidate neighbors are obtained by:

  • removing one active group from the current split,

  • adding one inactive group to the left side,

  • adding one inactive group to the right side.

When ini = NULL, the grouped composition used for initialization is obtained by replacing each group with the product of its parts, and the constrained principal balance of this grouped composition is used as the initial grouped split. When ini is a vector, it is used directly as the initial grouped split.

Examples

set.seed(1)
X <- matrix(rexp(200), ncol = 4)
lI <- list(1, 2, c(3, 4))

res1 <- partial_pb_tabu_search(
  X = X,
  lI = lI,
  iter = 20,
  tabu_size = 3
)

res2 <- partial_pb_tabu_search(
  X = X,
  lI = lI,
  iter = 20,
  tabu_size = 3,
  ini = c(-1, 1, 0)
)

res1$variance
#> [1] 1.039536
res1$balance_raw
#> [1]  1 -1  1
res1$balance
#>            b1
#> c1  0.4082483
#> c2 -0.8164966
#> c3  0.4082483