import os
os.environ['MKL_DISABLE_FAST_MM'] = '1'
# Rest des Codes...import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import linprog

# Definiere das Beispiel eines linearen Optimierungsproblems
# Maximiere: f(x, y) = 3x + 2y
# unter den Nebenbedingungen:
#   2x + y ≤ 20
#   x + 2y ≤ 20
#   x, y ≥ 0

# Für linprog müssen wir das Problem umformulieren:
# Minimiere: -3x - 2y
# unter den Nebenbedingungen:
#   2x + y ≤ 20
#   x + 2y ≤ 20
#   x, y ≥ 0

# Koeffizienten der Zielfunktion (negativ für Maximierung)
c = [-3, -2]

# Koeffizienten der Ungleichungsnebenbedingungen
A = [[2, 1],  # 2x + y ≤ 20
     [1, 2]]  # x + 2y ≤ 20

# Rechte Seite der Ungleichungsnebenbedingungen
b = [20, 20]

# Löse das lineare Optimierungsproblem
res = linprog(c, A_ub=A, b_ub=b, bounds=(0, None))

# Ausgabe der Ergebnisse
print(f"Optimale Lösung gefunden: {res.success}")
print(f"Optimaler Punkt: x = {res.x[0]:.2f}, y = {res.x[1]:.2f}")
print(f"Optimaler Zielfunktionswert: {-res.fun:.2f}")  # Negativ, da wir maximieren

# Visualisierung
x = np.linspace(0, 25, 1000)

# Nebenbedingungen als Funktionen von x
y1 = 20 - 2*x  # 2x + y = 20 => y = 20 - 2x
y2 = (20 - x)/2  # x + 2y = 20 => y = (20 - x)/2

# Zielfunktionswerte für verschiedene Ebenen
z_levels = [0, 20, 40, 60]
z_lines = [(z - 3*x)/2 for z in z_levels]  # 3x + 2y = z => y = (z - 3x)/2

# Plot erstellen
plt.figure(figsize=(10, 6))

# Zeichne den zulässigen Bereich
plt.fill_between(x, 0, np.minimum(y1, y2), where=(x >= 0) & (y1 >= 0) & (y2 >= 0), 
                 alpha=0.2, color='skyblue', label='Zulässiger Bereich')

# Zeichne die Nebenbedingungen
plt.plot(x, y1, 'r-', label='2x + y = 20')
plt.plot(x, y2, 'g-', label='x + 2y = 20')
plt.axhline(y=0, color='k', linestyle='-', alpha=0.3, label='y = 0')
plt.axvline(x=0, color='k', linestyle='-', alpha=0.3, label='x = 0')

# Zeichne die Zielfunktionsebenen
for i, z_line in enumerate(z_lines):
    plt.plot(x, z_line, 'b--', alpha=0.5, label=f'3x + 2y = versch.' if i==0 else None)

# Markiere den optimalen Punkt
plt.plot(res.x[0], res.x[1], 'ro', markersize=10, label=f'Optimum ({res.x[0]:.1f}, {res.x[1]:.1f})')

# Beschrifte den Plot
plt.xlim(0, 22)
plt.ylim(0, 15)
plt.xlabel('x')
plt.ylabel('y')
plt.title('Lineares Optimierungsproblem: Maximiere 3x + 2y')
plt.grid(True, alpha=0.3)
plt.legend(loc='upper right')

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from scipy.optimize import minimize

# Definiere eine konvexe Funktion: f(x,y) = x^2 + 2y^2 + 2*x*y + 2x + 4y + 3
def konvexe_funktion(X):
    x, y = X
    return x**2 + 2*y**2 + 2*x*y + 2*x + 4*y + 3

# Gradient der Funktion (für effizientere Optimierung)
def gradient(X):
    x, y = X
    return np.array([2*x + 2*y + 2, 4*y + 2*x + 4])

# Erstelle Gitterpunkte für die Visualisierung
x = np.linspace(-5, 3, 100)
y = np.linspace(-4, 2, 100)
X, Y = np.meshgrid(x, y)
Z = np.zeros_like(X)

# Berechne die Funktionswerte für alle Gitterpunkte
for i in range(len(x)):
    for j in range(len(y)):
        Z[j, i] = konvexe_funktion([X[j, i], Y[j, i]])

# Führe die Optimierung durch - finde das Minimum der Funktion
startpunkt = np.array([0.0, 0.0])  # Startpunkt für die Optimierung
ergebnis = minimize(konvexe_funktion, startpunkt, method='BFGS', jac=gradient)

# Ausgabe der Optimierungsergebnisse
print("Optimierung erfolgreich:", ergebnis.success)
print("Anzahl der Funktionsaufrufe:", ergebnis.nfev)
print("Minimum gefunden bei x =", ergebnis.x[0], ", y =", ergebnis.x[1])
print("Funktionswert am Minimum:", ergebnis.fun)

# Zeige mathematisch, dass diese Funktion tatsächlich konvex ist
print("\nNachweis der Konvexität:")
print("Die Hesse-Matrix dieser Funktion ist:")
print("H = [[2, 2], [2, 4]]")
print("Eigenwerte der Hesse-Matrix:", np.linalg.eigvals(np.array([[2, 2], [2, 4]])))
print("Da alle Eigenwerte positiv sind, ist die Funktion streng konvex.")

# Zeichne die Funktion und das Minimum als 3D-Plot
fig = plt.figure(figsize=(12, 5))

# 3D-Oberflächenplot
ax1 = fig.add_subplot(1, 2, 1, projection='3d')
surf = ax1.plot_surface(X, Y, Z, cmap='viridis', alpha=0.8, linewidth=0, antialiased=True)
ax1.scatter(ergebnis.x[0], ergebnis.x[1], ergebnis.fun, color='red', s=50, label='Minimum')

ax1.set_xlabel('x')
ax1.set_ylabel('y')
ax1.set_zlabel('f(x,y)')
ax1.set_title('Konvexe Funktion: f(x,y) = x² + 2y² + 2xy + 2x + 4y + 3')
fig.colorbar(surf, ax=ax1, shrink=0.5, aspect=5)

