moocore.

generate_ndset

moocore.generate_ndset(n, d, /, method, *, seed=None, integer=False)

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.

Parameters:

• n (int) – Number of rows in the output.

• d (int) – Number of columns in the output.

• method (str) – Method used to generate the random nondominated set. See the Notes below for more details.

• seed (int | Generator | None) – Either an integer to seed numpy.random.default_rng(), a Numpy default random number generator (RNG) or an instance of a Numpy-compatible RNG. None uses the equivalent of a random seed, as in numpy.random.default_rng(). (default: None)

• integer (bool) – If True, return integer-valued points. (default: False)

Returns:

ndarray – A numeric matrix of size \(n \times d\) containing nondominated points.

Notes

The available methods are:

'simplex' | 'linear' | 'L'

Uniformly samples points on the standard simplex. This shape of nondominated set is also called 'linear' in the literature [1].

The standard \((d-1)\)-simplex is defined by \(\{\vec{x}\in \mathbb{R}_+^d : \sum_{i=1}^d x_i = 1\}\). 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\) [2]. Values sampled from the exponential distribution are guaranteed to be positive. Sampling from either the standard normal distribution [3] or the uniform distribution [1] does not produce a uniform distribution when projected onto the simplex.

'concave-sphere' | 'sphere' | 'C'

Uniformly samples points on the positive orthant of the hypersphere, 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}\) [4]. The absolute value in the numerator ensures that points are sampled on the positive orthant of the hypersphere. Sampling from the uniform distribution [1] would not result in a uniform sampling when projected onto the surface of the hypersphere.

'convex-sphere' | 'X'

Equivalent to 1 - generate_ndset(..., method='concave-sphere'), which is convex for minimisation problems. This shape has also been called inverted convex [5]. This sampling is uniform.

It corresponds to translating points from the negative orthant of the hypersphere to the positive orthant. Thus, the sampling remains uniform.

cliff-concave

Equivalent to generating a 2D set using method='concave-sphere', then generating the other \(d-2\) columns uniformly at random within the unit hypercube [6][7]. This method does not make sense for d=2.

In the resulting set, the first two columns are mutually nondominated, i.e., no point can dominated another regardless of the other objectives. while the remaining \(d-2\) columns do not provide any ordering. These sets are adversarial for algorithms that aim to exploit dominance structure.

The dimensions that are generated at uniformly random should be chosen adversarially according to the algorithm being tested. Alternatively, the columns may be randomly shuffled using numpy.random.shuffle().

cliff-convex

Equivalent to 1 - generate_ndset(..., method='cliff-concave'). This method does not make sense for d=2.

'convex-simplex'

Equivalent to generate_ndset(..., method='simplex') ** 2, which is convex for minimisation problems. Such a set cannot be obtained by any affine transformation of a subset of the hypersphere. This sampling is not uniform.

The corresponding surface is equivalent to a simplex curved towards the origin. The generated points \(\vec{z} \in (0,1)^d \subset \mathbb{R}^d\) satisfy \(\sum_{i=1}^d \sqrt{z_i} = 1\). Although the sampling on the simplex is uniform, the transformed points are not.

'concave-simplex'

Equivalent to 1 - generate_ndset(..., method='convex-simplex'), which is concave for minimisation problems. This shape has also been called inverted concave [5]. This sampling is not uniform because method='convex-simplex' is not uniform.

'inverted-simplex' | 'inverted-linear'

Equivalent to 1 - generate_ndset(..., method='simplex'). This sampling is uniform.

Methods 'inverted-simplex', 'concave-simplex' and 'convex-sphere' are translations of 'simplex', 'convex-simplex' and 'concave-sphere', respectively. These translations have been called inverted shapes in the literature and have different properties than their regular counterparts [5].

References

[1] (1,2,3)

Renaud Lacour, Kathrin Klamroth, and Carlos M. Fonseca. A box decomposition algorithm to compute the hypervolume indicator. Computers & Operations Research, 79:347–360, 2017. doi:10.1016/j.cor.2016.06.021, [BibTeX].

