TU Wien:Heuristic Optimization Techniques VU (Raidl)

From VoWi
Jump to navigation Jump to search

Daten[edit]

Lecturers Daniel ObszelkaGünther RaidlJohannes Varga
ECTS 3
Alias Heuristic Optimization Techniques (en)
Department Forschungsbereich Algorithms and Complexity
When winter semester
Last iteration 2021WS
Language English
Mattermost heuristic-optimization-techniquesRegisterMattermost-Infos
Links tiss:186112, Homepage
Zuordnungen
Master Data Science Wahlmodul BDHPC/EX - Big Data and High Performance Computing - Extension
Masterstudium Computational Science and Engineering Wahlmodul Algorithmics
Master Logic and Computation Wahlmodul Algorithmics and Complexity
Master Visual Computing Wahlmodul Methods of Visual Computing
Master Software Engineering & Internet Computing Wahlmodul Algorithmik
Master Technische Informatik Wahlmodul Algorithms and Programming
Master Informatikdidaktik Wahlmodul Algorithmik


Inhalt[edit]

[... 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[edit]

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[edit]

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[edit]

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[edit]

[... 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[edit]

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[edit]

siehe LVA-HP

Tipps[edit]

  • 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.

Verbesserungsvorschläge / Kritik[edit]

noch offen

Attachments

This page has no attachments yet but you can add some.