OR

AG OR/ML - Dr. Jörn Schönberger

ML


Memetische Algorithmen und die Lösung kombinatorischer Optimierungsprobleme mit Nebenbedingungen


Die Identifizierung und Verifizierung einer global dominierenden Lösung für komplexe kombinatorische Optimierungsprobleme erfordert typischerweise einen prohibitiv hohen Rechenaufwand. Suboptimierende Verfahren ('Heuristiken'), sind oftmals in der Lage, Lösungen von ähnlicher Qualität zu identifizieren, jedoch wird auf die Verifizierung der Optimalität verzichtet.

In den letzten zwei Jahrzehnten wurden verschiedene Meta-Konzepte entwickelt, die als 'Grundgerüst' für den Entwurf und die Implementierung leistungsstarker Heuristiken verwendet werden. Effizienz- und Effektivitätszuwächse bei der Lösungssuche können durch die Integration verschiedener Suchstrategien in hybriden Verfahren realisiert werden.

Die Klasse der memetischen Algorithmen umfasst hybride Suchverfahren, die eine globale genetische Suche mit lokal optimierenden Verfahren kombinieren. Die wichtigste Anwendung memetischer Algorithmen sind kombinatorische Optimierungsprobleme mit komplexen Nebenbedingungen. Die in die genetische Suche integrierten lokalen Suchprozeduren ermöglichen einerseits die Reparatur von Restriktionsverletzungen. Andererseits werden sie zur Verbesserung von Lösungsvorschlägen der genetischen Suche verwendet.

In diesem Vortrag wird die beispielhafte Entwicklung und Anwendung eines memetischen Algorithmus zur Lösung eines kombinatorischen Optimierungsproblems aus dem Bereich der Planung nicht-kommerzieller Sportligen beschrieben. In diesem Problem müssen verschiedene Restriktionen eingehalten werden, um einerseits den Spielregeln zu genügen und andererseits die Attraktivität der erzeugten Lösungen sicherzustellen.

Zunächst wird das Anwendungs-Problem beschrieben. Die Konfiguration eines Genetischen Algorithmus folgt. Anschließend wird ein Hill-Climbing-Verfahren zur Reduzierung von Restriktionsverletzungen vorgestellt. Dann erfolgt die Beschreibung der Integration des Hill-Climbers in das Framework des Genetischen Algorithmus. In verschiedenen Experimenten wird die Leistungsfähigkeit des entwickelten memetischen Algorithmus evaluiert.


back - Mathematics - OR - LNM - Theoretical Computer Science - Computer Science - University of Osnabrück.

B.Hammer