# Konturplot mit Optimierungspfad
ax2 = fig.add_subplot(1, 2, 2)
contour = ax2.contour(X, Y, Z, 20, cmap='viridis')
ax2.scatter(ergebnis.x[0], ergebnis.x[1], color='red', s=50, label='Minimum')

# Zeige zwei Punkte und ihre Verbindungslinie, um die Konvexitätseigenschaft zu demonstrieren
punkt1 = np.array([-3, -2])
punkt2 = np.array([2, 1])
linie_x = np.linspace(punkt1[0], punkt2[0], 100)
linie_y = np.linspace(punkt1[1], punkt2[1], 100)
linie_z = np.zeros_like(linie_x)

# Berechne Funktionswerte entlang der Linie
for i in range(len(linie_x)):
    linie_z[i] = konvexe_funktion([linie_x[i], linie_y[i]])

# Zeichne die Punkte und die Linie im 3D-Plot
ax1.scatter(punkt1[0], punkt1[1], konvexe_funktion(punkt1), color='blue', s=50)
ax1.scatter(punkt2[0], punkt2[1], konvexe_funktion(punkt2), color='blue', s=50)
ax1.plot(linie_x, linie_y, linie_z, 'b-', linewidth=2)

# Zeichne die Punkte auch im Konturplot
ax2.scatter(punkt1[0], punkt1[1], color='blue', s=50)
ax2.scatter(punkt2[0], punkt2[1], color='blue', s=50)
ax2.plot(linie_x, linie_y, 'b-', linewidth=2, label='Verbindungslinie')

ax2.set_xlabel('x')
ax2.set_ylabel('y')
ax2.set_title('Höhenlinien und Minimum')
ax2.legend()
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

# Demonstration der Konvexitätseigenschaft
# Berechne einige Punkte auf der Verbindungslinie und vergleiche mit der tatsächlichen Funktion
print("\nDemonstration der Konvexitätseigenschaft:")
print("Für zwei Punkte auf dem Funktionsgraphen:")
print(f"Punkt 1: ({punkt1[0]}, {punkt1[1]}) mit f(Punkt1) = {konvexe_funktion(punkt1):.2f}")
print(f"Punkt 2: ({punkt2[0]}, {punkt2[1]}) mit f(Punkt2) = {konvexe_funktion(punkt2):.2f}")

# Wähle einen Punkt auf der Verbindungslinie (z.B. bei t=0.4)
t = 0.4
punkt_mitte = t * punkt1 + (1-t) * punkt2
f_mitte = konvexe_funktion(punkt_mitte)
f_linie = t * konvexe_funktion(punkt1) + (1-t) * konvexe_funktion(punkt2)

print("\nFür t =", t, "gilt:")
print(f"Punkt auf der Verbindungsstrecke: ({punkt_mitte[0]:.2f}, {punkt_mitte[1]:.2f})")
print(f"Tatsächlicher Funktionswert: f(Punkt) = {f_mitte:.2f}")
print(f"Wert auf der Verbindungslinie: {f_linie:.2f}")
print(f"Konvexitätsbedingung: f(Punkt) ≤ Wert auf Verbindungslinie: {f_mitte:.2f} ≤ {f_linie:.2f}")
print(f"Die Konvexitätsbedingung ist {'erfüllt' if f_mitte <= f_linie else 'nicht erfüllt'}")

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from mpl_toolkits.mplot3d import Axes3D

# Definiere die konvexe Funktion: f(x,y) = x^2 + 2y^2 + 2*x*y + 2x + 4y + 3
def konvexe_funktion(x, y):
    return x**2 + 2*y**2 + 2*x*y + 2*x + 4*y + 3

# Gradient der Funktion
def gradient(x, y):
    df_dx = 2*x + 2*y + 2
    df_dy = 4*y + 2*x + 4
    return np.array([df_dx, df_dy])

# Implementierung des Gradient Descent Algorithmus
def gradient_descent(start_punkt, lernrate, max_iterationen, toleranz=1e-6):
    # Startpunkt
    punkt = np.array(start_punkt, dtype=float)
    
    # Liste zur Speicherung der Punktfolge für die Visualisierung
    punkte_historie = [punkt.copy()]
    funktionswerte = [konvexe_funktion(punkt[0], punkt[1])]
    
    # Iteratives Update
    for i in range(max_iterationen):
        # Berechne den Gradienten am aktuellen Punkt
        grad = gradient(punkt[0], punkt[1])
        
        # Berechne die Norm des Gradienten (für Abbruchkriterium)
        grad_norm = np.linalg.norm(grad)
        
        # Abbruchkriterium: Wenn der Gradient nahe Null ist, haben wir ein Minimum gefunden
        if grad_norm < toleranz:
            print(f"Konvergenz nach {i+1} Iterationen!")
            break
            
        # Update-Regel: Bewegung in Richtung des negativen Gradienten
        punkt = punkt - lernrate * grad
        
        # Speichere für die Visualisierung
        punkte_historie.append(punkt.copy())
        funktionswerte.append(konvexe_funktion(punkt[0], punkt[1]))
    
    # Wenn die maximale Anzahl an Iterationen erreicht wurde
    else:
        print(f"Maximale Anzahl von {max_iterationen} Iterationen erreicht ohne Konvergenz.")
    
    return np.array(punkte_historie), np.array(funktionswerte)

# Optimales analytisches Minimum berechnen
# Für f(x,y) = x^2 + 2y^2 + 2*x*y + 2x + 4y + 3
# Löse das lineare Gleichungssystem:
# df/dx = 2x + 2y + 2 = 0
# df/dy = 4y + 2x + 4 = 0

# Aus der ersten Gleichung: x = -y - 1
# In die zweite einsetzen: 4y + 2(-y - 1) + 4 = 0
# 4y - 2y - 2 + 4 = 0
# 2y + 2 = 0
# y = -1

# Dann x = -y - 1 = -(-1) - 1 = 0
optimum = np.array([0, -1])
optimum_wert = konvexe_funktion(optimum[0], optimum[1])
print(f"Analytisches Optimum bei x = {optimum[0]}, y = {optimum[1]}")
print(f"Optimaler Funktionswert: {optimum_wert}")

