Matthias Bernauer - Freiburg im Breisgau
      Start > Skript-Sammlung > Kuenstliche Intelligenz > Genetische Algorithmen >>







Genetische Algorithmen

Genetic Algorithms

Imitiert die Evolution (Natur). Idea: Similar to evolution, we search for solutions by “cross-over” (Zwei parents produzieren einen Nachfolger mit geerbten Eigenschaften), “mutation” (Zufallseinflüsse), and “selection” (ein node ändert seinen Zustand) successful solutions.

Ingredients:

• Coding of a solution into a string of symbols or bit-string

• fitness-Funktion (ähnlich zur Evaluierungsfunktion) to judge the fitness of configurations

• A population of configurations

Beispiel: 8-queens-Problem als eine Verkettung von 8 Zahlen.

Fitness is judged by the number of non-attacks. The

population consists of a set of arrangements of queens.



Die Besten haben die größte WSK selektiert zu werden



Eine Zufallsposition wird in die Konfiguration mit aufgenommen


while(fitness-Funktion sich nicht mehr verbessert)


(a) es gibt 8^8 Populationen, denen einen Wert durch die fitness-Funktion (b) zugeordnet wird. Auf Grund dieser wird die WSK für deren Selektion (c) bestimmt. Die selektierten Elemente werden gekreuzt (d) und mutieren anschließend (e)



Pfadplanung


Mögliche Versuche:

  • Reactive: Berechne die Bewegung des Motors, Kommandos basieren auf der aktuellen Beobachtung und Zielposition. Versuche gerade aus zum Ziel vorwärts zu bewegen und umfahre Hindernisse. Kann in lokalen Optimas steckenbleiben (suboptimal)

  • Deliberative: Generiere/Plane einen fast optimalen Pfad zum Ziel


Vereinfachende Annahmen

  • kontinuirliche oder millimetergenaue Navigation nicht möglich. Teile Raum auf -> Diskretisierung.

  • Die Bewegung anderer Agenten ist bekannt oder irrelevant

  • ändert sich die Umgebung (Zustand) muss kontinuirlich neu geplant werden (replaning), d.h. der Pfad neu berechnet werden.


Suche im 5D-Raum

  • Postition des Agenten (x,y) = location

  • Richtung/Sicht des Agenten = orientation 

  • Geschwindigkeit w

  • Beschleunigung v

Durchsuche diesen Raum mittels A* um den schnellsten Weg zur Zielkonfiguration zu finden. Da die Suche zu speicherintensiv ist, finden weitere Vereinfachungen statt:

  • loaction nur in 2D

  • suche den kürzesten Pfad, ignoriere die orientation

  • alle objekte sind kreise

  • reduziere den agenten als punkt und vergrößere die anderen objekte mit diesem unterschied.





Durchsuche den Visibility-Graph und verwende die Luftliniendistanz als Heuristik

--> beschränkter Such/Zustandsraum

--> Optimale Lösung des Sichtbarkeitsgraphen ist nicht zwangsläufig die optimale Lösung des ursprünglichen Problems.

--> Kreise fixierd, weil die Bewegung der anderen Agenten zur Vereinfachung ignoriert

--> kürzeste Weg ist weder der sicherste noch der schnellste.


  • Heuristiken werden benutz, um die Suche in die richtige Richtung zu steuern
    --> Vollständigkeit, Optimalität

  • Es gibt viele Variantionen von A*

  • Alernativen: Lokale und genetic Suchmethoden

  • Es gibt meist keine fertigen Lösungen, sondern basiert meist auf Versuchen und Verbessern



Constraint Satisfaction Probleme


In den bisherigen Suchproblemen hatten die Zustände keine innere Struktur. Bei den CPS haben die Zustände innere Strukturen/Variablen mit Werten. Der Zieltest prüft, ob alle Variablen ihren gültigen Zustand erreicht haben.




Oftmals lassen sich Hyper-Graphen in binäre umwandeln


Später werden auch Baumstrukturen untersucht


Variationen:

  • endliche Werte d, z.B. 3 Farben --> d^n Möglichkeiten, z.B. 3^n Färbungsmöglichkeiten

  • unendliche domain
    - reel oder ganzzahlig (int)
    - lineare constraints
    lösbar in P (polynomiel)
    - nicht-lineare consists
    nicht lösbar oder NP

