构建12007个保持排序、平移与旋转不变的伪布尔景观类，用于优化算法研究。
Inventory of the 12 007 Low-Dimensional Pseudo-Boolean Landscapes Invariant to Rank, Translation, and Rotation
- 基于排序、邻域与对称性定义景观等价类，系统分类低维伪布尔函数。
- 在1~3维下共发现12,007个不变景观类，远少于仅考虑排序的情况。
- 揭示非单射函数带来更丰富景观结构，适合研究算法性能与难题构造。
许多随机优化算法具有排序不变性，仅依赖解的相对顺序而非绝对适应值。本文提出更强的排序景观不变性：若两个问题的排序、邻域结构及对称性（平移与旋转）诱导出相同景观，则视为等价。这促使我们研究景观类而非单一函数。以往工作孤立分析单射函数的排序，本文首次完整枚举1、2、3维伪布尔函数中所有保持排序、平移与旋转不变的景观类，包含非单射情形。分析发现总计12,007个景观类，显著少于仅考虑排序不变性的情形。结果表明，非单射函数产生的不变景观类远多于单射函数。此外，拓扑景观特性与算法行为间出现复杂耦合，尤其体现在欺骗性、中立性及爬山策略表现上。该清单可作为教学资源与基准设计基础，支持构建具有可控难度的大规模问题，推动对景观难易度与算法性能的理解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。