Lösungsansätze
Next: Direkte Heuristiken Up: Theorie und Praxis der Previous: Zusammenfassung
Lösungsansätze
Wie bei den meisten Optimierungsproblemen mit Nebenbedingungen gibt es auch bei der automatischen Stundenplanerstellung die Möglichkeit, die einzelnen Bedingungen nahezu beliebig auf Zielfunktion und Nebenbedingungen zu verteilen. Hierbei schränkt eine Betonung der Nebenbedingungen den Suchraum stark ein und verkompliziert die Operationen, die nötig sind, um von einer Lösung zur anderen zu wechseln, während deren Einbeziehung in die Zielfunktion durch Barrier- und Penalty-Funktionen den Suchraum einfacher gestaltet und auch dann eine annähernd gute Lösung liefert, wenn das Suchproblem nur schwer lösbar ist. Im Gegenzug aber kann die Zahl der möglichen Varianten nochmals wesentlich ansteigen.
Letzteres Vorgehen bietet sich bei
-leichten Problemen natürlich an, da das Überprüfen der Qualität der Lösung
entsprechend in 
liegt.
Der fortlaufenden Beschleunigung der Rechner folgend zeigt sich daher in jüngerer Zeit die Tendenz, zu größeren Suchräumen und
allgemeinen Suchverfahren überzugehen. Die nachfolgende Aufzählung ist mit Ausnahme des letzten Punktes primär chronologisch
aufgebaut, was jedoch immanent auch einer Ordnung nach der zunehmenden Größe des Suchraumes entspricht. Im Rahmen der gängigen Terminologie ([CK93]) werden dabei jene Nebenbedingungen, die während des Optimierunsprozesses nicht verletzt werden, als
Invarianten bezeichnet. CATONI [Cat98] gibt eine Variante an, wie verschiedene Metaheuristiken im klassischen Suchraum operieren können.
- Direkte Heuristiken
- Wissensbasierte Verfahren / Expertensysteme
- Graphentheoriebasierte Verfahren
- Lineare Programmierung / Ganzzahlige Lineare Programmierung / Semidefinite Programme
- Constraintbasierte Verfahren
- Genetische Algorithmen / Evolutionsstrategien
- Lokale Suchverfahren: Simulated Annealing und
Threshold Accepting - Negotiation
- Weitere Ansätze
- Unergiebige Ansätze
- Zusammenfassung
(c) Martin Loehnertz 1999