This study introduces a novel train-and-test approach referred to as apprenticeship learning (AL) for generating selection hyper-heuristics to solve the Quadratic Unconstrained Binary Optimisation (QUBO) problem. The primary goal is to automate the design of hyper-heuristics by learning from a state-of-the-art expert and to evaluate whether the apprentice can outperform that expert. The proposed method collects detailed search trace data from the expert and trains the apprentice based on the machine learning models to predict heuristic selection and parameter settings. Multiple data filtering and class balancing techniques are explored to enhance model performance. The empirical results on unseen QUBO instances show that indeed, “student surpasses the teacher”; the hyper-heuristic with the generated heuristic selection not only outperforms the expert but also generalises quite well by solving unseen QUBO instances larger than the ones on which the apprentice was trained. These findings highlight the potential of AL to generalise expert behaviour and improve heuristic search performance.
This study introduces a novel train-and-test approach referred to as apprenticeship learning (AL) for generating selection hyper-heuristics to solve the Quadratic Unconstrained Binary Optimisation (QUBO) problem. The primary goal is to automate the design of hyper-heuristics by learning from a state-of-the-art expert and to evaluate whether the apprentice can outperform that expert. The proposed method collects detailed search trace data from the expert and trains the apprentice based on the machine learning models to predict heuristic selection and parameter settings. Multiple data filtering and class balancing techniques are explored to enhance model performance. The empirical results on unseen QUBO instances show that indeed, “student surpasses the teacher”; the hyper-heuristic with the generated heuristic selection not only outperforms the expert but also generalises quite well by solving unseen QUBO instances larger than the ones on which the apprentice was trained. These findings highlight the potential of AL to generalise expert behaviour and improve heuristic search performance.
A popular method for solving a constrained combinatorial optimisation problem is to first convert it into a quadratic unconstrained binary optimisation (QUBO) problem, and solve it using a standard QUBO solver. However, this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints, and their chosen values significantly impact performance. Hence, hyper-parameters tuning is important. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them inefficient for performance critical applications when repeated solutions of similar combinatorial optimisation problems are required. In this paper, we propose the QROSS method, in which we build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce promising hyper-parameters with fewer calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate QROSS finds better solutions with fewer calls to QUBO solver, compared with conventional hyper-parameter tuning techniques. Moreover, with simple adaptation methods, QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.
Though empirical testing is broadly used to evaluate heuristics, there are major shortcomings with how it is applied in practice. In a systematic review of Max-Cut and Quadratic Unconstrained Binary Optimization (QUBO) heuristics papers, we found only 4% publish source code, only 10% compare heuristics with identical hardware and termination criteria, and most experiments are performed with an articial, homogeneous set of problem instances. To address these limitations, we rst propose a framework for reproducible heuristic evaluation based on large-scale open-source implementation, expanded sets of test instances, and evaluation with cloud computing. We give a proof of concept of the framework by testing 37 Max-Cut and QUBO heuristics across 3,298 problem instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners. We hope our framework will be applied broadly to identify \what works best when among heuristics for a range of optimization problems.
Advances in artificial intelligence (AI) and deep learning have raised concerns about its increasing energy consumption, while demand for deploying AI in mobile devices and machines at the edge is growing. Binary neural networks (BNNs) have recently gained attention as energy and memory efficient models suitable for resource constrained environments; however, training BNNs exactly is computationally challenging because of its discrete characteristics. Recent work proposing a framework for training BNNs based on quadratic unconstrained binary optimisation (QUBO) and progress in the design of Ising machines for solving QUBO problems suggest a potential path to efficiently optimising discrete neural networks. In this work, we extend existing QUBO models for training BNNs to accommodate arbitrary network topologies and propose two novel methods for regularisation. The first method maximises neuron margins biasing the training process toward parameter configurations that yield larger pre-activation magnitudes. The second method employs a dropout-inspired iterative scheme in which reduced subnetworks are trained and used to adjust linear penalties on network parameters. We apply the proposed QUBO formulation to a small binary image classification problem and conduct computational experiments on a GPU-based Ising machine. The numerical results indicate that the proposed regularisation terms modify training behaviour and yield improvements in classification accuracy on data not present in the training set.
This study extends previous work on quantum-enhanced selection operators [Von Dollen et al.(2022)], where selection operators of evolutionary algorithms for classical black-box optimization are framed as quadratic binary optimization (QUBO) models, applied to black-box objective functions. We test our algorithms using both elitist and non-elitist strategies. First, we benchmark all heuristics over black-box, multi-modal functions. We find that for 94.4% of test cases, our method shows performance improvements with respect to fitness. Then, we similarly benchmark over the problem of hyperparameter selection for machine learning models, also a black-box optimization problem, and compare it to random search. We find that our method achieves some improvement with an average validation accuracy of 98.492% and highest ranking of 4.529412 (out of 5) when averaged across all test cases. We also apply our method towards neuroevolution, where we evolve weight spaces for small feedforward neural networks for learning tasks. In these settings, our method shows improved average reward in the reinforcement learning case and increased velocity in learning the XOR function.
Leveraging quantum computers for optimization problems holds promise across various application domains. Nevertheless, utilizing respective quantum computing solvers requires describing the optimization problem according to the Quadratic Unconstrained Binary Optimization (QUBO) formalism and selecting a proper solver for the application of interest with a reasonable setting. Both demand significant proficiency in quantum computing, QUBO formulation, and quantum solvers, a background that usually cannot be assumed by end users who are domain experts rather than quantum computing specialists. While tools aid in QUBO formulations, support for selecting the best-solving approach remains absent. This becomes even more challenging because selecting the best solver for a problem heavily depends on the problem itself. In this work, we are accepting this challenge and propose a predictive selection approach, which aids end users in this task. To this end, the solver selection task is first formulated as a classification task that is suitable to be solved by supervised machine learning. Based on that, we then propose strategies for adjusting solver parameters based on problem size and characteristics. Experimental evaluations, considering more than 500 different QUBO problems, confirm the benefits of the proposed solution. In fact, we show that in more than 70% of the cases, the best solver is selected, and in about 90% of the problems, a solver in the top two, i.e., the best or its closest suboptimum, is selected. This exploration proves the potential of machine learning in quantum solver selection and lays the foundations for its automation, broadening access to quantum optimization for a wider range of users. The pre-trained classifier is integrated into the MQT Quantum Auto Optimizer (MQT QAO) framework, publicly available on GitHub (https://github.com/cda-tum/mqt-qao) as part of the Munich Quantum Toolkit (MQT).
A constantly increasing number of parameters in modern machine learning models has become a significant bottleneck in their efficient training, resulting in a disproportionate consumption of resources, expressed in terms of energy and computational time. The vast majority of such resources are allocated to the training phase rather than the inference stage, leading to an inefficient process [1] , [2] , [3] . This study addresses this problem by introducing a quantum alternative for training machine learning models, formalized as a Quadratic Unconstrained Binary Optimization ( QUBO ) problem. Adiabatic quantum computers have shown promise in approximately solving certain NP -hard problems, such as QUBO , potentially offering speed advantages over classical computers in specific scenarios [ 4 , 5, [6] , [7] ]. Given that many machine learning problems are also NP -hard, adiabatic quantum computers could play a pivotal role in efficiently training machine learning models. Furthermore, inspired by the ones’ complement binary numeral system, this work includes the proposal of an efficient binary-to-decimal encoding, which improves data representation in the quantum context. A concrete implementation of a regression training problem on specific quantum hardware is also presented here, the results of which suggest that the adoption of quantum techniques in model training allows not only to address the problem of parameter explosion but also to offer promising prospects for significantly accelerate the training process by exploiting the unique properties of quantum computation.