Zustandsbasierte Modelle

Zentrales Motto: Lokal modellieren, global optimieren

• Model: Lokale Interaktionen
• Inferenz: Suche global optimale Lösung

State / Zustände

Ein Zustand ist eine möglichst kompakte Beschreibung aller vergangenen Aktionen, die ausreicht um in Zukunft optimale Entscheidungen zu treffen.

Zustände bilden einen Graph in dem wir uns bewegen

Wie kann man die 7 Provinzen einfärben (Rot, Blau, Grün), so dass keine benachbarten Provinzen die gleiche Farbe haben?

https://commons.wikimedia.org/wiki/File:Australia_map,_States-simple.svg

Formulierung als Suchproblem

• Zustand: Welche Provinz Provinz hat schon welche Farbe.
• Aktion: Die nächste Provinz erhält eine mögliche Farbe.

Wir haben mehr Struktur als in Suchproblemen

• Reihenfolge nicht relevant
• Manche Entscheidungen sind unabhängig

Nenne ein Land das mit K anfängt und neben einem Land liegt, in dem Slowenisch gesprochen wird.

Factor Graph (Beispiel)

Definition: Factor Graph

• Variablen: $X = (X_1, \ldots, X_n)$, $X_i \in \operatorname{Domain}_i$
• Factors: $f_1, \ldots, f_m$, $f_i(X) \geq 0$

Beispiel: Map coloring

Variablen $X = (\text{WA},\text{NT},\text{SA},\text{Q},\text{NSW},\text{V},\text{T})$ $\operatorname{Domain}_i = \{ {\color{red} \text{R}}, {\color{green} G}, {\color{blue} B} \}$ Factors $f_1(X) = 1[\text{WA} \neq \text{NT}]$ $f_2(X) = 1[\text{WA} \neq Q]$ $\ldots$

• Scope eines Factor $f_i$: Menge aller Variablen, von denen $f_i$ abhängt.
• Arity von $f_i$: Anzahl an Variablen im Scope.
• Ein unary factor hat Arity 1
• Ein binary factor hat Arity 2

Beispiel: Der Scope von $f_1(X) = 1[\text{WA} \neq \text{NT}]$ ist $\{\text{WA}, \text{NT}\}$ (binary factor).

Eine Lösung (Assignment) $x = (x_1, x_2, \ldots, x_n)$ ist eine Zuweisung von Werten $x_i \in \operatorname{Domain}_i$ zu allen Variablen.

Das Gewicht (Weight) einer Lösung ist das Produkt aller Factors: \[ \operatorname{weight}(x) = \prod_{i = 1}^m f_i(x) \]

Unser Ziel ist es, eine Lösung mit maximalem Gewicht zu finden: \[ \operatornamewithlimits{arg\,max}_x \; \operatorname{weight}(x) \]

Das Gewicht ließe sich auch äquivalent als Summe ausdrücken: \[ \log(\operatorname{weight}(x)) = \sum_{i = 1}^m \log(f_i(x)) \]

Assignment:

\[ x = \{ \text{WA}: {\color{red} R}, \text{NT}: {\color{green} G}, \text{SA}: {\color{blue} B}, \text{Q}: {\color{red} R}, \text{NSW}: {\color{green} G}, \text{V}: {\color{red} R}, \text{T}: {\color{blue} B}\} \\[2mm] \operatorname{weight}(x) = 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 = 1 \]

Assignment:

\[ x = \{ \text{WA}: {\color{red} R}, \text{NT}: {\color{red} R}, \text{SA}: {\color{blue} B}, \text{Q}: {\color{red} R}, \text{NSW}: {\color{green} G}, \text{V}: {\color{red} R}, \text{T}: {\color{blue} B}\} \\[2mm] \operatorname{weight}(x) = 0 \cdot 0 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 = 0 \]

Einen Factor $f_i(x) \in \{0,1\}$ nennen wir (harte) Nebenbedingung / (hard) constraint.
Eine Nebenbindung ist erfüllt, wenn $f_i(x)=1$

Ein constraint satisfaction problem (CSP) ist ein factor graph, wo alle factors constraints sind.

Ein CSP ist konsistent / consistent, wenn $\operatorname{weight}(x) = 1$

Teillösung / partial assignment
z.B.: $x = \{ \text{WA}: {\color{red} R}, \text{NT}: {\color{blue} B}\}$

