Black-box functions are broadly used to model complex problems that provide no explicit information but the input and output. Despite existing studies of black-box function optimization, the solution set satisfying an inequality with a black-box function plays a more significant role than only one optimum in many practical situations. Covering as much as possible of the solution set through limited evaluations to the black-box objective function is defined as the Black-Box Coverage (BBC) problem in this paper. We formalized this problem in a sample-based search paradigm and constructed a coverage criterion with Confusion Matrix Analysis. Further, we propose LAMBDA (Latent-Action Monte-Carlo Beam Search with Density Adaption) to solve BBC problems. LAMBDA can focus around the solution set quickly by recursively partitioning the search space into accepted and rejected sub-spaces. Compared with La-MCTS, LAMBDA introduces density information to overcome the sampling bias of optimization and obtain more exploration. Benchmarking shows, LAMBDA achieved state-of-the-art performance among all baselines and was at most 33x faster to get 95% coverage than Random Search. Experiments also demonstrate that LAMBDA has a promising future in the verification of autonomous systems in virtual tests.
翻译:黑箱功能被广泛用于模拟复杂问题,不提供明确的信息,而提供输入和输出。尽管对黑箱功能优化进行了现有的研究,但用黑箱功能满足不平等的解决方案在很多实际情况下比一个最佳的功能发挥更重要的作用。通过对黑箱目标功能的有限评价尽可能覆盖设定的解决方案被定义为本文件中的黑箱覆盖问题。我们通过基于样本的搜索模式将这一问题正规化,并构建了连接矩阵分析的覆盖标准。此外,我们提议用黑箱功能优化解决BBBC问题。LAMBDA(蒙泰-卡罗BAmbA搜索与密度适应性适应性调适的Latent-Action Monte-Carlo Baam搜索)可以快速地聚焦于所设定的解决方案,通过循环将搜索空间分割成被接受和被拒绝的子空间。与La-MCTS相比,LAMBDA引入了密度信息,以克服优化的抽样偏差,并获得更多的探索。基准显示,LAMBDA在所有基线中达到了最先进的性性性表现,最多33x比随机搜索更快获得95%的覆盖率。实验还表明,在虚拟系统中进行自主测试。