6. Weiche Constraints

[ Constraint Logic Programming Seminar ] ... [ Thema Stundenplangenerierung mit CLP ] ... [ 7. Lösungsbewertung ]

Übersicht

6.1. Allgemein

Da erstrebenswerte Nebenbedingungen sich teilweise gegenseitig ausschliessen, es also keine Garantie für eine Lösung gibt, die alle erstrebenswerten Nebenbedingungen erfüllt, dürfen die erstrebenswerten Nebenbedingungen nicht in Form von harten Constraints implementiert werden. Die Verwendung von harten Constraints führt immer dazu, das entweder eine Lösung alle harten Constraints erfüllt, oder das es keine Lösung gibt.

6.2. Hinterlegung der Informationen in der Wissensbasis

Für die Verarbeitung von weichen Constraints ist es notwendig, Informationen zu speichern, da sie, im Gegensatz zu harten Constraints, für jede Probleminstanz unterschiedliche Anforderungen stellen. Diese Informationen können in Form von Prologfakten in der Wissesnbasis hinterlegt werden. Als Beispiel sei hier das weiche Constraint Veranstaltungsbelegung aufgeführt, dass den Wunsch eines Teilnehmers repräsentiert, das seine Veranstaltung an einem bestimmten Tag zu einer bestimmten Zeit stattfindet.
veranstaltungamum(VeranstaltungsID, gewünschter Tag, gewünschte Zeit, Priorität)

Beispiel:
veranstaltungamum(analysis1_1, 2, 3, 10).

Dieses Beispiel repräsentiert den Wunsch, das der erste Block der Vorlesung Analysis1 am Dienstag von 11:00-12:15 stattfindet und das dieser Wunsch eine Priorität von 10 hat. Die Hinterlegung von Informationen von anderen weichen Constraints läft nach dem gleichen Schema ab. Wenn ein weiches Constraint mehrere Veranstaltungen gleichzeitig betrifft (z.B.: der Wunsch, dass zwei oder mehr Veranstaltungen direkt hintereinander stattfinden), dann kann die Menge der betroffenen Veranstaltungen als Liste repräsentiert werden.
Beispiel:
hintereinander([analysis1_1, analysis1_ueb1], 10).

6.3. Verarbeitung weicher Constraints

6.3.1. Allgemein

Für die Verarbeitung der weichen Constraints werden hier zwei unterschiedliche Ansätze vorgestellt. Der Branch-and-Bound-Ansatz wird ausschliesslich beim oder nach der labeling-Phase angewendet, während der PCSP-Ansatz schon in der Constrain-Phase eine Rolle spielt.

6.3.2. Branch and Bound

Das Branch-and-Bound-Konzept sieht vor, dass bei der Generierung einer Lösung für ein Problem, das Nebenbedingungen beeinhaltet, Kosten für jede Nebenbedingung, die nicht eingehalten wird, entstehen. Wenn eine erste Lösung gefunden worden ist, dann wird eine weitere Lösung durch Modifikation der ersten Lösung generiert, die weniger Kosten verursachen muss als die Erste. So wird auf Grundlage einer alten Lösung jeweils eine neue bessere generiert, solange bis keine kostengünstigere Lösung mehr gefunden werden kann. Im Zusammenhang mit dem Stundenplanproblem werden für jede Problemvariable in der labeling-Phase mit findall alle weichen Constraints, die diese Veranstaltung betreffen, aus der Wissensbasis gesucht und die dort angegebenen Vorgaben mit den gerade für Raum Tag und Zeit gesetzten Werte verglichen. Stimmen die tatsächlichen Werte nicht mit den Vorgaben der weichen Constraints überein, so entstehen Kosten in Abhängigkeit der Priorität der Constraints. Die Kosten, die durch eine Auswahl einer Wertekombination für die Domain-Variablen Raum, Tag und Zeit entstehen, werden mit Hilfe des in der FiniteDomain Library vorgegebenen Constraints minimize minimiert. Dadurch wird eine Werteauswahl erzwungen, die der optimalen Erfüllung der Constraints für diese Veranstaltung am nächsten kommt.
Es werden also mit indomain solange Wertebelegungen durchgeführt (wobei natürlich die auch die bereits beschriebenen Heuristiken verwendet werden können ), bis die Kosten, welche über die Wertebelegung und die mit der Problemvariablen verbundenen Constraints berechnet werden, minimal sind. (vgl. [1])

Beispiel:
Auszug aus der Wissensbasis
...
veranstaltungamum(analysis1_1, 2, 3, 10).
veranstaltungamum(bwl_1, 1, 1, 5).
...
Auszug aus dem Programm
labeling([]).
labeling([PVar|PVRest]) :-
  minimize(wertebelegung(PVar, Kosten), Kosten),
  labeling(PVRest).