# Gitterpunkte für die Visualisierung erstellen
x = np.linspace(-5, 5, 100)
y = np.linspace(-5, 5, 100)
X, Y = np.meshgrid(x, y)
Z = konvexe_funktion(X, Y)

# Startpunkt für alle drei Versuche
startpunkt = np.array([4.0, 3.0])

# Drei verschiedene Lernraten ausprobieren
# 1. Zu groß (führt zu Divergenz oder Oszillation)
lernrate_zu_gross = 0.9
# 2. Zu klein (zu langsame Konvergenz)
lernrate_zu_klein = 0.01
# 3. Optimal (schnelle Konvergenz)
lernrate_optimal = 0.1

# Anzahl der maximalen Iterationen
max_iter = 50

# Durchführung der Optimierung mit drei verschiedenen Lernraten
punkte_zu_gross, werte_zu_gross = gradient_descent(startpunkt, lernrate_zu_gross, max_iter)
punkte_zu_klein, werte_zu_klein = gradient_descent(startpunkt, lernrate_zu_klein, max_iter)
punkte_optimal, werte_optimal = gradient_descent(startpunkt, lernrate_optimal, max_iter)

# Erstelle Plots für die Visualisierung
fig, axs = plt.subplots(2, 2, figsize=(16, 12))

# 3D-Plot der Funktion (oben links)
ax_3d = fig.add_subplot(2, 2, 1, projection='3d')
surf = ax_3d.plot_surface(X, Y, Z, cmap='viridis', alpha=0.7, linewidth=0)
ax_3d.set_xlabel('x')
ax_3d.set_ylabel('y')
ax_3d.set_zlabel('f(x,y)')
ax_3d.set_title('Konvexe Funktion und optimale Gradient-Descent-Trajektorie')

# Optimale Trajektorie im 3D-Plot
ax_3d.plot(punkte_optimal[:, 0], punkte_optimal[:, 1], werte_optimal, 'r.-', linewidth=2, markersize=8)
ax_3d.plot([optimum[0]], [optimum[1]], [optimum_wert], 'mo', markersize=10, label='Globales Minimum')

# Contour-Plot mit zu großer Lernrate (oben rechts)
axs[0, 1].contour(X, Y, Z, levels=50, cmap='viridis')
axs[0, 1].set_title(f'Lernrate zu groß (η = {lernrate_zu_gross})')
axs[0, 1].plot(punkte_zu_gross[:, 0], punkte_zu_gross[:, 1], 'r.-', linewidth=2, markersize=8)
axs[0, 1].plot(optimum[0], optimum[1], 'mo', markersize=10)
axs[0, 1].set_xlabel('x')
axs[0, 1].set_ylabel('y')
axs[0, 1].grid(True)

# Contour-Plot mit zu kleiner Lernrate (unten links)
axs[1, 0].contour(X, Y, Z, levels=50, cmap='viridis')
axs[1, 0].set_title(f'Lernrate zu klein (η = {lernrate_zu_klein})')
axs[1, 0].plot(punkte_zu_klein[:, 0], punkte_zu_klein[:, 1], 'r.-', linewidth=2, markersize=8)
axs[1, 0].plot(optimum[0], optimum[1], 'mo', markersize=10)
axs[1, 0].set_xlabel('x')
axs[1, 0].set_ylabel('y')
axs[1, 0].grid(True)

# Contour-Plot mit optimaler Lernrate (unten rechts)
axs[1, 1].contour(X, Y, Z, levels=50, cmap='viridis')
axs[1, 1].set_title(f'Lernrate optimal (η = {lernrate_optimal})')
axs[1, 1].plot(punkte_optimal[:, 0], punkte_optimal[:, 1], 'r.-', linewidth=2, markersize=8)
axs[1, 1].plot(optimum[0], optimum[1], 'mo', markersize=10)
axs[1, 1].set_xlabel('x')
axs[1, 1].set_ylabel('y')
axs[1, 1].grid(True)

# Legende für das gesamte Figure
fig.legend(['Gradient Descent Pfad', 'Globales Minimum'], loc='upper center', bbox_to_anchor=(0.5, 0.05), ncol=2)

plt.tight_layout()

# Plot der Konvergenz (Funktionswert über Iterationen)
plt.figure(figsize=(10, 6))
plt.plot(werte_zu_gross, 'r-', linewidth=2, label=f'Zu große Lernrate (η = {lernrate_zu_gross})')
plt.plot(werte_zu_klein, 'g-', linewidth=2, label=f'Zu kleine Lernrate (η = {lernrate_zu_klein})')
plt.plot(werte_optimal, 'b-', linewidth=2, label=f'Optimale Lernrate (η = {lernrate_optimal})')
plt.axhline(y=optimum_wert, color='m', linestyle='--', label='Optimaler Wert')
plt.xlabel('Iteration')
plt.ylabel('Funktionswert')
plt.title('Konvergenzverhalten bei verschiedenen Lernraten')
plt.grid(True)
plt.legend()
plt.yscale('log')  # Logarithmische Skala für bessere Sichtbarkeit

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt

# Für Reproduzierbarkeit einen Seed setzen
np.random.seed(42)

# Anzahl der zu generierenden Punkte
n_samples = 2000

# 1. Generiere gleichverteilte Zufallszahlen im Intervall [0,1] x [0,1]
uniform_samples = np.random.uniform(0, 1, size=(n_samples, 2))

# 2. Generiere normalverteilte Zufallszahlen mit Mittelwert 0 und Standardabweichung 1
gaussian_samples = np.random.normal(0, 1, size=(n_samples, 2))

# Erstelle eine Figur mit zwei Subplots
fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# --- PLOT 1: Gleichverteilung ---
axes[0].scatter(
    uniform_samples[:, 0], 
    uniform_samples[:, 1],
    s=10,  # Punktgröße
    alpha=0.6,  # Transparenz
    c='teal'  # Farbe
)

