Lære Partikelsværmsoptimering | Sværmbaserede Algoritmer

Definition

Particle Swarm Optimization (PSO) er en populationsbaseret, bio-inspireret algoritme, der henter sin inspiration fra den kollektive adfærd hos fugleflokke og fiskestimer. I PSO arbejder man med en sværm af simple agenter kaldet partikler. Hver partikel repræsenterer en potentiel løsning på optimeringsproblemet og bevæger sig gennem søgeområdet ved at opdatere sin position og hastighed.

Kernekoncepter

Bevægelsen af hver partikel påvirkes af to hovedfaktorer:

Personlig bedste: Den bedste position, som partiklen selv har fundet indtil nu;
Global bedste: Den bedste position, som hele sværmen har fundet på noget tidspunkt under søgningen.

Denne dynamik gør det muligt for sværmen at udforske løsningsrummet effektivt og balancere udforskning (undersøgelse af nye områder) og udnyttelse (forfining af kendte gode områder), idet partiklerne kommunikerer og lærer af hinanden.

Vigtige begreber i PSO:

Partikler: agenter, der repræsenterer mulige løsninger;
Position: den aktuelle placering af en partikel i søgeområdet;
Hastighed: retning og fart for partiklens bevægelse;
Personlig bedste position: den bedste position, som hver partikel har fundet indtil nu;
Global bedste position: den bedste position, som nogen partikel i sværmen har fundet.

Ved iterativt at opdatere positioner og hastigheder baseret på disse principper muliggør PSO løsning af komplekse optimeringsproblemer på en fleksibel og effektiv måde.

Eksempel: Grundlæggende PSO-implementering


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

Trin-for-trin: Opdatering af position og hastighed i PSO

Evaluering af hver partikel: For hver partikel beregnes objektivfunktionen ved dens nuværende position;
Opdatering af personlig bedste: Hvis den nuværende position giver en bedre score end tidligere positioner, gemmes den som den nye personlige bedste;
Opdatering af global bedste: Identificer den bedste score blandt alle personlige bedste og opdater den globale bedste position tilsvarende;
Opdatering af hastighed: For hver partikel beregnes den nye hastighed ved hjælp af:
- Inerti-termen (w * velocity), som opmuntrer partiklen til at fortsætte i sin nuværende retning;
- Kognitiv term (c1 * r1 * (personal_best - position)), som trækker partiklen mod dens egen bedste erfaring;
- Social term (c2 * r2 * (global_best - position)), som trækker partiklen mod det bedste fundet af sværmen;
Opdatering af position: Læg den nye hastighed til den nuværende position for at opnå partiklens nye placering i søgeområdet.

Partikler gentager disse trin i et fastsat antal iterationer eller indtil konvergenskriterier er opfyldt.

Eksempel: Visualisering af partikelbaner


              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

Valget af PSO-parametre har stor indflydelse på algoritmens adfærd og ydeevne:

Inerti-koefficient (w): Kontrollerer hvor meget af den tidligere hastighed, der bevares;
- Højere værdier fremmer udforskning og hjælper partikler med at undslippe lokale minima;
- Lavere værdier favoriserer udnyttelse og fremskynder konvergens.
Kognitiv koefficient (c1): Bestemmer hvor stærkt partikler trækkes mod deres egne bedste positioner;
- Forøgelse af denne værdi fremmer uafhængig udforskning og hjælper med at opretholde sværmens diversitet.
Social koefficient (c2): Styrer tiltrækningen til den globale bedste position;
- Forøgelse af denne værdi fremskynder konvergens ved at fremme kollektiv læring;
- For høje værdier kan forårsage for tidlig stagnation.

Omhyggelig justering af disse koefficienter er afgørende for at opnå robust optimeringsydelse i forskellige problemområder. Juster parametrene for at balancere udforskning og udnyttelse, så partiklerne søger effektivt uden at sidde fast eller konvergere for hurtigt.

Var alt klart?

Tak for dine kommentarer!

Sektion 3. Kapitel 2

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Awesome!

Completion rate improved to 6.25

Stryg for at vise menuen