Check out the Quantum-Assisted Genetic Algorithm (QAGA). This is a genetic algorithm for solving the QUBO problem, but it uses a quantum computer for recombination and for mutation. Thus, this is a hybrid algorithm. When I first saw this paper and the algorithm, I did not understand the isoenergetic cluster move - the input of the algorithm is a QUBO, and the output is a solution vector. The individuals in the genetic algorithm are also solution vectors. So how could it then be that recombination (and specifically, the isoenergetic cluster move) worked on 2-dimensional data?
*Figure from the QAGA paper linked above.
The way it works now is as follows.
- First, pick two potential solution vectors.
- Save the XOR difference between those two vectors.
- Interpret the QUBO as a graph, and remove the nodes in which values of both vectors are equal. This results in a reduced graph.
- Pick a random node from the reduced graph, and compute its cluster (connected components to that node).
- The corresponding indices in both solution vectors are now flipped based on the nodes in that cluster.
With this, it is possible to use the isoenergetic cluster move as a recombination operator in a genetic algorithm, such as QAGA. Note that as the mutation operator, reverse annealing is used.