# Beschriftung des ersten Plots
axes[0].set_title('Gleichverteilung im Einheitsquadrat [0,1] × [0,1]')
axes[0].set_xlabel('X ~ U(0,1)')
axes[0].set_ylabel('Y ~ U(0,1)')
axes[0].grid(True, alpha=0.3)
axes[0].set_xlim(-0.05, 1.05)
axes[0].set_ylim(-0.05, 1.05)

# --- PLOT 2: Normalverteilung ---
axes[1].scatter(
    gaussian_samples[:, 0], 
    gaussian_samples[:, 1],
    s=10,
    alpha=0.6,
    c='navy'
)

# Beschriftung des zweiten Plots
axes[1].set_title('Normalverteilung mit Mittelwert 0 und Standardabweichung 1')
axes[1].set_xlabel('X ~ N(0,1)')
axes[1].set_ylabel('Y ~ N(0,1)')
axes[1].grid(True, alpha=0.3)
axes[1].set_xlim(-4, 4)
axes[1].set_ylim(-4, 4)

# Konzentrische Kreise für die Wahrscheinlichkeitsmasse (1, 2 und 3 Standardabweichungen)
circles = [1, 2, 3]
for r in circles:
    circle = plt.Circle((0, 0), r, fill=False, color='red', linestyle='--', alpha=0.7)
    axes[1].add_patch(circle)

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt

# Wir verwenden die gleiche konvexe Funktion wie zuvor:
# f(x,y) = x^2 + 2y^2 + 2*x*y + 2x + 4y + 3
def konvexe_funktion(x, y):
    return x**2 + 2*y**2 + 2*x*y + 2*x + 4*y + 3

# Einfache stochastische Optimierung: Random Search
def random_search(max_iterationen, suchbereich):
    # Analytisches Optimum (zum Vergleich)
    optimum = np.array([0.0, -1.0])
    optimum_wert = konvexe_funktion(optimum[0], optimum[1])
    
    # Startpunkt zufällig wählen
    beste_lösung = np.random.uniform(suchbereich[0], suchbereich[1], size=2)
    bester_wert = konvexe_funktion(beste_lösung[0], beste_lösung[1])
    
    # Historie für die Visualisierung
    historie_lösungen = [beste_lösung.copy()]
    historie_werte = [bester_wert]
    
    for i in range(max_iterationen):
        # Erzeuge einen zufälligen Punkt im Suchbereich
        kandidat = np.random.uniform(suchbereich[0], suchbereich[1], size=2)
        kandidat_wert = konvexe_funktion(kandidat[0], kandidat[1])
        
        # Speichere den Kandidaten für die Visualisierung
        historie_lösungen.append(kandidat.copy())
        historie_werte.append(kandidat_wert)
        
        # Wenn der Kandidat besser ist, aktualisiere die beste Lösung
        if kandidat_wert < bester_wert:
            beste_lösung = kandidat.copy()
            bester_wert = kandidat_wert
    
    return beste_lösung, bester_wert, np.array(historie_lösungen), np.array(historie_werte), optimum, optimum_wert

# Parameter
max_iter = 1000
suchbereich = [-5, 5]  # Suchbereich für x und y: [-5, 5] x [-5, 5]

# Führe die stochastische Optimierung durch
np.random.seed(42)  # Für Reproduzierbarkeit
beste_lösung, bester_wert, historie_lösungen, historie_werte, optimum, optimum_wert = random_search(max_iter, suchbereich)

# Ergebnisse ausgeben
print(f"Beste gefundene Lösung: x = {beste_lösung[0]:.4f}, y = {beste_lösung[1]:.4f}")
print(f"Bester gefundener Wert: {bester_wert:.4f}")
print(f"Analytisches Optimum: x = {optimum[0]:.4f}, y = {optimum[1]:.4f}")
print(f"Optimaler Wert: {optimum_wert:.4f}")
print(f"Abweichung vom Optimum: {abs(bester_wert - optimum_wert):.4f}")

# Visualisierung der Konvergenz
plt.figure(figsize=(15, 6))

# Plot 1: Alle getesteten Punkte im Suchraum
plt.subplot(1, 2, 1)
# Gitterpunkte für den Hintergrund (Konturen der Funktion)
x = np.linspace(suchbereich[0], suchbereich[1], 100)
y = np.linspace(suchbereich[0], suchbereich[1], 100)
X, Y = np.meshgrid(x, y)
Z = np.zeros_like(X)
for i in range(len(x)):
    for j in range(len(y)):
        Z[j, i] = konvexe_funktion(X[j, i], Y[j, i])

# Zeichne Konturen
plt.contour(X, Y, Z, 20, cmap='viridis', alpha=0.7)

# Zeige alle getesteten Punkte
plt.scatter(historie_lösungen[:, 0], historie_lösungen[:, 1], 
            c=np.arange(len(historie_lösungen)), cmap='autumn', 
            alpha=0.6, s=10, label='Getestete Punkte')

# Markiere das gefundene und das analytische Optimum
plt.scatter(beste_lösung[0], beste_lösung[1], 
            color='red', s=100, marker='*', label='Gefundenes Optimum')
plt.scatter(optimum[0], optimum[1], 
            color='blue', s=100, marker='o', label='Analytisches Optimum')

plt.xlim(suchbereich)
plt.ylim(suchbereich)
plt.title('Stochastische Optimierung: Random Search')
plt.xlabel('x')
plt.ylabel('y')
plt.grid(True, alpha=0.3)
plt.legend()

# Plot 2: Konvergenzverlauf des besten Funktionswerts
plt.subplot(1, 2, 2)

# Berechne den besten Wert bis zur i-ten Iteration
beste_werte_bis_i = np.minimum.accumulate(historie_werte)

# Zeichne den Konvergenzverlauf
plt.plot(beste_werte_bis_i, 'r-', linewidth=2, label='Bester Wert')
plt.axhline(y=optimum_wert, color='blue', linestyle='--', label='Optimaler Wert')

