Intelligente Systeme

Intelligenz:

• nicht genau definierbar

• Angabe eines operationalen Kriteriums, welches es ermöglicht zu entscheiden, ob ein technisches System intelligent ist. Weit verbreitetes Beispiel ist der Turing Test

• Definition der Fähigkeiten und Merkmale, die ein System haben muß, um intelligent zu sein

Künstliche Intelligenz:

• Der Begriff ist nicht eindeutig abgrenzbar, da es bereits an einer genauen Definition von Intelligenz mangelt. Dennoch findet er in der Forschung und Entwicklung Anwendung. Im Allgemeinen bezeichnet KI den Versuch, eine menschenähnliche Intelligenz nachzubilden, d.h., einen Computer zu bauen oder so zu programmieren, dass dieser eigenständig Probleme bearbeiten kann. Oftmals wird damit aber auch eine effektvoll nachgeahmte, vorgetäuschte Intelligenz bezeichnet, insbesondere bei Computerspielen, die durch meist einfache Algorithmen ein intelligentes Verhalten simulieren soll

• Bewußt soll sich die KI nicht auf die Nachbildung von menschlichen Vorgehensweisen beschränken, sondern es Maschinen auch gestatten, neue und nicht-menschliche Problemlösungsmethoden zu entwickeln

Von IBM entwickelt für das Spiel Jeopardy!

• Es gibt noch keine Künstliche Intelligenz die den Begriff Intelligenz definieren könnte

• Resultat: Nein

• Ist ein Stück hin Ingenieurskunst

Alan Turing (1950): Ein System ist intelligent, wenn es kognitive Leistungen erbringt, die ausreichen, um einen (menschlichen) Fragesteller zu täuschen

Erforderliche Fähigkeiten sind:

• Verarbeitung natürlicher Sprache

• Wissensrepräsentation

• Schlußfolgern

• Lernen

• Simulation menschlichen Fehlverhaltens

Funktionsweise:

Der Turing-Test beschreibt die Situation, dass sich in zwei abgeschlossenen Räumen jeweils ein Mensch M und eine Maschine C befindet. Darüber hinaus existiert ein zusätzlicher Beobachter B. Der zusätzliche Beobachter kann sowohl mit M als auch mit C kommunizieren, ohne beide zu sehen. Falls es dem Beobachter B nicht gelingt, durch geschickte Anfragen an beide Teilnehmer, M und C, den Menschen vom Computer zu unterscheiden, wird die Maschine als intelligent betrachtet.

Klassische KI/ Symbolverarbeitende KI:

• Nach Regeln bestimmen

• Beispiel: 2 Arme, 2 Beine, Bart -> Mann

• Überwachtes Lernen

• Akinator

Sämtliches Wissen und alle Regeln, die den jeweiligen Entscheidungsprozessen zugrunde liegen, sind entweder hartcodiert oder werden aus einer seperaten Datei ins Programm eingelesen.

Vereinfacht ausgedrückt führt ein regelbasiertes KI-System lediglich eine mehr oder weniger große Anzahl von Wenn-dann-Entscheidungen aus, die sich in Form eines endlichen Zustandsautomaten (FSM, Finite State Machine) implementieren lassen.

Subsymbolische KI/ Konnektivistische KI:

• nicht expliziet mit Regeln

• kann nicht verbalisiert werden

• Künstliche Neuronale Netze

• Unüberwachtes Lernen

• Fuzzy-System (mindestens 1 Eingang, 1 Ausgang, ReLU-Funktion)

• Classifier System (Nearest Neighbor)

• Evolutionäre Algorithmen

• Neuronale Netze

• Klassische Regelbasierte KI Systeme

ML nutzt statistische Methoden, um aus Erfahrungen zu lernen ohne dabei explizit programmiert worden zu sein

• überwachtes Lernen

  • selbständig Muster in Daten erkennen (Beispieldaten/Label werden vorgegeben: Student: Jeans, 20-30 Jahre alt, Rucksack)

  • durch erlernte Muster sind sie Beispielsweise in der Lage Prognosen zu unbekannten Daten zu erstellen (Unterscheidung Student und Mitarbeiter/ Vorhersagen an der Börse/ Hunderassen unterscheiden)

• unüberwachtes Lernen

  • Beim unüberwachten Lernen liegen keine Ausgabedaten vor. Ziel eines Modells ist es, Strukturen in den Daten zu lernen.

• Verstärkendes Lernen

  • ein Software-Agent erlernt selbständig eine Strategie, um erhaltene Belohnungen zu maximieren. Dabei wird dem Agenten nicht vorgezeigt, welche Aktion in welcher Situation die beste ist, sondern er erhält durch die Interaktion mit seiner Umwelt zu bestimmten Zeitpunkten eine Belohnung, die auch negativ sein kann.

• es gibt eine Vielzahl unterschiedlicher Modelle und Methoden

• Grundlegende Konzepte sind bei vielen Modellen ähnlich

Neuronale Netze, die auch als künstliche neuronale Netze (KNN) oder simulierte neuronale Netze (SNN) bezeichnet werden, sind ein Teilbereich der Displizin des maschinellen Lernens (ML) und stellen das Herzstück von Deep-Learning-Algorithmen dar.

KNN bestehen aus einer Knotenschicht, die eine Eingabeschicht, eine oder mehrere verborgene Schichten und eine Ausgabeschicht enthält. Jeder Knoten bzw. jedes künstliche Neuron ist mit einem anderen verbunden und verfügt über eine ihm zugeordnete Gewichtung und einen Schwellenwert. Wenn die Ausgabe eines beliebigen einzelnen Knotens über dem für ihn festgelegten Schwellenwert liegt, wird dieser Knoten aktiviert und sendet Daten an die nächste Schicht im Netz. Andernfalls werden keine Daten an die nächste Schicht des Netzes weitergegeben.

• Überwachtes Lernen nutzt Beispieldaten mit einer Zielvariable, um aus diesen Daten Muster zu erlernen und diese auf unbekannte Daten anzuwenden 

• Wird für Klassifikationen und Regressionen genutzt, also für die Vorhersage von Wahrscheinlichkeiten oder numerischen Werten

• Überwachtes Lernen setzt eine aufwendige Datenvorverarbeitung voraus

• Beispiel für Eingaben sind Bilder, Sprache, oder

  Emails.

