Modul ProjO: Projektseminar Optimierung - Exam

Aufgabe 1)

Ein mittelständisches Unternehmen plant die Produktion zweier Produkte, A und B. Für die Produktion beider Produkte werden zwei Ressourcen verwendet: Maschinenzeit und Arbeitskraft. Die verfügbare Maschinenzeit beträgt 240 Stunden und die verfügbare Arbeitskraft beträgt 100 Stunden. Produkt A benötigt 2 Stunden Maschinenzeit und 1 Stunde Arbeitskraft pro Einheit, während Produkt B 1 Stunde Maschinenzeit und 1 Stunde Arbeitskraft pro Einheit benötigt. Der Gewinn pro Einheit beträgt 300 Euro für Produkt A und 200 Euro für Produkt B. Ziel des Unternehmens ist es, den Gesamtgewinn zu maximieren. Du bist damit beauftragt, das Unternehmen bei der optimalen Produktionsplanung zu unterstützen.

a)

Formuliere das Optimierungsproblem als lineares Programm (LP). Lege die Zielfunktion und die Nebenbedingungen fest.

Lösung:

Um das Optimierungsproblem als lineares Programm (LP) zu formulieren, müssen wir die Zielfunktion sowie die Nebenbedingungen festlegen. Folgende Schritte sind dazu notwendig:

• Definition der Variablen:
  • x: Anzahl der produzierten Einheiten von Produkt A
  • y: Anzahl der produzierten Einheiten von Produkt B
• Zielfunktion:Das Ziel ist es, den Gesamtgewinn zu maximieren. Der Gewinn pro Einheit beträgt 300 Euro für Produkt A und 200 Euro für Produkt B. Daher lautet die Zielfunktion:

  Maximiere Z = 300x + 200y

• Nebenbedingungen:Die verfügbaren Ressourcen begrenzen die Produktion. Dies führt zu folgenden Ungleichungen:
  • Maschinenzeit:
    • Produkt A benötigt 2 Stunden pro Einheit.
    • Produkt B benötigt 1 Stunde pro Einheit.
    • Die gesamte verfügbare Maschinenzeit beträgt 240 Stunden.
    • 2x + y ≤ 240
  • Arbeitskraft:
    • Beide Produkte benötigen je 1 Stunde pro Einheit.
    • Die gesamte verfügbare Arbeitskraft beträgt 100 Stunden.
    • x + y ≤ 100
  • Nicht-Negativitätsbedingungen:
    • x ≥ 0
    • y ≥ 0

Daher sieht das vollständige lineare Programm folgendermaßen aus:

• Zielfunktion:

  Maximiere Z = 300x + 200y

• Nebenbedingungen:

  2x + y ≤ 240x + y ≤ 100x ≥ 0y ≥ 0

b)

Verwende den Simplex-Algorithmus, um die optimalen Produktionsmengen für Produkt A und Produkt B zu bestimmen.

Lösung:

Um den Simplex-Algorithmus zur Lösung des Optimierungsproblems anzuwenden, führen wir die folgenden Schritte durch:

• Schritt 1: Formuliere das lineare Programm in Tabellenform (Simplex-Tabelle):
• Unser lineares Programm lautet:

  Maximiere Z = 300x + 200y

  unter den Nebenbedingungen:

  2x + y ≤ 240x + y ≤ 100x ≥ 0y ≥ 0

• Wir führen Schlupfvariablen s1 und s2 ein, um die Ungleichungen in Gleichungen umzuwandeln:
• 2x + y + s1 = 240x + y + s2 = 100Mit den Schlupfvariablen transformieren wir das Problem in ein standardmäßiges Simplex-Format, wobei Z unsere Zielfunktion repräsentiert.Z - 300x - 200y = 0
• Schritt 2: Initialisiere die Simplex-Tabelle:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	2	1	240
s2	0	1	1	1	100
Z	0	0	300	200	0

Schritt 3: Iteriere durch die Simplex-Algorithmen-Schritte:

