About the author:
Daniel is CTO at rhome GmbH, and Co-Founder at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning and quantum computing. He writes about technical topics in quantum computing and startups.
jrnl · home about list ventures publications LinkedIn Join my Slack

# Improving evolutionary algorithms using quantum computing

I love the concept of QAGA - the quantum-assisted genetic algorithm. A standard evolutionary algorithm consists of a recombination phase, a mutation phase, and a selection phase. In the case of QAGA the mutation phase is done using reverse quantum annealing. In the latest research from Aqarios in cooperation with LMU Munich we improved the published QAGA algorithm on a set of problems (Graph Coloring, Knapsack, SAT). Since simulated annealing can be used for reverse annealing as well, we first tested solely on classical compute (we called the algorithm using simulated annealing SAGA), and later went for experiments with quantum compute. Slightly risky, but very effective, this allowed us to test a large number of modifications due to the high cost of QC right now.

We will publish the results in the QC Workshop at GECCO 2022 - I will link the paper soon.

Note that the recombination phase can also be computed with quantum annealing - see my other post here.

Specifically, the following modifications were tested:

  • Simpler selection (ignoring the shared Ising energy and only using the individual energy)
  • Simpler recombination (one-point crossover, random crossover) instead of the cluster moves
  • Incremental sampling size, specifically increasing the number of sweeps and the population size over time
  • Decreasing annealing temperature over time
  • Parameter mutation - each individual of the population also includes the annealing temperature, which is thus mutated as well
  • Multiprocessing
  • Combinations of the above and further minor modifications (see our publication)

The next Figure shows an overview of the modifications from the paper with shortnames. The shortnames are important to understand further Figures with results.

Next, the first results are shown. It is clear that our crossover modifications work well, and that we find for all problems a modification that improves upon the baseline - though we are not able to find a general improvement on all problems investigated here at the same time. Increasing the number of sweeps and decreasing the annealing temperature also both work very well.

Lastly, the following Figure shows our results on quantum hardware. It is clear that the modifications on SAGA also partly transfer to quantum compute.

Not only does this show that we were able to improve a genetic algorithm (that I would call the strategic micro-scale of this project), but this also shows that it is feasible to do experimentation on classical hardware and transfer the results to quantum compute later.

Super happy about the results - only possible with all the great work by everyone involved!

Published on