R/local_search.R

In bbotk: Black-Box Optimization Toolkit

#' @title Local Search Control
#'
#' @description
#' Control parameters for local search optimizer, see [local_search()] for details.
#'
#' @param minimize (`logical(1)`)\cr
#'   Whether to minimize the objective.
#' @param n_searches (`integer(1)`)\cr
#'   Number of local searches.
#' @param n_steps (`integer(1)`)\cr
#'   Number of steps per local search.
#' @param n_neighs (`integer(1)`)\cr
#'   Number of neighbors per local search.
#' @param mut_sd (`numeric(1)`)\cr
#'   Standard deviation of the mutation.
#' @param stagnate_max (`integer(1)`)\cr
#'   Maximum number of no-improvement steps for a local search before it is randomly restarted.
#'
#' @return (`local_search_control`)\cr
#'   List with control params as S3 object.
#'
#' @export
local_search_control = function(
  minimize = TRUE,
  n_searches = 10L,
  n_steps = 5L,
  n_neighs = 10L,
  mut_sd = 0.1,
  stagnate_max = 10L
  ) {
  assert_int(n_searches, lower = 1L)
  assert_int(n_steps, lower = 0L)
  assert_int(n_neighs, lower = 1L)
  assert_number(mut_sd, lower = 0)
  assert_int(stagnate_max, lower = 1L)
  res = list(minimize = minimize, n_searches = n_searches, n_steps = n_steps, n_neighs = n_neighs, mut_sd = mut_sd, stagnate_max = stagnate_max)
  set_class(res, "local_search_control")
}

#' @title Local Search
#'
#' @description
#' Runs a local search on the objective function.
#' Somewhat similar to what is used in [SMAC](https://github.com/automl/SMAC3/blob/main/smac/acquisition/maximizer/local_search.py) for acquisition function optimization of mixed type search spaces with hierarchical dependencies.
#'
#' The function always minimizes.
#' If the objective is to be maximized, we handle it by multiplying with "obj_mult" (which will be -1).
#'
#' 'Currently, automatically applying the search space transformations is not supported,
#'  if you need this, do this yourself in the objective function or use `OptimInstanceBatchLocalSearch`.
#'
#' @details
#' We run "n_searches" in parallel.
#' Each search runs "n_steps" iterations.
#' For each search in every iteration we generate "n_neighs" neighbors.
#' A neighbor is the current point, but with exactly one parameter mutated.
#'
#' Mutation works like this:
#' For num params: we scale to 0,1, add Gaussian noise with sd "mut_sd", and scale back.
#' We then clip to the lower and upper bounds.
#' For int params: We do the same as for numeric parameters, but round at the end.
#' For factor params: We sample a new level from the unused levels of the parameter.
#' For logical params: We flip the bit.
#'
#' Hierarchical dependencies are handled like this:
#' Only active params can be mutated.
#' After a mutation has happened, we check the conditions of the search space in topological order.
#' If a condition is not met, we set the param to NA (making it inactive);
#' if all conditions are met for a param, but it currently has is NA, we set it a random valid value.
#'
#' After the neighbors are generated, we evaluate them.
#' We go to the best neighbor, or stay at the current point if the best neighbor is worse.
#'
#' There is a restart mechanism to avoid local minima.
#' For each search, we keep track of the number of no-improvement steps.
#' If this number exceeds "stagnate_max", we restart the search with a random point.
#'
#' @param objective (`function(xdt)`)\cr
#'   Objective to optimize.
#'   The first arg (name 'xdt' is not enforced) will be a data.table with (scalar) columns corresponding exactly the search space, in the same order.
#'   The function should must return numeric vector of exactly the same length as the number of rows in the dt, containing the objective values.
#' @param search_space ([paradox::ParamSet])\cr
#'   Search space for decision variables.
#'   Must be non-empty, can only contain `p_int`, `p_dbl`, `p_fct`, `p_lgl`, all must be bounded.
#' @param control ([local_search_control])\cr
#'   Control parameters for the local search, generated by [local_search_control()].
#' @param init_points (`data.table`)\cr
#'   Initial points to start the local search from,
#'   same format as described for the argument of 'objective'.
#'   Must have as many rows as 'control$n_searches'.
#'   If NULL, we generate "n_searches" random points.
#'
#' @return (named `list`). List with elements:
#'   - 'x': (`list`)\cr
#'     The best point found, length and element names and their order correspond exactly to the search space.
#'   - 'y': (`numeric(1)`)\cr
#'     The objective value of the best point.
#' @export
local_search = function(objective, search_space, control = local_search_control(), init_points = NULL) {
  assert_function(objective)
  assert_class(search_space, "ParamSet")
  assert_true(!search_space$is_empty)
  # Check that search space only contains scalar params of allowed types
  allowed_classes = c("ParamDbl", "ParamFct", "ParamInt", "ParamLgl")
  if (!all(search_space$class %in% allowed_classes)) {
    stopf("Search space can only contain parameters of class: %s", str_collapse(allowed_classes))
  }
  assert_true(search_space$all_bounded)
  assert_class(control, "local_search_control")
  if (is.null(init_points)) {
    init_points = generate_design_random(search_space, n = control$n_searches)$data
  } else {
    assert_data_table(init_points, nrows = control$n_searches)
    search_space$assert_dt(init_points)
  }
  .Call("c_local_search", objective, search_space, control, init_points, PACKAGE = "bbotk")
}