• Pivotiere um das Element in der Spalte mit dem höchsten positiven Koeffizienten in der Z-Reihe (erste Iteration):

Wähle die y-Spalte, da der Koeffizient 200 der höchste ist.

• Berechne die Verhältnisse der Rechtswerte zu den Elementen der y-Spalte:s1: 240/1 = 240s2: 100/1 = 100s2 hat das kleinste Verhältnis. Daher ist s2 die Schwenkzeile.
• Führe die Pivot-Operation durch. Die neue Tabelle sieht wie folgt aus:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	0	1	140
y	0	1	1	1	100
Z	0	0	100	0	20000

• Pivotiere um das Element in der x-Spalte in der nächsten Iteration:

Wähle die x-Spalte, da der Koeffizient 100 der höchste ist.

• Berechne die Verhältnisse der Rechtswerte zu den Elementen der x-Spalte:s1: 140/0 (unendlich, daher ignorieren)y: 100/1 = 100y hat das kleinste Verhältnis. Daher ist y die Schwenkzeile.
• Führe die Pivot-Operation durch. Die neue Tabelle sieht wie folgt aus:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	-1	0	40
x	0	1	1	0	100
Z	0	0	0	0	50000

In der letzten Tabelle haben alle Werte in der Z-Reihe, die mit den Entscheidungsvariablen multipliziert werden, negative oder null Werte. Das bedeutet, dass wir die maximale Zielfunktion erreicht haben.

Schlussfolgerung: Die optimalen Produktionsmengen sind x=100 (Produkt A) und y=0 (Produkt B), und der maximale Gewinn beträgt 50000 Euro.

c)

Erkläre, welche Bedeutung die Schlupfvariablen in deinem Simplex-Tableau haben und interpretiere diese im Kontext des Problems.

Lösung:

Schlupfvariablen (oder Überschussvariablen) spielen eine wichtige Rolle im Simplex-Algorithmus, um Ungleichungen in Gleichungen zu transformieren. Dies ist notwendig, um das lineare Programmierung (LP) Problem in eine Standardform zu bringen, die mit dem Simplex-Verfahren gelöst werden kann. Lassen Sie uns die Bedeutung und Interpretation der Schlupfvariablen im Kontext des gegebenen Problems erörtern:

• Was sind Schlupfvariablen?Schlupfvariablen sind zusätzliche Variablen, die in die Ungleichungen eingeführt werden, um diese in Gleichungen umzuwandeln. Sie repräsentieren die ungenutzten Kapazitäten der Ressourcen.
• Definition der Schlupfvariablen in unserem Problem:Für die Maschinezeit-Bedingung:

  2x + y + s1 = 240

  Für die Arbeitskraft-Bedingung:

  x + y + s2 = 100

  Hier sind s1 und s2 die Schlupfvariablen und repräsentieren die Restkapazitäten der Maschinenzeit und Arbeitskraft, die nach der Herstellung der Produkte A und B übrig bleiben.
• Interpretation der Schlupfvariablen:
  • s1 (Maschinenzeit Schlupfvariable): Diese Variable zeigt an, wie viel Maschinenzeit nach der Produktion von x Einheiten von Produkt A und y Einheiten von Produkt B noch verfügbar bleibt.
  • s2 (Arbeitskraft Schlupfvariable): Diese Variable zeigt an, wie viel Arbeitskraft nach der Produktion von x Einheiten von Produkt A und y Einheiten von Produkt B noch verfügbar bleibt.
• Interpretation im Beispiel-Tableau:Um die Schlupfvariablen s1 und s2 in den verschiedenen Iterationen des Simplex-Tableaus zu verstehen, schauen wir auf die Ergebnis-Tabelle:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	-1	0	40
x	0	1	1	0	100
Z	0	0	0	0	50000

