Simulated Annealing

[Owen Densmore]

Does anyone have a pointer to using simulated annealing to solve the
traveling salesman problem? .. or a good tutorial on SA?

        -- Owen

Owen Densmore - http://backspaces.net - [hidden email]

[Robert Holmes]

I used SA in a real-life application, optimizing the allocation of staff to
shifts on a power station. An interesting problem, because as well as having
to deal with the getting the right grades of people on any given shift (unit
operator, assistant unit operator, maintenance etc.), you had to get the
right mix of skills (electrician, engineer etc.) and make sure that no
temporal constraints were being broken (you can only work the night shift
three nights in a row, everyone needs to have done the same number of
day-shifts/night-shifts etc over a year). Add into this the need to allocate
overtime fairly and deal with unplanned absences, and things got a little
complex.

The solution: represent this all as one big-ass objective function and let a
simple SA program lose on it. Usually got a good enough solution within 5
minutes or so. I got the SA algorithm from Numerical Recipes.

- rh

> -----Original Message-----
> From: Owen Densmore [mailto:[hidden email]]
> Sent: Monday, October 11, 2004 4:25 PM
> To: The Friday Morning Applied Complexity Friam
> Subject: [FRIAM] Simulated Annealing
>
> Does anyone have a pointer to using simulated annealing to
> solve the traveling salesman problem? .. or a good tutorial on SA?
>
> -- Owen
>
> Owen Densmore - http://backspaces.net - [hidden email]
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org
>
>
>

[Richard Harris-5]

As Robert has mentioned, Numerical Recipes has a nice intro. They also,
fortunately, have online pdf's for free at www.nr.com. The link to the
chapter about SA is at the following.

http://www.library.cornell.edu/nr/bookcpdf/c10-9.pdf 

The original paper is also pretty easy to get through.

Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. 1983, Science, vol. 220, pp.
671-680.

If my memory's correct, in their model, which is basically the model in the
NR chapter, they have two types of Monte-Carlo moves that they use, which
are based on the two-opt and three-opt tour improvement heuristics of Lin
and Kernighan. You could also refer back to that paper for a better
understanding. I think this is the correct reference.

S. Lin & B.W. Kernighan (1973), "An Effective Heuristic Algorithm for the
Travelling-Salesman Problem", Operations Research 21, p498-516

BTW, I did my first Master's thesis on applying an alternate form of physics
to Simulated Annealing. In this alternate form, based on the Microcanonical
Ensemble, you vary the total Energy of your system, rather than the
Temperature, which is the usual practice and is based on the Canonical
ensemble with the Maxwell-Boltzman distribution.

Of course, there's one more paper that might be interesting. ;-)

John R. Ray and Richard W. Harris, "Simulated annealing in the
microcanonical ensemble," Physical Review E 55, 5270 (1997)

Rich


-----Original Message-----
From: Owen Densmore [mailto:[hidden email]]
Sent: Monday, October 11, 2004 4:25 PM
To: The Friday Morning Applied Complexity Friam
Subject: [FRIAM] Simulated Annealing

Does anyone have a pointer to using simulated annealing to solve the
traveling salesman problem? .. or a good tutorial on SA?

        -- Owen

Owen Densmore - http://backspaces.net - [hidden email]


============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9AM @ Jane's Cafe
Lecture schedule, archives, unsubscribe, etc.:
http://www.friam.org