Lära Partikelsvärmsoptimering | Svärmbaserade Algoritmer

Definition

Particle Swarm Optimization (PSO) är en populationsbaserad, bioinspirerad algoritm som hämtar sin inspiration från det kollektiva beteendet hos fågelflockar och fiskstim. I PSO arbetar du med en svärm av enkla agenter kallade partiklar. Varje partikel representerar en möjlig lösning på optimeringsproblemet och rör sig genom sökutrymmet genom att uppdatera sin position och hastighet.

Kärnkoncept

Varje partikels rörelse påverkas av två huvudfaktorer:

Personbästa: Den bästa positionen som partikeln själv har upptäckt hittills;
Globalbästa: Den bästa positionen som hela svärmen har hittat vid någon tidpunkt under sökningen.

Denna dynamik gör det möjligt för svärmen att utforska lösningsutrymmet effektivt, med en balans mellan utforskning (söka nya områden) och exploatering (förfina kända bra områden) när partiklarna kommunicerar och lär sig av varandra.

Nyckelbegrepp i PSO:

Partiklar: agenter som representerar möjliga lösningar;
Position: den aktuella platsen för en partikel i sökutrymmet;
Hastighet: riktning och fart för partikelns rörelse;
Personbästa position: den bästa positionen som varje partikel hittills har hittat;
Globalbästa position: den bästa positionen som någon partikel i svärmen har hittat.

Genom att iterativt uppdatera positioner och hastigheter baserat på dessa principer möjliggör PSO lösning av komplexa optimeringsproblem på ett flexibelt och effektivt sätt.

Exempel: Grundläggande PSO-implementation


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

Steg-för-steg: Uppdatering av position och hastighet i PSO

Utvärdera varje partikel: För varje partikel, beräkna objektivfunktionen vid dess nuvarande position;
Uppdatera personbästa: Om den aktuella positionen ger ett bättre resultat än någon tidigare position, lagra den som nytt personbästa;
Uppdatera globalbästa: Identifiera det bästa resultatet bland alla personbästan och uppdatera globalbästa positionen därefter;
Uppdatera hastighet: För varje partikel, beräkna den nya hastigheten med hjälp av:
- Tröghetstermen (w * velocity), som uppmuntrar partikeln att fortsätta i sin nuvarande riktning;
- Kognitiva termen (c1 * r1 * (personal_best - position)), som drar partikeln mot dess egen bästa erfarenhet;
- Sociala termen (c2 * r2 * (global_best - position)), som drar partikeln mot det bästa som hittats av svärmen;
Uppdatera position: Lägg till den nya hastigheten till den nuvarande positionen för att få partikelns nya plats i sökutrymmet.

Partiklarna upprepar dessa steg under ett förutbestämt antal iterationer eller tills konvergenskriterier är uppfyllda.

Exempel: Visualisering av partikelbanor


              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()

Parameteranalys

Valet av PSO-parametrar har stor inverkan på algoritmens beteende och prestanda:

Tröghetskoefficient (w): Styr hur mycket av den tidigare hastigheten som behålls;
- Högre värden uppmuntrar utforskning och hjälper partiklar att undvika lokala minima;
- Lägre värden gynnar exploatering och påskyndar konvergens.
Kognitiv koefficient (c1): Avgör hur starkt partiklar dras mot sina egna bästa positioner;
- Högre värden uppmuntrar självständig utforskning och hjälper till att bevara svärmens mångfald.
Social koefficient (c2): Styr attraktionen till den globala bästa positionen;
- Högre värden påskyndar konvergens genom att främja kollektivt lärande;
- Alltför höga värden kan orsaka för tidig stagnation.

Noggrann justering av dessa koefficienter är avgörande för att uppnå robust optimeringsprestanda inom olika problemområden. Justera parametrarna för att balansera utforskning och exploatering, så att partiklarna söker effektivt utan att fastna eller konvergera för snabbt.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Awesome!

Completion rate improved to 6.25

Svep för att visa menyn