Impara Ottimizzazione Tramite Sciame di Particelle

Definizione

L'ottimizzazione tramite sciame di particelle (Particle Swarm Optimization, PSO) è un algoritmo bio-ispirato basato sulla popolazione che trae ispirazione dal comportamento collettivo degli stormi di uccelli e dei banchi di pesci. In PSO si lavora con uno sciame di agenti semplici chiamati particelle. Ogni particella rappresenta una possibile soluzione al problema di ottimizzazione e si muove nello spazio di ricerca aggiornando la propria posizione e velocità.

Concetti fondamentali

Il movimento di ciascuna particella è influenzato da due fattori principali:

Best personale: la migliore posizione conosciuta che la particella stessa ha scoperto finora;
Best globale: la migliore posizione conosciuta trovata dall'intero sciame in qualsiasi momento durante la ricerca.

Questa dinamica consente allo sciame di esplorare lo spazio delle soluzioni in modo efficiente, bilanciando esplorazione (ricerca di nuove aree) e sfruttamento (raffinamento delle aree già note) mentre le particelle comunicano e apprendono l'una dall'altra.

Concetti chiave in PSO:

Particelle: agenti che rappresentano soluzioni possibili;
Posizione: la posizione attuale di una particella nello spazio di ricerca;
Velocità: direzione e velocità del movimento della particella;
Best personale: la migliore posizione trovata da ciascuna particella finora;
Best globale: la migliore posizione trovata da qualsiasi particella nello sciame.

Aggiornando iterativamente posizioni e velocità secondo questi principi, PSO consente di risolvere problemi di ottimizzazione complessi in modo flessibile ed efficiente.

Esempio: Implementazione base di 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}")

Passo dopo passo: Aggiornamenti di posizione e velocità in PSO

Valutazione di ogni particella: Per ogni particella, calcolare la funzione obiettivo nella posizione attuale;
Aggiornamento del best personale: Se la posizione attuale fornisce un punteggio migliore rispetto a qualsiasi posizione precedente, salvarla come nuovo best personale;
Aggiornamento del best globale: Identificare il miglior punteggio tra tutti i best personali e aggiornare di conseguenza la posizione del best globale;
Aggiornamento della velocità: Per ogni particella, calcolare la nuova velocità utilizzando:
- Il termine di inerzia (w * velocity), che incoraggia la particella a continuare a muoversi nella direzione attuale;
- Il termine cognitivo (c1 * r1 * (personal_best - position)), che attira la particella verso la propria migliore esperienza;
- Il termine sociale (c2 * r2 * (global_best - position)), che attira la particella verso il best trovato dallo sciame;
Aggiornamento della posizione: Sommare la nuova velocità alla posizione attuale per ottenere la nuova posizione della particella nello spazio di ricerca.

Le particelle ripetono questi passaggi per un numero prefissato di iterazioni o fino al soddisfacimento dei criteri di convergenza.

Esempio: Visualizzazione delle traiettorie delle particelle


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

Analisi dei parametri

La scelta dei parametri PSO ha un impatto significativo sul comportamento e sulle prestazioni dell'algoritmo:

Coefficiente di inerzia (w): Controlla quanto della velocità precedente viene mantenuto;
- Valori più alti favoriscono l'esplorazione e aiutano le particelle a sfuggire ai minimi locali;
- Valori più bassi favoriscono lo sfruttamento e accelerano la convergenza.
Coefficiente cognitivo (c1): Determina quanto fortemente le particelle sono attratte verso le proprie migliori posizioni;
- Un valore più alto incoraggia l'esplorazione indipendente e aiuta a mantenere la diversità dello sciame.
Coefficiente sociale (c2): Regola l'attrazione verso la posizione del best globale;
- Un valore più alto accelera la convergenza promuovendo l'apprendimento collettivo;
- Valori eccessivamente alti possono causare una stagnazione prematura.

Una regolazione accurata di questi coefficienti è essenziale per ottenere prestazioni di ottimizzazione robuste in diversi domini di problemi. Regolare i parametri per bilanciare esplorazione e sfruttamento, assicurando che le particelle cerchino in modo efficace senza bloccarsi o convergere troppo rapidamente.

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 2

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Awesome!

Completion rate improved to 6.25

Scorri per mostrare il menu