Regensburg 1998 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Dynamik und Statistische Physik
DY 26: Allgemeine Statistische Physik II
DY 26.5: Vortrag
Dienstag, 24. März 1998, 15:30–15:45, H3
Iteratives Überschreiben von Lösungsteilen – ein Werkzeug für GLS Optimierungsverfahren — •A. Möbius1, B. Freisleben2, P. Merz2 und M. Schreiber3 — 1Institut für Festkörper- und Werkstoffforschung, 01171 Dresden — 2Fachbereich Elektrotechnik und Informatik, Universität-Gesamthochschule Siegen, 57068 Siegen — 3Institut für Physik, Technische Universität Chemnitz, 09107 Chemnitz
Genetische Algorithmen der kombinatorischen Optimierung, bei denen die betrachteten Spezies lokale Minima der Zielgröße sind, haben sich in den vergangenen Jahren als sehr effektiv erwiesen [1]. Ein wichtiger Teil dieser ‘genetic local search’ Verfahren (GLS) ist die Kreuzung zweier Spezies. Wir stellen hierzu eine Methode vor, die auf dem iterativen Überschreiben von Lösungsteilen wachsender Größe beruht. Ihre Effizienz wird am Problem des Handlungsreisenden demonstriert. Die Einbeziehung eines entsprechenden Schrittes in die Optimierung mittels thermischer Zyklen [2], welche auch als ein nur auf Mutationen beruhender GLS Algorithmus verstanden werden kann, führt zu einer beträchtlichen Beschleunigung dieses Verfahrens. So kann die exakte Lösung des Padberg-Rinaldi 532-Städte-Problems innerhalb 4 CPU Minuten auf einer HP K460 mit etwa 90 % Wahrscheinlichkeit reproduziert werden.
[1] P. Merz and B. Freisleben, in Proc. 1997 IEEE Int. Conf. on Evolutionary Computing, Indianapolis, (IEEE Press,1997), S. 159.
[2] A. Möbius, A. Neklioudov, A. Díaz-Sánchez, K.H. Hoffmann, A. Fachat, and M. Schreiber, Phys. Rev. Lett. 79, 4297 (1997).