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.

See the visualisations in the vignette Sampling Random Nondominated Sets.

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-simplex": Equivalent to generate_ndset(..., method="simplex")^2, which is convex for minimisation. Such a set cannot be obtained by any affine transformation of a subset of the hyper-sphere. This sampling is not uniform.
"convex-sphere" or "X": Equivalent to 1 - generate_ndset(..., method="concave-sphere"), which is convex for minimisation. This shape has also been called inverted convex (Ishibuchi et al. 2019) . This sampling is uniform.
"inverted-simplex" or "inverted-linear": Equivalent to 1 - generate_ndset(..., method="simplex"). This sampling is uniform.
"concave-simplex": Equivalent to 1 - generate_ndset(..., method="convex-simplex"), which is concave for minimisation. This shape has also been called inverted concave (Ishibuchi et al. 2019) . This sampling is not uniform because method="convex-simplex" is also not uniform.

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 onto 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) would not result in a uniform sampling when projected onto the surface of the hyper-sphere.

Method "convex-simplex" is equivalent to generate_ndset(..., method="simplex")^2, which is convex for minimisation problems. The corresponding surface is equivalent to a simplex curved towards the origin. Although the sampling on the simplex is uniform, the transformed points are not.

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. Thus, the sampling remains uniform.

Methods "inverted-simplex" and "concave-simplex" are similar translations of "simplex" and "convex-simplex", respectively. These translations have been called inverted shapes in the literature and have different properties than their regular counterparts (Ishibuchi et al. 2019) .

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 .

Hisao Ishibuchi, Linjun He, Ke Shang (2019). “Regular Pareto Front Shape is not Realistic.” In Proceedings of the 2019 Congress on Evolutionary Computation (CEC 2019), 2034–2041. doi:10.1109/cec.2019.8790342 .

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,] 0.0466076812 0.0002070015 0.4869208586 0.005173520
#> [2,] 0.1969203249 0.0593303025 0.0005033912 0.084232547
#> [3,] 0.2195593888 0.0122730922 0.1255022257 0.004406494
#> [4,] 0.0004391516 0.0092938485 0.1015625920 0.318040262