Abhängige Faktoren / dependent factors

$D(x, X_i)$ ist die Menge aller factors, die von $X_i$ und $x$ abhängen, aber von keinen anderen Variablen (oder nur von $x$).

$D(\{ \text{WA}: {\color{red} R}, \text{NT}: {\color{blue} B}\}, \text{SA}) =\\ \{1[\text{WA}\neq\text{SA}], 1[\text{NT} \neq \text{SA}]\}$

Algorithmus: Backtracking Search

Backtrack($x$, $w$, $\text{Domains}$):

• Wenn $x$ vollständig, dann Return $x$
• Wähle eine nicht zugewiesene Variable $X_i$
• Sortiere die Werte aus $\text{Domain}_i$
• Für jeden Wert $v$ in der Reihenfolge:
  • $\delta \gets \prod_{f \in D(x, X_i)} f(x \cup \{X_i : v \})$
  • $\text{Domains}' \gets $ Noch mögliche Werte aus $\text{Domains}$ (Lookahead)
  • Wenn eine $\text{Domains}' = \empty$, dann fahre mit nächstem Wert fort
  • Backtrack($x \cup \{X_i : v \}$, $w\delta$, $\text{Domains}'$)

Lookahead: Forward Checking

Idee: Wenn wir $X_i$ einen Wert zuweisen, dann entfernen wir inkompatible Werte aus den Domains von den Nachbarn von $X_i$

Wird eine Domain leer, können wir abbrechen

Wahl der nächsten Variable

Idee: Wähle die Variable mit der kleinsten Domain

Welchen Wert probieren wir für $X_i$?

Idee: Nehme den Wert, der die Nachbarn von $X_i$ am wenigsten einschränkt.

$2+2+2=6$ verbleibende Werte	$1+1+2=4$ verbleibende Werte

• Am stärksten eingeschränkte Variable / most constrained variable (MCV)
• Am wenigsten eingeschränkter Wert / least constrained value (LCV)

Arc consistency

Wir wollen die Domains noch weiter einschränken

• $X_1 \in \text{Domain}_1 = \{1,2,3,4,5\}$
• $X_2 \in \text{Domain}_2 = \{1,2\}$
• Factor: $1[X_1 + X_2 = 4]$

$\text{Domain}_1 \gets \{2,3\}$

$\operatorname{EnforceArcConsistency}(X_i, X_j)$: Entferne Werte aus $\text{Domain}_i$ die verhindern, dass $X_i$ arc consistent zu $X_j$ ist.

Forward checking: Nachdem wir $X_i$ zuweisen, stellen wir arc concistency von $X_j$ zu $X_i$ für alle Nachbarn $X_j$ her.

AC-3 kann auch nicht alles entdecken

• Backtracking Search
• Most constrained variable (MCV)
• Least constrained value (LCV)
• Forward checking (arc consistency auf Nachbarn)
• AC-3 (globale arc consistency)

Je früher wir eine unmögliche Zuweisung finden, umso besser

Wenn wir factors $f(X) \geq 0$ haben, die nicht nur 0 und 1 ausgeben,
dann suchen wir nicht nur eine zulässige
($\operatorname{weight}(x) > 0$), sondern die optimale Lösung.

Backtracking muss über alle zulässigen Lösungen weiter laufen.

Backtracking Search

Greedy Search

Idee: Kein Backtracking, immer die beste nächste Lösung nehmen.

Greedy Suche

Beam Search

Idee: Greedy, aber behalte Liste mit mehreren (maximal $K$) besten Kandidaten im Blick.

Beam Search (K=3)

Such Strategien

• Backtracking/Beam/Greedy Search: partial assignment vervollständigen
• Local Search: fertiges assignment modifizieren

$x = \{X_1: {\color{blue} B}, X_2: {\color{blue} B}, X_3: {\color{blue} B}\}, \operatorname{weight}(x) = 3$

$x' = \{X_1: {\color{blue} B}, X_2: {\color{blue} B}, {\color{orange} X_3}: {\color{red} R}\}, \operatorname{weight}(x') = 4$

Lokales Optimum

$x = \{X_1: {\color{red} R}, X_2: {\color{red} R}\}, \operatorname{weight}(x) = 1$