• Ist die Ausgabe eine (oder mehrere) von M

  vorgegebenen Kategorien (z.B. Ziffern 0-9,

  Labels “Hund/Katze/Maus/...",

  Spam:“ja/nein"), spricht man von Klassifikation.

  Ist die Ausgabe kontinuierlich (z.B. 12,342

  [USD]), handelt es sich um eine Regression. Die Variable nimmt einen bestimmten Wert an oder nicht

• MNIST Datensatz für Zahlen (gelabelter Datensatz):

• Beim unüberwachten Lernen liegen keine

  Ausgabedaten vor. Ziel eines Modells ist es,

  Strukturen in den Daten zu lernen.

• Anwendungsfälle

  sind z.B.

  • Kategorisierung (Clustering)

  • Dimensionalitätsreduktion (z.B. zur Kompression/ Visualisierung)

  • Dichteschätzung

  • Wissensgewinnung (die gefundenen Muster selbst sind von Interesse)

  • Finden von Anomalien, z.B. für fraud detection

• Features eines ungelabelten Bildes werden von dem Algorithmus selbst konstruiert

• Fraud detection: Beispiel Geld abheben immer in Bocholt mit Radius +-30km. Jetzt wird in Kreta Geld abgehoben. Ungewöhnlich, deswegen Meldung

  
  

• Bestärkendes Lernen oder verstärkendes Lernen steht für eine Reihe von Methoden des maschinellen Lernens, bei denen ein Software-Agent selbständig eine Strategie erlernt, um erhaltene Belohnungen zu maximieren. Dabei wird dem Agenten nicht vorgezeigt, welche Aktion in welcher Situation die beste ist, sondern er erhält durch die Interaktion mit seiner Umwelt zu bestimmten Zeitpunkten eine Belohnung, die auch negativ sein kann.

• Die Methoden von RL unterscheiden sich von anderen ML-Methoden maßgeblich.

• wird häufig verwendet (Beispiel: Wir wollen nach Rhede, müssen aber vorher ein Stück Richtung Bocholt fahren um auf eine Straße Richtung Rhede zu kommen)

Overfitting:

Durch zu viele Testdaten wird eine zu genaue Kurve erzeugt und ein Testpunkt wird falsch zugeordnet. Neue Daten können nicht vorhergesagt werden

Underfitting:

Durch eine Gerade können die Testdaten nicht genau eingegrenzt werden und neue Testpunkte werden falsch detektiert. Das Modell kann komplexe Zusammenhänge nicht abbilden

Right Fitting:

Passender wäre eine Kurve die an den Datensatz angepasst ist, sodass wir nicht zu exakt und nicht zu wenige Daten anlernen

• Fehler minimieren (meistens mit Fehlerfunktion von Gauß)

• Trainingsalgorithmus und Trainingsfunktion

Vorhersage:

Accuracy: (TP+TN)/(TP+TN+FP+FN)

Recall: TP/(TP+FN) -> alle Risse erkennen: Recall vergrößern (Wahrscheinlich mehr FP)

Precision: TP/(TP+FP) -> Auf Recall oder Precision gehen

F1-Score: 2*(Precision*Recall)/(Precision+Recall)

• Fehlerfunktion

• ein perfekter Klassifikator hat einen loss von 0

• Der Kreuzentropieverlust ist eine Metrik, die beim maschinellen Lernen verwendet wird, um zu messen, wie gut ein Klassifizierungsmodell abschneidet

• Eine Verlustfunktion, die den Fehler zwischen einer vorhergesagten Wahrscheinlichkeit und der Bezeichnung, die die tatsächliche Klasse darstellt, messen kann, wird als Cross-Entropy Verlustfunktion bezeichnet.

Herleitung Christoph

• Der Gradient ist der Vektor, der alle partiellen Ableitungen einer Funktion in einem Punkt enthält

• Wir können den Gradient descent auf eine konvexe Funktion und den Gradient ascent auf eine konkave Funktion anwenden

• Der Gradient descent findet das nächstgelegene Minimum einer Funktion, der Gradient ascent das nächstgelegene Maximum.

• Wir können beide Formen der Optimierung für dasselbe Problem verwenden, wenn wir die Zielfunktion umdrehen können.

In der Praxis ist der Gradient descent jedoch häufiger anzutreffen als der Gradient ascent.

Herleitung Christoph

• Der Gradient ist der Vektor, der alle partiellen Ableitungen einer Funktion in einem Punkt enthält

• Wir können den Gradient descent auf eine konvexe Funktion und den Gradient ascent auf eine konkave Funktion anwenden

• Der Gradient descent findet das nächstgelegene Minimum einer Funktion, der Gradient ascent das nächstgelegene Maximum.

• Wir können beide Formen der Optimierung für dasselbe Problem verwenden, wenn wir die Zielfunktion umdrehen können.

In der Praxis ist der Gradient descent jedoch häufiger anzutreffen als der Gradient ascent.

• Implementierungsebene (Basiswerkzeuge)

  • Algorithmen und Modelle beibringen

• Grundlagen und Methoden

  • Auslegung der Algorithmen für die Klassifizierung

• Anwendungssysteme und KI Systeme

Künstliche Intelligenz umfasst die Idee einer Maschine, die menschliche Intelligenz imitieren kann. Maschinelles Lernen hingegen nicht. Ziel des maschinellen Lernens ist es, einer Maschine beizubringen, eine bestimmte Aufgabe auszuführen und präzise Ergebnisse durch Identifizieren von Mustern zu liefern.

KI:

• Neuronale Netze

• Deep Learning

ML:

• Überbegriff für die “künstliche” Generierung von Wissen aus Erfahrung

Lernen automatisch Muster und Zusammenhänge aus Daten und verbessern sich, ohne expliziet programmiert zu sein

Überwachtes Lernen

Unüberwachtes Lernen

Verstärkendes Lernen

Teilüberwachtes Lernen:

• Teilüberwachtes Lernen (Semi-supervised Machine Learning) nutzt sowohl Beispieldaten mit konkreten Zielvariablen, als auch unbekannte Daten und ist somit eine Mischung aus überwachtem und unüberwachtem Lernen. Die Einsatzgebiete von teilüberwachtem Lernen sind im Grunde die gleichen wie bei dem überwachten Lernen.

Hunde von Katzen von Mäusen unterscheiden

3 Modelle bauen die jeweils eine Kategorie erkennen (Hund: ja/nein)

und diese dann zusammenfügen

oder es wird verglichen Klasse 1 mit 2/3

wenn Klasse 2/3 dann wird Klasse 2 mit 3 verglichen

Überwachtes Lernen: ist eine Art maschinelles Lernen, bei der einem Computer beigebracht wird, Prognosen oder Entscheidungen auf Basis von Beispielen zu treffen. Denken Sie dabei an Studierende, die von ihren Dozentinnen oder Dozenten lernen: Der/die Dozent/in konfrontiert die Studierenden mit einer Reihe von Problemen und richtigen Antworten auf diese Probleme. Die Studierenden machen sich mit diesen Beispielen vertraut, um zu lernen, Muster zu erkennen. Wenn die Studierenden sich dann einem neuen Problem gegenübersehen, können sie ihr vorheriges Wissen nutzen, um dafür die richtige Antwort zu finden.

Beim überwachten Lernen erhält der Computeralgorithmus einen Datensatz mit Eingabedaten (Problemen) und den richtigen Ausgabedaten (Antworten). Der Algorithmus macht sich mit diesem Datensatz vertraut und lernt die Beziehung zwischen der Ein- und Ausgabe kennen. Schließlich kann der Algorithmus dann Prognosen oder Entscheidungen für neue Daten treffen, die er noch nicht kennt.

Fraud detection: Diese kann aus den historischen Daten eines Onlineshops lernen, welche Merkmale einer Bestellung auf einen Betrug hindeuten. Die erkannten Muster aus den historischen Bestellungen können dann auf neue Bestellungen getestet und im Zuge dieses Tests klassifiziert werden.

Grundlage für die Betrugserkennung ist ein neuronales Netzwerk. Dieses wird mithilfe von überwachtem Lernen dahingehend trainiert, um aus historischen Bestellungen eines Onlineshops zu lernen und so zukünftige Bestellungen klassifizieren zu können.

Fraud Detection – Überwachung 

Unternehmen, die täglich Tausende oder mehr Kundendaten täglich in Ihrem Datenstrom verarbeiten müssen, stehen vor der großen Schwierigkeit, Anomalien oder betrügerische Nutzungsversuche erkennen zu müssen. Unsupervised Learning wird an dieser Stelle eingesetzt, um Abweichungen von der Norm in Echtzeit zu erkennen und direkt eingreifen zu können. Selbst komplexe, automatisierte Prozesse können so durchgehend überwacht werden.

Es gibt zu wenig Beispiele (historische Daten) um mit überwachtem Lernen Fraud detection zu betreiben

Bankbeispiel

Validierungsdatensatz: Ein Validierungsdatensatz ist ebenfalls wie der Trainingsdatensatz ein Beispieldatensatz. Die Validierungsdaten werden für die Abstimmung der Modellparameter (d.h. für künstliche Neuronale Netzwerke der Architektur) eines Modells verwendet.

So wird vor allem eine Überanpassung des Modells auf die Trainingsdaten vermieden.

Testdatensatz: Um das Netz auf Korrektheit zu prüfen

Regularisierung bezeichnet eine Reihe von Techniken, die Overfitting in künstlichen neuronalen Netzen verhindern und somit die Genauigkeit des Modells verbessern

• L1 Regularisierung (irrelevante Feature eleminieren, dabei wird die Verlustfunktion des neuronalen Netzes um einen sog. absoluten Regularisierungsterm erweitert)

• L2 Regularisierung (starke Anpassung der Gewichte, dabei wird die Verlustfunktion des neuronalen Netzes um einen sog. quadratischen Regularisierungsterm erweitert)

• Dropout Regularisierung (Neuronen weglassen, Die Neuronen, die gerade anfangen ausendig zu lernen, fallen weg und andere müssen lernen)

• Augmentieren (Dadurch bekommt das Netzso viele Daten, dass es keine Chance zum auswendig lernen hat, Regularisierung durch Überforderung)

• Fehlerrate F1-Score = 2*(Precision*Recall)/(Precision+Recall)

• Recall TP/(TP+FN)

• Accuracy (TP+TN)/(TP+TN+FP+FN)

• Precision TP/(TP+FP)

Durch die Kreuzvalidierung können wir verschiedene Methoden des maschinellen Lernens vergleichen und ein Gefühl dafür bekommen, wie gut sie in der Praxis funktionieren. Zum Beispiel wollen wir SVM mir kNN und Regression vergleichen. Dazu machen wir für jedes Modell die Cross Validation und können anhand der Richtig erkannten und Falsch erkannten von jedem Modell herausfinden welches sich für unseren Anwendungsfall am Besten eignet.

Testen der Leistung eines Vorhersagemodells für Machine Learning

Jedes Teilstück eines Datensatzes wird als Trainingsmodell benutzt, sodass jede Zahl einmal als Validierung (Validierungsdatensatz) genutzt wird. Dann wird der Mittelwert gebildet

einfache/dreifache/zehnfache cross validierung

TTV / TTV, TVT, VTT / TTTTTTTTTV, TTTTTTTTVT, TTTTTTTVTT, usw.

Ein Neuron ist über gewichtete Verbindungen mit anderen Neuronen verbunden.

Die Ausgabe eines Neurons wird an andere Neuronen weitergeleitet.

Zelle, Element, unit:

formalisierte Entsprechung einer Sinneszelle im biologischen Systems.

Eigenschaften:

• Aktivierungszustand:

  • aktueller Zustand des Neurons (Bias)

• Propagierungsfunktion:

  • Verhalten des Neurons im Hinblick auf die Informationsverarbeitung. I.d.R. Aufsummierung der Ausgaben der vorgeschalteten Neuronen entsprechend der Gewichtung der Eingangskanten.

• Aktivierungsfunktion:

  • Es wird der Aktivierungszustand aus dem Ergebnis der Propagierungsfunktion berechnet. Unter Umständen wird für den neuen Aktivierungszustand (Zeitpunkt t + 1) der vorhergehende Aktivierungszustand (Zeitpunkt t) mitberücksichtigt (recurrent neural network)

  • ReLU

  • Sigmoid

• Ausgabefunktion:

  • Legt den Ausgabewert in Abhängigkeit des Aktivierungszustandes fest.

Rekurrente und Feedforward-Netze

Beschreibt die Topologie des Netzes. Viele KNNs können als gerichteter Graph interpretiert werden, dessen Kanten die gewichteten Verbindungen zwischen den Neuronen sind

• 1997 von Hochreiter und Schmidhuber vorgestellt Variante von rekurrenten Neuronalen Netzen

• löst das Problem des vanishing gradients beim Gradientenabstiegsverfahren durch Einführung eines “Gedächtnisses” (memory)

• LSTM ist eine Aktivierungsfunktion, bekommt Output wieder als Input

• Anwendungen: Spracherkennung, Handschrifterkennung

• ersetzt Neuronen durch LSTM-Module mit drei verschiedenen Gates

  • Input Gate (nimmt Wert der vorherigen Zelle auf)

  • Forget Gate (wie stark wird der bisherige Zustand beibehalten)

  • Output Gate (wie wird der Zustand an die nachfolgende Zelle weitergereicht)

Ist die Nichtberücksichtgung zufällig ausgewählter Neuronen (bis zu 30%) bei einem Trainingsschritt eines neuronalen Netzes

Ist die Vervielfältigung bestehender Daten durch ihre Abänderung

• Spiegeln, Drehen, Skalieren, Deformieren, Zuschneiden, Verfärben, …

• Netz ist weniger störanfällig bei zum Beispiel dunkleren Bildern

• um einen Datensatz aus einem ursprünglichen Bild zu bekommen

• eventuell mit Regularisierung um Overfitting zu vermeiden

Convolutional Networks werden oft und recht erfolgreich für die Klassifikation von Bildern oder Tonsequenzen verwendet.

Sie bestehen aus einer Abfolge von einem oder mehreren Convolutional Layern und einer Pooling Layer.

• Convolutional Layer:

  • Eingabe in der Regel zwei- oder drei-dimensionale Bilder.

  • Mit Hilfe eines Kernels werden lokal zusammenhängende Neuronen der Inputschicht jeweils auf auf ein Neuron der Folgeschicht abgebildet (Faltung).

• Pooling Layer:

  • aggregiert die Ergebnisse von Convolutional Layern, indem er nur das jeweils stärkste Signal weiter gibt.

  • MaxPooling Layer verwendet nur die höchsten Wert einer

    Kernel-Matrix.

  • Ziel ist nur relevanteste Signale an die nächsten Schichten

    weiter zu geben, eine abstraktere Repräsentation des Inhalts zu

    erreichen und die Anzahl der Parameter eines Netzes zu

    reduzieren.

• Nach mehreren Convolutional und Pooling Layers wird oft

  noch eine fully-connected layer verwendet.

• Training oft über Backpropagation

max pooling/ subsampling

Merkmalsvorverarbeitung

• Architektur initialer Schichten eines neuronalen Netzes spiegelt die Lokalität in den Daten wieder

• Extraktion der Merkmale erfolgt durch das neuronale Netz

• Einbeziehung der Merkmalsextraktion in den Optimierungsprozess neuronaler Netze: Merkmale werden automatisiert evolviert

• Transferlernen: ist die Modellbildung und anschließende Modellanwendung auf verwandte Fragestellungen.

  Training der Merkmalsextraktionsschichten an diversen Datensätzen, Fixierung der Merkmalsextraktionsschichten, Nachtrainieren der finalen vollständig verschalteten Schichten für neue anwendungsspezifische Datensätze

• unüberwachtes Lernen

• Datenkompression, generierung ähnlicher Datenpunkte

• Ein Autoencoder ist ein künstliches neuronales Netz, das dazu genutzt wird, effiziente Codierungen zu lernen. Das Ziel eines Autoencoders ist es, eine komprimierte Repräsentation für einen Satz Daten zu lernen und somit auch wesentliche Merkmale zu extrahieren. Dadurch kann er zur Dimensionsreduktion genutzt werden.

• mehrschichtiges Perzeptron

• Verwendung für Dimensionalitätsreduktion und deep learning

• Hingelegte Sanduhr: Encoder, komprimierter Code, Decoder

• Aufbau

  • eine sichtbare Schicht x (An Eingangsneuronen wird Trainingsdatensatz der Länge n angehängt)

  • mindestens einer hidden layer h (Die hidden Neuronen stellen eine nicht lineare Repräsentation des Inputs dar)

  • einer Ausgabeschicht z (Die Ausgabeneuronen stellen eine Rekonstruktion des Inputs dar)

Die Gewichte W und W ′ verbinden x mit h und h mit z

Zwei deterministische Funktionen:

• encoding function h = c(x; θ), welche den Input x ∈ 0, 1^n auf die hidden layer h ∈ 0, 1^m (mit den Parametern θ und n, m ∈ N abbildet.

• decoding function z = f (h; θ′), die h auf die Rekonstruktion z ∈ 0, 1^n abbildet.

• Encoding und decoding function sind oft gewählt als

  • c(x) = sigm(x ∗ W + b^h) und

  • f (h) = sigm(h ∗ W ′ + b^z )

• wobei sigm(x) = 1/(1+exp^−x) die logistische Funktion, W und W ′

  Gewichtsmatrizen der Größe (n × m) und (m × n) und bh ∈ R^m, b^z ∈ R^n Biaswerte.

  Oft sind W und W ′ verknüpft (tied), was heißt dass W ′ = W ^⊤. In

  diesem Fall sind die Parameter des AE θ = W , b^h, b^z , welche mit

  dem Gradientenabstiegsverfahren gelernt werden können.

Training: Finde die Parameters θ, θ′, welche den reconstruction

error Errθ,θ′ (x, z) minimieren. Der Fehler wird berechnet als der

Unterschied zwischen x und z für alle Samples x^i , i ∈ 1, ..., τ des

Trainingsets:

Oft Verwendung einer quadratischen Fehlerfunktion

oder

cross entropy

Denoising:

Falls die hidden layer eines Autoencoders groß genug ist, ist ein Modell die Identitätsfunktion, welche jedes Eingangsneuron direkt auf das zugehörige Ausgangsneuron abbildet. Ein Denoising Autoencoder ist ein Beispiel für einen Autoencoder mit Regularisierung. Hierbei wird jeder Trainingsdatensatz x verrauscht und mit dem Denoising Autoencoder wird die Rekonstruktion des verrauschten Inputs berechnet

Rausfiltern von Rauschen mit Tiefpassfilter (Integrieren)

Sampling:

• Es ist nicht möglich (und auch nicht sinnvoll) von „normalen” AE (Autoencoder) neue Lösungen zu generieren (samplen)

• Da allerdings ein DAE (Denoising Autoencoder) implizit die Verteilung der Trainingsdaten lernt, kann man aus trainierten DAE neue Lösungen generieren, die der vom Modell gelernten Wahrscheinlichkeitsverteilung entsprechen

Datenerhebung, Werfen einer Münze ob Kopf oder Zahl

Hunderassen erkennnen

• 4x4 Feld

• In dem Kästchen in dem der Wumpus sich befindet und in den Nachbarkästchen nimmt man üblen Geruch wahr (Stench)

• In Kästchen neben Fallgrube (Pit) nimmt man Luftzug wahr (Breeze)

• Im Kästchen mit Gold glitzert es (Glitter)

• Wenn der Agent gegen eine Wand läuft bekommt er einen Schlag

• Wenn der Wumpus getötet ist hört man es überall (Todesschrei)

• Wahrnehmungen werden als 5-Tupel dargestellt. Z.B. [Stench, Breeze, Glitter, None, None] bedeutet, dass es stinkt, zieht und glitzert, aber es gab weder einen Schlag noch einen Todesschrei. Der Agent kann seinen Standort nicht wahrnehmen

• Aktionen:

  • gehe vorwärts

  • 90° nach rechts drehen

  • 90° nach links drehen

  • greife ein Objekt im selben Kästchen

  • schieße (es gibt nur einen Pfeil)

  • verlasse die Höhle (funktioniert nur in Kästchen [1,1])

  • Der Agent stirbt, wenn er in eine Fallgrube fällt oder dem lebenden Wumpus begegnet

  • Anfangszustand: Agent in [1,1] nach Osten schauend, irgendwo 1 Wumpus, 1 Haufen Gold, und 3 Fallgruben

  • Ziel: Hole das Gold und verlasse die Höhle

• Formulierung des Zieles, weltzustände mit bestimmten Eigenschaften

• Festlegen des Weltzustandraums

• Festlegen der Aktionen, die einen Weltzustand in einen anderen überführen

• Bestimmung des Problemtyps, der abhängig vom Wissen über Weltzustände und Aktionen ist → Zustände im Suchraum

• Bestimmung der Kosten für das Suchen (Suchkosten, Offline-Kosten) und der Ausführungskosten (Pfadkosten, Online-Kosten)

  
  

  Achtung: Die Art der Problemformulierung kann einen großen Einfluss auf die Schwierigkeit der Lösung haben.

• Gegeben ist ein nxn Brett, bei dem an beiden diagonal gegenüberliegenden Ecken je ein Feld entfernt wurde

• Ziel: Das Brett so mit Dominosteinen, die jeweils zwei benachbarte Felder überdecken, belegen, dass alle Felder abgedeckt werden.

  -> Ziel, Zustandsraum, Aktionen, Suche,…

Alternative Problemformulierung:

• Frage: Kann man ein Brett, auf dem es n^2/2 schwarze und n^2/2-2 weiße Felder gibt, so mit Dominosteinen, die jeweils ein weißes und ein schwarzes Feld überdecken, belegen, dass alle Felder abgedeckt sind?

• Antwort: Funktioniert nicht aufgrund ungleicher Anzahl schwarzer und weißer Felder

• Weltzustandsraum: 2 Positionen, Schmutz, kein Schmutz

• 8 Weltzustände

• Aktionen:

  • links (L)

  • rechts (R)

  • saugen (S)

  • Ziel: kein Schmutz in den Räumen

  • Pfadkosten: pro Aktion eine Einheit

• Problemtypen:

  • Einzustandsproblem

    • vollständiges Weltzustandswissen

    • vollständiges Aktionswissen

      -> der Agent weiß immer in welchem Zustand er ist

  • Mehrzustandsproblem

    • unvollständiges Weltzustandswissen oder

    • unvollständiges Aktionswissen

      -> der Agent weiß nur, in welcher Menge von Weltzuständen er ist

  • Kontingenzproblem

    • es ist unmöglich, eine komplette Sequenz von Aktionen zur Lösung im voraus zu bestimmen, da nicht alle Informationen über Zwischenzustände vorliegen

  • Explorationsproblem

    • Zustandsraum und Effekte der Aktionen nicht vollständig bekannt. Schwer!

Anfangszustand: Zustand, von dem der Agent glaubt, anfangs zu sein

Zustandsraum: Menge aller möglichen Zustände

Operator: Beschreibung einer Aktion durch Angabe des resultierenden Zustands

Zieltest: Test, ob die Beschreibung eines Zustands einem Zielzustand entspricht

Pfad: Sequenz von Aktionen, die von einem Zustand zu einem anderen führen

Pfadkosten: Kostenfunktion g über Pfade. Setzt sich üblicherweise aus der Summe der Kosten der Aktionen zusammen

Lösung: Pfad von einem Anfangs- zu einem Zielzustand

Suchkosten: Zeit- und Speicherbedarf, um eine Lösung zu finden

Gesamtkosten: Suchkosten + Pfadkosten

Staubsaugerwelt als Einzustandsproblem:

Falls die Welt vollständig zugänglich ist, weiß der Staubsauger

immer, wo er und der Schmutz sind. Problemlösen reduziert sich

dann auf die Suche nach einem Pfad von unserem Anfangszustand

zu einem Zielzustand.

Zustände für die Suche: Die Weltzustände 1–8.

Staubsaugerwelt als Mehrzustandsproblem:

Falls der Staubsauger keine Sensoren besitzt, weiß er nicht, wo er

ist und wo Schmutz ist. Trotzdem kann er das Problem lösen.

Zustände sind dann Wissenszustände (siehe folgende Folie)

Zustände für die Suche: Potenzmenge (Menge aller Teilmengen)

der Weltzustände 1–8.

Zustände:

• Beschreibung der Lage jedes der 8 Kästchen und (aus Effizienzgründen) des Leerkästchens

• Operatoren: “Verschieben” des Leerkästchens nach links, rechts, oben und unten

• Zieltest: Entspricht aktueller Zustand dem rechten Bild?

• Pfadkosten: Jeder Schritt kostet eine Einheit

• Zieltest: 8 Damen auf dem Brett, keine angreifbar

• Pfadkosten: 0 (nur die Lösung interessiert)

• Darstellung 1

  • Zustände: beliebige Anordnung von 0-8 Damen

  • Operatoren: setze eine der Damen aufs Brett

  • Problem: 64^8 (oder genau 64!/56!) Zustände

  • findet definitiv Lösung

• Darstellung 2

  • Zustände: Anordnung von 0-8 Damen in unangreifbarer Stellung

  • Operatoren: Setze eine der Damen soweit wie möglich links unangreifbar auf das Brett

  • Problem: wenige Zustände (2057), aber manchmal keine Aktion möglich

  • findet definitiv Lösung

• Darstellung 3

  • Zustände: 8 Damen auf dem Brett, eine in jeder Spalte

  • Operatoren: verschiebe eine angegriffene Dame in der selben Spalte

  • keine Garantie, dass Lösung gefunden wird

Suchkosten/ Offline-Kosten: Bestimmung der Kosten für das Suchen: Zeitkosten, Kosten vom Speicherplatz

Ausführungskosten: Pfadkosten, Online-Kosten

Beispiel Staubsauger (Einzustandsproblem)

Informelle Problembeschreibung:

• An einem Fluss haben sich 3 Kannibalen und 3 Missionare getroffen, die alle den Fluss überqueren wollen

• Es steht ein Boot zur Verfügung, das maximal zwei Leute aufnehmen kann.

• Es sollte nie die Situation auftreten, dass an einem Ufer Missionare und Kannibalen sind und dabei die Anzahl der Kannibalen die Anzahl der Missionare übertrifft.

  → Finde eine Aktionsfolge, die alle an das andere Ufer bringt.

• Zustände: Tripel (x,y,z) mit 0<=x,y<=3 und z<=1, wobei x, y und z angeben, wieviele Missionare, Kannibalen und Boote sich zur Zeit am Ausgangsufer befinden

• Anfangszustand: (3,3,1)

• Operatoren: Von jedem Zustand aus entweder einen Missionar, einen Kannibalen, zwei Missionare, zwei Kannibalen, oder einer von jeder Sorte über den Fluss bringen (also 5 Operatoren)

• Beachte: Nicht jeder Zustand damit erreichbar [z.B. (0,0,1)] und einige sind illegal.

• Endzustand (0,0,0)

• Pfadkosten 1 Einheit pro Flussüberquerung

Kriterien:

• Vollständigkeit: Wird immer eine Lösung gefunden, sofern es eine gibt?

• Zeitkomplexität: Wie lange dauert es (im schlechtesten Fall) bis eine Lösung gefunden ist?

• Platzkomplexität: Wie viel Speicher benötigt die Suche (im schlechtesten Fall)?

• Optimalität: Findet das Verfahren immer die beste Lösung?

uninformierte oder blinde Suche:

keine Information über die Länge oder Kosten eines Lösungspfades

Breitensuche

Uniforme Kostensuche

Tiefensuche

Tiefenbeschränkte Suche

Iterative Tiefensuche

Bidirektionale Suche

CSPs bilden eine spezielle Problemklasse, die aufgrund struktureller

Einschränkungen besondere Suchtechniken erlauben.

• Zustände sind durch Werte von Variablen definiert.

• Operatoren belegen eine Variable mit einem Wert.

• Der Zieltest wird durch Constraints (Bedingungen) spezifiziert, welche die Variablenbelegungen erfüllen müssen.

• Ein Zielzustand ist eine Belegung der Variablen mit Werten, die alle Constraints erfüllen

Das 8 Damen Problem als CSP:

• Es gibt 8 Variablen V1, ..., V8, wobei Vi für die Dame in der i-ten Spalte steht.

• Vi kann einen Wert von aus {1, 2, ..., 8} annehmen, der für die Zeilenposition steht.

• Zwischen allen Paaren von Variablen gibt es Constraints, welche die Nichtangreifbarkeit ausdrücken.

→ diskretes, endliches, binäres CSP

Einfärben von Graphen als CSP:

Gegeben ein Graph mit n Knoten, färbe die Knoten mit k Farben so ein, dass zwei durch eine Kante verbundene Knoten nicht die gleiche Farbe haben (→ NP-vollständiges Problem!)

Beispiel: Kann der folgende Graph mit 3 Farben eingefärbt werden?

Standardsuche für das Einfärbesystem:

Allgemeine Suche zum CSP lösen:

• Tiefensuche ist bei CSPs vollständig, da ja nur maximal n Operatoren (Belegung von Variablen durch Werte) möglich sind.

• Bei naiver Implementation ist der Verzweigungsfaktor sehr hoch! Sei Di die Menge der möglichen Werte für Vi . Dann ist der Verzweigungsfaktor b = ∑n i=1 Di .

• Die Reihenfolge der Instantiierungen der Variablen ist für die Lösung unerheblich. Deshalb kann mann bei jeder Expansion eine Variable (nicht-deterministisch) aussuchen, d.h. der Verzweigungsfaktor ist (∑ni=1 Di )/n.

• Nach jeder Operatoranwendung kann geprüft werden, ob bereits Constraints verletzt wurden. In dem Fall braucht man den aktuellen Knoten nicht weiter expandieren → Tiefensuche + Test = Backtracking (oder Rücksetzsuche)

Vorwärtstest und Kantenkonsistenz:

Wenn beim Backtracking Entscheidungen getroffen wurden, die eine

Lösung unmöglich machen, wird dies u.U. doch erst in den Blättern

des Suchbaums bemerkt → unnötige Exploration des Unterbaums.

Lösungen:

• Vorwärtstest (Forward checking): Bei allen noch nicht belegten Variablen werden die Werte eliminiert, die nicht mehr möglich sind. Backtracking, falls Domain einer Variable leer wird.

• Spezielle Form des Vorwärtstests: Kantenkonsistenz (Arcconsistency). Ein CSP ist kantenkonsistent, falls der Wertebereich jeder Variablen nur Werte enthält, die konsistent mit jedem Constraint auf der Variablen sind.

Beispiel:

Die Funktion ist höchstens

Wir müssen 1000 Werte sortieren, System würde nie mehr als 1000 Schritte machen

Meisten Systeme brauchen nlogn(o(n^2)) Schritte

Wir haben eine Stadt, man weiß nicht wo die Leitungen liegen, sonst weiß man wie viel Wert das Unternehmen ist

Man betrachtet einen Haushalt mit wie vielen KWatt Stunden verbrauch

O wächst sehr schnell (n= 1500 geht noch n=2000 dauert ewig)

Zeitkomplexität: Je tiefer,desto mehr Zeit wird benötigt zur Berechnung

Platzkomplexität: Breite verbaucht viel Speicher, je weniger desto besser

Optimalität: Wird immer die beste Lösung gefunden?

Vollständigkeit: Wird immer eine Lösung gefunden?

Tiefensuche nicht optimal, warum?

Verzweigungsgrad (Exponent)

• Gehören zu den Optimierungsverfahren

• Idee: keine Garantie des Findens der optimalen Lösungen, Erhöhung der Sucheffizienz → Heuristiken

• Heuristiken (oft auch als “single pass heuristic” bezeichnet) sind auf Erfahrung (“rules of thumb”) beruhende Vorgehensweisen zur Erzeugung von guten, aber nicht notwendigerweise optimalen Lösungen.

• Durch die Implementierung von Heuristiken werden also problembezogenes Erfahrungswissen und plausibel erscheinende Vorgehensweisen formalisiert Hauptproblem liegt in der Identifikation einfacher heuristischer Vorgehensweisen, die möglichst gute Lösung bezüglich vorgegebener Zielkriterien liefern.

• Heuristiken basieren häufig auf Greedy-Strategien

• Beispiele für Heuristiken sind Prioritätsregeln in der Produktionssteuerung, welche für die Reihenfolgeplanung von Arbeitsgängen im Rahmen der Fertigungsauftragsplanung eingesetzt werden können. Hierbei werden durch Prioritätsregeln Arbeitsaufträge, welche in einer Wartschlange vor einzelnen Maschinen zur Bearbeitung anstehen, entsprechend ihrer Charakteristika und abhängig vom aktuellen Stand des Produktionssystems eingeplant.

• Konstruktionsheuristiken

  • Auch bekannt als single-pass Heuristiken

  • Erzeugen Lösung in einem Durchgang

    • starten mit einer leeren Lösung

    • Mehrere Schritte

    • Pro Schritt wird ein Teil der Lösung festgelegt

    • Oft: Festlegen einer Entscheidungsvarialbe pro Schritt

  • Stoppen, wenn Lösung vollständig ist

  • Keine Verbesserungsschritte

• Verbesserungsheuristiken

  • Starten mit einer vollständigen Lösung

  • Verbesserung der Lösung

    • Mehrere Schritte

    • Mögliche Veränderung der Lösung definieren eine Nachbarschaft

    • Keine Diversifikation: Nur Schritte erlaubt, die Qualität der Lösung erhöhen

    • Wenn keine Verbesserung der Lösung mehr notwendig: Stoppen der Heuristik

Traveling Salesperson Problem

Ziel: Verbinde n Städte mit Pfad T minimaler Distanz l

Gegeben: Distanzen zwischen den n Städten.

Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzen Station ist.

Gegeben: Städteindizes, Distanzmetrik

Finde: eine Permutation

Wachstum des Suchraums: (Tabelle)

n 10 100 1000 10000

n^2 100 10000 10^6

Problem des Handlungsreisenden

Mehrere Reisen (mehr als 2)

Bestimmter Name

ECO Strecke, Autobahn Strecke, Schnellste Route,…

K-opt Heuristik:

• Verbesserungsheuristik

• Verallgemeinerung von 2-opt. Untersuchen Sie einige oder alle

k-Teilmengen von Kanten in einer Tour

• Wenn der Austausch von k Kanten die Tour nicht verbessert, ist die Tour k-optimal

• Wenn die Dreiecksungleichung gilt, ist der schlechteste Leistungsgrad von

  k-opt höchstens

Strategien:

Random Neighbor, Next Improvement, Best Improvement

Treshold Accepting Algorithmus

• lokale Suche

• akzeptiert Verschlechterungen solange sie nicht schlechter als ein vorgegebener Schwellenwert sind

• Schwellenwert wird im Verlauf der Optimierung gesenkt

• Ziel: Globale Optimierung in komplexen Suchräumen.

• Vorgehen:

  • Zufällige Festlegung eines Schwellenwerts.

  • Iterative Schritte, bei denen neue Schwellenwerte akzeptiert werden, wenn sie zu Verbesserungen in der Zielfunktion führen.

• Charakteristik:

  • Stochastischer Ansatz.

  • Ermöglicht die Suche nach akzeptablen Lösungen, ohne sich auf lokale Minima zu beschränken.

• Beispiel:

  • Ein Beispiel für die Anwendung von Threshold Accepting ist das Problem der Bildsegmentierung. Angenommen, Sie möchten automatisch die Konturen eines Objekts in einem Bild identifizieren. Sie könnten Threshold Accepting verwenden, um einen Schwellenwert für die Intensität der Pixel festzulegen. Während des Algorithmus könnten neue Schwellenwerte akzeptiert werden, wenn sie zu einer besseren Segmentierung des Objekts führen. Dies ermöglicht die flexible Anpassung des Schwellenwerts, um optimale Ergebnisse in Bezug auf die Bildsegmentierung zu erzielen.

Simulated Annealing Algorithmus = Metropolis Algoithm

• akzeptiert Verschlechterungen in der Bewertung eines Zwischenergebnisses nur mit einer bestimmten – im Verlauf der Optimierung kleiner werdenden – Wahrscheinlichkeit

• Ziel: Globale Optimierung durch Simulation des Abkühlens eines physikalischen Systems.

• Vorgehen:

  • Start mit einer zufälligen Lösung.

  • Durchführung von zufälligen Schritten, wobei schlechtere Lösungen unter bestimmten Bedingungen akzeptiert werden.

  • Temperaturparameter wird allmählich verringert, um die Wahrscheinlichkeit der Akzeptanz schlechterer Lösungen zu reduzieren.

• Charakteristik:

  • Inspiriert von metallurgischem Abkühlen, um energetisch günstigere Zustände zu erreichen.

  • Stochastischer Ansatz, der lokale Minima überwinden kann.

  • Erlaubt zeitweilige Verschlechterungen der Lösung, um aus dem Suchraum zu entkommen.

• Beispiel:

  • Ein Beispiel für die Anwendung von Simulated Annealing ist das Problem des Handlungsreisenden (Traveling Salesman Problem, TSP). In diesem Problem muss der Handlungsreisende eine Route finden, die alle Städte in einem Netzwerk besucht, wobei die Gesamtstrecke minimiert werden soll. Simulated Annealing kann hier eingesetzt werden, um eine gute Näherungslösung zu finden, indem es schrittweise durch den Lösungsraum geht und zeitweise schlechtere Lösungen akzeptiert, um lokale Minima zu überwinden und eine bessere globale Lösung zu erreichen.

• starte mit zufällig ausgewählter Lösung

• 2-opt random improvement Nachbarschaft

• Kühlschema

  • setze T_0 so, dass 3% der Lösungen, die schlechter sind

maschinelles Lernen, adaptive Systeme und komplexitätstheoretische Fragestellungen.

Adaptive Systeme: Ein adaptives System ist ein System, das seine Verhaltensweisen und Strukturen automatisch an sich ändernde Bedingungen oder Umgebungen anpassen kann. In Bezug auf Simulated Annealing könnte das beispielsweise ein Schema oder ein Temperaturplan sein, der in Echtzeit angepasst wird, basierend auf den Ergebnissen der bisherigen Exploration.

Im Bereich maschinelles Lernen könnte Simulated Annealing dazu genutzt werden, Optimierungsprobleme bei der Modelltrainierung zu lösen, indem es hilft, lokale Minima in Verlustfunktionen zu überwinden und somit bessere Modelle hervorzubringen. Die Möglichkeit, Schemata und Abkühlpläne dynamisch anzupassen, würde dabei eine adaptive Optimierung ermöglichen.

Treshold Accepting

Record to Record

Great Deluge Algorithm

Heuristik

Idee: akzeptiere eine Lösung, wenn…

• Grundidee: Inspiriert von Simulated Annealing, senkt schrittweise einen Schwellenwert ab, um systematisch nach Verbesserungen zu suchen.

• Anwendung: Häufig für kombinatorische Optimierungsaufgaben.

• Einschränkungen: Kann möglicherweise zu langsam sein, um in großen Suchräumen zu konvergieren.

Der Great-Deluge-Algorithmus (GD) ist ein allgemeiner Algorithmus, der auf Optimierungsprobleme angewendet wird. Er ähnelt in vielerlei Hinsicht den Hill-Climbing- und Simulated-Annealing-Algorithmen.

Der Name leitet sich von der Analogie ab, dass eine Person, die einen Hügel erklimmt, bei einer großen Überschwemmung versucht, sich in jede Richtung zu bewegen, in der sie keine nassen Füße bekommt, in der Hoffnung, einen Weg nach oben zu finden, wenn der Wasserspiegel ansteigt.

Bei einer typischen Implementierung von GD beginnt der Algorithmus mit einer schlechten Annäherung, S, an die optimale Lösung. Auf der Grundlage von S wird ein numerischer Wert, die so genannte Schlechtigkeit, berechnet, der angibt, wie unerwünscht die anfängliche Annäherung ist. Je höher der Wert der Schlechtigkeit ist, desto unerwünschter ist die ungefähre Lösung. Ein weiterer numerischer Wert, die Toleranz, wird auf der Grundlage einer Reihe von Faktoren berechnet, zu denen häufig auch die anfängliche Schlechtigkeit gehört.

Auf der Grundlage von S wird eine neue Näherungslösung S' , genannt Nachbar von S, berechnet. Die Schlechtigkeit von S' , b' , wird berechnet und mit der Toleranz verglichen. Ist b' besser als die Toleranz, wird der Algorithmus rekursiv neu gestartet mit S : = S' , und Toleranz := decay(Toleranz) , wobei decay eine Funktion ist, die die Toleranz senkt (was einen Anstieg des Wasserspiegels darstellt). Wenn b' schlechter als die Toleranz ist, wird ein anderer Nachbar S* von S gewählt und der Vorgang wiederholt. Wenn alle Nachbarn von S Näherungslösungen jenseits der Toleranz ergeben, wird der Algorithmus beendet und S als die beste erhaltene Näherungslösung angegeben.

Idee: akzeptiere eine Lösung, wenn ihre Güte…

Bei Record to Record Travel ist der Record die Gesamtentfernung der besten bisher beobachteten Lösung und die Abweichung ist r% des Records. Wenn der Zielfunktionswert kleiner als Record + Abweichung ist, wird die neue Lösung ausgewählt. Bergaufwärtsbewegungen sind erlaubt, um zu vermeiden, dass man in einem schlechten lokalen Minimum gefangen ist.

• Grundidee: Nutzt den aktuellen Rekord als Referenzpunkt und versucht schrittweise, diesen Rekord zu verbessern.

• Anwendung: Flexibel und kann für verschiedene Arten von Optimierungsproblemen angepasst werden.

• Einschränkungen: Die Effizienz hängt von der Definition des Nachbarschaftsoperators und anderen Parametern ab.

Kann nur Besser, Gleichgut oder nur um eine bestimmte Konstante besser sein

Beste Lösung ist bei 90%

1) Gradient Ascent

• Grundidee: Verfolgt den Gradienten der Zielfunktion, um die Richtung zu finden, in der die Funktion am schnellsten ansteigt.

• Anwendung: Geeignet für kontinuierliche Optimierungsaufgaben.

• Einschränkungen: Kann in lokalen Minima stecken bleiben und ist empfindlich auf die Wahl des Startpunkts.

2) Great Deluge Algorithmus (gestrichelte Linie ist Wasserstand mit Pfeil geht also nach oben, man akzeptiert nur bessere Lösung)

