Simulated annealing mimics the metallurgical process of annealing to find good solutions to a problem. The user must specify the starting temperature and cooling rate. The program examines worse solutions to avoid local minimums. Cooling decreases the percentage of worse solutions explored until a pre-set fraction is reached. Simulated annealing reduces the time required to find a near-optimal solution. Other AI search algorithms include genetic algorithms, ant colony optimization, particle swarm optimization, nearest neighbor, and Bayesian classifiers.
Simulated annealing is a computer technique that can find good, though not necessarily optimal, solutions to a problem. It is so named because it mimics the metallurgical process of annealing. In metals, annealing is the process of purifying the metal by heating it and then slowly cooling it. The computer program “purifies” the solution space until all that is left are better or near better solutions.
There are two critical factors that the user of a simulated annealing program must specify: the starting temperature, or the percentage of worst-case solutions that can be explored; and the cooling rate, which is how quickly that percentage is reduced. A low initial temperature often results in a result that is far from optimal. Starting up at a very hot temperature can cause the search to take much longer than necessary. Similarly, too fast a cooldown rate will generate poor results, while a very slow cooldown rate will result in a program that runs for a very long time.
The “high temperature” state for the simulated annealing program is a setting that allows you to examine a wide range of solutions, including many worse than the solutions already found. The computer may examine many solutions worse than the current solution to avoid remaining at a local minimum substantially worse than the best. For example, you can imagine starting from the top of a hill or mountain with the goal of reaching the base. There may be ravines or chasms along the way. If the computer can’t go uphill far enough to get out, it will crash even if it’s not near base.
How far uphill the program can go is determined by the percentage of worst-case solutions the program is allowed to examine. Over time, progressively better solutions are found, and the risk of a deep chasm decreases, so the percentage of worse solutions that the computer can explore decreases. The decrease of this fraction is called “cooling”. When the temperature reaches a pre-set fraction, which need not be 0, the search ends.
The reason for using simulated annealing or other AI research techniques is to reduce the time required to find a near-optimal solution to a manageable amount. For many problems, an exhaustive search — testing every possible solution against every other possible solution — could take months or years. The best known alternative to simulated annealing are genetic algorithms. Other popular AI search algorithms include ant colony optimization, particle swarm optimization, nearest neighbor, and Bayesian classifiers.
Protect your devices with Threat Protection by NordVPN
