Lernen Partikelschwarmoptimierung | Schwarmbasierte Algorithmen

Definition

Particle Swarm Optimization (PSO) ist ein populationsbasierter, bio-inspirierter Algorithmus, der sich von dem kollektiven Verhalten von Vogelschwärmen und Fischschwärmen inspirieren lässt. In PSO arbeitet man mit einem Schwarm aus einfachen Agenten, den sogenannten Partikeln. Jedes Partikel stellt eine potenzielle Lösung für das Optimierungsproblem dar und bewegt sich durch den Suchraum, indem es seine Position und Geschwindigkeit aktualisiert.

Zentrale Konzepte

Die Bewegung jedes Partikels wird von zwei Hauptfaktoren beeinflusst:

Persönliches Bestes: Die beste bisher vom Partikel selbst gefundene Position;
Globales Bestes: Die beste Position, die vom gesamten Schwarm zu irgendeinem Zeitpunkt während der Suche gefunden wurde.

Diese Dynamik ermöglicht es dem Schwarm, den Lösungsraum effizient zu erkunden, wobei ein Gleichgewicht zwischen Exploration (Erkundung neuer Bereiche) und Exploitation (Verfeinerung bekannter guter Bereiche) entsteht, da die Partikel miteinander kommunizieren und voneinander lernen.

Schlüsselkonzepte im PSO:

Partikel: Agenten, die mögliche Lösungen repräsentieren;
Position: der aktuelle Ort eines Partikels im Suchraum;
Geschwindigkeit: Richtung und Geschwindigkeit der Partikelbewegung;
Persönlich beste Position: die beste Position, die jedes Partikel bisher gefunden hat;
Global beste Position: die beste Position, die ein beliebiges Partikel im Schwarm gefunden hat.

Durch die iterative Aktualisierung von Positionen und Geschwindigkeiten auf Basis dieser Prinzipien ermöglicht PSO die Lösung komplexer Optimierungsprobleme auf flexible und effiziente Weise.

Beispiel: Grundlegende PSO-Implementierung


              123456789101112131415161718192021222324252627282930313233343536373839404142434445
            
import numpy as np

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Initialize particle positions and velocities
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

# PSO loop
for iteration in range(num_iterations):
    # Evaluate current positions
    scores = objective(positions)
    # Update personal bests
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    # Update global best
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    # Update velocities and positions
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities

print(f"Best position found: {global_best_position:.3f}")
print(f"Objective value: {objective(global_best_position):.3f}")

Schritt-für-Schritt: Positions- und Geschwindigkeitsaktualisierung im PSO

Jede Partikel bewerten: Für jedes Partikel den Wert der Zielfunktion an seiner aktuellen Position berechnen;
Persönliches Bestes aktualisieren: Wenn die aktuelle Position einen besseren Wert als jede vorherige Position liefert, diese als neues persönliches Bestes speichern;
Globales Bestes aktualisieren: Das beste Ergebnis unter allen persönlichen Bestwerten identifizieren und die globale Bestposition entsprechend aktualisieren;
Geschwindigkeit aktualisieren: Für jedes Partikel die neue Geschwindigkeit berechnen unter Verwendung von:
- Dem Trägheitsterm (w * velocity), der das Partikel dazu ermutigt, sich in seiner aktuellen Richtung weiterzubewegen;
- Dem kognitiven Term (c1 * r1 * (personal_best - position)), der das Partikel zu seiner eigenen besten Erfahrung zieht;
- Dem sozialen Term (c2 * r2 * (global_best - position)), der das Partikel zum vom Schwarm gefundenen Besten zieht;
Position aktualisieren: Die neue Geschwindigkeit zur aktuellen Position addieren, um die neue Position des Partikels im Suchraum zu erhalten.

Die Partikel wiederholen diese Schritte für eine festgelegte Anzahl an Iterationen oder bis Konvergenzkriterien erfüllt sind.

Beispiel: Visualisierung von Partikeltrajektorien


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
            
import numpy as np
import matplotlib.pyplot as plt

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Re-run the PSO loop, recording particle trajectories
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

trajectories = [positions.copy()]

for iteration in range(num_iterations):
    scores = objective(positions)
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities
    trajectories.append(positions.copy())

trajectories = np.array(trajectories)

# Plot trajectories
plt.figure(figsize=(10, 6))
for i in range(num_particles):
    plt.plot(trajectories[:, i], label=f"Particle {i+1}", alpha=0.5)
plt.axhline(3, color='red', linestyle='--', label='Optimum (x=3)')
plt.title('Particle Trajectories in PSO')
plt.xlabel('Iteration')
plt.ylabel('Position')
plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left', fontsize='small')
plt.tight_layout()
plt.show()

Parameteranalyse

Die Wahl der PSO-Parameter hat einen erheblichen Einfluss auf das Verhalten und die Leistung des Algorithmus:

Trägheitskoeffizient (w): Steuert, wie viel der vorherigen Geschwindigkeit beibehalten wird;
- Höhere Werte fördern die Exploration und helfen Partikeln, lokalen Minima zu entkommen;
- Niedrigere Werte begünstigen die Ausnutzung und beschleunigen die Konvergenz.
Kognitiver Koeffizient (c1): Bestimmt, wie stark Partikel zu ihren eigenen besten Positionen gezogen werden;
- Eine Erhöhung dieses Wertes fördert unabhängige Exploration und erhält die Diversität des Schwarms.
Sozialer Koeffizient (c2): Steuert die Anziehung zur globalen Bestposition;
- Eine Erhöhung dieses Wertes beschleunigt die Konvergenz durch Förderung des kollektiven Lernens;
- Zu hohe Werte können zu vorzeitiger Stagnation führen.

Eine sorgfältige Abstimmung dieser Koeffizienten ist entscheidend, um eine robuste Optimierungsleistung in verschiedenen Problembereichen zu erreichen. Die Parameter sollten so angepasst werden, dass ein Gleichgewicht zwischen Exploration und Ausnutzung entsteht, damit die Partikel effektiv suchen, ohne steckenzubleiben oder zu schnell zu konvergieren.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 2

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Awesome!

Completion rate improved to 6.25

Swipe um das Menü anzuzeigen