WORLD SCIENTIFIC (EUROPE) eBooks
METAHEURISTIC SEARCH TECHNIQUES: GENETIC ALGORITHMS AND QUANTUM ANNEALING
Abstract
This part of the course introduces heuristic search methods — optimization techniques typically inspired by naturally occurring phenomena. We will focus on two such methods: genetic algorithms and quantum annealing. These represent opposite ends of the heuristic spectrum: in one, the problem of interest is largely decoupled from the mechanics of the search, while in the other, the problem is directly embedded within it. Although many other heuristic techniques exist, these two examples illustrate key advantages (e.g., broad applicability, potential speed-ups in suitable settings) and drawbacks (e.g., limited explainability) shared by many heuristic methods. In the tutorials, we will consider several discrete problems, such as Taxicab numbers and the Knapsack problem. The former is a well-known curiosity in number theory, while the latter is a classic problem in combinatorial optimization. Both are also morally analogous to certain discrete structures that arise in physics, such as anomaly cancellation conditions and partition function computations.