R/generate.R

In moocore: Core Mathematical Functions for Multi-Objective Optimization

#' Generate a random set of mutually nondominated points
#'
#' @description
#' Generate a random set of `n` mutually nondominated points of dimension `d`
#' with the shape defined by `method`.
#'
#' When `integer = FALSE` (the default), the points are generated within the
#' hypercube \eqn{(0,1)^d} and can be scaled to another range using
#' [normalise()].  Otherwise, points are scaled to a non-negative integer range
#' that keeps the points mutually nondominated.
#'
#' @param n `integer(1)`\cr Number of rows in the output.
#' @param d `integer(1)`\cr Number of columns in the output.
#' @param method `character(1)`\cr Method used to generate the random nondominated set.
#'   See **Details** below for more information.
#' @param seed `integer(1)`\cr Integer seed for random number generation. If `NULL`,
#'   a random seed is generated.
#' @param integer `logical(1)`\cr If `TRUE`, return integer-valued points.
#'
#' @return A numeric matrix of size `n × d` containing nondominated points.
#'
#' @details
#' The available methods are:
#'
#' * `"simplex"`, `"linear"`, or `"L"`: Uniformly samples points on the
#'   standard simplex.
#' * `"concave-sphere"`, `"sphere"`, or `"C"`: Uniformly samples points
#'   on the positive orthant of the unit hypersphere (concave for minimisation).
#' * `"convex-sphere"` or `"X"`: Equivalent to `1 - generate_ndset(..., method="concave-sphere")`,
#'   which is convex for minimisation.
#' * `"convex-simplex"`: Equivalent to `generate_ndset(..., method="concave-sphere")^4`,
#'   which is convex for minimisation. Such a set cannot be obtained by any
#'   affine transformation of a subset of the hyper-sphere.
#'
#' Method `"simplex"` uniformly samples points on the standard
#' \eqn{(d-1)}-simplex defined by \eqn{\{x \in R_+^d : \sum_i x_i = 1\}}. This
#' shape of nondominated set is also called `"linear"` in the literature
#' \citep{LacKlaFon2017box}.  Each point \eqn{\vec{z} \in (0,1)^d \subset
#' \mathbb{R}^d} is generated by sampling \eqn{d} independent and identically
#' distributed values \eqn{(x_1,x_2, \dots, x_d)} from the exponential
#' distribution, then dividing each value by the L1-norm of the vector,
#' \eqn{z_i = x_i / \sum_{i=1}^d x_i} \citep{RubMel1998simulation}.  Values
#' sampled from the exponential distribution are guaranteed to be positive.
#'
#' Sampling from either the standard normal distribution
#' \citep{GueFonPaq2021hv} or the uniform distribution \citep{LacKlaFon2017box}
#' does not produce a uniform distribution when projected into the simplex.
#'
#' Method `"concave-sphere"` uniformly samples points on the positive orthant
#' of the hyper-sphere, which is concave when all objectives are minimised.
#' Each point \eqn{\vec{z} \in (0,1)^d \subset \mathbb{R}^d} is generated by
#' sampling \eqn{d} independent and identically distributed values
#' \eqn{\vec{x}=(x_1,x_2, \dots, x_d)} from the standard normal distribution,
#' then dividing each value by the l2-norm of the vector, \eqn{z_i =
#' \frac{|x_i|}{\|\vec{x}\|_2}} \citep{Muller1959sphere}. The absolute value in
#' the numerator ensures that points are sampled on the positive orthant of the
#' hyper-sphere.  Sampling from the uniform distribution
#' \citep{LacKlaFon2017box} does not result in a uniform sampling when
#' projected onto the surface of the hyper-sphere.
#'
#' Method `"convex-sphere"` is equivalent to `1 - generate_ndset(...,
#' method="concave-sphere")`, which is convex for minimisation problems.  It
#' corresponds to translating points from the negative orthant of the
#' hyper-sphere to the positive orthant.
#'
#' Method `"convex-simplex"` is equivalent to `generate_ndset(...,
#' method="concave-sphere")^4`, which is convex for minimisation problems.
#' The corresponding surface is equivalent to a simplex curved towards the
#' origin.
#'
#' @references
#'
#' \insertAllCited{}
#'
#' @examples
#' generate_ndset(5, 3, "simplex", seed = 42)
#' generate_ndset(5, 3, "simplex", seed = 42, integer = TRUE)
#' generate_ndset(4, 2, "sphere", seed = 123)
#' generate_ndset(3, 5, "convex-sphere", seed = 123)
#' generate_ndset(4, 4, "convex-simplex", seed = 123)
#'
#' @export
generate_ndset <- function(n, d, method, seed = NULL, integer = FALSE)
{
  seed <- if (is.null(seed)) get_seed() else as_integer(seed)
  withr::local_seed(seed)

  sample_simplex <- function() {
    x <- rexp(n * d)
    dim(x) <- c(n, d)
    x <- x / rowSums(x)
    x
  }

  sample_sphere <- function() {
    x <- abs(rnorm(n * d))
    dim(x) <- c(n, d)
    x <- x / sqrt(rowSums(x * x))
    x
  }

  sample_convex_sphere <- function() 1. - sample_sphere()
  sample_convex_simplex <- function() sample_sphere()^4L

  sample_fun <- (
    if (method %in% c("simplex", "linear", "L")) sample_simplex
    else if (method %in% c("concave-sphere", "sphere", "C")) sample_sphere
    else if (method %in% c("convex-sphere", "X")) sample_convex_sphere
    else if (method == "convex-simplex") sample_convex_simplex
    else stop("Unknown method =", method)
  )

  repeat {
    x <- sample_fun()
    # Due to rounding or bad luck, we may actually have dominated points.
    if (!any_dominated(x)) {
      if (!integer) return(x)
      break
    }
  }

  x <- x * 64
  repeat {
    y <- trunc(x)
    if (!any_dominated(y)) return(y)
    x <- x * 2
  }
}