Black-box optimization (BBO) can be used to optimize functions whose analytic form is unknown. A common approach to realising BBO is to learn a surrogate model which approximates the target black-box function which can then be solved via white-box optimization methods. In this paper, we present our approach BOX-QUBO, where the surrogate model is a QUBO matrix. However, unlike in previous state-of-the-art approaches, this matrix is not trained entirely by regression, but mostly by classification between 'good' and 'bad' solutions. This better accounts for the low capacity of the QUBO matrix, resulting in significantly better solutions overall. We tested our approach against the state-of-the-art on four domains and in all of them BOX-QUBO showed better results. A second contribution of this paper is the idea to also solve white-box problems, i.e. problems which could be directly formulated as QUBO, by means of black-box optimization in order to reduce the size of the QUBOs to the information-theoretic minimum. Experiments show that this significantly improves the results for MAX-k-SAT.
翻译:黑盒优化 (BBO) 可用于优化分析形式未知的功能 。 实现 BBO 的常见方法是学习一种替代模型, 这个模型接近目标黑盒功能, 然后可以通过白盒优化方法解决。 在本文中, 我们展示了我们的方法 BOX- QUBO, 这个替代模型是一个 QUBO 矩阵。 但是, 与以前最先进的方法不同, 这个矩阵不是完全通过回归来训练, 而是主要通过“ 良好” 和“ 坏” 解决方案的分类来训练。 这更好地说明了QUBO 矩阵的容量较低, 从而导致总体解决方案大大改善。 我们在四个领域测试了我们的方法, 在所有这些领域, BOX- QUBO 都显示了更好的结果。 本文的第二个贡献是同时解决白箱问题, 也就是说, 可以通过黑盒优化来直接制定为 QUBO, 从而将 QUBO 的大小缩小到 信息- 智能最小值 。 实验显示 MAX 大大改进了 。