TU Wien:Heuristic Optimization Techniques VU (Raidl)

Daten

Zuordnungen

Masterstudium Data Science	Modul BDHPC/EX - Big Data and High Performance Computing - Extension
Masterstudium Logic and Computation	Modul Algorithmics and Complexity (Gebundenes Wahlfach)
Masterstudium Visual Computing	Modul Methods of Visual Computing (Gebundenes Wahlfach)
Masterstudium Software Engineering & Internet Computing	Modul Algorithmik
Masterstudium Technische Informatik	Modul Algorithms and Programming (Gebundenes Wahlfach)

Inhalt

[... In dieser Vorlesung mit Übung beschäftigen wir uns mit heuristischen Methoden zur näherungsweisen Lösung von Optimierungsaufgaben. Die behandelten Verfahren sind vor allem für in der Praxis auftretende Probleme geeignet, deren Komplexität so groß ist, dass herkömmliche exakte Lösungsmethoden wegen des zu hohen Rechenaufwands nicht sinnvoll einsetzbar sind.

Anwendungsgebiete sind:

• kombinatorische oder logistische Aufgabenstellungen wie beispielsweise Scheduling, Studenplanerstellung, Verschnittoptimierung, Netzwerkdesign, Routenplanung
• Parameteroptimierung nichtlinearer, numerischer Funktionen
• Optimierung nichtlinearer Strukturen (z.B. neuronale Netze, Regeln in Klassifizierungssystemen, elektronische Schaltkreise)
• Optimierung sich zeitlich ändernder oder verrauschter Probleme

Unter anderem werden folgende Verfahren behandelt:

• Konstruktive Heuristiken
• Lokale Suche
• Simulated Annealing
• Tabu-Suche
• Guided Local Search
• Variable Neighborhood Search
• Very Large Neighborhood Search
• GRASP
• Genetische Algorithmen
• Evolutionsstrategien
• Ant Colony Optimization
• Genetic Programming
• Hybride Ansätze

Neben einigen theoretischen Grundlagen werden vor allem praktische Anwendungen und die Verbindung von Metaheuristiken mit problemspezifischen Heuristiken vermittelt. ...](Quelle: http://www.ads.tuwien.ac.at/teaching/LVA/186112.html#Inhalte)

Ablauf

Der Stoff wird in wöchentliche Vortragen von Klocker (1. Teil) und Frohner (2. Teil) durchgegangen, zusätzlich werden zwischen mal die Programmieraufgaben vorgestellt. Zu beiden Aufgaben gibt es Abgabegespräche, wobei beim 2. im Anschluss noch Theorie fragen gestellt werden (mündliche Prüfung).

Vortrag

Die Vorträge sind alle ganz gut gehalten, nur mit den Folien/Skriptum sollte der Stoff aber auch zum Erlernen sein.

WS 2021: The lectures were relatively dry, although the blame lies mostly with the material rather than the lecturers. The presenters seemed genuinely excited about the matter and tried their best to keep it interesting. Personally I switched to learning purely via the slides a few lectures in and had good success with that strategy.

Übungen

Es sind 2 Programmieraufgaben in Gruppen (2 Personen) während des Semesters zu lösen. Die Programmieraufgaben sind als "Wettbewerb" organisiert und müssen beim Abgabegespräch erklärt werden können. Die Aufgaben sind an sich recht witzig und bringen einen Teil des Stoffes angenehm näher. Die Problemstellung ist bei beiden Aufgaben dieselbe. Es müssen dafür je unterschiedliche heuristische Methoden angewandt werden. Es gab immer eine Auswahl welche Methoden man implementieren möchte. Die Wahl der Programmiersprache ist vollkommen frei. Man muss den Code auch nicht abgeben/vorzeigen. Es muss nur für jede Testinstanz die beste Lösung pro Methode abgegeben und eine Ausarbeitung je Aufgabe erstellt werden die dann auch Grundlage für die Abgabegespräche ist.

Prüfung, Benotung

[... Um die Lehrveranstaltung positiv abzuschließen ist die Ausarbeitung und Abgabe von zwei Programmieraufgaben Voraussetzung. Die Abgabe des zweiten Beispiels erfolgt im Rahmen einer abschließenden mündlichen Prüfung zum gesamten Stoff ...]

siehe Ablauf

Wenn man beide Aufgaben löst und den Stoff halbwegs überblickt, sollte die LVA kein Thema sein. Vor dem zweiten Gespräch die Folien einmal durchgehen und verstehen, dann sollte es kein Problem sein. Es wurde nicht sehr ins Detail gefragt.

W2019/20: Prüfung war zusammen mit dem Interview über Übungsblatt und Programmieraufgabe. Für die Prüfung hat es gereicht zu wissen, wie die Algorithmen funktionieren und was ihr Sinn ist (z.B.: SA um aus lokalen optima herauszukommen,...). Es wurden auch Fragen aus dem ersten Foliensatz gestellt (z.B: was ist ein kombinatorischen Optimierungsproblem, was ist Pareto Dominanz.).

WS 2021: The exercise sheets should not be underestimated in terms of work required. Since there is no written exam, the interview sessions serve the double purpose of acting as oral tests. The questioning can be very specific (i.e. "Recall the example X given during the lecture, how did we solve Y?") and require fairly detailed preperation if you intend to score highly. The programming exercises were not too bad in terms of time requirement. Overall, the effort to get a good grade rivals lectures that give 6 ECTS, but if you're just aiming to pass with an average or worse grade it is probably one of the less effortful technical lectures.

Zeitaufwand

niedrig bis hoch

niedrig: jedes Beispiel zu 2t über 2 Wochen nebenher betreiben und 1-2 Tage Folien lernen
mittel: die Beispiel nicht nur auf "es geht i.wie" lösen, in die Vorlesung schauen und die Folien gewissenhaft durchgehen
hoch: in den Beispielen die weltweite Referenzloesung übertreffen und weiterfüherende Papers zum Stoff lesen

Unterlagen

siehe LVA-HP

Tipps

• Für die Beispiele ein sauberes Design überlegen nachdem die Heuristiken, die verwendet werden sollen, verstanden wurden
• Es ist recht viel Zeit zw. Bereitstellen der Angabe und den Deadlines -> lässt sich gut einteilen
• Motivierte/n Kollege/in für die Aufgaben suchen, alleine ist es doch etwas anstrengender
• Angaben der Programmieraufgaben genau lesen
• Mit anderen Gruppen reden. Da man oft in die gleichen Probleme läuft.
• Bei der ersten Aufgabe ein gutes Framework für die Aufgabe erstellen. Das kann man dann für die Zweite Aufgabe übernehmen.

Highlights / Lob

noch offen

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Diese Seite hat noch keine Anhänge, du kannst aber neue hinzufügen.