|
 |
The Traveling Salesman Problem is typical of a large class of "hard" optimization problems that have intrigued mathematicians and computer scientists for years. Most important, it has applications in science and engineering. For example, in the manufacture of a circuit board, it is important to determine the best order in which a laser will drill thousands of holes. An efficient solution to this problem reduces production costs for the manufacturer. — World-Record Traveling Salesman Problem for 3038 Cities Solved
In 1992 I came upon an article in a physics journal (I don't remember where or by whom it was written) which described the use of the so-called Simulated Annealing Algorithm to solve this problem. The algorithm is so named because it can be seen as a simulation of the physical process of annealing (in which a hot material cools slowly, allowing its constituent atoms to assume arrangements that would not be possible with rapid cooling). I then wrote a program to implement this algorithm.
A good explanation of the simulated annealing algorithm is given by Robert C. Williams:
The impetus behind the SA algorithm is its analogy to the statistical mechanics of annealing solids ... When a physical system is at a high temperature, the atoms in the system are in a highly disordered state, and consequently the associated ensemble energy of the system is also high. Lowering the temperature of the system results in the atoms of the system acquiring a more orderly state, thus reducing the energy of the system.
For example, to grow a crystal, which is highly ordered, the system needs to be heated to a temperature which allows many atomic rearrangements. Then the system must be carefully cooled, ensuring a thermal equilibrium is reached at each temperature stage, until the system is `frozen' into a good crystal. ...
This process of cooling is known as annealing. If the cooling process is performed too quickly, extensive irregularities can be locked into the crystals structure, with the resulting energy level far greater than in a perfect crystal.
The Metropolis algorithm ..., developed to simulate the behaviour of atoms in thermal equilibrium at a particular temperature, begins with an initial configuration with energy E0. Each subsequent iteration involves performing a small random perturbation to the current configuration i (with associated energy Ei), then the energy, Ej, of the resulting configuration j is calculated. If the change in energy E'' = Ej - Ei ≤ 0 the configuration j is accepted with probability 1 and becomes the current configuration of the next iteration. If E'' > 0, then configuration j is accepted with probability exp(- E''/kT), with the aim of obtaining a Boltzman distribution. If configuration j is rejected the current configuration i remains unchanged. After a large number of iterations the accepted configurations approximate a Boltzman distribution at a particular temperature, T.
— The Single Machine Tardiness Scheduling Problem: A Simulated Annealing Approach Coded in Java [link expired]
At present this program exists only in a demonstration version. (A version allowing input of site locations, names, etc., so as to produce useful results would require further work, which, due to lack of demand, is unlikely to happen.)
This demo version, TS3DEMO.EXE (Version 3.10 — 37,919 bytes), can be downloaded from this site for personal, non-commercial, use (it is also contained in TS3DEMO.ZIP — 37,132 bytes).
The program is run from the DOS prompt. If no command line parameters are given then upon startup The Travelling Salesman program displays the following notice:
The Travelling Salesman, Version 3.10
This is the demonstration version (and at present the only version) of
"The Travelling Salesman" program, written by Peter Meyer.
This program uses the Simulated Annealing Algorithm to solve a form of the
travelling salesman problem, which is to find the shortest (or a nearly
shortest) path connecting a set of sites, such as cities or delivery points.
Two input values can be specified on the DOS command line:
Use: "TS3DEMO N:num_sites L:layout"
The number of sites ("num_sites") must be in the range 9 through 240.
There are two types of layout available:
"L:G" produces a rectangular grid. "L:R" produces a random layout.
Default values are N:81 and L:R
For example, to specify 120 locations situated randomly use "TS3DEMO N:120".
To specify 169 locations on an 13x13 grid use "TS3DEMO N:169 L:G".
|
Here are three results obtained using a Pentium II running at 300 MHz. Firstly the initial and final states for 100 sites in a random layout:
Secondly the initial and final states for 225 sites in a random layout:
Thirdly the initial and final states for 100 sites in a grid layout:
Some relevant documents on the web:
| The Travelling Salesman Problem | Simulated Annealing |
| Hermetic Systems Home Page |