• s1 = 40: Dies bedeutet, dass nach der Produktion der optimalen Menge (x = 100 und y = 0) noch 40 Stunden Maschinenzeit ungenutzt bleiben.
• s2 = 0: Zeigt, dass die gesamte verfügbare Arbeitskraft von 100 Stunden vollständig genutzt wird und keine Restkapazität bleibt.

Die Schlupfvariablen helfen somit dabei, die Nutzung der Produktionsressourcen zu überwachen und zu verstehen, wie effizient diese im optimalen Produktionsplan eingesetzt werden.

d)

Diskutiere, wie sich die optimale Lösung verändert, wenn der Gewinn pro Einheit für Produkt A auf 400 Euro erhöht wird, während alle anderen Bedingungen unverändert bleiben. Berechne die neue Lösung.

Lösung:

Um zu sehen, wie sich die optimale Lösung verändert, wenn der Gewinn pro Einheit für Produkt A auf 400 Euro erhöht wird, bleiben wir bei der Struktur des vorherigen linearen Programms und passen die Zielfunktion entsprechend an. In diesem Fall lautet die neue Zielfunktion:

• Maximiere Z = 400x + 200y

Die Nebenbedingungen und Variablen bleiben gleich:

• Maschinenzeit: 2x + y ≤ 240
• Arbeitskraft: x + y ≤ 100
• Nicht-Negativitätsbedingungen: x ≥ 0, y ≥ 0

Das modifizierte lineare Programm lautet also:

• Zielfunktion: Maximiere Z = 400x + 200y
• Nebenbedingungen:

  2x + y ≤ 240x + y ≤ 100x ≥ 0y ≥ 0

Wir setzen diese Anpassung in das Simplex-Tableau um.

• Schritt 1: Initialisiere die Simplex-Tabelle unter Berücksichtigung der neuen Zielfunktion:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	2	1	240
s2	0	1	1	1	100
Z	0	0	-400	-200	0

• Schritt 2: Iteriere durch die Simplex-Algorithmen-Schritte:

Pivotiere um das Element in der x-Spalte (erste Iteration):

• Wähle die x-Spalte, da der Koeffizient -400 der kleinste ist.
• Berechne die Verhältnisse der Rechtswerte zu den Elementen der x-Spalte:
• s1: 240/2 = 120
• s2: 100/1 = 100

s2 hat das kleinste Verhältnis. Daher ist s2 die Schwenkzeile.

• Führe die Pivot-Operation durch:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	1	0	140
x	0	1	1	1	100
Z	0	0	0	200	40000

Wähle die y-Spalte, da der Koeffizient 200 der höchste verbleibende positive Koeffizient ist :

• Berechne die Verhältnisse der Rechtswerte zu den Elementen der y-Spalte:
• s1: 140/0 (unendlich, daher ignorieren)
• x: 100/1 = 100
• Führe die Pivot-Operation durch. Die neue Tabelle sieht wie folgt aus:

Basis	s1	s2	x	y	Rechtswert
s1	1	0	1	0	140
x	0	1	1	1	100
Z	0	0	0	0	40000

In der letzten Tabelle haben alle Werte in der Z-Reihe, die mit den Entscheidungsvariablen multipliziert werden, positive oder null Werte. Das neue optimale Produktionsmengen sind x=100 (Produkt A) und y=0 (Produkt B), und der neue maximale Gewinn beträgt 40000 Euro.

Aufgabe 2)

Nichtlineare OptimierungsmethodenBetrachte ein nichtlineares Optimierungsproblem, bei dem eine Zielfunktion mit nichtlinearen Nebenbedingungen minimiert werden soll. Die Zielfunktion ist definiert als \[f(x) = x_1^4 - 3x_1^2 + x_2^4 - 2x_2^2\], und die Nebenbedingungen sind \[g_1(x) = x_1^2 + x_2^2 - 4 \leq 0\] und \[g_2(x) = -x_1 - x_2 + 1 \leq 0\].Setze zur Lösung dieses Problems die Methoden der nichtlinearen Optimierung ein und beantworte die folgenden Fragen.