• Grundidee: Inspiriert von Simulated Annealing, senkt schrittweise einen Schwellenwert ab, um systematisch nach Verbesserungen zu suchen.

• Anwendung: Häufig für kombinatorische Optimierungsaufgaben.

• Einschränkungen: Kann möglicherweise zu langsam sein, um in großen Suchräumen zu konvergieren.

3) Treshold Accepting

• Grundidee: Verwendet einen zufälligen Schwellenwert und akzeptiert Lösungen, die Verbesserungen in der Zielfunktion bewirken, auch wenn sie den Schwellenwert überschreiten.

• Anwendung: Häufig bei kombinatorischen Optimierungsproblemen und Bildsegmentierung.

• Einschränkungen: Erfordert die richtige Wahl des Schwellenwerts für optimale Ergebnisse.

4) Record-to-Record Algorithmus

• Grundidee: Nutzt den aktuellen Rekord als Referenzpunkt und versucht schrittweise, diesen Rekord zu verbessern.

• Anwendung: Flexibel und kann für verschiedene Arten von Optimierungsproblemen angepasst werden.

• Einschränkungen: Die Effizienz hängt von der Definition des Nachbarschaftsoperators und anderen Parametern ab.

Allgemein:

Floorplanung ein nur (kleiner) Schritt im “IC Design and Verification Flow”

