Inventory of the 12 007 Low-Dimensional Pseudo-Boolean Landscapes Invariant to Rank, Translation, and Rotation

Arnaud Liefooghe; Sébastien Verel

cs.AIApr 7, 2026

Inventory of the 12 007 Low-Dimensional Pseudo-Boolean Landscapes Invariant to Rank, Translation, and Rotation

Authors: Arnaud Liefooghe, Sébastien Verel

Organizations: LISIC · Univ. Littoral Côte d’Opale, UR 4491, LISIC, F-62100 Calais, France

Abstract

Many randomized optimization algorithms are rank-invariant, relying solely on the relative ordering of solutions rather than absolute fitness values. We introduce a stronger notion of rank landscape invariance: two problems are equivalent if their ranking, but also their neighborhood structure and symmetries (translation and rotation), induce identical landscapes. This motivates the study of rank landscapes rather than individual functions. While prior work analyzed the rankings of injective function classes in isolation, we provide an exhaustive inventory of the invariant landscape classes for pseudo-Boolean functions of dimensions 1, 2, and 3, including non-injective cases. Our analysis reveals 12,007 classes in total, a significant reduction compared to rank-invariance alone. We find that non-injective functions yield far more invariant landscape classes than injective ones. In addition, complex combinations of topological landscape properties and algorithm behaviors emerge, particularly regarding deceptiveness, neutrality, and the performance of hill-climbing strategies. The inventory serves as a resource for pedagogical purposes and benchmark design, offering a foundation for constructing larger problems with controlled hardness and advancing our understanding of landscape difficulty and algorithm performance.

Figures & tables

$x$	$f_{1}(x)$	rank	$f_{2}(x)$	rank	$f_{3}(x)$	rank	$f_{4}(x)$	rank	$f_{5}(x)$	rank
00	$4.0$	C	$3.6$	C	$7.0$	D	$7.0$	D	$3.0$	B
01	$1.0$	A	$2.9$	A	$2.9$	B	$3.0$	C	$3.0$	B
10	$9.0$	D	$3.7$	D	$3.0$	C	$2.9$	B	$7.0$	C
11	$3.0$	B	$3.1$	B	$2.0$	A	$2.0$	A	$2.0$	A

Table 1: Solutions, fitness values, and corresponding ranks for five example two-dimensional pseudo-Boolean functions to be minimized.

	$(1)^{k}$	$+$	$i$	$=$	$\lambda$	$p_{k}$	$F_{\lambda}$
$k=4$	$(1,1,1,1)$	$+$	$(0,0,0,0)$	$=$	$(1,1,1,1)$	$1$	$24$
$k=3$	$(1,1,1)$	$+$	$(1,0,0)$	$=$	$(2,1,1)$	$3$	$12$
		$+$	$(0,1,0)$	$=$	$(1,2,1)$		$12$
		$+$	$(0,0,1)$	$=$	$(1,1,2)$		$12$
$k=2$	$(1,1)$	$+$	$(2,0)$	$=$	$(3,1)$	$3$	$4$
		$+$	$(1,1)$	$=$	$(2,2)$		$6$

Table 2: Enumeration of partitions for two-dimensional pseudo-Boolean functions:

p_{k}

denotes the number of partitions with

k

ranks,

F_{\lambda}

denotes the number of rank-invariant function classes for partition

\lambda

${n=3}$
	$p_{\lambda}$	$\sum_{\lambda:d_{\lambda}=k}F_{\lambda}$
$k=1$	$1$	$1$
$k=2$	$7$	$254$
$k=3$	$21$	$5\,796$
$k=4$	$35$	$40\,824$
$k=5$	$35$	$126\,000$

Table 3: Number of partitions and rank-invariant function classes by rank count

k

for three- and four-dimensional pseudo-Boolean functions.

	ranks	rankings	automorphisms	invariant landscape classes
	$2^{n}$	$2^{n}!$	$2^{n}\cdot n!$	$(2^{n}-1)!/n!$
$n=1$	$2$	$2$	$2$	$1$
$n=2$	$4$	$24$	$8$	$3$
$n=3$	$8$	$40\,320$	$48$	$840$
$n=4$	$16$	$\approx 2^{44.25}\approx 10^{13.32}$	$384$	$\approx 2^{35.67}\approx 10^{10.73}$

Table 4: Number of invariant landscape classes for injective pseudo-Boolean fitness functions with