b)

Formuliere die notwendigen Karush-Kuhn-Tucker (KKT) Bedingungen für dieses Optimierungsproblem.

Lösung:

Nichtlineare Optimierungsmethoden

• Betrachte ein nichtlineares Optimierungsproblem, bei dem eine Zielfunktion mit nichtlinearen Nebenbedingungen minimiert werden soll. Die Zielfunktion ist definiert als \[f(x) = x_1^4 - 3x_1^2 + x_2^4 - 2x_2^2\], und die Nebenbedingungen sind \[g_1(x) = x_1^2 + x_2^2 - 4 \leq 0\] und \[g_2(x) = -x_1 - x_2 + 1 \leq 0\].

Setze zur Lösung dieses Problems die Methoden der nichtlinearen Optimierung ein und beantworte die folgenden Fragen.Formuliere die notwendigen Karush-Kuhn-Tucker (KKT) Bedingungen für dieses Optimierungsproblem.Die KKT-Bedingungen sind notwendige Bedingungen für ein Optimierungsproblem mit Gleichungs- und Ungleichungsnebenbedingungen. Um die KKT-Bedingungen für das gegebene Problem zu formulieren, müssen wir Folgendes berücksichtigen:1. Zielfunktion: \(f(x) = x_1^4 - 3x_1^2 + x_2^4 - 2x_2^2\)2. Ungleichungsnebenbedingungen: \[g_1(x) = x_1^2 + x_2^2 - 4 \leq 0\]\[g_2(x) = -x_1 - x_2 + 1 \leq 0\]Die KKT-Bedingungen bestehen aus den folgenden Teilen:1. Stationaritätsbedingung: Der Gradient der Lagrange-Funktion \(L(x, \boldsymbol{u})\) bezüglich \(x\) muss null sein.Die Lagrange-Funktion lautet:\[L(x, u_1, u_2) = f(x) + u_1 g_1(x) + u_2 g_2(x)\]\(L(x, u_1, u_2) = x_1^4 - 3x_1^2 + x_2^4 - 2x_2^2 + u_1 (x_1^2 + x_2^2 - 4) + u_2 (-x_1 - x_2 + 1)\)Wir berechnen den Gradienten der Lagrange-Funktion:\(\frac{\partial L}{\partial x_1} = 4x_1^3 - 6x_1 + u_1 2x_1 - u_2 = 0\)\(\frac{\partial L}{\partial x_2} = 4x_2^3 - 4x_2 + u_1 2x_2 - u_2 = 0\)2. Primal-F feasibility (Primal Machbarkeit): Die Nebenbedingungen müssen erfüllt sein:\[g_1(x) \leq 0\]\[g_2(x) \leq 0\]3. Dual-F feasibility (Dual Machbarkeit): Die Lagrange-Multiplikatoren müssen nicht negativ sein:\[u_1 \geq 0\]\[u_2 \geq 0\]4. Komplementaritätsbedingung: Für jede Nebenbedingung muss das Produkt der Nebenbedingung und des zugehörigen Lagrange-Multiplikators null sein:\[u_1 g_1(x) = 0\]\[u_2 g_2(x) = 0\]Zusammenfassend ergeben sich die KKT-Bedingungen für dieses Optimierungsproblem als:

• \(4x_1^3 - 6x_1 + u_1 2x_1 - u_2 = 0\)
• \(4x_2^3 - 4x_2 + u_1 2x_2 - u_2 = 0\)
• \(g_1(x) = x_1^2 + x_2^2 - 4 \leq 0\)
• \(g_2(x) = -x_1 - x_2 + 1 \leq 0\)
• \(u_1 \geq 0\)
• \(u_2 \geq 0\)
• \(u_1 (x_1^2 + x_2^2 - 4) = 0\)
• \(u_2 (-x_1 - x_2 + 1) = 0\)

Aufgabe 3)