• Aufgaben der Floorplanung: Berechnen einer Startlösung für die “Placement”

und “Routing” Schritte

• obwohl bei der Floorplanung kleinere Instanzen optimiert werden, sind sie bereits zu groß für direkte Methoden

• Simulated Annealing hat sich wegen der Einfachheit und Anpassungsfähigkeit

etabliert, benötigt drei Komponenten

1. Formale Beschreibung bzw. Simulationsmodell einer Lösung

2. Suchraumoperatoren

3. Zielfunktion

• sollte die Aufgabe zu groß für den direkten Einsatz einer (Meta-)Heuristik sein,

bieten hierarchische Divide-and-Conquer Verfahren einen Ausweg

Ziele:

Erzeugung eines Floorplans, der gut geroutet werden kann

• Komplexe (nicht rechteckige) und variable Modulformen

• Abschätzung des Erfolgs des Routing-Schrittes und der Leitungsdichte der Routing-Kanäle

Definition:

Aufgabenstellung

• sei B = {b1 , b2 , . . . , bm } eine Menge auf m rechteckigen Modulen mit der Breite, Höhe und Fläche wi , hi , und ai , 1 Æ i Æ m

• Module können rotiert werden

• sei (xi , yi ) die Koordinate der unteren, linken Ecke des Moduls bi ,

• ein Floorplan F ist eine Zuweisung von (xi , yi ) an jedes bi sodass sich keine Module überlappen

• das Ziel ist die Minimierung einer Kostenfunktion, die beispielsweise die Fläche und Leitungslängen minimiert

Optimierungsziele:

• Fläche

• Summe der Leitungslängen

• Längen der kritischen Pfade

• “Routability”

• Leistungsverbrauch

• Temperaturverteilung

Nebenbedingungen:

• Breite und Höhe des Dies

• Wäremleitfähigkeit

• Seitenverhältnis

• . . .

Abschätzen der Optimierungsziele:

• Fläche:

  • kleinsten umfassendes Rechteck

• Leitungslängen

  • half-perimeter wire length (HPWL)

Slicing:

• Sukzessive aufteilbar duch geradlinige Schnitte (horizontal und vertikal)

• Kodierung:

  • ein Slicing Tree ist ein binärer Baum mit Modulnamen an den

    Blättern und Schnitttypen an den inneren Knoten

  • zwei Schnitttypen

    • h - horizontal

    • v - vertical

  • zu einem Slicing Floorplan kann es mehrere Slicing Trees geben

    • Skewed Slicing Tree: enthält keinen Knoten des gleichen Schnitttyps wie sein rechtes Kind

    • eindeutige Kodierung eines Slicing Floorplans

  • Constraint Graphs = Slicing Floorplan

    • slicing Floorpläne können nicht zur Modellierung genereller Floorpläne verwendet werden

    • Horizontal und Vertikal Constraint Graphs (HCG, VCG) sind ein flexibleres Modell zur Kodierung von Floorplänen

      • ein Knoten repräsentiert ein Modul

      • falls es eine Kante zwischen A und B im HCG (VCG) gibt, ist Modul A der linke (untere) Nachbar des Moduls B

Non Slicing:

• nicht durch wiederholte gerade Schnitte teilbar

• Kodierung:

  • slicing Floorpläne können nicht zur Modellierung genereller Floorpläne verwendet werden

  • Horizontal und Vertical Constraint Graphs (HCG, VCG) sind

    ein flexibleres Modell zur Kodierung von Floorplänen

    • ein Knoten repräsentiert ein Modul

    • falls es eine Kante zwischen A

    und B im HCG (VCG) gibt, ist Modul A der linke (untere) Nachbar des Moduls B

Slicing Floorpläne:

Beispiel:

v

/ \

h h

/ \ / \

1 2 h 5

/ \

3 4

(1h2)v((3h4)h5) Infix

v(h12)(h(h34)5) Prefix

Postfix: (Normalisierte Polnische Notation)

• ein Skewed Slicing Tree

  • ein Skewed Slicing Tree enthält keinen Knoten des gleichen Schnitttyps wie sein rechtes Kind -> ein Ausdruck in normalisierter Polnischer Notation enthält keine Sequenzen gleichen Schnitttyps, wie beispielsweise “hh” oder “vv”

• “balloting” Eigenschaft Polnischer Notation:

  In jedem Teilausdruck ist die Anzahl der Operanden größer als die Anzahl der Operatoren

• Suchraumgröße:

  • habe ein Floorplan mit n Modulen einen Normalisierte Polnische Notation Ausdruck mit n Operanden (und n ≠ 1 Operatoren)

• adjazente Operanden: wenn es keinen weiteren Operanden zwischen den Operanden gibt

• adjazente Operatoren: wenn es keine weiteren Operande und keinen weiteren Operator zwischen den Operatoren gibt

• Operand und Operator sind adjazent: wenn sie in der Sequenz benachbart

  sind

• Kette: ist eine Sequenz aus adjazenten Operatoren

  • in Ausdrücken in normalisierter Polnischer Notation dürfen nur

    “hvh. . . ” und “vhv. . . ” auftreten

• Op1: vertausche zwei adjazente Operanden

• Op2: invertiere eine Operatorkette “v” -> “h” und “h” -> “v”

  • Op1 und Op2 angewendet auf Ausdruck in normalisierter Polnischer Notation erzeugen immer einen Ausdruck in normalisierter Polnischer Notation

• Op3: tausche adjazente Operanden und Operatoren

  • kann Ausdrücke erzeugen, die die “balloting” Eigenschaft verletzen (“hh”, “vv”)

  • überprüfe, ob der resultierende Ausdruck normalisiert ist

    • sei Ni die Anzahl der Operatoren im Ausdruck (e1 e2 . . . ei )

    • im Ausdruck in gültiger normalisierter Polnischer Notation muss es immer weniger Operatoren als Operanden geben; es sollte immer gelten: 2Ni < i

  • Tausch adjazenter Operanden ei und Operatoren ei+1 möglich, falls:

    2Ni+1 < i

ausgeführte Operatoren:

• Op1: tausche adjazente Operanden 4 und 3

• Op2: invertiere die letzte Kette vh

• Op3: tausche Operand und Operator h4

Unterfunktionsart von Fitnessfunction oder loss function

allgemeinübliche Metriken

• Fläche A; nomalisierte Fläche A_norm

• Leitungslänge W; normalisierte Leitungslänge W_norm

  • während des Floorplanning wird kein Routingschritt ausgeführt; Schätze Leitungslänge durch “half-perimeter wire length”

  • “half-perimeter wire length” (HPWL) ist der halbe Umfang des kleinsten Rechtecks, dass alle Pins umschließt

  • sollten Position der Pins nicht spezifiziert sein, können Modulmittelpunkte verwendet werden

• um normalisierte Werte berechnen zu können, werden m zufällige Floorpläne erzeugt und die durchschnittlichen Flächen und Leitungslängen berechnet

  • m sollte zu n proportional sein

sei aE [0, 1], dann

Beispiel:

Beispiel 2: Berechnung der HPWL (half-perimeter wire length)

Manhatten lenght

half perimeter wire lenght

50% wertung (Kostenfunktion,so klein wie möglich)

Simulated Annealing

wir haben bereits drei Komponenten

• Kodierung

  • eindeutig

  • vollständig, d.h. alle Slicing Floorpläne können kodiert werden

  • Suchraum schnell wachsend mit

• Suchraumoperatoren für Lösungen

  • vollständig, d.h. alle Lösungen können in endlicher Anzahl Schritte und gestartet von zufälliger Initiallösung generiert werden

• Zielfunktion als Linearkombination der Fläche und der Leitungslängenabschätzung

  • Fläche eines Floorplans kann in Polynomialzeit berechnet werden

  • HPWL kann effizient approximiert werden

SA für Floorplanung

• initiale Temperatur T1 <- - delta_avg/ ln(P) mit P als Akzeptanzkriterium für verschlechternde Lösungen (uphill move); P ist am Anfang nahezu 1.0

• durchschnittliche “uphill move” Kosten werden berechnet durch:

  1. mehrmaliges Permutieren einer zufälligen Lösung

  2. Mitteln der Kostenverschlechterung

• E als Abbruchtemperatur

• geometrisches Kühlschema mit r = 0.85

• k als die Anzahl der Iterationen in jeder Temperaturebene

Fast Simulated Annealing

• Beobachtung: das Akzeptieren vieler schlechter Lösungen am Anfang der Suche verlangsamt die Konvergenz

• Verbesserung

  1. führe Hochtemperatur-Zufallssuche am Anfang (T -> unendlich)

  2. führe im zweiten Drittel lokale Suche (Hill Climbing, T -> 0) aus

  3. führe regulären SA Lauf im letzen Drittel aus

Allgemein:

• ein kompaktierter Floorplan ist ein Floorplan, bei dem kein Modul mehr nach links oder unten verschoben werden kann

• ein kompaktierter Floorplan kann durch einen B* Baum kodiert werden

• bei einem B* Baum haben alle inneren Knoten genau zwei Kindsknoten; weiterhin ist der Baum “geordnet”, d.h. es existiert eine Sortierung der Baumknoten

• die Zuordnung zwischen B* Bäumen und Floorplänen ist eindeutig

  • zu einem kompaktierten Floorplan gibt es genau eine Kodierung als B* Baum

  • ein B* kodiert genau einen Floorplan

Von Floorplan -> B* Baum:

1. kompaktiere den Floorplan durch verschieben der Module nach links und unten

2. baue einen B* Baum von der Wurzel an auf; Reihenfolge der besuchten Module/ hinzugefügten Knoten - Tiefensuche

   • baue rekursiv zuerst den linken Unterbaum dann den rechten Unterbaum auf

   • Beispiel: Sei Ri die Menge aus Modulen, die adjazent zu und rechts von Modul (i) platziert sind; z.B. i = (3) und r = {4}; der linke Kindknoten von n3 entspricht dem tiefsten, nicht besuchten Modul in R3: (4); der rechte Kindsknoten von n3 entspricht dem tiefsten Modul über Modul (3) mit der selben x-Koordinate wie Modul (3): Modul (6)

Von B* Baum -> Floorplan:

zu einem B* Baum T kann der zugehörige Floorplan wie folgt berechnet

werden:

• der Wurzelknoten in T repräsentiert das tiefste Modul auf der linken Seite des Floorplans

• ist der Knoten nj das linke Kind des Knotens ni , dann wird das Modul (j)

  adjazent zu modul (i) und (j) wird rechts von (i) platziert

• ist der Knoten nj das rechte Kind des Knotens ni , dann wird das Modul (j) über dem Modul (i) platziert; die x-Koordinaten von (i) und (j) stimmen überein

Berechnung der normalisierten Floorplanfläche

• die Fläche eines adjazenten Floorplans kann in O(1) berechnet werden

  
  

  die Suchraumgröße der B* -Bäume

• die Anzahl der Floorpläne für B* Bäume mit n Konten beträgt (ähnlich zu normalisierten Polnischen Ausdrücken)

Operatoren für B* Bäume

folgende drei Operatoren können verwendet werden, um adjazente B* Bäume zu

erzeugen

• Op1: rotieren eines Moduls

• Op2: Neuplatzieren eines Moduls im B* Baum

• Op3: Tausch zweier Module

Op1 und Op3 können die Topologie eines Baums nicht ändern

Op2 ist als eine Knotenlöschung deletion und Knoteneinfügung insertion imple-

mentiert; die Löschung eines Knotens unterteilt sich in drei Fälle

• Blattknoten: kann ohne weitere Nebenbedingungen gelöscht werden

• ein Knoten mit einem Kind: der Kindsknoten ersetzt den Elterknoten

• ein Knoten mit zwei Kindern: einer der Kindsknoten ersetzt den Elterknoten; falls der Kindsknoten selber Unterknoten hat, wird das gleiche Ersetzungsschema fortgeführt, bis man auf ein Blatt trifft

ein Knoten kann an zwei Positionstypen eingefügt werden

• externe Position, als ein Blattknoten

• interne Position, zwischen zwei Knoten im B* Baum

Beispiel: B* Baumtransformation

Kodierung:

• für die Kodierung allgemeiner Floorpläne sind die normalisierte Polnische Notation und die B ú Bäume nicht geeignet

• ein Sequenzpaar besteht aus zwei geordneten Listen mit Modulnamen; z.B. kodiert das Sequenzpaar (124536, 326145) ein Floorplan mit sechs Modulen (1),(2),. . . ,(6)

• Wie kommt man von einem Floorplan zu einem Sequenzpaar?

  1. alle Module müssen “Räumen” zugewiesen werden

  2. in jedem “Raum” darf exakt ein Modul sein

Berechnung eines Sequenzpaares:

• für ein Modul kann der positive und negative Pfad definiert werden

• der positive Pfad setzt sich aus dem right-up Pfad und dem left-down Pfad zusammen

• der right-up Pfad des Moduls i wird bestimmt als

  • der Pfad startet im Mittelpunkt des Moduls und läuft nach rechts

  • der Pfad wechselt die Laufrichtung zwischen “rechts” und “aufwärts”, wenn er auf

    1. eine Seite eines Raums

    2. einen anderen Pfad

    3. den Chiprand

    trifft.

  • der right-up Pfad ist vollständig, wenn er auf die obere rechte Ecke des Chips trifft

positive (negative) Pfade kreuzen sich nicht

• positive (negative) Pfade können linear geordnet werden und induzieren damit eine Ordnung für Module

• sei T+ die lineare Sortierung aller positiver Pfade, die aus right-up und left-down Pfaden konstruiert worden sind (linkes Bild: T+ = {124536})

• sei T- die lineare Sortierung aller negativer Pfade, die aus up-left und down-right Pfaden konstruiert worden sind (rechtes Bild: T- = {326145})

• dann kodiert das Sequenzpaar (T+ , T- ) = (124536, 326145) den Floorplan eindeutig

• die geometrische Relation der Module i und j folgt zwei Regeln

  1. das Modul i ist links von Modul j, wenn i vor j in T+ und T- einsortiert ist

  2. das Modul i ist unterhalb des Moduls j, wenn i nach j in T+ und vor j in T- einsortiert ist

Erstellung eines Floorplans mithilfe der Sequenzpaarkodierung

• erstelle für einen Floorplan mit n Modulen ein n x n Gitter

• beschrifte vertikale und horizontale Gitterlinien mit Modulnamen gemäß ihrer Sortierung in T+ und T- , von oben nach unten und von links nach rechts

• rotiere das Gitter gegen den Uhrzeigersinn um 45°

• platziere jedes Modul i an der Gitterkreuzung (i, i)

die Konstruktion der Horizontal- und Vertical-Constraint Graphen

• Konstruktion des HCGs GH (V, E)

  • V : besteht aus einer Quelle s, einer Senke t, und allen Modulnamen

  • E: umfasst für jedes Modul i die Kanten (s, i) und (i, t) sowie alle Kanten (i, j) gdw. i der linke Nachbar von j ist (horizontal constraint)

  • Gewichtung der Knoten: Null für s and t, die Breite des Moduls i für den Knoten i

