- Let's get to know the annealing machine even better!
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 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.
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.
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.
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.
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.
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.
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.
Meta-heuristics and Natural Computing (co-authored by Masashi Furukawa et al.), Corona Publishing Co.
This article is part of the ACW Skills Roadmap. Use the skills roadmap to learn with ACW.
Did you find the article helpful? Please share it with others.
Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.
In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.
This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.
For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".
This article provides an easy-to-understand explanation of the mathematical assumptions you need to understand, focusing on "quadratic" and "discrete," which are some of the characteristics of the problems that annealing machines excel at solving.