Anwendungen: FloorPlaning, Scheduling, Timetabling, Spreadsheets

Backtracking-Suche (Form der Tiefensuche, da den Variablen ebenenweise Werte zugeordnet werden, bis auf einer Ebene ein Konflikt entsteht und man backtracken muss)


assigned = Zuweisung für Variablen


Verbesserte Effizienz:

  • Variablenordnung: Welche Variablen soll zuerst ausgewählt werden?


    • 1ste Heuristik: most constraint first
      Die eingeschränkteste Variable ist diejenige, der noch am wenigsten verbleibende Werte aus ihrer Domain zur Verfügung stehen
      --> Reduzierung des Branchingfaktors

    • 2te Heuristik: most constraining variable first
      Wähle die Variable, die am meisten Bedingungen mit anderen Variablen eingeht
      z.B. färbe zuerst SA (oben blau) ein, da diese mit 5 Nachbarländern Bedingungen eingeht, danach evtl. NT (oben grün), da dieses 2 Bedingungen einginge, ...

  • Wertordnung: Welcher Wert soll zuerst probiert werden?

    • Gegebene Variable: Wähle den am wenigsten eingeschränkten Wert. --> Wertzuweisung soll gefunden werden, die allen Bedinungen genügt.

    • Forward-checking: Bei der Wertzuweisung zu einer Variablen, haben andere Variablen evtl. ungültige Werte, die entfernt werden.
      WA=rot -> NT kann nicht rot werden. Wurden für eine Variable alle Werte entfernt, ist der Wertebereich leer und wir können die Suche stoppen.
      --> Speedup zum normalen Backtracking

    • Forward-Checking propagiert zwar Informationen von zugewiesenen Variablen auf noch nicht zugewiesene Variablen, jedoch nicht von unassigned zu unassigned:
      siehe Beispiel rechts, wo in der dritten Zeile
      kein Informationsaustausch zwischen NT und SA (beide unzulässigerweise blau) stattfindet -> Forward-checking unvollst.
      --> Kantenkonsistenz

    • Kantenkonsistenz mittels gerichtetem KonsistenzGraph. Ein ungerichteter Graph lässt sich durch Ersatz in jeweil zwei gerichtete Kanten umwandeln.
      Eine gerichtete Kante X->Y ist konsistent, wenn es für jeden Wert von X einen Wert von Y existiert, so dass (x,y) die Bedingung erfüllt ist.
      z.B. ist der Zustand in der dritten Zeile nicht kantenkonsist, da SA->NT nicht konsistent ist.
      Kantenkonsistenz entdeckt Fehler früher. Versuche Kantenkonsistenz mittels Backtracking herbeizuführen, z.B. entferne blau aus SA in der dritten Zeile.
      Kann als preprocessing (Vorbereitung) verwendet werden.
      --> als Algorithmus AC3


    • Komplexität von AC3 in O(dÂłn²), mit n Knoten und d als max. Wertebereich
      AC3 findet nicht alle Inkosistenzen, da dies NP-Hart ist.

  • Versuche Fehler so früh wie möglich zu entdecken

  • Versuche die Problemstruktur zu erforschen, z.B. ist die kleine Insel unabhängiger Subgraph, d.h. CSP hat unabhängige Teilkomponenten. Löse diese Teile unabhängig voneinander und füge sie zu einer Gesamtlösung zusammen --> reduziert den Suchraum extrem
    Ist der Graph ein Baum, vereinfacht sich das Problem zu O(nd²), denn allg. benötigen CSP O(n^d) im worst case. Idee: Bestimme einen Knoten als Wurzel und ordne die restlichen Knoten entsprechend an. Prüfe auf inkonsistente Kanten von den Blättern ausgehend zur Wurzel.