• der VCG GV (V, E) kann analog konstruiert werden (diesmal mit den Modulhöhen als Knotengewichten)

124536 miteinander vergleichen 326145:

linkes Bild: 1 ist links von 4,5; 2 ist links von 4,5;…

rechtes Bild: 6 nach 1 lins, 6 vor 1 rechts -> 6 liegt unter 1; …

Flächenberechnung

• die x-Koordinate eines Moduls i wird durch den längsten Pfad von s nach i in GH bestimmt

• die y-Koordinate eines Moduls i wird durch den längsten Pfad von s nach i in GV bestimmt

• die Breite und Höhe eines Floorplans können nun als die längsten Pfade zwischen s unt t in GH und GV berechnet werden

• die Berechnung des längsten Pfades in einem gerichteten, azyklischen Graph (DAG) benötigt O(N^2 ) Zeit Suchraumgröße

• Jede Permutation von T+ und T- erzeugt gültige Floorpläne

• T kann n! Mal permutiert werden

• insgesamt ergeben sich für ( T+ , T- ) (n!)^2 Permutationsmöglichkeiten

Operatoren:

• Op1: Rotieren eines Moduls

• Op2: Tausch von zwei Modulen in einer Sequenz

• Op3: Tausch von zwei Modulen in beiden Sequenzen

• Fast Simulated Annealing kann nun auf Sequenzpaare angewendet werden (wie im Slicing Floorplans Fall)

Wenn es regnet dann gibt es wolken

Wenn es niederschlag gibt und es unter 0 grad ist schneit es

KNN ist realitätsnah

Reale Anwendungen sind komplex deswegen symbolverarbeitend nicht möglich

Multilayer Perzeptron

CNN (Feedforward Netze)

Rekurrente Netze (RNN)

Long Short Term Memory

1. Architektur und Anwendung:

• LSTM (Recurrent Neural Network):

  • Architektur: LSTMs sind rekurrente neuronale Netzwerke, die auf die Verarbeitung von sequenziellen Daten ausgerichtet sind, wie z.B. Zeitreihen oder natürliche Sprache.

  • Anwendung: Häufig verwendet für Aufgaben wie maschinelles Übersetzen, Textgenerierung und Zeitreihenvorhersage.

• CNN (Convolutional Neural Network):

  • Architektur: CNNs sind spezialisiert auf die Verarbeitung von Gitterdaten wie Bildern und arbeiten gut mit hierarchischen Merkmalen.

  • Anwendung: Hauptanwendungen sind Bildklassifikation, Objekterkennung und Bildsegmentierung.

2. Datenstruktur:

• LSTM:

  • Geeignet für sequenzielle Datenstrukturen, bei denen die zeitliche Abhängigkeit der Daten wichtig ist.

  • Speichert und verarbeitet Informationen über lange Zeiträume hinweg und kann somit auf zeitliche Muster zugreifen.

• CNN:

  • Optimal für Gitterdaten wie Bilder, bei denen lokale Strukturen und Hierarchien von Merkmalen von Bedeutung sind.

  • Verwendet Convolutional Layer, um lokale Muster in den Daten zu erfassen.

3. Verwendung von Gewichtungen:

• LSTM:

  • Verwendet Gewichtungen und spezielle Zellzustände, um die Modellierung von langfristigen Abhängigkeiten in Sequenzen zu ermöglichen.

  • Eignet sich gut für Aufgaben, bei denen zeitliche Zusammenhänge wichtig sind.

• CNN:

  • Verwendet Faltungsschichten, um Merkmale in lokalen Bereichen der Daten zu extrahieren und sie über die Hierarchie des Netzwerks zu aggregieren.

  • Optimal für Aufgaben, bei denen lokale Muster in den Daten entscheidend sind.

4. 3D-Struktur:

• LSTM:

  • LSTMs können für eine Dimension (eine Zeitreihe), zwei Dimensionen (z.B. Text) oder mehr angewendet werden.

• CNN:

  • Häufig für zweidimensionale Datenstrukturen wie Bilder verwendet, aber es gibt auch 1D- und 3D-CNN-Architekturen.

Overfitting verhindern

Wofür ist es?

Dropout Regularisierung (Während des Trainings werden Gewichtungen für ca. 80% der Knoten geändert)

L2 Regularisierung

L1 Regularisierung

Data Augmentation

Aufteilung der Daten in Trainings Validierungs und Testdaten

Konvolution ist ein anderer Begriff für die lineare Faltung. Letztendlich ist diese ein lineares Filter mit einer um 180° gedrehten Filtermaske.

Vergleich mit Multilayer Perzeptronen

Merkmalsextraktion durch Neuronales Netz, Filter werden auch gelernt, benachbarte Pixel haben eine Abhängigkeit zueinander

Die Merkmale werden gelernt, Filter werden gelernt

1. Lokale Rezeptive Felder:

• CNNs verwenden lokale Rezeptive Felder, um Informationen in kleinen Bereichen der Eingabedaten zu erfassen. Dies ermöglicht es dem Netzwerk, lokale Muster und Strukturen zu identifizieren.

2. Faltungsschichten:

• Anstatt jedes Neuron mit allen Eingangsneuronen zu verbinden (wie in vollständig verbundenen Schichten), verwenden CNNs Faltungsschichten. Diese Schichten führen Faltungsoperationen auf den Eingabedaten durch, um Merkmale zu extrahieren.

3. Gewichtete Verbindung (Shared Weights):

• CNNs verwenden gemeinsam genutzte Gewichtungen (geteilte Gewichtungen) für die Faltungsschichten. Dies bedeutet, dass die gleichen Gewichtungen auf verschiedene Bereiche der Eingabedaten angewendet werden. Dies führt zu einer geringeren Anzahl von Parametern und ermöglicht das Erlernen von Merkmalen, die in verschiedenen Teilen der Daten wiederverwendet werden können.

4. Pooling-Schichten:

• Nach den Faltungsschichten enthalten CNNs oft Pooling-Schichten, um die räumliche Dimension der Daten zu reduzieren. Pooling aggregiert Informationen über kleine Bereiche und reduziert die Anzahl der Parameter im Netzwerk.

5. Hierarchische Struktur:

• CNNs haben oft eine hierarchische Struktur mit mehreren Schichten. Niedrigere Schichten extrahieren einfache Merkmale wie Kanten, während höhere Schichten komplexere Merkmale und Strukturen lernen.

6. Transferlernen:

• CNNs können von Transferlernen profitieren, indem sie auf vorab trainierten Netzwerken basieren. Dies ermöglicht es, Merkmale zu nutzen, die auf großen Datensätzen für ähnliche Aufgaben gelernt wurden.

7. Aktivierungsfunktionen:

• CNNs verwenden nichtlineare Aktivierungsfunktionen wie ReLU (Rectified Linear Unit), um nichtlinearere Beziehungen zwischen den Merkmalen zu modellieren.

8. Regularisierung:

• Methoden wie Dropout werden oft in CNNs verwendet, um Überanpassung zu reduzieren. Dropout deaktiviert zufällig einige Neuronen während des Trainings, um eine robustere Netzwerkstruktur zu erzielen.

9. Automatische Merkmalsextraktion:

• CNNs sind so konzipiert, dass sie automatisch relevante Merkmale aus den Eingabedaten extrahieren können, ohne dass Merkmale manuell definiert werden müssen.

CNN: Klassifizierung von Objekten

Denoising: Klassifizierung von Codierungen

Autoencoder:

Aufbau Netzte: Große Schicht (1000 Gewichte), kleinere Schichten (100 Gewichte), größere Schichten (1000 Gewichte)

Komprimierung zur Datenübertragung

Verlust von Informationen

Mittelwerte (average pooling) wird genutzt

Denoising Autoencoder:

Bilder die verrauscht sind kommen rein, man möchte die richtigen (unverrauschten) Bilder rausbekommen

1. Man hat Autoencoder (auf die Seite gelegte Sanduhrform)

2. Man steckt verrauschte Bilder rein (von Hund)

3. bekommt am Ende Bild von etwas was einem Hund ähnlich aussieht

Man steckt am Anfang Rauschen rein

Am Ende kommt Bild von etwas was einem Hund ähnlich aussieht

Tensorflow nutzt Stochastic Gradient Descent

Adam ist eine Metaheuristik,

• Overfitting vermeiden (Auswendig lernen vermeiden)

• Generalisierung: dass unvorhergesehene Daten besser bestimmt werden können

• Aufteilung der Daten in Trainings-, Validierungs- und Testdaten

• L2 und L1 Regularisierung

• Dropout Regularisierung

• Data Augmentation

  
  

Feedforward-Netze:

Knoten des Netzes sind in einzelne geordnete Schichten zusammengefasst

FF-Netz 1. Ordnung: nur gerichtete Verbindungen zwischen Schicht Nh

und Schicht Nh + 1. Das Netz ist schichtweise miteinander verbunden.

FF-Netz iter Ordnung: Neuronen einer Schicht Nh haben nur Verbindungen zu Neuronen höherer Schichten Nh + i. Verbindungen die Schichten überspringen, werden shortcut connections oder skip-layer connections genannt.

Rekurrente Netze:

Bei rekurrenten Netzen verlaufen gerichtete Verbindungen auch von

Neuronen höherer Schichten zu Neuronen niedriger Schichten. Diese

Rückkopplung kann bei Problemen mit zeitlicher Dynamik (Sequenzen)

hilfreich sein. Bei rekurrenten Netzen mit direkter Rückkopplung erhält ein Neuron nh seine Ausgabe direkt wieder als Eingabe. Bei indirekter Rückkopplung gibt es sowohl Verbindungen von Schicht Nh zu Nl , wobei l ≤ h, als auch von Schichten Nl zu Schichten Nl + k mit k ≤ h − l.

Das Perzeptron ist ein sehr einfacher Netztyp, der lediglich aus einer Eingabe- und einer Ausgabeschicht besteht. In der Trainingsphase werden an das Netz Ein/Ausgabetupel (x, t) angelegt und die Gewichte gemäß angepasst. Das Netz hat die Trainingsmenge eingelernt, wenn es alle Paare (x, t) korrekt klassifizieren kann (E = ∑ i i(yi − ti )2 = 0).

Die Neuronen sind sehr einfach aufgebaut. Es wird keine explizite

Ausgabefunktion verwendet und als Aktivierungsfunktion wird eine

einfache Schwellwertfunktion benutzt. Als mögliche

Aktivierungszustände für das Neuron sind nur die Werte 0 oder 1

zugelassen. Es gilt somit:

Wird ein fehlerhaftes aj ausgegeben, wird das Gewicht wij der Verbindung von Neuron ni nach Neuron ηj nach folgender Lernregel für einfache Perzeptrons angepasst:

Das Netz ist trainiert, wenn alle Trainingsdaten korrekt

wiedergegeben werden können. Das Perzeptron-Konvergenztheorem

von Rosenblatt sagt aus, dass das Perzeptron für alle Lernprobleme,

die prinzipiell mit dem Perzeptron lösbar sind, konvergiert.

Allerdings ist die Menge der mit einem Perzeptron lösbaren

Probleme stark eingeschränkt.

• Unter deep learning versteht man das Trainieren von Modellen mit vielen Schichten. Meist geht es um neuronale Netze.

• Hat ein KNN viele Schichten, ist das Approximationsvermögen sehr hoch - das Modell kann sehr komplexe Funktionen abbilden. Dadurch braucht Deep Learning viele Trainingsdaten (Millionen (!) von Datensätzen)

• Gleichzeitig treten eine Reihe von Problemen auf, z.B. das vanishing gradient und exploding gradient-Problem.

• Viele der Probleme sind in der Praxis handhabbar, beispielsweise durch vorsichtige Initialisierung der Parameter, spezielle selbstadaptive Trainingsverfahren (Varianten von Gradient Descent), oder Verfahren zur Regularisierung

• Deep Learning-Verfahren sind momentan der state-of-the-art für viele Praxisprobleme!

Weniger Kosten- und Zeitaufwand

Neuronale Netze sind keine Suchalgorithmen

Haben nichts miteinander zu tun

Suchalgorithmen sind Verfahren, die die beste Lösung für ein Problem finden, können bauen

Neuronale Netze können analysieren nicht bauen, verwenden Suchalgorithmen um zu klassifizieren, haben andere Aufgaben

→ zielorientierte Agenten

Formuliere: Ziel und Problem

Gegeben: Anfangszustand

Gewünscht: Erreichen eines bestimmten Ziels (eines Zustandes) durch Ausführen geeigneter Aktionen

→ Suche einer geeigneten Aktionsfolge und Ausführung dieser Folge

Ein intelligenter Agent formuliert zuerst ein Ziel, dann ein Problem, dessen Lösung ein Pfad zum Ziel ist. Danach löst er das Problem mit Suche. Zurück gibt er eine Aktion sowie alle anderen Aktionen, die notwendig sind, das Ziel zu erreichen (REMAINDER). Für einen (intelligenten) Agenten ist notwendig:

• Darstellung der Welt

• Darstellung von möglichen Handlungsoptionen

• Wissen über seinen eigenen Zustand

• Ziele

• Finden einer geeigneten (optmalen) Strategie

• a) Anfangszustand (3,3,1)

• b) nach Expansion von (3,3,1)

• c) nach Expansion von (3,2,0)

Implementierung des Suchbaums:

Datenstruktur für Knoten im Suchbaum:

• State: Zustand des Zustandsraums

• Parent-Node: Vorgängerknoten

• Operator: Operator, der den aktuellen Knoten erzeugt hat

• Depth: Tiefe im Suchbaum

• Path-Cost: Pfadkosten bis zu diesem Knoten

Funktionen zum Manipulieren einer Warteschlange (Queue):

• Make-Queue(Elements): Erzeugt eine Queue

• Empty?(Queue): Testet auf Leerheit

• Remove-Front(Queue): Gibt erstes Element zurück

• Queuing-Fn(Elements, Queue): Fügt neue Elemente ein (verschiedene Möglichkeiten)

Informierte Suche: Information über Kosten von aktuellem Knoten bis zum Ziel in Form einer Evaluierungsfunktion h, die jedem Knoten eine reelle Zahl zuweist.

Bestensuche

Greedy Search

A*-Suche

Heuristiken für CSPs

Lokale Suche

Genetische Algorithmen

• Bestensuche: Ein Suchalgorithmus, der den kürzesten Weg zu einer Lösung in einem Graphen oder Netzwerk findet, indem er schrittweise den vielversprechendsten Pfad auswählt.

• Greedy Search: Ein heuristischer Suchalgorithmus, der sich bei jedem Schritt für den nächsten Zustand entscheidet, der am vielversprechendsten erscheint, ohne jedoch die Möglichkeit zu berücksichtigen, dass dieser Schritt zu einer optimalen Lösung führt.

• A*-Suche: Ein informierter Suchalgorithmus, der die Bestensuche mit einer heuristischen Schätzung kombiniert, um die Effizienz zu steigern, indem er den vielversprechendsten Weg zum Zielknoten priorisiert.

• Heuristiken für CSPs: Techniken, die bei der Lösung von Constraint Satisfaction Problems (CSPs) eingesetzt werden, indem sie intelligente Schätzungen verwenden, um die Suche nach einer Lösung zu lenken und zu beschleunigen.

• Lokale Suche: Ein Suchalgorithmus, der sich durch einen Zustandsraum bewegt, indem er schrittweise von einer Lösung zu einer benachbarten Lösung geht, wobei nur die direkten Nachbarn betrachtet werden, um eine optimale Lösung zu finden.

• Genetische Algorithmen: Ein Optimierungsalgorithmus, der von der biologischen Evolution inspiriert ist und eine Population von Lösungen erzeugt, die sich im Laufe der Zeit durch Mutationen, Rekombination und natürliche Selektion weiterentwickeln, um bessere Lösungen zu finden.

• das genügend Speicher zur Verfügung steht

• Ist die Speicherplatzbeschränkung zu restriktiv, kann die optimale Lösung unerreichbar sein.

  
  

• zulässige Zielfunktion: Schätzung h(n) (Luftlinie von Arad nach Bucharest) muss immer besser/ kleiner sein als die exakte Berechnung/ tatsächliche Kosten des optimalen Pfades von n zum nächsten Ziel h*(n) (Strecke)

• h(n)<=h*(n)