wertbelegung(PVar, Kosten) :-
  PVar = raumTagZeit(Raum, Tag, Zeit, VeranstaltungsID),
  % veranstaltung am um
  findall(bevTermin(BTag, BZeit, Prio), veranstaltungamum(VerID, BTag, BZeit, Prio),
    BTerminListe),
  verarbeite_veramum(Tag, Zeit, BTerminListe, Kosten). 
  
verarbeite_veramum(_, _, [], 0).
verarbeite_veramum(Tag, Zeit, [BevTermin|BTRest], Kosten) :-
  BevTermin = bevTermin(BTag, BZeit, Prio),
  (BTag =/= Tag; BZeit =/= Zeit),
  Kosten0 is Prio,
  verarbeite_veramum(Tag, Zeit, BTRest, KostenNew),
  Kosten is Kosten0 + KostenNew.
verarbeite_veramum(Tag, Zeit, [BevTermin|BTRest], Kosten) :-
  verarbeite_veramum(Tag, Zeit, BTRest, Kosten).

6.3.3. PCSP Konzept

Während beim Branch-and-Bound Konzept zunächst eine, in Bezug auf die Erfüllung von Constraints, suboptimale Wertebelegung der Domainvariablen durchgeführt wird, und auf dieser aufbauend nach optimaleren Wertebelegungen im Suchraum gesucht wird, stellt [5] einen anderen Ansatz vor. Mit diesem Ansatz, kann durch eine die Constraints berücksichtigende Heuristik, die Werteauswahl der Domainvariablen in Richtung einer möglichst optimalen Belegung gesteuert werden. Dazu werden für die Wertebereiche der DomainVariablen aller Problemvariablen je eine Liste geführt, welche in Bezug auf die Erfüllung von weichen Constraints qualitative Bewertungen (in numerischer Form) der Werte des Wertebereichs enthalten. Diese Bewertungswerte werden nach der Anwendung der harten Constraints, also dann, wenn die Wertebereiche bereits eingeschränkt worden sind, generiert. Diese Bewertungswerte haben am Anfang der Berechnung (nach der Anwendung harter und vor der Anwendung weicher Constraints) den neutralen Wert 0.
Bsp.:
[..., raumTagZeit(1..6, 1..5, 1..8, analysis1_1), ...]
[..., bewertung([0,0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0,0,0,0], analysis1_1), ...]
Für die Anwendung der weichen Constraints werden die Informationen über diese aus der Wissensbasis gelesen. Wenn das weiche Constraint darin besteht, das ein gewisser Wert bevorzugt werden soll, dann wird der zu dem zu bevorzugendem Wert gehörende Bewertungswert um die Priorität erhöht. Z.B.: Veranstaltung analysis1_1 sollte wenn möglich Montags stattfinden. Diese Bedingung hat eine Priorität von 5
[..., raumTagZeit(1..6, 1..5, 1..8, analysis1_1), ...]
[..., bewertung([0,0,0,0,0,0], [5,0,0,0,0], [0,0,0,0,0,0,0,0], analysis1_1), ...]
Wenn das weiche Constraint darin besteht, das eingewisse Werte ausgeschlossen werden sollen, dann wird von dem zu bevorzugendem Wert gehörende Bewertungswert die Priorität des weichen Constraints abgezogen. Z.B.: Veranstaltung analysis1_1 sollte wenn möglich nicht Freitags stattfinden. Diese Bedingung hat eine Priorität von 2 in einer Prioritätenhierachie von 1 bis 10
[..., raumTagZeit(1..6, 1..5, 1..8, analysis1_1), ...]
[..., bewertung([0,0,0,0,0,0], [5,0,0,0,-2], [0,0,0,0,0,0,0,0], analysis1_1), ...]
Nun kann, wie schon unter 5.3. beschrieben, die Werteauswahl gesteuert werden, indem die Wertebereiche der Domainvariablen anhand der umgekehrten numerischen Ordnung dieser Bewertungswerte sortiert werden. Der Vorteil an diesem Ansatz ist, dass bei der Werteauswahl im labeling nicht mehrere suboptimale Wertekombinationen ausprobiert werden müssen, sondern, das die erste Werteauswahl die weichen Constraints bestmöglich berücksichtigt. Der Nachteil an diesem Ansatz ist, das nur lokale und nicht globale weiche Constraints mit diesem Ansatz berücksichtigt werden können, da die Zusammenhänge zwischen meheren Problemvariablen, die globale Constraints ausdrücken nicht auf lokale Bewertungen einzelner Werte abgebildet werden können. Ein Beispiel für so ein weiches globales Constraint ist das Constraint, das ausdrückt, dass eine Menge von Veranstaltungen hintereinander stattfinden sollen. Die beste Strategie wäre daher eine Kombination des PCSP Ansatz mit dem Branch-and-Bound Ansatz, um eine bereits die lokalen weichen Constraints optimal berücksichtigende Werteauswahl dann im Branch-and-Bound unter der Berücksichtigung der globalen weichen Constraints zu optimieren.
[ Constraint Logic Programming Seminar ] ... [ Thema Stundenplangenerierung mit CLP ] ... [ 7. Lösungsbewertung ]