plt.title('Konvergenzverlauf')
plt.xlabel('Iteration')
plt.ylabel('Funktionswert')
plt.grid(True, alpha=0.3)
plt.legend()
plt.yscale('log')  # Logarithmische Skala für bessere Sichtbarkeit

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# Rastrigin-Funktion: eine bekannte Testfunktion mit vielen lokalen Minima
# f(x,y) = 20 + x^2 + y^2 - 10*cos(2π*x) - 10*cos(2π*y)
# Das globale Minimum ist bei (0,0) mit f(0,0) = 0
def rastrigin(x, y):
    return 20 + x**2 + y**2 - 10*np.cos(2*np.pi*x) - 10*np.cos(2*np.pi*y)

# Implementierung von Simulated Annealing mit verschiedenen Abkühlungsstrategien
def simulated_annealing(cooling_schedule, max_iter, suchbereich, init_temp):
    # Analytisches Optimum (zum Vergleich)
    optimum = np.array([0.0, 0.0])
    optimum_wert = rastrigin(optimum[0], optimum[1])
    
    # Startpunkt zufällig wählen
    aktuelle_lösung = np.random.uniform(suchbereich[0], suchbereich[1], size=2)
    aktueller_wert = rastrigin(aktuelle_lösung[0], aktuelle_lösung[1])
    
    # Beste gefundene Lösung speichern
    beste_lösung = aktuelle_lösung.copy()
    bester_wert = aktueller_wert
    
    # Historie für die Visualisierung
    historie_lösungen = [aktuelle_lösung.copy()]
    historie_werte = [aktueller_wert]
    historie_beste_werte = [bester_wert]
    historie_temperatur = [init_temp]
    
    # Initiale Temperatur
    temperatur = init_temp
    
    # Schleife über alle Iterationen
    for i in range(max_iter):
        # Aktualisiere die Temperatur je nach Abkühlungsstrategie
        if cooling_schedule == "logarithmisch":
            # Logarithmische Abkühlung: T(i) = T_0 / ln(i+2)
            temperatur = init_temp / np.log(i + 2)
        elif cooling_schedule == "geometrisch":
            # Geometrische Abkühlung: T(i) = T_0 * alpha^i
            alpha = 0.99  # Abkühlungsrate
            temperatur = init_temp * (alpha ** i)
        elif cooling_schedule == "linear":
            # Lineare Abkühlung: T(i) = T_0 * (1 - i/max_iter)
            temperatur = init_temp * (1 - i/max_iter)
        
        # Speichere die aktuelle Temperatur
        historie_temperatur.append(temperatur)
        
        # Erzeuge eine neue Nachbarlösung durch Gaußsche Mutation
        # Die Standardabweichung der Mutation hängt von der Temperatur ab
        sigma = 0.1 + temperatur * 0.5  # Größere Schritte bei höherer Temperatur
        nachbar = aktuelle_lösung + np.random.normal(0, sigma, size=2)
        
        # Beschränke die Nachbarlösung auf den Suchbereich
        nachbar = np.clip(nachbar, suchbereich[0], suchbereich[1])
        nachbar_wert = rastrigin(nachbar[0], nachbar[1])
        
        # Speichere den Nachbarn für die Visualisierung
        historie_lösungen.append(nachbar.copy())
        historie_werte.append(nachbar_wert)
        
        # Entscheide, ob der Nachbar akzeptiert wird
        if nachbar_wert < aktueller_wert:
            # Wenn der Nachbar besser ist, akzeptiere ihn immer
            aktuelle_lösung = nachbar.copy()
            aktueller_wert = nachbar_wert
            
            # Aktualisiere ggf. die beste gefundene Lösung
            if aktueller_wert < bester_wert:
                beste_lösung = aktuelle_lösung.copy()
                bester_wert = aktueller_wert
        else:
            # Wenn der Nachbar schlechter ist, akzeptiere ihn mit einer gewissen Wahrscheinlichkeit
            # Die Wahrscheinlichkeit hängt von der Verschlechterung und der Temperatur ab
            delta = nachbar_wert - aktueller_wert
            p = np.exp(-delta / temperatur)
            
            if np.random.random() < p:
                aktuelle_lösung = nachbar.copy()
                aktueller_wert = nachbar_wert
        
        # Speichere den besten Wert bis zur aktuellen Iteration
        historie_beste_werte.append(bester_wert)
    
    return beste_lösung, bester_wert, np.array(historie_lösungen), np.array(historie_werte), np.array(historie_beste_werte), np.array(historie_temperatur), optimum, optimum_wert

# Parameter
max_iter = 10000
suchbereich = [-5.12, 5.12]  # Typischer Suchbereich für die Rastrigin-Funktion
init_temp = 10.0  # Initiale Temperatur

# Liste der zu testenden Abkühlungsstrategien
cooling_schedules = ["logarithmisch", "geometrisch", "linear"]
farben = ["blue", "green", "red"]

# Visualisierung der Rastrigin-Funktion
x = np.linspace(suchbereich[0], suchbereich[1], 100)
y = np.linspace(suchbereich[0], suchbereich[1], 100)
X, Y = np.meshgrid(x, y)
Z = rastrigin(X, Y)

fig = plt.figure(figsize=(12, 9))
ax1 = fig.add_subplot(2, 2, 1, projection='3d')
surf = ax1.plot_surface(X, Y, Z, cmap='viridis', alpha=0.8, linewidth=0, antialiased=True)
ax1.set_xlabel('x')
ax1.set_ylabel('y')
ax1.set_zlabel('f(x,y)')
ax1.set_title('Rastrigin-Funktion')

# Konturplot
ax2 = fig.add_subplot(2, 2, 2)
contour = ax2.contour(X, Y, Z, 20, cmap='viridis')
ax2.set_xlabel('x')
ax2.set_ylabel('y')
ax2.set_title('Höhenlinien der Rastrigin-Funktion')
fig.colorbar(contour, ax=ax2)

# Konvergenzplot für verschiedene Abkühlungsstrategien
ax3 = fig.add_subplot(2, 2, 3)