Bedingung: Wenn Schätzunggenauigkeit exponentiell ansteigt und Fehler immer kleiner werden

|h*(n)-h(n)|<=O(log(h*(n))

Man kann nie so gut schätzen, deswegen wird A* nie optimal

Suchverfahren unterscheiden sich durch die Strategie zur Auswahl des Knotens im Suchbaum, der als nächstes expandiert werden soll.

Uninformierte Suche: starre Strategien ohne Information über Kosten von aktuellen Knoten bis Ziel.

Informierte Suche: Information über Kosten von aktuellem Knoten bis zum Ziel in Form einer Evaluierungsfunktion h, die jedem Knoten eine reelle Zahl zuweist.

1

\

3

/ \

2 5

\

4

1. V

   / \

H 4

/ \

V 3

/ \

1 2

1. 12V3H4V

   12V -> (5,2)

   12V + 3H -> (5,2) + (4,2) = (5,4)

   12V3H + 4V -> (5,4) + (5,3) = (10,4)

Gehört zur Uninformierten Suche/ Blinde Suche

Breitensuche:

• Expandiere Knoten in der Reihenfolge, in der sie erzeugt werden

• Findet immer die flachste Lösung (vollständig)

• Die Lösung ist optimal, wenn Pfadkosten eine nichtfallende Funktion der Knotentiefe ist (z.B. wenn jede Aktion identische, nichtnegative Kosten hat)

• Allerdings sind die Kosten sehr hoch. Sei b der maximale Verzweigungsfaktor, d die Tiefe eines Lösungspfads. Dann müssen maximal 1+b+b^2+b^3+…+b^d Knoten expandiert werden, also O(b^d)

• Optimal und vollständig

• Beispiel: b = 10, 1000 Knoten/s, 100 Bytes/Knoten:

Gehört zur Uninformierten Suche/ Blinde Suche

Uniforme Kostensuche:

• In Abwandlung der Breitensuche wird immer der Knoten n mit den geringsten (für Minimierungsproblem!) Pfadkosten g(n) expandiert

• Optimal und vollständig

• Findet immer günstigste Lösung, falls g (nachfolgeknoten(n)) ≥ g (n) für alle n (Minimierungsproblem!)

Gehört zur Uninformierten Suche/ Blinde Suche

Tiefensuche:

• Expandiere immer einen nicht expandierten Knoten mit maximaler Tiefe

• Erstbeste Lösung wird gefunden (Nicht optimal, nicht vollständig)

• Beispiel: Knoten der Tiefe 3 haben keinen Nachfolger

• (Speichert nur die Kosten des Pfades von Knoten zu Knoten)

Gehört zur Uninformierten Suche/ Blinde Suche

Tiefenbeschränkte Suche:

• Es wird nur bis zu einer vorgegebenen Pfadlänge Tiefensuche durchgeführt

• Nicht optimal, vollständig wenn Tiefenlimit >= Tiefe der Lösung

• z.B. Wegeplanung: Bei n Städten ist die maximale Tiefe n -1

Gehört zur Uninformierten Suche/ Blinde Suche

Iterative Tiefensuche:

• Optimal und vollständig wie Breitensuche, aber weniger Speicherplatz

• kombiniert Tiefen- und Breitensuche

• Iterative Tiefensuche ist nicht viel schlechter und i.allg. die bevorzugte Suchmethode bei großen Suchräumen mit unbekannter maximaler Suchtiefe

Zahl der Expansionen:

Für b = 10 werden nur 11% mehr Knoten expandiert als bei Breitensuche, wobei der Platzbedarf erheblich niedriger ist!

Zeitkomplexität: O(bd )

Platzkomplexität: O(b × d)

→ Iterative Tiefensuche ist nicht viel schlechter und i.allg. die bevorzugte Suchmethode bei großen Suchräumen mit unbekannter maximaler Suchtiefe.v

Gehört zur Uninformierten Suche/ Blinde Suche

Bidirektionale Suche:

• Sofern Vorwärts- und Rückwärtssuche symmetrisch sind, erreicht man Suchzeiten von O(2 × bd/2) = O(bd/2).

  z.B. für b = 10, d = 6 statt 111111 nur 2222 Knoten!

  Probleme:

  • Die Operatoren sind nicht immer oder nur sehr schwer umkehrbar (Berechnung der Vorgängerknoten).

  • In manchen Fällen gibt es sehr viele Zielzustände, die nur unvollständig beschrieben sind. Beispiel: Vorgänger des “Schachmatt”.

  • Man braucht effiziente Verfahren, um zu testen, ob sich die Suchverfahren “getroffen” haben.

  • Welche Art der Suche wählt man für jede Richtung (im Bild: Breitensuche, die nicht immer optimal ist)?

Gehört zur Informierten Suche

• Bestensuche

  • Suchverfahren, das Knoten mit dem “besten” h-Wert expandiert.

  • Bestensuche expandiert die (nach irgendeinem Maß) am

    besten bewerteten Knoten zuerst.

  • → Wenn h immer richtig ist, brauchen wir nicht zu suchen!

Gehört zur Informierten Suche

• Greedy Search

  • Mit der Minimierung der geschätzten Kosten zum Ziel h

    erhalten wir gierige Suche.

  • Eine Möglichkeit die “Güte” von Knoten zu beurteilen ist es, ihren Abstand zum Ziel zu schätzen. h(n) = geschätzter Abstand von n zum Ziel. Einzige tatsächliche Einschränkung für h : h(n) = 0 falls n

    Zielknoten.

  • Bestensuche mit dieser Funktion heißt gierige Suche.

  • Die Evaluierungsfunktion h im Falle gieriger Suche wird auch heuristische Funktion oder Heuristik genannt.

    • In der KI gibt es zwei Bedeutungen:

      • Heuristiken sind schnelle aber u.U. unvollständige Methoden, um Probleme zu lösen [Newell, Shaw, Simon 1963] (gierige Suche ist tatsächlich i.allg. nicht vollständig)

      • Heuristiken sind Methoden, um die Suche im Normalfall zu beschleunigen

  • → Auf jeden Fall ist eine Heuristik problemspezifisch und fokussiert die Suche!

  • Beispiel: h = Luftlinienentfernung zwischen zwei Orten (Arad nach Bucharest)

Gehört zur Informierten Suche

• A*-Suche

  • Minimierung von f (n) = g (n) + h(n) kombiniert uninformierte

    Kostensuche mit gieriger Suche. Falls h(n) zulässig ist, d.h.

    h∗ nie überschätzt, erhalten wir A*-Suche, die vollständig

    und optimal ist.

  • Minimierung der geschätzten Pfadkosten

  • A* verbindet uniformierte Kostensuche mit gieriger Suche.

    • g (n) = tatsächliche Kosten vom Anfangszustand bis n.

    • h(n) = geschätzte Kosten von n bis zum nächsten Ziel.

    • f (n) = g (n) + h(n), d.h. geschätzte Kosten des günstigsten Pfades, der durch n verläuft.

    • Seien h∗(n) die tatsächlichen Kosten des optimalen Pfades von n

      zum nächsten Ziel.

    • h heißt zulässig, wenn für alle n gilt: h(n) ≤ h∗(n)

    • Wir verlangen für A*, dass h zulässig ist (Luftlinienentfernung ist

      zulässig)

  • Optimalität von A*

    • Behauptung: Die erste von A* gefundene Lösung ist eine mit

      minimalen Pfadkosten.

      Beweis: Wir nehmen an, dass es einen Zielknoten G mit optimalen Pfadkosten f ∗ gibt, dass A* aber einen anderen Knoten G2 mit g (G2) > f ∗ gefunden hat.

      Sei n ein Knoten auf dem optimalen Pfad vom Start nach G , der

      noch nicht expandiert wurde. Da h ja zulässig ist, haben wir

      f (n) ≤ f ∗. Da n nicht vor G2 expandiert wurde, muss gelten

      f (G2) ≤ f (n) und somit f (G2) ≤ f ∗. Wegen h(G2) = 0 folgt daraus, dass g (G2) ≤ f ∗

      → Widerspruch zur Annahme!

  • Vollständigkeit und Komplexität

    • Vollständigkeit: A* findet eine Lösung, falls es eine gibt, unter der

      Voraussetzung, dass

      • jeder Knoten nur endlich viele Nachfolgerknoten hat und

      • es eine positive Konstante δ gibt, so dass jeder Operator mindestens die Kosten δ hat.

      → nur endlich viele Knoten n mit f (n) ≤ f ∗.

      Komplexität: Falls |h∗(n) − h(n)| ≤ O(log (h∗(n)), werden nur

      subexponentiell viele Knoten expandiert.

      Normalerweise: Exponentielles Wachstum, weil der Fehler

      proportional zu den Pfadkosten ist.

  • Iterative A*-Tiefensuche: IDA* (iterative deepening A*)

    • Idee: Kombination von IDS und A*, d.h. es werden alle Knoten

      innerhalb einer Kontur abgesucht.

  • Beispiel 1: A*-Suche von Arad nach Bucharest

Innerhalb des Suchraums ergeben sich Konturen, in denen jeweils für gegebenen f -Wert alle Knoten expandiert werden:

Pfadplanung für Roboter in einer Grid-Welt:

Beispiel 2: Heuristische Funktion

Empirische Auswertung:

Gehören zur Informierten Suche

• Heuristiken für CSPs

  • Heuristiken fokussieren die Suche.

  • Eingeschränkteste Variable zuerst:

    → reduziert den Verzweigungsfaktor!

  • Einschränkendste Variable zuerst (alternativ):

    d.h. die Variable, die Constraints mit den meisten noch nicht

    belegten Variablen hat → reduziert zukünftigen Verzweigungsfaktor

  • Den am wenigsten einschränkenden Wert zuerst:

    → erlaubt mehr Freiheiten bei zukünftigen Entscheidungen

    → Lösen des 1000-Damen Problems!

Gehört zur Informierten Suche

• Lokale Suche

  • Lokale Suche arbeitet immer nur auf einem Zustand und

    versucht, diesen schrittweise zu verbessern.

  • Für viele Probleme ist es irrelevant, wie man zum Zielzustand

    kommt – nur der Zielzustand selber ist interessant (8-Damen

    Problem, VLSI Design, TSP). Wenn sich außerdem ein Qualitätsmaß für Zustände angeben läßt, kann man lokale Suche benutzen, um Lösungen zu finden.

    Idee: Man fängt mit einer zufällig gewählten Konfiguration an und verbessert diese schrittweise → Hill climbing

  • Probleme:

    • Lokale Maxima:

      • Der Algorithmus gibt eine suboptimale Lösung aus.

    • Plateaus:

      • Hier kann der Algorithmus nur zufällig herumwandern.

    • Grate Ähnlich wie Plateaus.

      
      

      Verbesserungsmöglichkeiten:

    • Neustarts, wenn keine Verbesserung mehr

    • Rauschen “injizieren” (Random walk)

    • Tabu-Suche: Die letzten n angewandten Operatoren nicht

      anwenden

      
      

      Welche Strategien (mit welchen Parametern) erfolgreich sind (auf einer Problemklasse), kann man meist nur empirisch bestimmen.

  • Threshold Accepting:

    • Treshold Accepting akzeptiert alle Variationen, bei denen die Verschlechterung unterhalb eines Schwellenwerts T bleibt

  • Simuliertes Abkühlen:

    • Im Simulated-Annealing-Algorithmus erfolgt das “Injizieren” von

      Rauschen systematisch: Erst stark, dann abnehmend.

    • Iterative Anwendung von kleinen Suchschritten

    • In jedem Suchschritt wird ein Variationsoperator auf x^t angewandt um x^n zu erhalten

    • x^n wird mit Wahrscheinlichkeit

• Strategieparameter Temperatur T

• Anwendung auf CSPs:

  • Obwohl bei CSPs Konfigurationen entweder Lösungen sind oder

    nicht, kann man auch hier lokale Suche anwenden.

    Qualitätsmaß: Anzahl der erfüllten Constraints. Lokale Suche

    heißt in diesem Kontext dann auch heuristisches Reparieren.

    Heuristisches Reparieren wird z.B. für das Scheduling des

    Hubble-Teleskops eingesetzt. Reduzierung der Rechenzeit von 3

    Wochen auf 10 Minuten. Im Kontext vom Finden erfüllender Belegungen für Boole’sche Formeln kann man ähnliche Methoden mit großem Erfolg einsetzen.

Hill climbing:

Gehören zur Informierten Suche

• Genetische Algorithmen

  • Genetische Algorithmen ahmen die Evolution nach, indem

    sie gute Lösungen miteinander kombinieren.

  • Idee:

    Ähnlich wie bei der Evolution, sucht man Lösungen, indem man

    erfolgreiche Lösungen “kreuzt”, “mutiert” und “selektiert”.

    Ingredienzen:

    • Codierung von Konfigurationen als Zeichenkette oder Bit-String.

    • Fitness-Funktion, welche die Güte von Konfigurationen beurteilt.

    • Population von Konfigurationen

    Beispiel:

    8-Damen Problem kodiert als Kette von 8 Zahlen. Fitness

    berechnet sich aus der Anzahl der Nichtangriffe. Population besteht

    aus einer Menge von Anordnungen der Damen

kodiere einen Floorplan als ein System aus Gleichungen

• Objekt i und j sind weder vertikal noch horizontal überlappend

• horizontale Nebenbedingung

  xi + wi <= xj i links von j

  xj + wj <= xi i rechts von j

• vertikale Nebenbedingung

  yi + hi <= yj i unterhalb von j

  yj + hj <= yi i oberhalb von j

• nur eine aus vier Nebenbedingungen muss gültig sein

• Hilfsvariablen

  • binäre Variablen pij und qij , die dafür sorgen, dass mindestens eine Nebenbedingung “scharf” ist (gilt)

  • W und H als obere Schranken für die Breite und Höhe des Floorplans

• Zielmetrik: linerare Funktion

• resultierendes System der Ungleichungen für pij , qij E {0, 1}:

• das Ziel des Optimierungsalgorithmus ist die Minimierung von xy, mit x als Breite und y als Höhe eines Floorplans

• um xy zu linearisieren, kann man die Breite W fixieren und nur y minimieren

• resultierendes System der Ungleichungen:

• um jedes Modul rotieren zu können, muss eine weitere binäre Hilfsvariable ri eingeführt werden (ri = 1: Modul wird rotiert)

• resultierendes System der Ungleichungen:

• mit n Modulen beträgt die Anzahl

  • reelwertiger Variablen O(n)

  • ganzzahliger Variablen O(n^2 )

  • linearer Nebenbedingungen O(n^2 )

• sei folgender Floorplan gegeben

• berechne einen quadratischen Floorplan

• Fläche aller Module: 8 x 6 + 8 x 5 + 11 x 2 = 110 -> setze W = 10 ~= Wurzel(110)

• setze M = max(8, 6) + max(8, 5) + max(11, 2) = 27

• LP Solver: CPLEX, lp_solve, LINDO. . .

• mit größer werdenden Floorplänen wächst der Suchraum exponentiell an; direkte Methoden können nicht mehr angewendet werden

• Idee:

  • generiere einen Floorplan für einen Teil der Module

  • reduziere die Anzahl der Module durch Kombinieren platzierter Module zu größeren Modulen

  • fahre mit der nächsten Teilmenge noch nicht platzierter Module fort

• Leerräume (“dead spaces”) gehen in die Zusammenlegung platzierter Module ein

• resultierende Anzahl zusammengesetzter Module deutlich kleiner als die Anzahl der regulären Module

Nearest Neighbor Heuristik:

• Konstruktionsheuristik für TSP

• Beginne mit zufälliger Stadt

  • Verbinde Graph mit nächster unverbundener Stadt

  • Stoppe, wenn alle Städte verbunden sind

  • Obwohl eine obere Schranke für die Lösungsqualität existiert

    (l(T )/l(Topt) ≤ (log2n)/2), ist die Leistungsfähigkeit der Heuristik in der Praxis schlecht.

Nearest Insertion Heuristik:

• Konstruktionsheuristik für TSP

• Beginne mit zufälliger 2-Städte Tour

• Wähle Stadt mit minimaler Distanz zu einer der schon verbundenen Städte

• Füge Stadt so in die Tour ein, dass Länge der Tour minimal

Cheapest Insertion Heuristik:

• Konstruktionsheuristik für TSP

• Wie nearest insertion, aber es wird die Stadt ausgewählt, bei welcher die Länge der Tour am wenigsten ansteigt

• Worst-case performance: l(T )/l(Topt) ≤ log2n

Furthest Insertion Heuristik:

• Konstruktionsheuristik für TSP

• Beginne mit längster 2-Städte Tour

• Füge iterativ eine Stadt hinzu, die die Länge der Tour am stärksten erhöht. Stelle sicher, dass die einzufügende Stadt an der bestmöglichsten Position eingefügt wird.

• Idee: Beginne mit den Städten, die am meisten auseinanderliegen.

• Worst case performance with cheapest insertion, allerdings liefert furtherst insertion im Mittel bessere Ergebnisse als die anderen Konstruktionsheuristiken

Zwei-Optionen Heuristik:

• Verbesserungsheuristik

• Entfernen Sie zwei beliebige Kanten und erhalten Sie zwei Teilstrecken. Füge zwei neue Kanten ein, so dass die resultierende Tourlänge minimal ist.

• Wenn die Abstände euklidisch sind, kreuzen sich keine Kanten in der resultierenden Tour (keine kreuzende Tour)

• In Worst case performance beträgt das Leistungsverhältnis höchstens 4√n

Multi-Criteria Optimization

Gewicht und Tippcomfort beim Auwählen eines Computers

y Achse Tippcomfort von 0(schlecht)-10(gut)

x Achse Gewicht in 1/20(schlecht)-1/0,08(gut)

Multi-Criteria Problem Definition

a multi-objective function …

Searching for the best solution: Francis Ysidro Edgeworth/ Vilfredo Pareto

Pareto Optimum:

element x1 dominates element x2 weakly if x1<=x2

element x1 dominates element x2 if x1<x2

element x1 is called Pareto Optimal if it is not dominand to x2

Preorder:

• for weak dominance holds

  • reflexivity a<=a

  • transitivity if a<=b and b<=c then a<=c

• the domination relation imposes a preorder on all design points

Optimization Alternatives:

• use of classical single objective optimization methods …

Issues in Multi-Criteria Optimization:

• How to maintain a diverse Pareto set approximation?

  • density estimation

• …

Fittness Assignment Strategies:

• aggregation-based (weighted sum)

• criterion-based (VEGA)

• dominance-based (SPEA2)

Aggregation-based (weighted sum):

• weighted sum: put together n objective functions into one aggregated objective function, e.g. with

Formel

• choosing the weights:

Non-Convex Case:

• main disadvantage of the weighted-sum approach: for non-convex trade-off surfaces not all Pareto-optimal solutions can be generated

Population based Multi-objectie Approaches:

• historically, two generations of MOEAs

• first generation: characterized by the use of Pareto ranking and/ or fitness sharing to ensure …

Criterion-based (VEGA):

Vector Evaluated Genetic Algorithm (VEGA):

• …

• advantage: simple, without much computational effort

• disadvantage: clear …

Pareto-Based Ranking Evolutionary Algorithm:

• better approach: use concept of dominance for selection…

Multi-objective Genetic Algorithm (MOGA):

• consists of a scheme in which the rank of a certain individual corresponds …

Second Generation Elitism Based MOEAs:

• introduction of a secundary and elite archive population …

dominance count: the number of individuals in P dominated by x

dominance rank: the number of individuals in P dominating x

Script bis 2 562 erklären können!!!!!!!!!!!!!!!!!!!!

Historisch:

Evolutionäre Algorithmen (EAs) sind Computer-basierte heuristische Lösungsraumsuchverfahren, welche die Grundprinzipien der Natur imitieren: Sie basieren auf Annahmen über die Evolution von Darwin (1859)

Demzufolge ist Evolution ein Ergebnis von Selektion und Variation. Andere Ansätze sehen Evolution als eine Folge von neutralen Mutationen und genetischer Drift Kimura (1983).

Mendel entwickelte die Vererbungslehre und stellte fest, dass die Informationen über ein Individuum in Form von Genen gespeichert werden. Er war der erste Forscher, der die Gesetzmäßigkeiten der Vererbung systematisch untersuchte. Als Versuchsobjekte wählte Mendel Gartenerbsen, welche über eindeutig unterscheidbare phänotypische Merkmale verfügen. Die Verbreitung dieser Merkmale beobachtete er im Rahmen von Kreuzungsversuchen über mehrere Generationen hinweg. Zunächst erzeugte Gregor Mendel durch wiederholte Selbstbefruchtung (Inzucht) reinerbige Linien (z.B. lang- oder kurzstielig). Neue Merkmalsformen oder Merkmalskombinationen mußten daher ausschließlich ein Ergebnis der Kreuzungsbedingungen sein.

Wichtige Wegbegründer von Evolutionären Verfahren waren John Holland und Ingo Rechenberg.

Evolutionäre Algorithmen (EAs):

• Heuristische Optimierungs- und Suchverfahren auf der Basis von biologischer Evolution

  • Selektion (survival of the fittest)

  • Rekombination

  • Mutation

• arbeitet mit Genen und nicht mit Organismen

• populationsbasiert über mehrere Generationen

• Anzahl Individuen > 1

Genetische Algorithmen können für unterschiedlichste Arten von Optimierungsaufgaben eingesetzt werden.

• Kontinuierliche Probleme

• Kombinatorische Probleme

• Nichtlineare Systeme

• ....

Voraussetzung für einen Einsatz:

• Vergleich von unterschiedlichen Lösungsalternativen muss möglich sein.

• Problem muss derart repräsentiert werden können, dass es genetischen Operatoren zugänglich ist.

• Effiziente exakte Verfahren (ganzzahlige Optimierung, kürzeste Wege Algorithmen) oft nur für Spezialfälle vorhanden; im allgemeinen exponentielles Laufzeitverhalten für N P-schwere Probleme.

• Informierte Suche (z.B. Branch and Bound-Verfahren) nur effizient einsetzbar, wenn genügend Wissen über Problemstruktur vorhanden.

• hohe Anforderungen an die Struktur der Kostenfunktionen (Stetigkeit, Differenzierbarkeit, etc.).

• Für N P-vollständige Probleme oft nur für kleine Probleminstanzen einsetzbar.

• Probleme bei nichtlinearen Zielfunktionen (wie z.B. Simulationsoptimierung)

• Suchverfahren wie z.B. blinde Suche, Breitensuche, Tiefensuche sehr ineffizient und exponentielles Laufzeitverhalten.

• Heuristiken sind sinnvoll und schnell für Probleme, in denen allgemeingültige Designregeln (problemabhängiges Wissen) angegeben werden können.

• Probleme von Heuristiken: Kleine Abweichungen oder andere Skalierung des Problems kann zu fehlerhaften Ergebnissen führen. Darüber hinaus kann oft keine gute Heuristik für ein Problem angegeben werden.

• Oft keine Ermittlung der optimalen Lösung möglich.

Einsatz von einfachen mutationsbasierten Suchverfahren?

• Einfach mutationsbasierte Suchverfahren (z.B. Simulated Annealing oder Hill-Climbing-Varianten) bleiben bei komplexen Kosten- oder Fitnessstrukturen oft in lokalen Optima stecken.

• Operatoren von Evolutionären Algorithmus werden auf den Genotyp angewendet

• geringes problemspezifisches Wissen notwendig

  • Konstruktionsregel für den Genotyp

  • Berechnung der Fitness (Maßzahl für die Güte einer Lsg. (z.B. Kosten)) eines Individuums

Terminologie:

• Individuum: Lösungsvektor

• Population: Menge von Individuen

• Fitness eines Individuums: Qualität einer Lösung

• Phänotyp: Aussehen und Struktur der Lösung

• Genotyp: Kodierte Lösung auf der genetische Operatoren angewendet werden

• Genetische Operatoren: Mutation, Crossover, Selektion, etc.

• Chromosom: Darstellung einer Lösung als Genotyp, Summe der Allele

• Allel: Baustein von Chromosomen

• Gen: Ein bis mehrere Allele, welche für eine konkrete Ausprägung des Phänotypen verantwortlich sind

• Keine Einschränkung bezüglich der zu optimierenden Funktion

• Sowohl Parameterprobleme, als auch kombinatorische Probleme lösbar

• Wenig Informationen über den Suchraum notwendig

• Suche nach globalem Optimum (keine Suche ausschliesslich nach lokalen Optima)

• Statistisches Verfahren → keine Garantie für Finden der optimalen Lösung

• Zielgerichtete Suche durch Selektionsdruck

• Kombination mit anderen Verfahren (hybride Verfahren) oft einfach

• Parallelisierbar

• Kein spezielles Verfahren. Deswegen für eine große Menge an unterschiedlichen Problemen einsetzbar.

• Allerdings Tradeoff zwischen Spezifität und Lösungsgüte. (Man beachte in diesem Zusammenhang das No-Free-Lunch Theorem von Wolpert and Macready (1995), welches besagt, dass alle Optimierungsverfahren für alle möglichen Instanzen einer Problemklasse gleich gut sind.)

• Robustheit: EAs sind für viele unterschiedliche Problemtypen geeignet. Spezialisierte Methoden können oft für bestimmte Probleme bessere Ergebnisse bringen.

Diese Aussagen sind inkorrekt:

• Evolution ist eine Theorie über den Ursprung des Lebens.

• Evolution ist eine Theorie, die besagt, dass das Lebens ein Zufallsprodukt ist.

• Evolution bedeutet Fortschritt. Lebewesen werden besser und besser.

• Ein Lebewesen evolviert während seiner Lebenszeit.

• Evolution passiert langsam und stetig.

• Menschen evolvieren z.Zt. nicht.

• Die natürliche Auswahl bedeutet, dass Individuen sich versuchen anzupassen.

• Natürliche Auswahl ist eine “gute Kraft” für eine Spezies.

• Die besten Individuen sind die stärksten, gesundesten, schlausten, schnellsten,

größten...

• Die natürliche Auswahl bedeutet das Überleben der stärksten einer Spezies.

• Individuen existieren im Phänotypenraum

• sie werden durch Chromosome kodiert, die im Genotypenraum formalisert sind

  • Kodierung: Phänotyp → Genotyp (nicht notwendigerweise eine eins zu ein Abbildung)

  • Dekodierung: Genotyp → Phänotyp (muss eine eins-zu-eins Abbildung sein)

• Chromosome bestehen aus Genen, die üblicherweise eine feste Position (loci) im Genotyp haben und einen konkreten Wert (allele) annehmen können

• um ein globales Optimum finden zu können müssen alle Lösungen kodierbar sein

• Fitness gibt ein Ziel vor, an das sich die Population annähern bzw. adaptieren soll

• auch Zielfunktion bzw. “objective function”

• ordnet einer Lösung eine reelwertige Zahl zu, die im Selektionsprozess für den Vergleich mit anderen Lösungen verwendet wird

  • Fitnessfunktion bei Maximierungsproblemen

  • Kostenfunktion bei Minimierungsproblemen

  • Konversation trivial

• Menge aller aktuellen Lösungen bzw. ihrer Kodierungen

• hat oft eine feste Größe und ist eine Multimenge von Genotypen

• manche EAs (z.B. Multi Objective EAs) benutzen strukturierte Populationen (posets, Grids, archive und breeding Populationen)

• Selektionsoperatoren betrachten die gesamte Population und entscheiden aufgrund der relativen Fitnesssituation über die Reproduktionseigenschaften einzelner Individuen

• verschiedene Metriken für Diversität einer Population (Fitnesswerte, Morphologien, Genotypen...)

Elternauswahl

• Zuordnung von Reproduktionswahrscheinlichkeiten einzelnen Individuen in der Elterpopulation gemäß der Fitness der Individuen

• Zuordnung üblicherweise probabilistisch

  • Individuen mit höherer Fitness haben eine größere Chance sich zu reproduzieren, als Individuen mit niedrigerer Fitness

  • Reproduktion ist nicht garantiert

  • auch Individuen mit niedrigster Fitness können sich mit einer Wahrscheinlichkeit > 0 reproduzieren

• stochastische Elternauswahl hilft bei dem Verlassen lokaler Optima

n-Turnierselektion

• wähle eine zufällige Teilmenge der Größe n aus der Elterpopulation aus

• bestes Individuum aus der Menge gewinnt das Turnier und darf sich fortpflanzen

• haben die Aufgabe neue Individuen / Lösungen / Kinder zu generieren

• üblicherweise aufgeteilt in zwei Variationstypen, nach der Anzahl der Eltern

  • ein Elter: Mutationsoperatoren (SA, ILS: Perturbationsoperator, HC: Nachbarschaftoperator, VNS: shaking)

  • mehr als ein Elter: Rekombinationsoperatoren

  • genau zwei Elter: Crossover

• Welche Operatoren sind besser?

  • hängt von Kodierung und der Wirkweise der Operatoren ab

  • oft wurden beide Operatoren verwendet

• operiert auf einem Genotyp und erzeugt ein zweites

• Funktionsweise abhängig vom Repräsentationsmodell / Kodierung

  • binäre GAs: Erhaltung und Erneuerung der Populationsdiversität

  • EPs für FSM mit reelwertigen Variablen: genereller Suchraumoperator

  • GP: wenig benutzt, Erneuerung und Erhaltung der Populationsdiversität

• Konvergenz von Verbesserungsheuristiken wird oft über den Mutationsoperator gezeigt

• Randomisieren der Allelen zufällig ausgewählter Gene

• Anzahl mutierte Gene oft zufällig gewählt, sollte aber klein gewählt werden

• Mutationen führen oft zur funktionalen Degradation und Fitnessverlust

• Mutation kann bisher nicht existierende Allele erzeugen

• führt Teillösungen, die in Eltern kodiert sind, in Kindern zusammen

• die Auswahl der kombinierten Teillösungen ist stochastisch

• oft ist die funktionale Qualität der Kinder schlechter oder gleich der funktionalen Qualität der Eltern

• die Hoffnung ist, dass einige Kombinationen der elterlichen Teillösungen zu besseren Individuen kombiniert werden können

• das Prinzip wird von Züchtern seit Jahrtausenden erfolgreich angewandt

• tausche ein Stück des Chromosomes zwischen zwei Individuen aus

• One-Point-Crossover

  • wähle zufälligen Schnittpunkt, der Chromosome A und B in jeweils zwei gleich große Teilstücke A1, A2 und B1, B2 spaltet

  • kombiniere A1 mit B2 und A2 mit B1

  • Beispiel: Schnittlinie bei 2

• zweiter Auswahl- bzw. Selektionsoperator

• auch Ersetzungsoperator

• die meisten EAs haben fixe Populationsgrößen und brauchen einen Weg, um die Elter- und Kindspopulationen auf die Größe der Elterpopulation zu reduzieren

• Reduktionsvorschrift of deterministisch

  • Fitnessbasiert: sortiere Eltern und Kinder gemäß Fitness und nehme die Besten

  • Altersbasiert: generiere gleich viele Kinder wie Eltern und übernehme nur die Kinder

• oft auch Kombination beider Verfahren (Elitismus)

• Startindividuen werden meistens zufällig initialisiert

  • gute Abdeckung des Suchraums durch verschiedenartige Kombinationen der Allelen

  • gute Lösungen können auch in der Initialpoulation enthalten sein

  • Problemspezifische Verfahren können Initialpopulation mit guten Teil- bzw. Startlösungen “impfen”

• Stoppbedingung wird für jede Generation überprüft

  • erreichen bestimmter Fitness

  • erreichen der maximalen Anzahl der Fitnessevaluationen

  • erreichen maximalen Schwunds der Populationsdiversität

  • keine Verbesserung bzw. kein Fortschritt in letzen Generationen

Finde eine Platzierung für n Damen auf einem n × n Schachbrett, so dass in jeder

Spalte, Zeile und Diagonale genau eine Dame zu finden ist

Felder, die eine Dame schlagen kann

Eine Lösung des n-Damen Problems

Backtracking Lösung des n-Damen Problems

• platziere Damen Spalte für Spalte von unten nach oben (oder Zeile für Zeile von links nach rechts)

• gehe für jede Zeile wie folgt vor

  • teste von links nach rechts alle Felder einer Zeile für die Platzierung einer Dame; fange mit dem ersten Feld an und platziere eine Dame

  • keine Kollision: Rekursiver Aufruf mit der nächsthöheren Zeile zum Platzieren weiterer Damen

  • Verschiebe die Dame um ein Feld nach rechts und teste wieder; Wiederhole

  • Falls Dame aus aktueller Zeile rausgefallen, beende aktuelle Rekursionsstufe

• gebe kollisionsfreie Spielfigurenanordnung zurück

• ein Optimierungsalgorithmus ist nicht notwendig, um das n-Damen Problem zu lösen

• das n-Damen Problem erlaubt eine anschauliche Einführung in Funktionsweise evolutionärer Algorithmen

Kodierung

• Repräsentation: 1 Lösung = 1 Chromosom mit n Genen

• Gen: eine Zeile des Schachbretts mit n möglichen Allelen

• Belegung eines Gens: Position einer Dame in zugehöriger Zeile

• Läsungen mit mehr als einer Dame in einer Zeile sind ausgeschlossen

  → kleinerer Suchraum

Evaluation

• Fitness: negierte Anzahl an Zeilen und Spalten mit mehr als einer Dame

• zähle jede Spalte / Zeile / Diagonale mit ≥ 2 Damen

• Abbruchkriterium 1: Fitness == 0

• Abbruchkriterium 2: Erreichen der maximalen Anzahl der Generationen

grün: Standard-Algorithmus, schlecht

rot: EAs, etwas besser

blau: für bestimmte Probleme gut

• Trend in den 90er: Einbettung problemspezifischen Wissens in Suchraumoperatoren

• Verzerrung der Leistungskurve der EAs (Deformation):

  • besser für relevante Zielprobleme

  • schlechter für alle anderen Probleme

  • die Menge an Problemwissen kann variieren

Satz besagt, dass Suche nach “bestem” universellen Optimie-

rungsalgorithmus vergebens ist

Im folgenden betrachten wir die Elemente eines genetischen Algorithmus genauer.

Zunächst: Kodierung der Lösungskandidaten

• Wie bereits erwähnt, ist die Kodierung problemspezifisch zu wählen.

• Es gibt kein allgemeines „Kochrezept“, um eine (gute) Kodierung zu finden.

• Aber man kann einige Prinzipien angeben, die beachtet werden sollten.

Wünschenswerte Eigenschaften einer Kodierung: (Regeln)

• Ähnliche Phänotypen sollten durch ähnliche Genotypen dargestellt werden.

• Ähnlich kodierte Lösungskandidaten sollten eine ähnliche Fitneß haben.

• Der Suchraum (die Menge möglicher Lösungskandidaten) sollte, soweit möglich, unter den verwendeten genetischen Operatoren abgeschlossen sein.

Ähnliche Phänotypen sollten durch ähnliche Genotypen dargestellt werden.

• Mutationen einzelner Gene führen zu ähnlichen Genotypen (einzelne Alleländerungen → kleine Änderung des Chromosoms).

• Werden ähnliche Phänotypen nicht durch ähnliche Genotypen dargestellt, können naheliegende Verbesserungen u.U. nicht erzeugt werden. (Es ist dann eine große Änderung des Genotyps erforderlich, um zu einem ähnlichen (und vielleicht besseren) Phänotyp zu gelangen.)

Beispiel zur Verdeutlichung:

• Optimierung einer reellen Funktion y = f (x1, . . . , xn).

• Die (reellen) Argumente sollen durch Binärcodes dargestellt werden.

• Problem: einfache Kodierung als Binärzahl führt zu „Hamming-Klippen“

Binärkodierung reeller Zahlen:

Beispiel:

• Problem des Handlungsreisenden (Finde Rundreise mit minimalen Kosten durch n Städte.)

• Kodierung 1:

  Eine Rundreise wird durch eine Permutation der Städte dargestellt. (Stadt an k-ter Position wird im k-ten Schritt besucht.)

  Geringe Epistasie: z.B. Austausch zweier Städte ändert die Fitneß (Kosten der Rundreise) i.a. etwa gleich stark (lokale Touränderung).

• Kodierung 2:

  Die Rundreise wird durch Angabe der Position der jeweils nächsten Stadt in einer Liste beschrieben, aus der alle besuchten Städte gestrichen werden.

  Hohe Epistasie: Die Änderung eines Gens, speziell im Chromosom vorn liegender Gene, kann (fast) die gesamte Rundreise ändern (globale Touränderung) und führt daher oft zu großen Änderungen der Fitneß.

• Zeigt die verwendete Kodierung hohe Epistasie, so ist das Optimierungsproblem oft für einen genetischen Algorithmus schwer zu lösen, da Regelmäßigkeiten fehlen, die durch ihn ausgenutzt werden könnten. (Mutation und Crossover führen zu fast zufälligen Fitneßänderungen.)

• Läßt sich eine Kodierung mit sehr geringer Epistasie finden, so sind andere Verfahren oft besser geeignet (z.B. Zufallsaufstieg).

• Man hat versucht, mit dem Begriff der Epistasie Probleme als durch einen genetischen Algorithmus leicht oder schwer lösbar zu kennzeichnen [Davidor 1990].

  Das gelingt jedoch nicht:

  • Epistasie ist eine Eigenschaft der Kodierung, nicht des Problems. (Es kann für ein Problem Kodierungen mit hoher und niedriger Epistasie geben — siehe vorangehendes Beispiel.)

  • Es gibt Probleme, die mit geringer Epistasie kodiert werden können, und dennoch durch einen genetischen Algorithmus schwer zu lösen sind.

• Problem der Epistasie:

  • in der Biologie: Ein Allel eines Gens — des sogenannten epistatischen Gens— unterdrückt die Wirkung aller möglichen Allele eines anderen Gens (oder auch mehrerer anderer Gene).

  • in genetischen Algorithmen: Wechselwirkung zwischen den Genen eines Chromosoms. Die Änderung der Fitneß durch die Änderung eines Gens hängt stark von den Ausprägungen der anderen Gene ab.

• Epistasie in der Biologie:

  • Abweichungen von den Mendelschen Gesetzen beruhen oft auf Epistasie.

  • Kreuzt man reinerbige schwarz- und weißsamige Bohnen, so erhält man in der zweiten Nachkommengeneration schwarz-, weiß- und braunsamige Bohnen im Verhältnis 12:1:3, was den Mendelschen Gesetzen widerspricht.

• Der Suchraum (Menge der kodierten Lösungskandidaten) sollte, soweit möglich, unter den verwendeten genetischen Operatoren abgeschlossen sein.

• Was als Verlassen des Suchraums gilt, ist u.U. eine Definitionsfrage.

• Allgemein: Der Suchraum wird verlassen, wenn

  • das neue Chromosom nicht sinnvoll interpretiert/dekodiert werden kann,

  • der Lösungskandidat bestimmte prinzipielle Anforderungen nicht erfüllt,

  • der Lösungskandidat durch die Fitneßfunktion falsch bewertet wird.

• Problem der Abstimmung von Kodierung und genetischen Operatoren.

  • Verwenden kodierungsspezifischer genetischer Operatoren.

  • Einsatz von Mechanismen, die Chromosomen „reparieren“.

  • Einführen eines Strafterms, der die Fitneß von Chromosomen außerhalb des Suchraums (deutlich) verringert.

Beispiel zum Verlassen des Suchraums:

• n-Damen-Problem (Plazierung von n-Damen auf einem n × n-Schachbrett).

• Kodierung 1:

  Chromosom der Länge n, das die Spaltenpositionen der Damen je Zeile angibt (Allele 0, . . . , n − 1, siehe einführendes Beispiel).

  Operatoren: Ein-Punkt-Crossover, Standardmutation

  Es entstehen stets wieder gültige Vektoren von Spaltenpositionen.

  → Suchraum wird nicht verlassen.

• Kodierung 2:

  Chromosom der Länge n, das die Nummern der Felder (Allele 0, . . . , n2 − 1) angibt, auf denen Damen stehen.

  Operatoren: Ein-Punkt-Crossover, Standardmutation

  Es entstehen Chromosomen, die mehrere Damen auf das gleiche Feld setzen.

  → Suchraum wird verlassen.

Andere Kodierung verwenden: Da die erste Kodierung das Problem des

Verlassens des Suchraums vermeidet, außerdem der Suchraum deutlich kleiner

ist, ist sie vorzuziehen. (Dies ist, wenn durchführbar, die beste Variante!)

• Kodierungsspezifische genetische Operatoren

◦ Mutation: Schließe bereits vorhandene Allele bei der zufälligen Wahl aus.

◦ Crossover: Stelle zunächst die Feldnummern je Chromosom zusammen, die

im jeweils anderen Chromosom nicht vorkommen, und wende auf die so

verkürzten Chromosomen das Ein-Punkt-Crossover an.

• Reparaturmechanismus: Finde und ersetze doppelt bzw. mehrfach auftreten-

de Feldnummern, so daß alle Feldnummern verschieden werden.

• Strafterm: Verringere die Fitneß um die Anzahl der Doppel-/Mehrfachbelegungen

von Feldern, ggf. multipliziert mit einem Gewichtungsfaktor.

• Ähnliche Phänotypen sollten durch ähnliche Genotypen dargestellt werden.

• Ähnlich kodierte Lösungskandidaten sollten eine ähnliche Fitneß haben.

• Der Suchraum (die Menge möglicher Lösungskandidaten) sollte, soweit möglich, unter den verwendeten genetischen Operatoren abgeschlossen sein

• Prinzip der Selektion: Bessere Individuen (bessere Fitneß) sollen größere Chancen haben, Nachkommen zu haben (differentielle Reproduktion). Die Stärke der Bevorzugung guter Individuen heißt Selektionsdruck.

Bei der Wahl des Selektionsdrucks gibt es einen Gegensatz von

• Durchforstung des Suchraums (exploration):

  Die Individuen sollten möglichst breit über den Suchraum gestreut sein, damit die Chancen, daß das globale Optimum gefunden wird, möglichst groß sind.

  → geringer Selektionsdruck wünschenswert

• Ausbeutung guter Individuen (exploitation):

  Es sollte das (u.U. lokale) Optimum in der Nähe guter Individuen angestrebt werden (Konvergenz zum Optimum).

  → hoher Selektionsdruck wünschenswert

• Glücksradauswahl (roulette wheel selection) ist das bekannteste Verfahren.

• Berechne die relative Fitneß der Individuen:

und interpretiere sie als Auswahlwahrscheinlichkeit eines Individuums (sogenannte fitneßproportionale Selektion).

• Beachte: Die absolute Fitneß fabs(s) darf in diesem Fall nicht negativ sein; ggf. ist ein positiver Wert zu addieren oder negative Werte sind Null zu setzen.

• Beachte: Die Fitneß muß zu maximieren sein. (Sonst würden schlechte Individuen mit hoher Wahrscheinlichkeit gewählt).

• Veranschaulichung: Glücksrad mit einem Sektor je Individuum s. Die Sektorgrößen entsprechen den relativen Fitneßwerten frel(s).

Auswahl eines Individuums:

• Drehe Glücksrad.

• Wähle Chromosom, dessen Sektor an der Markierung liegt.

Auswahl der Zwischenpopulation:

• Wiederhole die Auswahl so oft, wie es Individuen in der Population gibt.

Technischer Nachteil der Glücksradauswahl:

• Zur Berechnung der relativen Fitneß müssen die Fitneßwerte aller Individuen summiert werden (Normierungsfaktor).

  • Ausgangspopulation muß während der Auswahl konstant bleiben.

  • Parallelisierung der Implementierung wird erschwert.

Dominanzproblem:

• Hat ein Individuum eine sehr hohe Fitneß, kann es die Auswahl dominieren.

• In den Folgegenerationen wird diese Dominanz noch verstärkt, da dann Kopien und sehr ähnliche Individuen vorliegen.

• Als Ergebnis kommt es zum Crowding: Die Population besteht aus gleichen und sehr ähnlichen Individuen.

• Crowding führt dazu, daß das (lokale) Optimum sehr schnell gefunden wird.

• Nachteil: Die Diversität der Population geht verloren.

  • Ausbeutung eines oder weniger guter Individuen.

  • Keine Durchforstung des Suchraums, sondern lokale Optimierung. (in späten Generationen erwünscht, am Anfang unerwünscht.)

Einfluss der Fitneßfunktion:

Das Dominanzproblem weißt auf den starken Einfluß der Fitneßfunktion auf die Wirkung der fitneßproportionalen Selektion hin.

• Problem der vorzeitigen Konvergenz:

  Nimmt die zu maximierende Funktion stark unterschiedliche Werte an, so kann es zu vorzeitiger Konvergenz kommen.

• Beispiel: Ist am Anfang im Bereich B kein Chromosom, so bleibt die Population durch die Selektion in der Nähe des (lokalen) Maximums im Bereich A

Selektionsintensität:

• für die meisten Probleme sind direkte Verfahren, falls anwendbar,:

  • besser als generische Suchverfahren

  • habe eingeschränkte Anwendbarkeit

  • generalisieren nicht für alle Probleme

• Ziel naturinspirierter Verfahren

  • durchschnittlich gute Leistungsfähigkeit

  • für eine breite und relevante Auswahl von Problemen und Probleminstanzen

Im Bereich der Computational Intelligence (CI) ist ein evolutionärer Algorithmus (EA) eine Untergruppe der evolutionären Berechnung (Evolutionary Computation (EC)), ein generischer populationsbasierter metaheuristischer Optimierungsalgorithmus. Ein EA verwendet Mechanismen, die von der biologischen Evolution inspiriert sind, wie Reproduktion, Mutation, Rekombination und Selektion.

Globale Optimierung:

• globale Optimierung: Suche nach dem globalen Optimum

• deterministische Ansätze

  • beispielsweise “box decomposition” (branch and bound usw)

  • finden garantiert eine optimale Lösung, benötigen aber super-polynomielle Laufzeit

• heuristische Ansätze (generate and test)

  • Regeln die besagen, welche Lösungen als nächstes erzeugt werden sollen

  • keine Garantien bezüglich Lösungsqualität

Lokale Optimierung:

• viele Heuristiken nutzen Suchraumoperatoren, die neue Lösungen in der “Nachbarschaft” einer aktuellen Lösung erzeugen

• solche Heuristiken können Optimalität einer Lösung in ihrer lokalen Umgebung garantieren, wie beispielsweise Hill-Climber:

  • es existieren oft viele lokale Optima

  • lokale Optima können schnell identifiziert werden

• EAs unterschieden sich durch

  • die Nutzung einer Population

  • Verwendung mehrerer, stochastischer Suchraumoperatoren

  • insbesondere Variationsoperatoren mit Arität >1

  • Informationsfluss zwischen Lösungen

  • stochastischer Selektion

• Problem: Benachbarte Zahlen können sehr verschieden kodiert sein, d.h. die Kodierungen haben einen großen Hamming-Abstand (Anzahl verschiedener Bits).

• Große Hamming-Abstände können durch Mutationen und Crossover nur sehr schwer überwunden werden (sogenannte „Hamming-Klippen“).

• Beispiel: Der Bereich der Zahlen von 0 bis 1 werde durch 4-Bit-Zahlen dargestellt, d.h. Abbildung k/15 → k. Dann haben die Kodierungen von 7/15 (0111) und 8/15 (1000) den Hamming-Abstand 4, denn jedes Bit ist verschieden.

• Lösung: Gray-Kodes — benachbarte Zahlen unterscheiden sich nur in einem Bit.

• Gray-Kodes sind nicht eindeutig:

  • Jeder Kode, in dem sich die Kodierungen benachbarter Zahlen nur in einem Bit unterscheiden, heißt Gray-Kode.

• Gray-Kodes werden meist aus einer Binärzahlkodierung berechnet.

Die Evaluierungsfunktion h im Falle gieriger Suche wird auch heuristische Funktion oder Heuristik genannt.

• Das Wort Heuristik ist vom griechischen “Heureka” abgeleitet und wurde vom Mathematiker Polya eingeführt, um Problemlösungstechniken zu beschreiben

• In der KI gibt es zwei Bedeutungen:

  • Heuristiken sind schnelle aber u.U. unvollständige Methoden, um Probleme zu lösen [Newell, Shaw, Simon 1963] (gierige Suche ist tatsächlich i.allg. nicht vollständig)

  • Heuristiken sind Methoden, um die Suche im Normalfall zu beschleunigen.

  → Auf jeden Fall ist eine Heuristik problemspezifisch und fokussiert die Suche!