Leer Deeltjeszwermoptimalisatie | Zwerm-Gebaseerde Algoritmen

Definitie

Particle Swarm Optimization (PSO) is een populatie-gebaseerd, bio-geïnspireerd algoritme dat zijn inspiratie haalt uit het collectieve gedrag van vogelzwermen en visscholen. In PSO wordt gewerkt met een zwerm van eenvoudige agenten, genaamd deeltjes. Elk deeltje vertegenwoordigt een potentiële oplossing voor het optimalisatieprobleem en beweegt door de zoekruimte door zijn positie en snelheid bij te werken.

Kernconcepten

De beweging van elk deeltje wordt beïnvloed door twee hoofdcomponenten:

Persoonlijk beste: De beste positie die het deeltje zelf tot nu toe heeft gevonden;
Globaal beste: De beste positie die door de gehele zwerm op enig moment tijdens het zoeken is gevonden.

Deze dynamiek stelt de zwerm in staat om de oplossingsruimte efficiënt te verkennen, waarbij exploratie (het zoeken naar nieuwe gebieden) en exploitatie (het verfijnen van bekende goede gebieden) worden gebalanceerd doordat deeltjes met elkaar communiceren en van elkaar leren.

Belangrijke concepten in PSO:

Deeltjes: agenten die mogelijke oplossingen representeren;
Positie: de huidige locatie van een deeltje in de zoekruimte;
Snelheid: de richting en snelheid van de beweging van het deeltje;
Persoonlijk beste positie: de beste positie die elk deeltje tot nu toe heeft gevonden;
Globaal beste positie: de beste positie die door een willekeurig deeltje in de zwerm is gevonden.

Door iteratief posities en snelheden bij te werken op basis van deze principes, maakt PSO het mogelijk om complexe optimalisatieproblemen op een flexibele en efficiënte manier op te lossen.

Voorbeeld: Basisimplementatie van PSO


              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}")

Stapsgewijs: Positie- en Snelheidsupdates in PSO

Evalueer elke deeltje: Voor elk deeltje de doelfunctie berekenen op de huidige positie;
Update Persoonlijk Beste: Indien de huidige positie een betere score oplevert dan eerdere posities, deze opslaan als het nieuwe persoonlijk beste;
Update Globaal Beste: De beste score onder alle persoonlijke besten identificeren en de globale beste positie dienovereenkomstig bijwerken;
Update Snelheid: Voor elk deeltje de nieuwe snelheid berekenen met:
- De inertieterm (w * velocity), die het deeltje aanmoedigt om in de huidige richting te blijven bewegen;
- De cognitieve term (c1 * r1 * (personal_best - position)), die het deeltje naar zijn eigen beste ervaring trekt;
- De sociale term (c2 * r2 * (global_best - position)), die het deeltje naar het beste resultaat van de zwerm trekt;
Update Positie: De nieuwe snelheid optellen bij de huidige positie om de nieuwe locatie van het deeltje in de zoekruimte te verkrijgen.

Deeltjes herhalen deze stappen gedurende een vastgesteld aantal iteraties of totdat aan de convergentiecriteria is voldaan.

Voorbeeld: Visualisatie van Deeltjessporen


              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

De keuze van PSO-parameters heeft een aanzienlijke invloed op het gedrag en de prestaties van het algoritme:

Inertiecoëfficiënt (w): Bepaalt hoeveel van de vorige snelheid behouden blijft;
- Hogere waarden bevorderen exploratie en helpen deeltjes lokale minima te vermijden;
- Lagere waarden bevorderen exploitatie en versnellen de convergentie.
Cognitieve coëfficiënt (c1): Bepaalt hoe sterk deeltjes naar hun eigen beste posities worden getrokken;
- Een hogere waarde stimuleert onafhankelijke verkenning en helpt de diversiteit van de zwerm te behouden.
Sociale coëfficiënt (c2): Bepaalt de aantrekkingskracht naar de globale beste positie;
- Een hogere waarde versnelt de convergentie door collectief leren te bevorderen;
- Te hoge waarden kunnen voortijdige stagnatie veroorzaken.

Zorgvuldige afstemming van deze coëfficiënten is essentieel voor robuuste optimalisatieprestaties in verschillende probleemdomeinen. Stel de parameters af om een balans te vinden tussen exploratie en exploitatie, zodat deeltjes effectief zoeken zonder vast te lopen of te snel te convergeren.

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 2

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Awesome!

Completion rate improved to 6.25

Veeg om het menu te tonen