# Führe Simulated Annealing mit jeder Abkühlungsstrategie durch
for i, schedule in enumerate(cooling_schedules):
    # Setze zufälligen Seed für Reproduzierbarkeit
    np.random.seed(42 + i)
    
    # Führe Simulated Annealing durch
    beste_lösung, bester_wert, historie_lösungen, historie_werte, historie_beste_werte, historie_temperatur, optimum, optimum_wert = simulated_annealing(schedule, max_iter, suchbereich, init_temp)
    
    # Ergebnisse ausgeben
    print(f"\nAbkühlungsstrategie: {schedule}")
    print(f"Beste gefundene Lösung: x = {beste_lösung[0]:.4f}, y = {beste_lösung[1]:.4f}")
    print(f"Bester gefundener Wert: {bester_wert:.4f}")
    print(f"Analytisches Optimum: x = {optimum[0]:.4f}, y = {optimum[1]:.4f}")
    print(f"Optimaler Wert: {optimum_wert:.4f}")
    print(f"Abweichung vom Optimum: {abs(bester_wert - optimum_wert):.4f}")
    
    # Zeichne Konvergenzverlauf
    ax3.plot(historie_beste_werte, color=farben[i], linewidth=2, label=f'{schedule}')
    
    # Zeichne Endpunkt in den Konturplot
    ax2.scatter(beste_lösung[0], beste_lösung[1], color=farben[i], s=100, marker='*', label=f'{schedule}')

# Füge Referenzlinie für das Optimum hinzu
ax3.axhline(y=optimum_wert, color='black', linestyle='--', label='Globales Optimum')

ax3.set_xlabel('Iteration')
ax3.set_ylabel('Bester Funktionswert')
ax3.set_ylim(.02,100)
ax3.set_title('Konvergenzverhalten')
ax3.set_xscale('log')  # Logarithmische Skala für bessere Sichtbarkeit
ax3.set_yscale('log')  # Logarithmische Skala für bessere Sichtbarkeit
ax3.grid(True, alpha=0.3)
ax3.legend()

# Temperaturverlauf für verschiedene Abkühlungsstrategien
ax4 = fig.add_subplot(2, 2, 4)

# Setze Zufallsseed für Reproduzierbarkeit zurück
np.random.seed(42)

# Berechne Temperaturverläufe ohne tatsächliche Optimierung durchzuführen
temperatur = init_temp
temp_log = [temperatur]
temp_geo = [temperatur]
temp_lin = [temperatur]

for i in range(1, max_iter + 1):
    # Logarithmische Abkühlung
    temp_log.append(init_temp / np.log(i + 2))
    
    # Geometrische Abkühlung
    alpha = 0.99
    temp_geo.append(init_temp * (alpha ** i))
    
    # Lineare Abkühlung
    temp_lin.append(init_temp * (1 - i/max_iter))

# Zeichne Temperaturverläufe
ax4.plot(temp_log, color='blue', linewidth=2, label='Logarithmisch')
ax4.plot(temp_geo, color='green', linewidth=2, label='Geometrisch')
ax4.plot(temp_lin, color='red', linewidth=2, label='Linear')

ax4.set_xlabel('Iteration')
ax4.set_ylabel('Temperatur')
ax4.set_title('Temperaturverlauf')
ax4.set_xscale('log')  # Logarithmische Skala für bessere Sichtbarkeit
ax4.grid(True, alpha=0.3)
ax4.legend()

plt.tight_layout()
plt.show()

import numpy as np
import time

# Seed für Reproduzierbarkeit
np.random.seed(42)

# Anzahl der Gegenstände
n_items = 20

# Generiere zufällige Gewichte und Werte für die Gegenstände
# Gewichte zwischen, 1 und 10
weights = np.random.randint(1, 11, size=n_items)
# Werte zwischen, 1 und 100
values = np.random.randint(1, 101, size=n_items)

# Kapazität des Rucksacks (ca. 30% der Gesamtgewichte)
capacity = int(np.sum(weights) * 0.3)

# Zeige das Problem
print(f"Rucksackproblem mit {n_items} Gegenständen und Kapazität {capacity}:")
print("\nGegenstände (Index, Gewicht, Wert, Wert/Gewicht-Verhältnis):")
for i in range(n_items):
    print(f"{i:2d}: Gewicht = {weights[i]:2d}, Wert = {values[i]:3d}, Verhältnis = {values[i]/weights[i]:5.2f}")

print(f"\nGesamtgewicht aller Gegenstände: {np.sum(weights)}")
print(f"Gesamtwert aller Gegenstände: {np.sum(values)}")
print(f"Rucksackkapazität: {capacity}")

# Save the problem definition for later reference
problem_size = n_items
problem_capacity = capacity
problem_weights = weights.copy()
problem_values = values.copy()

import numpy as np
import itertools
import time

# Brute-Force-Lösung für das Rucksackproblem
def brute_force_knapsack(weights, values, capacity):
    n = len(weights)
    max_value = 0
    best_combination = None
    
    # Starte die Zeitmessung
    start_time = time.time()
    
    # Evaluiere alle möglichen Kombinationen (2^n)
    total_combinations = 2**n
    evaluated = 0
    
    for i in range(1, total_combinations):
        # Binäre Repräsentation der aktuellen Kombination
        binary = bin(i)[2:].zfill(n)
        selection = [int(bit) for bit in binary]
        
        # Berechne Gesamtgewicht und -wert
        total_weight = sum(weights[j] for j in range(n) if selection[j] == 1)
        total_value = sum(values[j] for j in range(n) if selection[j] == 1)
        
        evaluated += 1
        
        # Prüfe, ob diese Kombination gültig ist und besser als die bisherige beste
        if total_weight <= capacity and total_value > max_value:
            max_value = total_value
            best_combination = selection
    
    # Ende der Zeitmessung
    end_time = time.time()
    execution_time = end_time - start_time
    
    # Zeige Details der optimalen Lösung
    if best_combination is not None:
        selected_items = [i for i in range(n) if best_combination[i] == 1]
        total_weight = sum(weights[i] for i in selected_items)
        
        print(f"Brute-Force-Lösung für {n} Gegenstände:")
        print(f"Ausgewählte Gegenstände: {selected_items}")
        print(f"Gewählte Gegenstände: {len(selected_items)} von {n}")
        print(f"Gesamtgewicht: {total_weight} von {capacity} ({total_weight/capacity*100:.1f}%)")
        print(f"Optimaler Wert: {max_value}")
        print(f"Ausgeführt in {execution_time:.6f} Sekunden")
        print(f"Evaluierte Kombinationen: {evaluated:,} von {total_combinations:,} ({evaluated/total_combinations*100:.2f}%)")
    else:
        print("Keine gültige Lösung gefunden!")
    
    return best_combination, max_value, execution_time

