Heuristic solution
- Let's get to know the annealing machine even better!
Overview
The computations performed by an annealing machine belong to a category called metaheuristics. This is one of the most effective approaches when, for example, one wants to efficiently obtain a good answer from a large number of possible combinations. When the number of candidate combinations is too large, it is clear from academic studies that prioritizing the accuracy of the answer would take too much computation time, so an approach to find a reasonably good solution, if not the most correct one, at a high speed is useful. In general, computers often employ procedures and algorithms that lead to the only correct solution (exact solution), but let's learn about the different heuristic features and the significance of annealing machines in this perspective.
Heuristics and Metaheuristics
Heuristics are methods of finding or improving solutions to a problem through experience and discovery. Heuristics that can be applied to many problems are called meta-heuristics. An annealing machine is a metaheuristic because it can solve various problems formulated in the Ising model. However, from now on, we will refer to them collectively as heuristics because we will discuss their properties compared to those of conventional computing.
Heuristic to find some high mountain in the big world.
Heuristics, while providing some good solutions, do not always provide the best solution. We have learned the theory of finding the only one correct solution in school mathematics. Therefore, some may be reluctant to accept the concept of a heuristic. Imagine that a series of candidate solutions form a mountain range. The correct solution, of which there should be only one, is called the "exact solution," and the exact solution is the highest mountain peak. School mathematics is an effort to reach the highest peak. The only way to find the highest peak is to climb the mountains to see if it is there, but the heuristic allows us to find a reasonably high peak at high speed by looking at a wide world of mountains from a bird's eye view. In the optimization problem, heuristics can be applied to situations where it takes time to identify the shortest path, but a significant advantage can be gained if the path can be significantly shortened in a very short time.
Various heuristics
Simulated Annealing Method
As the name suggests, simulated annealing (SA) is the basis of CMOS annealing machines, and was proposed by Kirkpatrick in 1983 as a method that applies the findings of thermodynamics in the natural world. Atoms of naturally occurring materials are randomly scattered with high energy at high temperatures, but as the temperature is gradually lowered, the particles become less energetic and reach a state where they are aligned. This natural phenomenon ”Annealing” is applied to the processing of metal products such as swords and castings, and by gradually cooling them from a high temperature state, it is possible to achieve a high-purity, high-quality finish..In simulated annealing, temperature is a parameter that contributes to the search.
Ant Colony Method
This optimization method, proposed by Marco Dorigo in 1992, refers to a natural phenomenon that allows ants to search for the shortest path from the nest to the feeding area. When ants find food, they disperse a signaling pheromone. This pheromone is used as a cue for other ants to reach the food site, and they further disperse signaling pheromones, gradually creating the shortest path to the food site indicated by the high concentration of the signaling pheromone. Modeling this phenomenon and applying it to the traveling salesman problem (TSP) has been the subject of much research.
Genetic Algorithm
A genetic algorithm is an algorithm that mimics the evolutionary process consisting of selection, crossover, and the mutation of organisms; it was proposed by J. H. Holland in 1975. The algorithm is applied to a population to obtain a good sample, which is the solution. It has been applied in various ways, including the knapsack problem and TSP.
The application of these natural processes to information processing is called natural computing. There are overlapping categories of natural computing and heuristics, and all three of the above are in that category.
How a dedicated heuristic calculator came into being
Simulated annealing and genetic algorithms have a long history of research and are widely used in logistics, finance, manufacturing, and more.
An annealing machine is a dedicated combinatorial optimization hardware based on simulated annealing. So, why is it that the heuristic of simulated annealing, which is already in use, is now being implemented again with an annealing machine? One of the factors behind this is that the importance of simulated annealing has increased, while the scale of the problem has grown so large that the performance requirements cannot be met by using heuristics. Therefore, annealing machines, which can be accelerated using hardware and dedicated algorithms, have suddenly begun to attract attention. Another background is that dedicated hardware actually started to emerge. In their 1998 paper "Quantum annealing in the transverse Ising model" (PHYSICAL REVIEW), Kadowaki and Nishimori proposed quantum annealing in which the ground state of the Ising model is derived from the binary spin of a qubit, and that theory was adapted. D-Wave announced a quantum annealing machine, a CMOS annealing machine that applied the theory to semiconductor spins, and other research institutes also announced one after another dedicated hardware. The new theory of annealing processing by replacing the problem with the Ising model made it possible to realize the theory as hardware. Although there is some difficulty in the preprocessing of replacing the problem with a binary variable in Ising model annealing, once the transformation is complete, dedicated hardware can be used for high-speed processing.
In addition, the research and development of annealing-specific hardware through ground state search of the Ising model has progressed, which in turn has led to research and development of algorithms to convert those algorithms into algorithms, which has progressed to the stage of applying those algorithms to practical use. The development of Neumann-type computers stimulated research on algorithms, and as simulated annealing matured, dedicated annealing hardware was researched, and new algorithms were created inspired by the research and development of dedicated annealing hardware.... Looking back, it can be said that hardware and algorithms have evolved by interacting with each other, and this interaction will continue to drive technological progress in the future.
Annealing machines coexist with conventional technologies and can be selected or combined according to requirements.
So far, we have explained that domain-specific annealing hardware is a technology based on simulated annealing. We also explained that it is a technology that has a different purpose and performs different processing than algorithms and software that search exact solutions. Von-Neumann type computers, which are now widely used in the world, are called general-purpose computers. The annealing machines are application-specific and cannot replace Von-Neumann type computers. The type of hardware and algorithms that should be applied to solve practical problems depends on the purpose and conditions.
- Is an exact solution necessary, or is a reasonably good solution sufficient?
- What is the target scale of the parameters to be processed and the target processing time?
Summary
- Heuristics are methods for finding or improving solutions to problems through experience and discovery. Heuristics and natural computing have overlapping categories, and annealing machines belong to both natural computing and heuristics.
- Heuristics are not a way to find exact solutions, but to find good solutions out there. In terms of the path finding problem, it cannot find the shortest path, but it can efficiently find a good path that approaches the shortest path, and the social value from this can be expected.
- Although heuristic algorithms are widely used in practical applications, the increasing demand for solving problems of even larger scale and the publication of the theory of quantum annealing using the Ising model have accelerated the development of annealing machines, which are dedicated hardware. Research and development of algorithms and hardware continue to develop in interaction with each other.
References
Meta-heuristics and Natural Computing (co-authored by Masashi Furukawa et al.), Corona Publishing Co.