n\leqslant 4

variables.

Figure 1: Fitness and rank landscapes of five three-dimensional pseudo-Boolean function examples, mapping to two distinct invariant landscape classes: (ab ′ ), (c ′ ), and (d ′ ) are automorphic (id 1580 in the 3D inventory in Section 5 ), while (e ′ ) belongs to a separate class (id 1371 ).

Figure 2: The 2 one-dimensional invariant landscape classes.

Panel of Figure 3 — Figure 3: The 14 two-dimensional invariant landscape classes.

id	ranks	rankings	deceptive	neutral	plateau	comments
0	4	8	✕	✕	✕	Injective
1	4	8	✕	✕	✕	Injective
2	4	8	$\ovoid$	✕	✕	Injective, Min. deceptive
3	3	8	✕	$\ovoid$	$\ovoid$
4	3	4	✕	✕	✕
5	3	4	✕	✕	✕	OneMax

Table 5: Properties of the 14 two-dimensional invariant landscape classes.

	best-improvement		first-improvement
id	success rate	multi-start ERT	success rate	multi-start ERT
0	1.000	5.000	1.000	4.375
1	1.000	5.000	1.000	4.750
2	0.750	5.333	0.500	7.000
3	1.000	4.000	1.000	3.812
4	1.000	4.000	1.000	3.500

Table 6: Expected performance of best- and first-improvement hill climber (single- and multi-start) on the 14 two-dimensional invariant landscape classes. ERT stands for expected runtime. See Tables 11 – 12 in Appendix for details.

Panel of Figure 4 — Figure 4: Examples from the 11 991 three-dimensional invariant landscape classes.

Panel of Figure 5 — Figure 5: Distribution of the three-dimensional invariant landscape classes by key properties: number of ranks, symmetries, global optima, suboptima, neutral edges, plateaus, and suboptimal plateaus.

deceptive	neutral	plateau	count	percentage
✕	✕	✕	$1\,233$	$10.28\%$
$\ovoid$	✕	✕	$3\,175$	$26.48\%$
✕	$\ovoid$	✕	$1\,098$	$9.16\%$
$\ovoid$	$\ovoid$	✕	$4\,130$	$34.44\%$
✕	$\ovoid$	$\ovoid$	$1\,130$	$9.42\%$
$\ovoid$	$\ovoid$	$\ovoid$	$1\,225$	$10.22\%$

Table 7: Number and percentage of the three-dimensional invariant landscape classes by combination of properties (deceptiveness, neutrality, and plateaus).

Panel of Figure 6 — Figure 6: Distribution of the three-dimensional invariant landscape classes by success rate and expected runtime for best-improvement and first-improvement hill climbers.

Figure 7: Cumulative distribution of the three-dimensional invariant landscape classes where the success rate and expected runtime fall below a threshold for best-improvement and first-improvement hill climbers.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

	translation $t_{z}$
	$z$
$x$	00	01	10	11
00 (0)	00 (0)	01 (1)	10 (2)	11 (3)
01 (1)	01 (1)	00 (0)	11 (3)	10 (2)
10 (2)	10 (2)	11 (3)	00 (0)	01 (1)
11 (3)	11 (3)	10 (2)	01 (1)	00 (0)

Appendix

Table 8: Landscape-invariant transformations for 2D hypercube landscapes: translations

t_{z}

(left) and rotations

r_{\sigma}

(right). The decimal equivalents of binary solutions are given in parentheses.

	translation $t_{z}$
	$z$
$x$	000	001	010	011	100	101	110	111
000 (0)	000 (0)	001 (1)	010 (2)	011 (3)	100 (4)	101 (5)	110 (6)	111 (7)
001 (1)	001 (1)	000 (0)	011 (3)	010 (2)	101 (5)	100 (4)	111 (7)	110 (6)
010 (2)	010 (2)	011 (3)	000 (0)	001 (1)	110 (6)	111 (7)	100 (4)	101 (5)
011 (3)	011 (3)	010 (2)	001 (1)	000 (0)	111 (7)	110 (6)	101 (5)	100 (4)

Appendix

Table 9: Landscape-invariant transformations for 3D hypercube landscapes: translations

t_{z}

(top) and rotations

r_{\sigma}

(bottom). The decimal equivalents of binary solutions are given in parentheses.

Figure 8: Behind the scenes: Original enumeration of 2D invariant landscape classes on the whiteboard.

