TU Wien:Heuristic Optimization Techniques VU (Raidl)

From VoWi
Jump to navigation Jump to search

Daten[edit]

Lecturers Günther Raidl, Nikolaus Frohner, Benedikt Klocker
ECTS 3
Department Forschungsbereich Algorithms and Complexity
Links tiss:186112
Zuordnungen
Master Embedded Systems Wahlmodul Algorithmik
Master Data Science Wahlmodul BDHPC/EX - Big Data and High Performance Computing - Extension
Master Logic and Computation Wahlmodul Algorithms and Complexity
Master Visual Computing Wahlmodul Methoden für Visual Computing
Master Software Engineering & Internet Computing Wahlmodul Algorithmik
Master Technische Informatik Wahlmodul Algorithms and Programming

Mattermost: Channel "heuristic-optimization-techniques" Team invite & account creation link Mattermost-Infos

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.

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

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.