7. Lösungsbewertung
[ Constraint Logic Programming Seminar ]
... [ Thema Stundenplangenerierung mit CLP ]
... [ 8. Literatur ]
Wie schon in 2.2.2.3. beschrieben, hängt die Güte einer Lösung des
Stundenplanproblem von der Menge der erfüllten erstrebenswerten Nebenbedingungen ab.
Die Verwendung des Branch-and-Bound-Konzepts legt nahe, die Qualität der Lösung
durch die Kosten zu beschreiben, die entstehen, wenn erstrebenswerte Nebenbedingungen nicht
erfüllt werden.
Jedoch ist die Verwendung der Kosten als einzelne Kennzahl nicht differenziert genug,
da ein bestimmter Kostenbetrag noch nicht die Berücksichtigung der Prioritätenhierachie
beschreibt. Ein hoher Kostenbetrag kann sowohl bedeuten, dass wenige weiche Constraints mit
hoher Priorität, als auch dass viele weiche Constraints mit geringer Priorität
erfüllt worden sind.
Eine differenziertere Aussage kann dadurch erzeugt werden, indem für jede Prioritätsstufe
innerhalb der Prioritätenhierachie, die Anzahl der erfüllten Constraints dieser
Priorität, der Anzahl der nicht erfüllten Constraints dieser Hierachie gegenübergestellt
wird.
Ausserdem kann es interessant sein, dieselbe Gegenüberstellung auch in Bezug auf die
unterschiedlichen Typen der weichen Constraints zu machen.
Die Ansätze zur Lösungsbewertung in der Literatur arbeiten mit statistischen Analogien.
[6] beschreibt die Qualität einer Lösung als die mittlere quadratische Abweichung
(mean square deviation) zwischen erstelltem und erstrebenswertem Stundenplan.
[7] beschreibt die Qualität mit Hilfe der Entropie in Abhängigkeit der
erfüllten weichen Constraints.
[ Constraint Logic Programming Seminar ]
... [ Thema Stundenplangenerierung mit CLP ]
... [ 8. Literatur ]