[2]

R. Y. Rubinstein and B. Melamed. Modern simulation and modeling. Wiley, New York, NY, 1998. [BibTeX].

[3]

Andreia P. Guerreiro, Carlos M. Fonseca, and Luís Paquete. The hypervolume indicator: computational problems and algorithms. ACM Computing Surveys, 54(6):1–42, 2021. doi:10.1145/3453474, [BibTeX].

[4]

Mervin E. Muller. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM, 2(4):19–20, 1959. doi:10.1145/377939.377946, [BibTeX].

[5] (1,2,3)

Hisao Ishibuchi, Linjun He, and Ke Shang. Regular pareto front shape is not realistic. In Proceedings of the 2019 Congress on Evolutionary Computation (CEC 2019), 2034–2041. Piscataway, NJ, June 2019. IEEE Press. doi:10.1109/cec.2019.8790342, [BibTeX].

[6]

Michael T. M. Emmerich and Carlos M. Fonseca. Computing hypervolume contributions in low dimensions: asymptotically optimal algorithm and complexity results. In R. H. C. Takahashi, Kalyanmoy Deb, Elizabeth F. Wanner, and Salvatore Greco, editors, Evolutionary Multi-criterion Optimization, EMO 2011, volume 6576 of Lecture Notes in Computer Science, pages 121–135. Springer, Berlin / Heidelberg, 2011. doi:10.1007/978-3-642-19893-9_9, [BibTeX].

[7]

Andreia P. Guerreiro and Carlos M. Fonseca. Computing and updating hypervolume contributions in up to four dimensions. IEEE Transactions on Evolutionary Computation, 22(3):449–463, June 2018. doi:10.1109/tevc.2017.2729550, [BibTeX].

Examples

>>> moocore.generate_ndset(5, 3, "simplex", seed=42)
array([[0.33742524, 0.32787894, 0.33469582],
       [0.15382676, 0.047522  , 0.79865124],
       [0.30561291, 0.67719985, 0.01718724],
       [0.47441115, 0.03192912, 0.49365973],
       [0.51684378, 0.11549762, 0.3676586 ]])
>>> moocore.generate_ndset(5, 3, "simplex", seed=42, integer=True)
array([[21, 20, 21],
       [ 9,  3, 51],
       [19, 43,  1],
       [30,  2, 31],
       [33,  7, 23]])
>>> rng = np.random.default_rng(42)
>>> moocore.generate_ndset(4, 2, "sphere", seed=rng)
array([[0.28118049, 0.9596549 ],
       [0.62368072, 0.78167919],
       [0.83175713, 0.5551397 ],
       [0.37478326, 0.92711246]])
>>> moocore.generate_ndset(3, 5, "convex-sphere", seed=rng)
array([[0.98843533, 0.41282763, 0.39468745, 0.46462554, 0.95454935],
       [0.37787475, 0.74198125, 0.52575586, 0.79648617, 0.47079199],
       [0.47186748, 0.96998408, 0.88885902, 0.5906188 , 0.26499673]])
>>> moocore.generate_ndset(4, 4, "convex-simplex", seed=rng)
array([[0.19863075, 0.05673281, 0.02294823, 0.02710852],
       [0.00335494, 0.01822224, 0.26522868, 0.08531355],
       [0.22390087, 0.07032143, 0.00793081, 0.02978433],
       [0.08611603, 0.02473488, 0.02168134, 0.16162454]])
>>> moocore.generate_ndset(3, 5, "cliff-convex", seed=42)
array([[0.71881951, 0.0403451 , 0.2388603 , 0.21393569, 0.87188637],
       [0.37631928, 0.21832081, 0.54961406, 0.62920198, 0.07323501],
       [0.16824287, 0.4448603 , 0.35613488, 0.17723839, 0.5565858 ]])

Gallery examples

Sampling Random Nondominated Sets

Sampling Random Nondominated Sets