Lære Partikkelsvermoptimalisering | Sverm-Baserte Algoritmer

Definisjon

Particle Swarm Optimization (PSO) er en populasjonsbasert, bio-inspirert algoritme som henter inspirasjon fra den kollektive atferden til fugleflokker og fiskestimer. I PSO arbeider man med en sverm av enkle agenter kalt partikler. Hver partikkel representerer en potensiell løsning på optimeringsproblemet og beveger seg gjennom søkeområdet ved å oppdatere sin posisjon og hastighet.

Kjernebegreper

Bevegelsen til hver partikkel påvirkes av to hovedfaktorer:

Personlig beste: Den beste posisjonen partikkelen selv har funnet så langt;
Globalt beste: Den beste posisjonen som hele svermen har funnet til enhver tid under søket.

Denne dynamikken gjør det mulig for svermen å utforske løsningsrommet effektivt, og balanserer utforskning (søke i nye områder) og utnyttelse (forbedre kjente gode områder) ettersom partiklene kommuniserer og lærer av hverandre.

Viktige begreper i PSO:

Partikler: agenter som representerer mulige løsninger;
Posisjon: den nåværende plasseringen til en partikkel i søkeområdet;
Hastighet: retning og fart på partikkelens bevegelse;
Personlig beste posisjon: den beste posisjonen hver partikkel har funnet så langt;
Globalt beste posisjon: den beste posisjonen funnet av en hvilken som helst partikkel i svermen.

Ved å iterativt oppdatere posisjoner og hastigheter basert på disse prinsippene, gjør PSO det mulig å løse komplekse optimeringsproblemer på en fleksibel og effektiv måte.

Eksempel: Grunnleggende 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}")

Steg-for-steg: Oppdatering av posisjon og hastighet i PSO

Evaluer hver partikkel: For hver partikkel, beregn objektivfunksjonen ved dens nåværende posisjon;
Oppdater personlig beste: Hvis den nåværende posisjonen gir en bedre verdi enn tidligere posisjoner, lagres denne som ny personlig beste;
Oppdater globalt beste: Identifiser den beste verdien blant alle personlige beste og oppdater den globale beste posisjonen deretter;
Oppdater hastighet: For hver partikkel, beregn ny hastighet ved å bruke:
- Inersialedet (w * velocity), som oppmuntrer partikkelen til å fortsette i samme retning;
- Kognitivt ledd (c1 * r1 * (personal_best - position)), som trekker partikkelen mot dens egen beste erfaring;
- Sosialt ledd (c2 * r2 * (global_best - position)), som trekker partikkelen mot det beste funnet av svermen;
Oppdater posisjon: Legg til den nye hastigheten til nåværende posisjon for å finne partikkelens nye plassering i søkeområdet.

Partiklene gjentar disse stegene et forhåndsdefinert antall iterasjoner eller til konvergenskriterier er oppfylt.

Eksempel: Visualisering av partikkelbaner


              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

Valg av PSO-parametere har stor innvirkning på algoritmens oppførsel og ytelse:

Inersialkoeffisient (w): Styrer hvor mye av forrige hastighet som beholdes;
- Høyere verdier fremmer utforskning og hjelper partiklene å unnslippe lokale minima;
- Lavere verdier favoriserer utnyttelse og gir raskere konvergens.
Kognitiv koeffisient (c1): Bestemmer hvor sterkt partiklene trekkes mot sine egne beste posisjoner;
- Høyere verdi fremmer uavhengig utforskning og bidrar til å opprettholde mangfold i svermen.
Sosial koeffisient (c2): Styrer tiltrekningen mot den globale beste posisjonen;
- Økt verdi gir raskere konvergens ved å fremme kollektiv læring;
- For høye verdier kan føre til for tidlig stagnasjon.

Nøye justering av disse koeffisientene er avgjørende for å oppnå robust optimaliseringsytelse i ulike problemområder. Juster parameterne for å balansere utforskning og utnyttelse, slik at partiklene søker effektivt uten å sette seg fast eller konvergere for raskt.

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Suggested prompts:

Can you explain how to choose good values for the PSO parameters?

What happens if I set the inertia or cognitive/social coefficients too high or too low?

Can you give examples of how parameter changes affect the optimization process?

Awesome!

Completion rate improved to 6.25

Sveip for å vise menyen