# Rufe die globalen Problemdefinitionen ab
weights = problem_weights
values = problem_values
capacity = problem_capacity
n_items = problem_size

# Nur ausführen, wenn die Anzahl der Gegenstände nicht zu groß ist
if n_items <= 25:  # Bei größerer Anzahl wird Brute-Force unpraktisch
    optimale_lösung, optimaler_wert, ausführungszeit_bf = brute_force_knapsack(weights, values, capacity)
else:
    print(f"ACHTUNG: Brute-Force für {n_items} Gegenstände ist zu rechenintensiv!")
    print(f"Das würde {2**n_items:,} Kombinationen erfordern.")
    print("Reduziere die Anzahl der Gegenstände auf <= 25 oder verwende nur den GA.")

import numpy as np
import matplotlib.pyplot as plt
import time

class GeneticAlgorithmKnapsack:
    def __init__(self, weights, values, capacity, population_size=100, generations=100, 
                 crossover_rate=0.8, mutation_rate=0.1, elitism=True, tournament_size=3):
        self.weights = weights
        self.values = values
        self.capacity = capacity
        self.population_size = population_size
        self.generations = generations
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.elitism = elitism
        self.tournament_size = tournament_size
        
        self.item_count = len(weights)
        self.best_solution = None
        self.best_fitness = 0
        self.fitness_history = []
        
    def initialize_population(self):
        """Erstelle eine zufällige Startpopulation"""
        population = np.random.randint(0, 2, size=(self.population_size, self.item_count))
        return population
    
    def calculate_fitness(self, individual):
        """Berechne die Fitness eines Individuums (= Gesamtwert, wenn gültig)"""
        total_weight = np.sum(individual * self.weights)
        total_value = np.sum(individual * self.values)
        
        # Wenn das Gewicht die Kapazität überschreitet, setze Fitness auf 0
        if total_weight > self.capacity:
            return 0
        return total_value
    
    def evaluate_population(self, population):
        """Berechne die Fitness für die gesamte Population"""
        fitness_values = np.zeros(self.population_size)
        for i in range(self.population_size):
            fitness_values[i] = self.calculate_fitness(population[i])
        return fitness_values
    
    def tournament_selection(self, population, fitness_values):
        """Wähle ein Individuum durch Turnierselektion"""
        # Wähle zufällig tournament_size Individuen
        tournament_indices = np.random.choice(self.population_size, self.tournament_size, replace=False)
        tournament_fitness = fitness_values[tournament_indices]
        
        # Wähle das Individuum mit der höchsten Fitness
        winner_index = tournament_indices[np.argmax(tournament_fitness)]
        return population[winner_index].copy()
    
    def crossover(self, parent1, parent2):
        """Ein-Punkt-Crossover zwischen zwei Eltern"""
        if np.random.random() < self.crossover_rate:
            # Wähle zufälligen Crossover-Punkt
            crossover_point = np.random.randint(1, self.item_count)
            
            # Erzeuge Kinder durch Austausch der Gene ab dem Crossover-Punkt
            child1 = np.concatenate([parent1[:crossover_point], parent2[crossover_point:]])
            child2 = np.concatenate([parent2[:crossover_point], parent1[crossover_point:]])
            
            return child1, child2
        else:
            # Keine Kreuzung, gib Eltern unverändert zurück
            return parent1.copy(), parent2.copy()
    
    def mutate(self, individual):
        """Bit-Flip-Mutation für ein Individuum"""
        for i in range(self.item_count):
            if np.random.random() < self.mutation_rate:
                individual[i] = 1 - individual[i]  # Flip 0->1 oder 1->0
        return individual
    
    def evolve(self, verbose=True):
        """Führe den genetischen Algorithmus aus"""
        start_time = time.time()
        
        # Initialisiere Population
        population = self.initialize_population()
        
        # Evaluiere initiale Population
        fitness_values = self.evaluate_population(population)
        
        # Finde das beste Individuum
        best_idx = np.argmax(fitness_values)
        self.best_solution = population[best_idx].copy()
        self.best_fitness = fitness_values[best_idx]
        
        # Sammle Fitness-Historie für die Visualisierung
        self.fitness_history = [self.best_fitness]
        
        # Evolutionsschleife
        for generation in range(self.generations):
            # Erzeuge neue Population
            new_population = np.zeros((self.population_size, self.item_count), dtype=int)
            
            # Elitismus: Bewahre das beste Individuum
            elite_offset = 0
            if self.elitism:
                new_population[0] = self.best_solution
                elite_offset = 1
            
            # Fülle die neue Population
            for i in range(elite_offset, self.population_size, 2):
                # Selektion
                parent1 = self.tournament_selection(population, fitness_values)
                parent2 = self.tournament_selection(population, fitness_values)
                
                # Crossover
                if i + 1 < self.population_size:
                    child1, child2 = self.crossover(parent1, parent2)
                    
                    # Mutation
                    child1 = self.mutate(child1)
                    child2 = self.mutate(child2)
                    
                    new_population[i] = child1
                    new_population[i+1] = child2
                else:
                    # Wenn ungerade Populationsgröße, füge nur ein Kind hinzu
                    child1 = self.mutate(parent1)
                    new_population[i] = child1
            
            # Ersetze alte Population
            population = new_population
            
            # Evaluiere neue Population
            fitness_values = self.evaluate_population(population)
            
            # Aktualisiere beste Lösung
            current_best_idx = np.argmax(fitness_values)
            current_best_fitness = fitness_values[current_best_idx]
            
            if current_best_fitness > self.best_fitness:
                self.best_solution = population[current_best_idx].copy()
                self.best_fitness = current_best_fitness
            
            # Füge zur Historie hinzu
            self.fitness_history.append(self.best_fitness)
            
            # Ausgabe des Fortschritts (optional)
            if verbose and (generation + 1) % 10 == 0:
                print(f"Generation {generation + 1}/{self.generations}, Beste Fitness: {self.best_fitness}")
        
        end_time = time.time()
        execution_time = end_time - start_time
        
        # Ergebnisse ausgeben
        if verbose:
            selected_items = [i for i in range(self.item_count) if self.best_solution[i] == 1]
            total_weight = sum(self.weights[i] for i in selected_items)
            
            print(f"\nGA-Lösung für {self.item_count} Gegenstände:")
            print(f"Ausgewählte Gegenstände: {selected_items}")
            print(f"Gewählte Gegenstände: {len(selected_items)} von {self.item_count}")
            print(f"Gesamtgewicht: {total_weight} von {self.capacity} ({total_weight/self.capacity*100:.1f}%)")
            print(f"Bester gefundener Wert: {self.best_fitness}")
            print(f"Ausgeführt in {execution_time:.6f} Sekunden")
        
        return self.best_solution, self.best_fitness, execution_time
    
    def plot_progress(self):
        """Visualisiere den Fortschritt des GA über die Generationen"""
        plt.figure(figsize=(10, 6))
        plt.plot(range(len(self.fitness_history)), self.fitness_history, 'b-')
        plt.title('Fortschritt des Genetischen Algorithmus')
        plt.xlabel('Generation')
        plt.ylabel('Beste Fitness (Wert)')
        plt.grid(True, alpha=0.3)
        
        # Zeichne Endwert als roten Punkt
        plt.plot(len(self.fitness_history)-1, self.fitness_history[-1], 'ro', markersize=8)
        plt.annotate(f'Finaler Wert: {self.fitness_history[-1]}', 
                    xy=(len(self.fitness_history)-1, self.fitness_history[-1]),
                    xytext=(10, -20), textcoords='offset points',
                    bbox=dict(boxstyle='round,pad=0.5', fc='yellow', alpha=0.5))
        
        plt.tight_layout()
        plt.show()