Einführung: Dynamische Programmierung ist eine Technik zur Lösung von Optimierungsproblemen, bei der komplexe Probleme in einfachere Teilprobleme zerlegt und rekursiv gelöst werden. Diese Methode wird häufig bei der Berechnung kürzester Pfade, dem Rucksackproblem und der Berechnung der Fibonacci-Zahlen eingesetzt. Kennzeichnend dafür ist das Speichern (Memoization) der Lösungen für Teilprobleme, um diese bei Bedarf wiederverwendbar zu machen und die Rekurrenzgleichungen, die das Problem mathematisch definieren.

a)

Angenommen, Du hast das 0/1-Rucksackproblem. Hierbei hast Du eine Menge von Gegenständen, jeder mit einem Gewicht und einem Wert, und einen Rucksack, der ein maximales Gewicht tragen kann. Beschreibe einen dynamischen Programmierungsansatz, um das Problem zu lösen. Formuliere die Rekurrenzgleichung und beschreibe, wie die Teilprobleme definiert und gespeichert werden. Wie lässt sich die Zeitkomplexität dieser Methode abschätzen?

Lösung:

Dynamischer Programmierungsansatz für das 0/1-Rucksackproblem:Um das 0/1-Rucksackproblem mittels dynamischer Programmierung zu lösen, gehen wir wie folgt vor:

• Definition der Teilprobleme: Wir definieren ein Teilproblem durch die Anzahl der betrachteten Gegenstände und die verbleibende Kapazität des Rucksacks. Sei dp[i][w] der maximale Wert, der mit den ersten i Gegenständen und einer Rucksackkapazität von w erzielt werden kann.
• Rekurrenzgleichung: Wir formulieren die Rekurrenzgleichung, indem wir entscheiden, ob ein Gegenstand i im optimalen Subset enthalten ist oder nicht. Für jeden Gegenstand i und Kapazität w haben wir folgende zwei Fälle:
  • Nicht aufnehmen: Der Wert bleibt gleich dem optimalen Wert ohne den aktuellen Gegenstand: dp[i-1][w].
  • Aufnehmen: Der Wert ist der Wert des Gegenstands i plus der optimale Wert, wenn wir die Rucksackkapazität um das Gewicht des Gegenstands i reduzieren: val[i] + dp[i-1][w-wt[i]].
  Die Rekurrenzgleichung lautet daher:

  dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])

  wenn w eindeutig größer oder gleich wt[i] ist, ansonsten

  dp[i][w] = dp[i-1][w]

  .
• Initialisierung:
  • dp[0][w] = 0 für alle w: Wenn keine Gegenstände vorhanden sind, ist der maximale Wert 0.
  • dp[i][0] = 0 für alle i: Wenn der Rucksack keine Kapazität hat, ist der maximale Wert 0.
• Speichern der Lösungen: Wir speichern die Lösungen für die Teilprobleme in einer Tabelle dp[][], die eine Größe von (n+1) x (W+1) hat, wobei n die Anzahl der Gegenstände und W die Kapazität des Rucksacks ist.
• Algorithmus: Der Algorithmus iteriert über alle Gegenstände und Rucksackkapazitäten und füllt die Tabelle dp[][] gemäß der Rekurrenzgleichung.
• Zeitkomplexität: Die Zeitkomplexität des Algorithmus beträgt O(nW), da wir eine Tabelle der Größe n x W füllen und jeder Eintrag in konstanter Zeit berechnet wird.

Zusammengefasst, löst der dynamische Programmierungsansatz das 0/1-Rucksackproblem effizient, indem er die optimalen Lösungen für kleinere Teilprobleme speichert und wiederverwendet, sodass die Gesamtlösung in polynomialer Zeit gefunden wird.

b)

Der Floyd-Warshall-Algorithmus ist ein bekannter Algorithmus zur Berechnung der kürzesten Pfade zwischen allen Paaren von Knoten in einem gewichteten Graphen. Implementiere diesen Algorithmus, wobei alle notwendigen Zwischenschritte deutlich kommentiert werden sollten. Wie wird die Zeitkomplexität des Floyd-Warshall-Algorithmus bestimmt? Erläutere die relevanten Schritte, die den Algorithmus optimieren.