Idee: Teste Paare (Tripel, ...) von Variablen auf Verbesserungen.

n-opt local search

Rechenaufwand pro Verbesserung: $O((m l)^n)$
($m$: Anzahl Variablen, $l$: Werte je Domain)

Mehr Struktur vom Problem erlaubt bessere Algorithmen

Boolean Satisfiability (SAT)-Problem

$(X_1 \vee \neg X_2) \wedge (\neg X_1 \vee X_3 \vee X_4) \wedge (X_2 \vee \neg X_4)$

SAT-Problem

• $\text{Domain}_i = \{\text{False}, \text{True}\}$ (bzw. $\{0, 1\}$)
• Jeder factor enthält nur mit logischem "oder" ($\vee$) verbundene Variablen oder negierte Variablen $\neg X_i$.

Conjunctive normal form (CNF)

Beispiel

In meiner Tasche befinden sich

• eine Uhr oder keine Münze
• eine Münze oder keine Büroklammer
• eine Büroklammer oder keine Uhr
• nicht alle 3 Gegenstände zusammen

$(X_1 \vee \neg X_2) \wedge (X_2 \vee \neg X_3) \wedge (X_3 \vee \neg X_1) \wedge (\neg X_1 \vee \neg X_2 \vee \neg X_3)$

Map Coloring als SAT-Problem

• Eine Variable $X_{t,c}$ je Territory $t$ und Farbe $c$.
• Für jedes Territory $t$ ein factor
  $f(X) = X_{t,{\color{red}R}} \vee X_{t,{\color{green}G}} \vee X_{t,{\color{blue}B}}$
• Für zwei benachbarte Territories $t_1$ und $t_2$ und jede Farbe $c$ ein factor:
  $f(X) = \neg X_{t_1, c} \vee \neg X_{t_2, c}$

Conflict-driven clause learning (CDCL)

Idee: Wenn wir einen Konflikt finden, suche generelle Regel, um diesen zu vermeiden.

https://en.wikipedia.org/wiki/Conflict-driven_clause_learning

Jupyter

(Mixed) Integer Programming (MIP)

\[ \begin{align*} \max\quad & c^T x \\ \text{s.t.}\quad & A x \leq b \\ & x \geq 0 \text{ oder } x \in \{0, 1, 2, \ldots\}\\ & \text{ oder } x \in \{0,1\} \end{align*} \]

(Mixed) Integer Programming (MIP)

• $\text{Domain}_i = \mathbb{R}_{\geq 0}$ oder $\mathbb{Z}_{\geq 0}$ oder $\{0, 1\}$
• Factor mit Arity 1 kann Form $f(x_i) = e^{c_i x_i}$ haben
• Sonstige factors der Form $a^T x \leq b$ oder $a^T x \geq b$ oder $a^T x = b$

Map coloring als MIP

• Eine Variable $x_{t,c}$ je Territory $t$ und Farbe $c$.
• Für jedes Territory $t$ eine Nebenbedingung
  $x_{t,{\color{red}R}} + x_{t,{\color{green}G}} + x_{t,{\color{blue}B}} \geq 1$
• Für zwei benachbarte Territories $t_1$ und $t_2$ und jede Farbe $c$ eine Nebenbedingung:
  $x_{t_1, c} + x_{t_2, c} \leq 1$

Linear Programming Relaxation

Idee: Wenn alle Variablen vom Typ $x\geq 0$ wären, wäre das Problem einfach. Nutze das als Heuristik für das eigentlich Problem.

Selbst wenn wir den MIP solver abbrechen, bevor er die optimale Lösung findet, kennen wir den Abstand zwischen der besten Lösung und der Schranke der Relaxierung

Können Qualtitätssiegel der Form: "Die Lösung ist höchstens x%" vom Optimum entfernt" angeben.

Praktische Hinweise

• Vor allem MIPs sind sehr mächtig um NP schwere Probleme zu lösen.
• Modellierung kann großen Unterschied machen
  • Präferiere binäre Variablen und Nebenbedingungen vom Typ $\sum x_i \leq 1$
• Sehr gute kommerzielle Solver sind auch sehr teuer.

Jupyter

Spezielle CSP Klassen

• SAT
• MIP

Lösungstechniken

• Conflict-driven clause learning
• Linear Programming Relaxation

Metaheuristiken