# Rufe die globalen Problemdefinitionen ab
weights = problem_weights
values = problem_values
capacity = problem_capacity
n_items = problem_size

# Parameter für den GA
population_size = 100
generations = 100
crossover_rate = 0.8
mutation_rate = 0.1
elitism = True
tournament_size = 3

# Führe den GA aus
print(f"Löse das Rucksackproblem mit {n_items} Gegenständen durch einen Genetischen Algorithmus...")
ga = GeneticAlgorithmKnapsack(
    weights, values, capacity,
    population_size=population_size,
    generations=generations,
    crossover_rate=crossover_rate,
    mutation_rate=mutation_rate,
    elitism=elitism,
    tournament_size=tournament_size
)

beste_lösung, bester_wert, ausführungszeit = ga.evolve(verbose=True)

# Visualisiere den Fortschritt
ga.plot_progress()

# Vergleiche mit Brute-Force, falls verfügbar
if n_items <= 25 and 'optimaler_wert' in globals():
    print("\nVergleich mit Brute-Force:")
    print(f"Brute-Force-Wert: {optimaler_wert}")
    print(f"GA-Wert: {bester_wert}")
    print(f"Unterschied: {abs(optimaler_wert - bester_wert)} ({abs(optimaler_wert - bester_wert)/optimaler_wert*100:.2f}%)")
    print(f"Brute-Force-Zeit: {ausführungszeit_bf:.6f} Sekunden")
    print(f"GA-Zeit: {ausführungszeit:.6f} Sekunden")
    print(f"Zeitverhältnis (Brute-Force/GA): {ausführungszeit_bf/ausführungszeit:.2f}")

import numpy as np
import matplotlib.pyplot as plt
from math import factorial

# Seed für Reproduzierbarkeit
np.random.seed(42)

# Anzahl der Städte
n_cities = 15

# Erstelle Fantasienamen für die Städte
city_names = [
    "Bergheim", "Talblick", "Waldkirchen", "Seehausen", "Flussbach",
    "Sonnental", "Mondberg", "Sternfeld", "Nebeldorf", "Windhaven",
    "Regenbogen", "Donnerfels", "Blitzhügel", "Schneegipfel", "Feuertal"
]

# Koordinaten der Städte generieren (in einem Bereich von 0 bis 100)
x_coords = np.random.uniform(0, 100, n_cities)
y_coords = np.random.uniform(0, 100, n_cities)

# Erstelle eine Liste von Stadt-Dictionaries mit Namen und Koordinaten
cities = []
for i in range(n_cities):
    cities.append({
        "name": city_names[i],
        "x": x_coords[i],
        "y": y_coords[i]
    })

# Zeige die Städte und ihre Koordinaten an
print(f"TSP-Problem mit {n_cities} Städten:")
print("\nStädte und ihre Koordinaten:")
for i, city in enumerate(cities):
    print(f"{i}: {city['name']} ({city['x']:.2f}, {city['y']:.2f})")

# Erstelle eine Karte der Städte
plt.figure(figsize=(10, 8))
plt.scatter(x_coords, y_coords, c='darkblue', s=100, zorder=5)

# Beschrifte die Städte
for i, city in enumerate(cities):
    plt.annotate(
        city['name'],
        (city['x'], city['y']),
        xytext=(5, 5),
        textcoords='offset points',
        fontsize=9,
        bbox=dict(boxstyle="round,pad=0.3", fc="white", ec="gray", alpha=0.8)
    )

plt.title('Fantasiekarte für das TSP-Problem')
plt.xlabel('x-Koordinate')
plt.ylabel('y-Koordinate')
plt.grid(alpha=0.3)
plt.xlim(-5, 105)
plt.ylim(-5, 105)
plt.tight_layout()
plt.show()

# Information über das Problem und die optimale Lösung
print(f"Die Gesamtzahl möglicher Routen beträgt (n-1)!/2 = {factorial(n_cities-1)/2:.2e}")

# Speichern der Daten für spätere Verwendung
tsp_n_cities = n_cities
tsp_city_names = city_names
tsp_x_coords = x_coords
tsp_y_coords = y_coords