Lösung:

Implementierung des Floyd-Warshall-Algorithmus:Der Floyd-Warshall-Algorithmus berechnet die kürzesten Pfade zwischen allen Paaren von Knoten in einem gewichteten Graphen. Hier ist ein Schritt-für-Schritt-Ansatz zur Implementierung des Algorithmus:

• Initialisierung: Wir beginnen mit der Initialisierung der Distanzmatrix. Diese Matrix speichert die kürzesten Distanzen zwischen jedem Paar von Knoten. Wenn es eine direkte Kante zwischen zwei Knoten gibt, setzen wir die Distanz gleich dem Gewicht der Kante, ansonsten setzen wir sie auf ∞ (Unendlichkeit). Die Diagonale der Matrix wird auf 0 gesetzt, weil die Distanz eines Knotens zu sich selbst 0 ist.
• Rekurrenzrelation: Wir durchlaufen jede Kombination von Knotenpaare und prüfen, ob ein kürzerer Pfad über einen dritten Knoten existiert. Wenn ja, aktualisieren wir die Distanz.
• Zeitkomplexität: Der Algorithmus hat eine Zeitkomplexität von O(V^3), wobei V die Anzahl der Knoten im Graphen ist, da wir in dreifach geschachtelten Schleifen über die Knoten iterieren.

Hier ist der vollständige Code in Python:

def floyd_warshall(graph):    # Initialisiere die Anzahl der Knoten    n = len(graph)    # Erstelle die Distanzmatrix und initialisiere sie mit den Gewichten des Graphen    dist = [[float('inf')] * n for _ in range(n)]    for i in range(n):        for j in range(n):            if i == j:                dist[i][j] = 0            elif graph[i][j] != 0:                dist[i][j] = graph[i][j]    # Der Hauptteil des Floyd-Warshall-Algorithmus    for k in range(n):        for i in range(n):            for j in range(n):                # Wenn der Pfad über den Knoten k kürzer ist als der direkte Pfad                if dist[i][j] > dist[i][k] + dist[k][j]:                    dist[i][j] = dist[i][k] + dist[k][j]    return dist

Erklärung der Schritte:

• Wir initialisieren die Distanzmatrix dist so, dass sie die direkten Distanzen zwischen den Knoten enthält, wobei unverbundene Paare mit ∞ initialisiert werden.
• Wir durchlaufen jede Kombination von Knotenpaare (i, j) und prüfen, ob ein kürzerer Pfad durch einen Zwischenknoten k existiert.
• Falls ja, aktualisieren wir die Distanz dist[i][j].

Optimierungen:

• Verwendung von geeigneten Datenstrukturen für die Distanzmatrix, um den Speicherverbrauch zu optimieren.
• Parallelisierung: Der Algorithmus kann leicht parallelisiert werden, da die Berechnungen für jede Kombination von Knoten unabhängig sind.

Zusammengefasst, besteht der Floyd-Warshall-Algorithmus aus der schrittweisen Aktualisierung der kürzesten Distanzen zwischen allen Knotenpaaren durch die Berücksichtigung eines dritten Knotens, wodurch eine Zeitkomplexität von O(V^3) erreicht wird.

Aufgabe 4)

Du bist als Datenwissenschaftler in einem Forschungsprojekt beteiligt, das stochastische Optimierungstechniken zur Lösung komplexer Probleme einsetzt. Deine Aufgaben umfassen die Nutzung und Weiterentwicklung bestehender Optimierungsverfahren sowie die Bewertung ihrer Effizienz. Eine besondere Herausforderung ist das Auffinden globaler Minima in hochdimensionalen und verrauschten Suchräumen.

a)