id	global optima	suboptima	neutral networks	optimal plateaus	suboptimal plateaus	neutral degree
0	1	0	0	0	0	0
1	1	0	0	0	0	0
2	1	1	0	0	0	0
3	2	0	1	1	0	2
4	2	0	0	0	0	0
5	1	0	0	0	0	0

Appendix

Table 10: Detailed properties of 2D landscape classes.

	success	successful trajectories		unsuccessful trajectories		multi-start
id	rate	exp. steps	exp. evals	exp. steps	exp. evals	ERT
0	1.000	1.000	5.000	–	–	5.000
1	1.000	1.000	5.000	–	–	5.000
2	0.750	0.667	4.333	0.000	3.000	5.333
3	1.000	0.500	4.000	–	–	4.000
4	1.000	0.500	4.000	–	–	4.000

Appendix

Table 11: Detailed expected performance metrics of best-improvement hill climber (single- and multi-start) on 2D landscape classes.

	success	successful trajectories		unsuccessful trajectories		multi-start
id	rate	exp. steps	exp. evals	exp. steps	exp. evals	ERT
0	1.000	1.000	4.375	–	–	4.375
1	1.000	1.250	4.750	–	–	4.750
2	0.500	0.500	3.500	0.500	3.500	7.000
3	1.000	0.625	3.812	–	–	3.812
4	1.000	0.500	3.500	–	–	3.500

Appendix

Table 12: Detailed expected performance metrics of first-improvement hill climber (single- and multi-start) on 2D landscape classes, assuming neighbors are explored in random order.

Fitness Landscape Analysis

See all 12 papers

On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization
May 27, 2026Sara Gjorgjieva, Eva Tuba, Barbara Koroušić Seljak +2Fitness Landscape Analysis Representation Learning
Jožef Stefan Institute, Ljubljana, Slovenia · Sorbonne Université, CNRS, LIP6, Paris, France
Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing
Sep 29, 2026Eugene Agyei-Kodie, Longxiu Huang, Shuang Li +1Nonconvex Optimization Optimization Convergence Analysis
Department of Mathematics, Michigan State University, 619 Red Cedar, East Lansing, 48824, MI, USA. · Department of Computational Mathematics, Science and Engineering, Michigan State University, 428 S Shaw Ln, East Lansing, 48824, MI, USA. · Department of Electrical and Computer Engineering, Iowa State University, 2520 Osborn Dr, Ames, 50011, IA, USA.
Population-Level Generative Modeling for Ranking Data
Aug 9, 2026Zhaoyang ShiSynthetic Data Generation
Center for Applied Mathematics, Fudan University Shanghai, China

May 27, 2026J/K move · Enter open · S save

On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

Sara Gjorgjieva, Eva Tuba, Barbara Koroušić Seljak, Carola Doerr+1

Jožef Stefan Institute, Ljubljana, Slovenia · Sorbonne Université, CNRS, LIP6, Paris, France

Fitness Landscape Analysis Representation Learning Black-Box Optimization

Open paper AskPDF arXiv

Landscape feature representations play a central role in automated algorithm selection and meta-learning for black-box optimization, yet little is known about how different representations agree (or disagree) in the structures they impose on problem spaces. This paper presents a systematic unsupervised evaluation of four state-of-the-art representations (ELA, DeepELA, TransOptAS, and DoE2Vec) using a diverse set of affine combinations of BBOB functions (MA-BBOB). By applying extensive clustering analyses, coverage-based stability measures, and cross-representation similarity assessments, we show that each representation organizes the same problems in markedly different ways: ELA and TransOptAS form compact geometric structures, DeepELA provides a balanced intermediate view, and DoE2Vec achieves strong semantic alignment but with substantial fragmentation. Our results reveal that no single representation dominates; rather, they capture complementary aspects of the underlying landscapes. These findings highlight the importance of multi-view analyses for understanding representation behavior and offer guidance on selecting or combining representations in downstream meta-learning and algorithm selection tasks. In addition, across two different algorithm families (Differential Evolution and Particle Swarm Optimization), we show that landscape representations face an inherent trade-off in how well they align structural landscape descriptions with observed performance, indicating that no single representation can fully capture algorithm performance.

Abstract

Fitness Landscape Analysis

Explore similar work

On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing

Population-Level Generative Modeling for Ranking Data