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 (Guerreiro et al. 2021) or the uniform distribution (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 (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. doi:10.1145/3453474 .

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