Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen

Lösungsansätze

next up previous contents
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 tex2html_wrap_inline5146 -leichten Problemen natürlich an, da das Überprüfen der Qualität der Lösung entsprechend in tex2html_wrap_inline5238 liegt.gif 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.

tex2html_wrap5552





(c) Martin Loehnertz 1999