Regensburg 1998 – scientific programme
Parts | Days | Selection | Search | Downloads | Help
DY: Dynamik und Statistische Physik
DY 16: Neuronale Netze
DY 16.4: Talk
Monday, March 23, 1998, 12:45–13:00, H3
’Bouncing’ towards the optimum – Improving the results of Monte Carlo optimization algorithms — •Johannes Schneider1, Ingo Morgenstern1, and Johannes Maria Singer2 — 1Fakultät Physik, Universität Regensburg, Universitätsstr. 31, D-93053 Regensburg — 2Physikinstitut, Universität Zürich, Winterthurerstr. 190, CH-8057 Zürich
Although there are formal proves that Simulated Annealing and related Monte Carlo-type optimization algorithms converge under certain conditions asymptotically (i.e. – possibly – for infinitely long simulation times) to a global optimum, practical implementations naturally allow only for finite simulation times and thus suffer regularly from the fact that the annealing process gets trapped in higher energetic, suboptimal configurations. We present a new algorithm - we call it ’bouncing’ - which takes the final low-energetic configuration of e.g. a conventional monotonically cooled annealing run as an input and subjects it to a schedule of repeatedly reheating/cooling. The maximum of a susceptibility and of a specific heat sampled during an initial monotonic cooling process serve as lower and upper starting temperature bounds for this secondary heating/cooling. We present in addition to a serial implementation a recipe for a parallel machine, and provide a number of results showing the success of the bouncing method at a prominent instance of combinatorial optimization problems, the traveling salesman problem [1].
[1] J. Schneider, I. Morgenstern, J. M. Singer, submitted to Phys Rev E