提出无需离散化的行为空间划分方法,提升高维优化问题的可扩展性。
Soft Quality-Diversity Optimization
- 用软性分布替代传统离散区域划分,避免维度灾难
- 新算法SQUAD在标准测试上表现媲美顶尖方法
- 适合高维复杂优化问题,代码开源可用
质量-多样性(QD)算法旨在发现优化问题中多样且高质量的解集。现有方法通常通过将行为空间划分为离散区域来保持多样性,再在每个区域搜索最优解。但在大规模解空间或高维行为空间中,该方法面临存储困难和离散化失效的问题。本文提出一种新框架——软质量-多样性(Soft QD),无需离散化即可维持多样性。我们验证了其具有良好性质,如单调性,并与广泛使用的QD Score指标在极限行为上建立关联。基于此,我们设计了一种新的可微分QD算法SQUAD(Soft QD Using Approximated Diversity),实验表明其在标准基准上性能接近当前最优,且在更高维问题中具备更好可扩展性。代码已公开于https://github.com/conflictednerd/soft-qd。
原文摘要 · Abstract (English)
Quality-Diversity (QD) algorithms constitute a branch of optimization that is concerned with discovering a diverse and high-quality set of solutions to an optimization problem. Current QD methods commonly maintain diversity by dividing the behavior space into discrete regions, ensuring that solutions are distributed across different parts of the space. The QD problem is then solved by searching for the best solution in each region. This approach to QD optimization poses challenges in large solution spaces, where storing many solutions is impractical, and in high-dimensional behavior spaces, where discretization becomes ineffective due to the curse of dimensionality. We present an alternative framing of the QD problem, called \emph{Soft QD}, that sidesteps the need for discretizations. We validate this formulation by demonstrating its desirable properties, such as monotonicity, and by relating its limiting behavior to the widely used QD Score metric. Furthermore, we leverage it to derive a novel differentiable QD algorithm, \emph{Soft QD Using Approximated Diversity (SQUAD)}, and demonstrate empirically that it is competitive with current state of the art methods on standard benchmarks while offering better scalability to higher dimensional problems. Source code is available at https://github.com/conflictednerd/soft-qd.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。