QUADRATIC UNCONSTRAINED BINARY OPTIMIZATION (QUBO) SOLVER ON GRAPHICS PROCESSING UNITS (GPUS)
Optimization problems, such as QUBO problems, can be solved using quantum or classical device. When solving using a classical device, GPUs are used to solve the problem. To optimize GPU usage and explore a deeper solution space, a genetic algorithm using an island model is used to generate an initial solution comprising bundles of close vectors and their associated energies. Simulated annealing is performed and initialized by the initial solution of the genetic algorithm. The simulated annealing process is combined with a student-teacher technique, in which teacher bundles are combined to form a student bundle that is subject to the simulated annealing process. The initialization of the simulated annealing processing using the initial solution from the genetic algorithm enhances the probability of identifying a solution close to the global minimum, while the student-teacher technique provides for deeper exploration of the solution space.
1 . A computerized method comprising:
employing a genetic algorithm to determine an initial solution from a population of potential solutions for an optimization problem; and
performing a simulated annealing process using a GPU architecture to determine an optimal solution to the optimization problem, the simulated annealing process initialized with the initial solution determined using the genetic algorithm.
2 . The method of claim 1 , wherein the simulated annealing process performs a single-flip operation that flips a single bit within a binary variable vector.
3 . The method of claim 1 , wherein the simulated annealing process performs a multi-flip operation that flips multiple bits within a binary variable vector.
4 . The method of claim 1 , wherein the simulated annealing process includes a tabu search technique, the tabu search technique prohibiting flipping of a previously flipped bit.
5 . The method of claim 1 , wherein the genetic algorithm employs an island model configured to introduce diversity in the potential solutions during determination of the initial solution.
6 . The method of claim 1 , wherein the initial solution determined by the genetic algorithm comprises a plurality of solution bundles, each solution bundle comprising variable vectors and energy levels corresponding to each variable vector, and wherein a teacher-student technique is employed during the simulated annealing process to explore solution space between the solution bundles.
7 . The method of claim 6 , wherein the teacher-student technique comprises:
merging the solution bundles into a unified student bundle; and
executing a parallel processing technique on the unified student bundle using the genetic algorithm.
8 . The method of claim 6 , wherein each of the potential solutions is represented as a binary variable vector.
9 . The method of claim 1 , wherein the optimization problem is formulated in a QUBO (quadratic unconstrained binary optimization) form.
10 . A computer system comprising:
at least one processor; and
one or more computer storage media storing computer readable instructions thereon that when executed by the at least one processor cause the at least one processor to perform operations comprising:
employing a genetic algorithm to determine an initial solution from a population of potential solutions for an optimization problem; and
performing a simulated annealing process using a GPU architecture to determine an optimal solution to the optimization problem, the simulated annealing process initialized with the initial solution determined using the genetic algorithm.
11 . The computer system of claim 10 , wherein the simulated annealing process performs a single-flip operation that flips a single bit within a binary variable vector.
12 . The computer system of claim 10 , wherein the simulated annealing process performs a multi-flip operation that flips multiple bits within a binary variable vector.
13 . The computer system of claim 10 , wherein the simulated annealing process includes a tabu search technique, the tabu search technique prohibiting flipping of a previously flipped bit for one or more iterations of the simulated annealing process.
14 . The computer system of claim 10 , wherein the genetic algorithm employs an island model configured to introduce diversity in the potential solutions during determination of the initial solution.
15 . The computer system of claim 10 , wherein the optimization problem is formulated in a QUBO (quadratic unconstrained binary optimization) form.
16 . A computer storage medium storing computer readable instructions that, when executed by one or more computing devices, cause the computing devices to perform operations, the operations comprising:
employing a genetic algorithm to determine an initial solution from a population of potential solutions for an optimization problem; and
performing a simulated annealing process using a GPU architecture to determine an optimal solution to the optimization problem, the simulated annealing process initialized with the initial solution determined using the genetic algorithm.
17 . The computer storage medium of claim 16 , wherein the simulated annealing process performs bit-flipping operation that flips one or more bits within a binary variable vector.
18 . The computer storage medium of claim 16 , wherein the simulated annealing process includes a tabu search technique, the tabu search technique prohibiting flipping of a previously flipped bit.
19 . The computer storage medium of claim 16 , wherein the initial solution determined by the genetic algorithm comprises a plurality of solution bundles, each solution bundle comprising variable vectors and energy levels corresponding to each variable vector, and wherein a teacher-student technique is employed during the simulated annealing process to explore solution space between the solution bundles.
20 . The computer storage medium of claim 16 , wherein the optimization problem is formulated in a QUBO (quadratic unconstrained binary optimization) form.