Bem.: alle dies ist nicht problemspezifisch


  • über den Knoten stehen die möglichen, anwendbaren Farben angeschrieben

  • Wende die Kantenkonsistenz an für (Xi,Xk) mit Xi ist parent von Xk.

  • Nun kann mit der Wertzuweisung begonnen werden. zufällige Initialbelegung, hier: rot für E

  • Der Algorithmus ist linear.

  • Ist (D,F) kantenkonsistent? Ja, den für R gibt es B und G, für G gibt es R und B

  • Ist (D,E) kantenkonsistent? Nein, denn für R gibt es keinen zulässigen Wert. Streiche daher das R in D.

  • (B,D) ist nicht konsistent; streiche daher G

  • (A,B): streiche R

  • Go forward: Wähle nun aus den verbleibenden Möglichkeiten eine Belegung aus

  • (D,F): G muss aus F entfernt werden



Bei Strukturen, die kein aber fast ein Baum sind, gibt es 2 Möglichkeiten


  • Conditioning: Initialisiere eine Variable mit einem Wert und update die umgebenden Variablen gem. den Bedingungen (unsystematisch: welcher Wert, welche Variable?)

  • Cutset Conditioning: Suche eine Anzahl von Variablen und überprüfe die Auswirkung.
    Das Finden einer minimalen Anzahl von Knoten, um einen Baum zu bekommen, (minimal Cut Set) ist NP-hart

  • Tree Decomposition
    Teile die Struktur in Subprobleme auf, die eine Baumstruktur darstellt, löse sie unabhängig und füge die Lösungen am Schluss zusammen.
    Folgende Eigenschaften müssen erfüllt sein:

    • Jede Variable des urspr. Problems muss noch in einem Teilproblem vorkommen.

    • Jede Bedingung des urspr. Problems muss auch in einem Teilproblem vorkommen.

    • Jede Variable, die in zwei Subproblemen vorkommt, muss auch in jedem dazwischenliegenden SubProblemen vorkommen, z.B. kommt SA ganz links und ganz rechts vor und somit auch in den dazwischenliegenden zwei Subproblemen.

    • Zwei Subprobleme sind miteinander verbunden, wenn sie eine Bedingung gemeinsam haben, z.B. sind die beiden Subprobleme, die NT-SA enthalten, miteinander verbunden.

    • Die Verbindungen formen eine Baumstruktur

Die zu Subproblemen zusammengefassten Knoten können nun mit Mega-Variablen
belegt werden (d.h. immer eine bestimmte Kombination aus Wertzuweisungen)
Nach der Wahl einer Wertzuweisung, müssen die anderen Subprobleme in überein-
stimmung dazu gebracht werden.

Die Komplexität hängt von der Baumweite (Größe des größten Teilproblems 1)
ab. Im Beispiel enthält das größte Subproblem 3 Variablen, so dass sich also 2 erg.


Die Baumweite des Graphen ist die minimalste Baumweite die man unter Betracht-
ung aller möglichen Dekompositionen finden kann (NP-hart)
Ist jedoch eine Dekompositionen mit Weite w bekannt, so kann das Problem in
O(nd^(w+1)) gelöst werden.



Adversarial Search


Die Welt ist nicht mehr statisch, sondern ein Externer erzeugt für uns ungünstige Situationen, d.h. es existiert ein Gegner, der unseren Nutzen minimieren möchte.


6.1 Spieltheorie

es existiert mehr als nur ein Agent --> Zustand der Welt nicht mehr hervorsagbar --> nicht alles auf einmal planbar, sondern updates der Berechnung erforderlich --> generiere Aktionen die auf diese Ungewissheit ausgerichtet ist, d.h. gut ist, unabhängig von der Handlung des Gegners (competetive environment)


Vereinfachungen:

  • extensive games
    Wir betrachten eine Folge/Sequenz von Aktionen (also nicht gleichzeitig). Ein zeitlicher Bezug besteht.

  • deterministic game. Jede Aktion wird tatsächlich ausgeführt

  • two-player-game: Genau zwei Agenten

  • Nullsummenspiel: Der Ausgang des Spiels addiert sich immer zu0, d.h. was der eine gewinnt, geht dem andern verloren und es kann nicht sein, dass beide gewinnen.

  • perfekte Informationen: vollständig beobachtbare Welt der andere Spieler spielt nicht verdeckt




Google MSN Suche
<< Start | Studium | Poolmgr | Tanzen | GPG | Impressum >>
Matthias Bernauer