Genetic algorithms have unique properties which are useful when applied to black-box optimization. Using selection, crossover, and mutation operators, candidate solutions may be obtained without... Show moreGenetic algorithms have unique properties which are useful when applied to black-box optimization. Using selection, crossover, and mutation operators, candidate solutions may be obtained without the need to calculate a gradient. In this work, we study results obtained from using quantum-enhanced operators within the selection mechanism of a genetic algorithm. Our approach frames the selection process as a minimization of a binary quadratic model with which we encode fitness and distance between members of a population, and we leverage a quantum annealing system to sample low-energy solutions for the selection mechanism. We benchmark these quantum-enhanced algorithms against classical algorithms over various black-box objective functions, including the OneMax function, and functions from the IOHProfiler library for black-box optimization. We observe a performance gain in the average number of generations to convergence for the quantum-enhanced elitist selection operator in comparison to classical on the OneMax function. We also find that the quantum-enhanced selection operator with ∗Corresponding author email: David.VonDollen@vw.com non-elitist selection outperforms benchmarks on functions with fitness perturbation from the IOHProfiler library. Additionally, we find that in the case of elitist selection, the quantum-enhanced operators outperform classical benchmarks on functions with varying degrees of dummy variables and neutrality Show less
Yarkoni, S.; Alekseyenko, A.; Streif, M.; Von Dollen, D.J.; Neukart, F.; Bäck, T.H.W. 2021
Quantum annealing devices such as the ones produced by D-Wave systems are typically used for solving optimization and sampling tasks, and in both academia and industry the characterization of their... Show moreQuantum annealing devices such as the ones produced by D-Wave systems are typically used for solving optimization and sampling tasks, and in both academia and industry the characterization of their usefulness is subject to active research. Any problem that can naturally be described as a weighted, undirected graph may be a particularly interesting candidate, since such a problem may be formulated a as quadratic unconstrained binary optimization (QUBO) instance, which is solvable on D-Wave's Chimera graph architecture. In this paper, we introduce a quantum-assisted finite-element method for design optimization. We show that we can minimize a shape-specific quantity, in our case a ray approximation of sound pressure at a specific position around an object, by manipulating the shape of this object. Our algorithm belongs to the class of quantum-assisted algorithms, as the optimization task runs iteratively on a D-Wave 2000Q quantum processing unit (QPU), whereby the evaluation and interpretation of the results happens classically. Our first and foremost aim is to explain how to represent and solve parts of these problems with the help of a QPU, and not to prove supremacy over existing classical finite-element algorithms for design optimization. Show less