In manchen Fällen sind exakte Methoden keine Option

• Problem lässt sich nicht (gut) als SAT oder MIP formulieren
• Problem ist zu groß für exakten Solver
• Zeit Constraints sind zu knapp
• Kosten für Solver sind ökonomisch

Metaheuristiken sind heuristische Ansätze, die auf generische Problemklassen anwendbar sind.

• Greedy Search
• Beam Search
• Local Search
• Simulated Annealing
• Tabu Search
• Ant Colony Optimization
• Genetic Algorithms
• Particle Swarm Optimization
• ...

Heuristische Methoden geben meistens keine Garantie für die Qualität der gefundenen Lösung

Konsequenz: Wir müssen mehrere Methoden Testen um ein Gefühl für die Qualität der Lösung zu bekommen.

Simulated Annealing

Idee: Lokale Suche, aber erlaube Verschlechterung mit sinkender Wahrscheinlichkeit.

Inspiriert von der Kristallbildung in abkühlenden Metallen

https://en.wikipedia.org/wiki/File:Hill_Climbing_with_Simulated_Annealing.gif

Abhängig vom Problem:

• Nachbarschaft eines Assignments $x$
• Übergangswahrscheinlichkeit $P(x, x', T)$

Nachbarschaft beim Map Coloring zum Beispiel:
Ändere Färbung für eine Territory
(analog zur lokalen Suche)

Übergangswahrscheinlichkeit:

Sei $f(x)$ die Anzahl benachbarter Gleichfärbungen

\[ P(x, x', T) = \begin{cases} 1 & \text{if } f(x') < f(x)\\ e^{-\frac{f(x') - f(x)}{T}} & \text{else} \end{cases} \]

Genetic Algorithms

Idee: Erstelle neue Lösungen als Rekombinationen von alten Lösungen

Inspiriert durch evolutionäre Weiterentwicklung genetischen Erbguts.

Representation von Lösungen

Eine Lösung muss so kodiert werden, dass leicht eine Crossover Funktion darüber implementiert werden kann.

Zum Beispiel: (binärer) Array konstanter Länge.

Beispiel für das Map Coloring Problem:

Array mit einem Eintrag je Territory. Eintrag entspricht Färbung:

[R, R, R, B, B, G, R]

Selection anhand der "Fitness" einer Lösung

Wir behalten eine Teilmenge der Lösungen. Je "fitter" die Lösung, desto höher die Wahrscheinlichkeit sie zu behalten.

Die Fitness Funktion bestimmt die Qualität einer Lösung.

Beispiel für das Map Coloring Problem:

Minus Anzahl benachbarter Regionen mit gleicher Farbe ($-f(x)$)

Crossover

Für zwei Lösungen bestimme zufällige Rekombination der Lösungen.

Bei Repräsentation als Arrays ("a" und "b") gleicher Länge:

• Sei $i$ ein zufälliger Index
• Nachwuchs: a[:i] + b[i:] und b[:i] + a[i:]

Eltern

• [R, R, R, B, B, G, R]
• [B, R, G, G, G, R, G]

Nachwuchs

• [R, R, R, G, G, R, G]
• [B, R, G, B, B, G, R]

Mutationen

Mit geringer Wahrscheinlichkeit modifizieren wir eine zufällige Stelle einer Lösung:
[R, R, R, G, G, R, G]
$\Rightarrow$
[R, B, R, G, G, R, G]

Eine Metaheuristik kann sehr starke Ergebnisse liefern, aber auch bei unpassenden Problemen komplett versagen.

$\Rightarrow$ Viel Experimentieren nötig

Wenn die Lösung für ein Optimierungsproblem den Kunden nicht zufrieden stellt, gibt es mehrere Möglichkeiten:

• Die gefundene Lösung ist zu schlecht.
• Die Zielfunktion ist die falsche.
• Unsere Nebenbedingungen sind falsch.

Agiles Vorgehen hilft: Kunde kann Probleme an konkreter Lösung meist besser benennen.

Viele nötige Nebenbedingungen fallen erst auf, wenn die konkrete Lösung sie verletzt:

• Pausenzeiten von Arbeitern
• Sicherheitsabstände
• Weiche Präferenzen
• Plan sollte ähnlich zu letztem Jahr sein
• ...

Erste Lösung mit Greedy Search, dann verbessern.