DPG Phi
Verhandlungen
Verhandlungen
DPG

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 Singer21Fakultä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

100% | Mobile Layout | Deutsche Version | Contact/Imprint/Privacy
DPG-Physik > DPG-Verhandlungen > 1998 > Regensburg