Simulated Annealing: Die Simulated Annealing Methode wird verwendet, um ein Optimierungsproblem zu lösen. Angenommen, die Zielfunktion ist stark verrauscht und besitzt viele lokale Minima. Erläutere das Prinzip des Simulated Annealing und beschreibe, wie die Temperaturparameterwahl den Optimierungsprozess beeinflusst.

Lösung:

Simulated Annealing: ist ein probabilistisches Optimierungsverfahren, das oft verwendet wird, um globale Minima in komplexen und verrauschten Suchräumen zu finden. Es ahmt den Prozess des Abkühlens von Metallen nach, bei dem ein System von einem hochenergetischen Zustand (hohe Temperatur) zu einem niedrigenergetischen Zustand (niedrige Temperatur) übergeht.

• Prinzip des Simulated Annealing:
  • Das Verfahren beginnt mit einer zufälligen Startlösung und einer hohen Anfangstemperatur.
  • In jeder Iteration wird eine neue mögliche Lösung generiert, die in der Nachbarschaft der aktuellen Lösung liegt.
  • Die Änderung der Zielfunktion \(\text{DeltaE}\) zwischen der aktuellen Lösung und der neuen Lösung wird berechnet.
  • Die neue Lösung wird wie folgt akzeptiert:
    • Ist die neue Lösung besser (d.h., \(\text{DeltaE} < 0\)), wird sie immer akzeptiert.
    • Ist die neue Lösung schlechter (d.h., \(\text{DeltaE} > 0\)), wird sie mit einer Wahrscheinlichkeit von \(\text{exp}(-\text{DeltaE} / T)\) akzeptiert, wobei \(T\) die aktuelle Temperatur ist.
  • Die Temperatur wird nach einem vordefinierten Plan reduziert, häufig nach der Formel \(T = T \times \text{alpha}\) (mit \(0 < \text{alpha} < 1\)).
  • Dieser Prozess wird fortgesetzt, bis ein Abbruchkriterium erfüllt ist (z.B. eine Mindesttemperatur oder eine maximale Anzahl an Iterationen).
• Einfluss der Temperaturparameter auf den Optimierungsprozess:
  • Anfangstemperatur: Die Wahl der Anfangstemperatur ist kritisch. Eine hohe Anfangstemperatur ermöglicht es dem Algorithmus, in den frühen Phasen aus lokalen Minima zu entkommen, indem er auch schlechtere Lösungen akzeptiert. Ist die Anfangstemperatur zu niedrig, kann der Algorithmus in einem lokalen Minimum gefangen bleiben.
  • Abkühlungsrate (Alpha): Die Abkühlungsrate bestimmt, wie schnell die Temperatur reduziert wird. Eine langsame Abkühlung (großes Alpha) erlaubt es dem Algorithmus, mehr vom Suchraum zu erkunden und eine bessere Lösung zu finden, kann aber die Laufzeit verlängern. Eine schnelle Abkühlung (kleines Alpha) kann den Algorithmus schnell zu einer Lösung konvergieren lassen, jedoch auf Kosten der Genauigkeit.
  • Mindesttemperatur: Das Abkühlungsverfahren wird beendet, wenn die Temperatur einen bestimmten minimalen Wert erreicht. Dieser Wert sollte so gewählt werden, dass der Algorithmus genügend Zeit hat, den Suchraum zu erkunden, ohne zu früh zu stoppen.

Durch eine sorgfältige Wahl der Temperaturparameter kann das Simulated Annealing Verfahren effektiv zur Lösung von Optimierungsproblemen verwendet werden, insbesondere wenn die Zielfunktion verrauscht ist und viele lokale Minima besitzt.

b)

Evolutionäre Algorithmen: Du sollst einen evolutionären Algorithmus zur Optimierung einer nich-differenzierbaren Funktion verwenden. Beschreibe den grundlegenden Ablauf eines solchen Algorithmus und nenne spezifische Parameter, die für die Effizienz und den Erfolg des Algorithmus entscheidend sind.

Lösung:

