Quantum-enhanced selection operators for evolutionary algorithms

Von Dollen, D.; Yarkoni, S.; Weimer, D.; Neukart, F.; Bäck, T.H.W.; Fieldsend, J.E.

doi:doi:10.1145/3520304.3528915

Persistent URL of this record https://hdl.handle.net/1887/3464619

View statistics

In Collections

This item can be found in the following collections:

Faculty of Science: Other

Von Dollen, D.; Yarkoni, S.; Weimer, D.; Neukart, F.; Bäck, T.H.W. (2022)

Quantum-enhanced selection operators for evolutionary algorithms

Article in monograph or in proceedings

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 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...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

Quantum Computing

Quantum Annealing

Quantum-Inspired Algorithms

Quantum-Enhanced Algorithms

Combinatorial Optimization

Evolutionary Algorithms

Genetic Algorithm

Selection Operators

Maximum Diversity Problem