Quality-Diversity optimisation (QD) has proven to yield promising results across a broad set of applications. However, QD approaches struggle in the presence of uncertainty in the environment, as it impacts their ability to quantify the true performance and novelty of solutions. This problem has been highlighted multiple times independently in previous literature. In this work, we propose to uniformise the view on this problem through four main contributions. First, we formalise a common framework for uncertain domains: the Uncertain QD setting, a special case of QD in which fitness and descriptors for each solution are no longer fixed values but distribution over possible values. Second, we propose a new methodology to evaluate Uncertain QD approaches, relying on a new per-generation sampling budget and a set of existing and new metrics specifically designed for Uncertain QD. Third, we propose three new Uncertain QD algorithms: Archive-sampling, Parallel-Adaptive-sampling and Deep-Grid-sampling. We propose these approaches taking into account recent advances in the QD community toward the use of hardware acceleration that enable large numbers of parallel evaluations and make sampling an affordable approach to uncertainty. Our final and fourth contribution is to use this new framework and the associated comparison methods to benchmark existing and novel approaches. We demonstrate once again the limitation of MAP-Elites in uncertain domains and highlight the performance of the existing Deep-Grid approach, and of our new algorithms. The goal of this framework and methods is to become an instrumental benchmark for future works considering Uncertain QD.
翻译:不确定性质-多样性: 评估方法学和不确定领域中质量-多样性的新方法
质量-多样性优化(QD)已证明在广泛的应用中产生了有前途的结果。然而,在环境中存在不确定性的情况下,QD方法很难量化解决方案的真实性能和新颖性。这个问题先前的文献独立地强调了多次。在此工作中,我们通过四个主要贡献提出了统一的观点。首先,我们规范了不确定领域的常见框架:不确定的QD环境,这是QD的一种特殊情况,在此情况下,每个解决方案的健身和描述符不再是固定值,而是可能值的分布。其次,我们提出了一种评估不确定的QD方法的新方法,依赖于新的每一代抽样预算以及用于不确定的QD的一组现有和新度量标准。第三,我们提出了三种新的不确定QD算法:Archive-sampling、Parallel-Adaptive-sampling和Deep-Grid-sampling。我们提出这些方法,考虑到QD社区近期对于使用硬件加速的进展,这使得大量并行评估成为一种经济的不确定性方法。我们最后的第四个贡献是使用这个新的框架和关联的比较方法来对现有和新的方法进行基准测试。我们再次证明了MAP-Elites在不确定领域中的局限性,并强调了现有Deep-Grid方法和我们的新算法的性能优势。这个框架和方法的目标是成为未来考虑不确定QD的工作的重要基准。