Heuristische Algorithmen werden überall dort angewandt, wo Zeit, Geld und Wissen die Entwicklung Problem-spezifischer Algorithmen limitieren. Sie sind sehr einfach anzuwenden, da sie das Problem typischerweise als Black Box ansehen und nur über eine Problem-abhängige Fitness-Funktion darauf zugreifen. Zu den Beispielen zählen von der Natur inspirierte Algorithmen wie Simulated Annealing und Schwarmintelligenz-Algorithmen, sowie Evolutionäre und Genetische Algorithmen. Diese Algorithmen sind inspiriert von den Optimierungsprozessen der Natur und sind anwendbar auf nahezu jedes Optimierungsproblem. In diesem Projektseminar vergleichen wir diese Heuristischen Optimierungsalgorithmem mit klassischen Optimierungsalgorithmen, wie etwa LP- und SAT-Solvers.
Der Kurs wird zweigeteilt sein. Zu Beginn des Kurses führen wir diese verschiedenen Algorithmen und Fallbeispiele ein; dabei analysieren wir einige der Algorithmen formal und experimentell im Rahmen von Übungsaufgaben. Im zweiten Teil, der den Hauptteil des Kurses einnimmt, beschäftigen wir uns im Rahmen eines Projekts mit dem Travelling Thief Problem (TTP). Dieses Problem kombiniert die NP-schweren Probleme vom Handelsreisenden (TSP) sowie das Rucksack-Problem (KP). Um die zwei verflochtenen Problem zu optimieren, sind neue Lösungsstrategien nötig. Die Teilnehmer des Kurses werden in Gruppen verschiedene Ansätze entwickeln und formal sowie experimentell untersuchen. Dabei ist etwa die Untersuchung eines stochastischen TTP denkbar, also eines TTP mit einer gegebenen Verteilung über die Problemeingabe.
