Eine Übersicht über die verschiedenen Ansätze gibt ein
Tutorial von Ronald L. Radin, Purdue
University, Indiana.
Im Rahmen des Praktikums sollen Student(inn)en verschiedene Techniken zur
Lösung diskreter Optimierungsprobleme kennenlernen und diese an einem
konkreten Problem umsetzen.
Bei der Auswahl der Probleme werden solche Probleme bevorzugt, die einen
Bezug zur Praxis haben. Ferner sollen die im Praktikum erarbeiteten
Lösungen mit Referenzimplementierungen bzw. Benchmarks verglichen werden,
sofern solche Daten zum behandelten Problem verfügbar sind. Ein
wünschenswertes Fernziel besteht darin, die Leistung solcher
Referenzimplementierungen zu erreichen oder sogar zu überbieten.
Grundsätzlich gliedert sich das Praktikum in zwei Teile:
|
Einarbeitungsphase: Grundlegende Techniken werden erklärt und
einfache Implementierungen davon umgesetzt.
|
|
Problemlösungsphase: Jeder Bearbeiter bzw. jedes Team überlegt sich
einen Ansatz, wobei selbstverständlich eine oder mehrere der zuvor
behandelten Techniken zum Einsatz kommen können, und versucht
davon eine möglichst leistungsstarke Implementierung
vorzunehmen. Hierzu ist ist nötig, den eigenen Ansatz sauber
umzusetzen und so weit wie möglich zu optimieren.
|
In einer speziellen zweistündigen Praktikumsvorlesung werden die bei
der Diskreten Optimierung verwendeten Verfahren erläutert. Hierbei geht es
mehr um das Verständnis der Verfahren als um den theoretischen
Hintergrund. Oftmals sind die Verfahren auch rein heuristischer Natur, so
daß kaum theoretische Aussagen getroffen werden können.
Vorausgesetzt werden neben guten Programmierkenntnissen
Grundkenntnisse über Design und Implementierung von Algorithmen,
wie sie beispielsweise in der
Vorlesungen "Effiziente Algorithmen und Datenstrukturen"
vermittelt werden. Der Besuch dieser
Vorlesungen ist empfehlenswert, aber nicht unbedingt erforderlich.
Mit dem Praktikum werden mehrere Ziele verfolgt:
|
|
Tieferes Verständnis der Methoden zur Diskreten Optimierung,
|
|
Erfahrungen bei der Entwicklung hochoptimierter Software für
rechenintensive Probleme.
|
|
Spaß an der Herausforderung, die bestmögliche Leistung aus dem
verfügbaren Rechensystem "herauszukitzeln".
|
Im Sommersemester 1999 beschäftigen wir uns mit der Optimierung der
Struktur von Rechnernetzen. Im Zusammenhang mit der Neustrukturierung des
B-WiN (Deutsches
Breitband-Wissenschaftsnetz) des DFN-Vereins ist dieses Problem von
aktueller Bedeutung.
Es geht dabei um folgende Fragestellung:
Wie kann ein Rechnernetz strukturiert werden, um ein gegebenes
Verkehrsaufkommen mit minimalen Leitungskosten zu bewältigen?
Im Detail sieht dies wie folgt aus: Es wird vorgegeben, welche Bandbreite
zwischen zwei Knoten im Netz benötigt wird. Das berechnete Netz muß in der
Lage sein, diese Bandbreiten zur Verfügung zu stellen. Dazu werden
Leitungen angemietet, für die je nach Länge und Bandbreite Kosten
anfallen. Das Optimierungsziel besteht darin, diese Kosten zu minimieren.
Dieses Problem wird an der TU München vom Lehrstuhl Prof. Jessen
untersucht. Volker
Fischer, der an diesem Projekt
arbeitet, versorgt uns dankenswerterweise mit Hintergrundinformationen und
wird im Rahmen des Praktikum eine kurze Einführung in die
zugrundeliegende Problematik geben.
Grundsätzlich soll das Praktikum nicht strikt dem klassischen Schema
Aufgabe-Lösung-Korrektur folgen. Besonders im zweiten Teil erhalten die Teilnehmer(innen) viel Freiheit bei der Umsetzung ihres Lösungsansatzes. Es geht eben
nicht darum, bekannte Algorithmen zu implementieren, sondern es
sind Kreativität und Ideen gefragt. Aus diesem Grund
erwarten wir von Interessenten, daß sie ein hohes Maß an Motivation und
Selbständigkeit mitbringen. Es gibt keine Musterlösung und keinen
garantiert erfolgreichen Ansatz, an dem man sich orientieren kann, sondern
die Teilnehmer(innen) sollen eigene Lösungsmöglichkeiten erkunden, wobei
sie selbstverständlich von den Praktikumsbetreuern bestmöglich unterstützt
werden.
Pro Woche findet eine Praktikumssitzung statt, bei der neue Techniken
eingeführt, die zu lösenden Aufgaben vorgestellt und die bisherigen
Ergebnisse und/oder Schwierigkeiten besprochen werden. Bei akuten Problemen
können die Betreuer selbstverständlich auch außerhalb dieser Sitzung
angesprochen werden.
Die Lösungen werden gewöhnlich in C++ unter Verwendung geeigneter
Bibliotheken implementiert. Der Phantasie der
Teilnehmer(innen) sind allerdings auch hier a priori keine Grenze gesetzt. Wenn Sie
ein gutes Argument finden, warum eine andere oder zusätzliche Bibliothek
vorteilhaft wäre, so ist es durchaus möglich, daß sich Ihr Vorschlag
durchsetzt. Wir wollen Probleme statt vorgefertigter Aufgaben lösen.
Die Bearbeitung der Praktikumsaufgaben kann entweder auf unseren
Lehrstuhl-Rechern (S 2237), in der Sunhalle oder auch auf einem
Linux-Rechner zu Hause erfolgen (sofern die nötigen Bibliotheken für Linux
verfügbar sind, was jedoch im Normalfall kein Problem darstellen sollte).
Um den Praktikums-Schein zu erhalten, müssen einfache Lösungen für alle
vorgestellten Ansätze erstellt werden und darüberhinaus eine erkennbare
Anstrengung bei der Erstellung einer optimierten Lösung unternommen werden.
Wir bieten eine interessante und herausfordernde Aufgabe und
erwarten im Gegenzug überdurchschnittliches Engagement. Auf dieser
Grundlage werden auch die Praktikums-Scheine vergeben werden.
WICHTIG: Das Praktikum Diskrete Optimierung zählt nach der alten
Prüfungsordnung als Wahlpflichtpraktikum im Bereich Informatik I
(Praktische Informatik), nach der neuen Prüfungsordnung (gültig ab
November 1996) aber im Bereich Informatik III (Theoretische Informatik).
Student(inn)en, die nach der neuen Prüfungsordnung DHP machen müssen,
können den Schein nicht als Praktikumsschein zu Informatik I verwenden.
Student(inn)en, die zwischen alter und neuer Prüfungsordnung wählen
dürfen, können den Schein wahlweise als Schein zu Informatik I oder
zu Informatik III verwenden. Für Details
hier
clicken!
|
|
Die Darstellung der verschiedenen heuristischen Optimierungsverfahren
orientiert sich an folgendem Buch:
C. R. Reeves (Hrsg.), Modern Heuristic Techniques For
Combinatorial Problems, Blackwell Scientific Publications, 1993.
|
|
|
Der "Vater" der genetischen Algorithmen:
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and
Machine Learning, Addison-Wesley, 1989.
|
Thomas Schickinger
Last modified: Fri Jun 18 11:15:28 METDST 1999