Evolutionäre Algorithmen: sind eine Klasse von stochastischen Optimierungsverfahren, die auf den Prinzipien der natürlichen Evolution basieren. Diese Algorithmen sind besonders nützlich für die Optimierung von nicht-differenzierbaren, nicht-linearen und hochdimensionalen Funktionen.

• Grundlegender Ablauf eines evolutionären Algorithmus:
  • Initialisierung: Erstelle eine anfängliche Population von Individuen (Lösungen), die zufällig oder basierend auf heuristischen Methoden generiert werden.
  • Bewertung: Berechne die Fitness jedes Individuums in der Population anhand der Zielfunktion. Diese Fitness gibt an, wie gut das Individuum das Optimierungsziel erfüllt.
  • Selektion: Wähle Individuen aus der aktuellen Population aus, die als Eltern für die nächste Generation dienen. Dabei werden Individuen mit höherer Fitness bevorzugt ausgewählt (z.B. durch Methoden wie Roulette-Rad-Selektion, Rangbasierte Selektion).
  • Rekombination (Crossover): Kombiniere Paare von Eltern-Individuen, um Nachkommen zu erzeugen. Dies geschieht durch Austausch von Teilen der Elternlösungen. Beispielsweise kann ein Ein-Punkt-Crossover verwendet werden, bei dem ein Schnittpunkt zufällig gewählt wird und die Teile der Elternlösungen ausgetauscht werden.
  • Mutation: Führe zufällige Änderungen an den Nachkommenlösungen durch, um die genetische Vielfalt in der Population zu erhalten und lokale Minima zu vermeiden. Dies kann durch kleine zufällige Änderungen an den Genen der Nachkommen geschehen.
  • Ersetzung: Ersetze die aktuelle Population durch die neu erzeugten Nachkommen (oder eine Kombination aus Eltern und Nachkommen). Hierbei kann auch eine Elitismus-Strategie angewendet werden, bei der die besten Individuen unverändert in die nächste Generation übernommen werden.
  • Abbruchkriterium: Wiederhole den Prozess der Bewertung, Selektion, Rekombination und Mutation, bis ein Abbruchkriterium erfüllt ist (z.B. eine maximale Anzahl von Generationen oder eine zufriedenstellende Fitness erreicht ist).
• Spezifische Parameter, die für die Effizienz und den Erfolg des Algorithmus entscheidend sind:
  • Populationsgröße: Eine größere Population ermöglicht eine bessere Abdeckung des Suchraums und eine höhere genetische Vielfalt, kann jedoch die Berechnungszeit erhöhen.
  • Mutationsrate: Eine höhere Mutationsrate erhöht die genetische Vielfalt und hilft, lokale Minima zu vermeiden, kann aber auch zu einer weniger fokussierten Suche führen. Eine zu niedrige Mutationsrate kann zur Stagnation in lokalen Minima führen.
  • Rekombinationsrate: Die Rate, mit der Rekombinationen durchgeführt werden, beeinflusst, wie stark neue Lösungen durch die Kombination von Elternlösungen erzeugt werden. Ein ausgewogenes Verhältnis ist wichtig, um eine gute Mischung aus Exploration und Exploitation zu erreichen.
  • Selektionsstrategie: Die Methode, mit der Individuen als Eltern ausgewählt werden, beeinflusst die Geschwindigkeit der Konvergenz und die genetische Vielfalt. Strikte Selektion (nur die besten Individuen auswählen) kann zu einer schnellen Konvergenz aber geringer Diversität führen, während eine zu breite Selektion (zufällige Auswahl) die Effizienz verringern kann.
  • Elitismus: Das Beibehalten der besten Individuen in der nächsten Generation kann die Konvergenz verbessern, indem es sicherstellt, dass gute Lösungen nicht verloren gehen.

Durch die sorgfältige Abstimmung dieser Parameter kann ein evolutionärer Algorithmus effektiv zur Optimierung nicht-differenzierbarer Funktionen eingesetzt werden.