发现组合优化中的代数结构，用商空间缩小搜索范围，提升找全局最优的效率。
Algebraic Structure Discovery for Real World Combinatorial Optimisation Problems: A General Framework from Abstract Algebra to Quotient Space Learning
- 通过特征向量编码将规则映射到布尔超立方体，逻辑与变为按位或。
- 在真实临床数据上，商空间遗传算法找到全局最优的概率达48%~77%。
- 适合需要高效搜索等价规则的医疗、分子筛选等实际问题。
许多组合优化问题隐藏着代数结构，一旦揭示，就能缩小搜索空间并提高找到全局最优解的概率。本文提出一个通用框架：(i) 识别代数结构，(ii) 形式化操作，(iii) 构建商空间以合并冗余表示，(iv) 在这些简化空间中直接优化。在一系列规则组合任务（如患者亚群发现和基于规则的分子筛选）中，合取规则构成一个幺半群。通过特征向量编码，我们证明其与布尔超立方体{0,1}^n同构，规则中的逻辑与对应编码中的按位或。由此获得一种有原则的商空间形式，将功能等价规则分组，并引导结构感知搜索。在真实临床数据和合成基准测试中，商空间感知的遗传算法在48%至77%的运行中找到全局最优，而标准方法仅为35%至37%，同时保持了等价类间的多样性。结果表明，揭示并利用代数结构为更高效的组合优化提供了一条简单且通用的路径。
原文摘要 · Abstract (English)
Many combinatorial optimisation problems hide algebraic structures that, once exposed, shrink the search space and improve the chance of finding the global optimal solution. We present a general framework that (i) identifies algebraic structure, (ii) formalises operations, (iii) constructs quotient spaces that collapse redundant representations, and (iv) optimises directly over these reduced spaces. Across a broad family of rule-combination tasks (e.g., patient subgroup discovery and rule-based molecular screening), conjunctive rules form a monoid. Via a characteristic-vector encoding, we prove an isomorphism to the Boolean hypercube $\{0,1\}^n$ with bitwise OR, so logical AND in rules becomes bitwise OR in the encoding. This yields a principled quotient-space formulation that groups functionally equivalent rules and guides structure-aware search. On real clinical data and synthetic benchmarks, quotient-space-aware genetic algorithms recover the global optimum in 48% to 77% of runs versus 35% to 37% for standard approaches, while maintaining diversity across equivalence classes. These results show that exposing and exploiting algebraic structure offers a simple, general route to more efficient combinatorial optimisation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。