Generate a random set of mutually nondominated points

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 \((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.

Usage

generate_ndset(n, d, method, seed = NULL, integer = FALSE)

Arguments

n: integer(1)
Number of rows in the output.
d: integer(1)
Number of columns in the output.
method: character(1)
Method used to generate the random nondominated set. See Details below for more information.
seed: integer(1)
Integer seed for random number generation. If NULL, a random seed is generated.
integer: logical(1)
If TRUE, return integer-valued points.

Value

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 \((d-1)\)-simplex defined by \(\{x \in R_+^d : \sum_i x_i = 1\}\). This shape of nondominated set is also called "linear" in the literature (Lacour et al. 2017) . Each point \(\vec{z} \in (0,1)^d \subset \mathbb{R}^d\) is generated by sampling \(d\) independent and identically distributed values \((x_1,x_2, \dots, x_d)\) from the exponential distribution, then dividing each value by the L1-norm of the vector, \(z_i = x_i / \sum_{i=1}^d x_i\) (Rubinstein and Melamed 1998) . Values sampled from the exponential distribution are guaranteed to be positive.

Sampling from either the standard normal distribution, as suggested by Guerreiro et al. (2021) , or the uniform distribution, as suggested by Lacour et al. (2017) , 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 \(\vec{z} \in (0,1)^d \subset \mathbb{R}^d\) is generated by sampling \(d\) independent and identically distributed values \(\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, \(z_i = \frac{|x_i|}{\|\vec{x}\|_2}\) (Muller 1959) . The absolute value in the numerator ensures that points are sampled on the positive orthant of the hyper-sphere. Sampling from the uniform distribution, as suggested by Lacour et al. (2017) , does not result in a uniform sampling when projected onto the surface of the hyper-sphere.

Method "convex-sphere" is quivalent 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

Andreia P. Guerreiro, Carlos M. Fonseca, Luís Paquete (2021). “The Hypervolume Indicator: Computational Problems and Algorithms.” ACM Computing Surveys, 54(6), 1–42.

Renaud Lacour, Kathrin Klamroth, Carlos M. Fonseca (2017). “A box decomposition algorithm to compute the hypervolume indicator.” Computers & Operations Research, 79, 347–360. doi:10.1016/J.COR.2016.06.021 .

Mervin E. Muller (1959). “A Note on a Method for Generating Points Uniformly on N-Dimensional Spheres.” Communications of the ACM, 2(4), 19–20. doi:10.1145/377939.377946 .

R Y Rubinstein, B Melamed (1998). Modern simulation and modeling. Wiley, New York, NY. Uniform sampling from the simplex.

Examples

generate_ndset(5, 3, "simplex", seed = 42)
#>            [,1]       [,2]       [,3]
#> [1,] 0.06596540 0.48679186 0.44724274
#> [2,] 0.19532517 0.09279699 0.71187784
#> [3,] 0.35895521 0.51930440 0.12174039
#> [4,] 0.02967672 0.92592202 0.04440126
#> [5,] 0.19376601 0.29273646 0.51349753
generate_ndset(5, 3, "simplex", seed = 42, integer = TRUE)
#>      [,1] [,2] [,3]
#> [1,]    4   31   28
#> [2,]   12    5   45
#> [3,]   22   33    7
#> [4,]    1   59    2
#> [5,]   12   18   32
generate_ndset(4, 2, "sphere", seed = 123)
#>            [,1]      [,2]
#> [1,] 0.97441130 0.2247724
#> [2,] 0.13301659 0.9911138
#> [3,] 0.95895269 0.2835661
#> [4,] 0.05564879 0.9984504
generate_ndset(3, 5, "convex-sphere", seed = 123)
#>           [,1]      [,2]      [,3]      [,4]      [,5]
#> [1,] 0.4061573 0.9252940 0.5116439 0.5278063 0.5753693
#> [2,] 0.8709372 0.9275071 0.2906674 0.3136450 0.9379391
#> [3,] 0.3780677 0.3156806 0.7259423 0.8564325 0.7782166
generate_ndset(4, 4, "convex-simplex", seed = 123)
#>              [,1]         [,2]         [,3]         [,4]
#> [1,] 1.063566e-01 0.0003011388 0.2398790054 2.780510e-02
#> [2,] 2.732218e-04 0.8421439916 0.0038396031 1.460775e-05
#> [3,] 2.981715e-01 0.0022797886 0.1134092373 4.821802e-03
#> [4,] 1.017756e-06 0.1054694460 0.0006902269 4.198501e-01