Logo der Fakultät Logo

Kurs 00857

Illustration

Optimierung mit Intelligenten Strategien

Autoren/innen: Prof. Dr. Wilhelm Rödder; Dr. Friedhelm Kulmann; Dr. Heinz Peter Reidmacher
Workload: 100 h
SWS: 2 , WS/SS

Prüfung: Klausur

Betreuung:

Beratung:

Kurszuordnung

Modul 31801: Problemlösen in graphischen Strukturen [WIWI]

Kurzbeschreibung

Viele praktische Aufgabenstellungen lassen sich als kombinatorische Optimierungsprobleme formulieren, für die keine effizienten Algorithmen existieren. In diesem Kurs werden zunächst die exakten Methoden Branch&Bound und der A*-Algorithmus gegenübergestellt; außerdem wird auf einige klassische Heuristiken eingegangen. Im weiteren Teil werden die neueren Entwicklungen Simulated Annealing, Tabu-Search und die Genetischen Algorithmen behandelt.
Das Video Problemlösungsstrategien multimedial erlernen [Nr. 76879; Prod.Nr. 98/07, Dauer 28 min], das vom jetzigen ZMI nach der gleichnamigen Fernsehsendung erstellt wurde, liefert weitere Informationen zu diesem Thema.

Sinnvoll ist eine vorherige Bearbeitung der Kurseinheit 1 des Kurses 00852 Optimierung in Graphen.

Inhaltsübersicht

1. Komplexität
1.1 Allgemeine Komplexitätsbetrachtungen
1.2 Die Komplexität spezieller Algorithmen
1.2.1 Test auf Nullelemente
1.2.2 Dublettensuche

2. Exakte Methoden
2.1 Das Branch & Bound-Verfahren
2.2 Das A*-Verfahren als Bestensuchverfahren
2.3 Vergleich von A*- und Branch & Bound-Verfahren
2.4 Beispiel zu Suchstrategien
2.4.1 Das Labyrinth - Problemstellung
2.4.2 Breiten- und Tiefensuche im Labyrinth
2.4.3 Das A*-Verfahren zur Lösung des Labyrinth-Problems

3. Klassische Heuristiken
3.1 Klassifizierung
3.2 Eröffnungsverfahren
3.3 Verbesserungsverfahren
3.4 Kritische Beurteilung klassischer Heuristiken
3.5 Praxisbeispiel Bandbreitennutzung

4. Simulated Annealing
4.1 Physikalischer Hintergrund und Idee des Simulated Annealing
4.2 Algorithmische Realisierung
4.3 Beispiele zum Simulated Annealing
4.3.1 Das Färbungsproblem
4.3.2 Ein Praxisbeispiel: Chipdesign
4.4 Übungen zur Anwendung von Simulated Annealing

5. Tabu Search
5.1 Die Grundidee des Tabu-Search
5.2 Vermeidung von Zyklen
5.2.1 Die Idee der Tabu-Liste
5.2.2 Die Rolle von Attributen
5.2.3 Aufhebung des Tabu-Status
5.3 Berechnung des TSP-Beispiels
5.4 Ein Praxisbeispiel: Digitaler Hörfunk
5.5 Übungen zur Anwendung von Tabu Search

6. Genetische Algorithmen
6.1 Einführung in die Genetischen Algorithmen
6.1.1 Die Evolutionstheorie
6.1.2 Merkmale des Genetischen Algorithmus
6.1.3 Entwicklung der Genetischen Algorithmen durch John Holland
6.2 Basiswissen zum Genetischen Algorithmus
6.2.1 Der Genetische Algorithmus im Überblick
6.2.2 Individuen und Generationen
6.2.3 Fitness und Selektion
6.2.4 Crossover
6.2.5 Mutation
6.3 Beispiele zum Genetischen Algorithmus
6.3.1 Master Mind
6.3.2 Bandabgleich
6.4 Genetische Algorithmen in der Praxis
6.4.1 Forschung und Anwendung
6.4.2 Karriereplanung
6.5 Übungen zu Genetischen Algorithmen

Literatur

Das Literaturverzeichnis zum Kurs 00852 »Optimierung in Graphen« steht im sogenannten virtuellen Semesterapparat online zur Verfügung. Von dort haben Sie die Möglichkeit, direkt im Katalog der UB, Aleph nachzuschlagen, ob ein gewünschtes Buch verfügbar ist.
Darüber hinaus gibt es noch weitere Recherchemöglichkeiten.

01.10.2015
FernUni-Logo FernUniversität in Hagen, Lehrstuhl für BWL, insb. Quantitative Methoden und Wirtschaftsmathematik, 58084 Hagen