Oppiskele Partikkeliparven Optimointi | Parvopohjaiset Algoritmit

Määritelmä

Particle Swarm Optimization (PSO) on populaatiopohjainen, bioinspiroitu algoritmi, joka saa inspiraationsa lintujen parvien ja kalaparvien kollektiivisesta käyttäytymisestä. PSO:ssa käytetään parvea yksinkertaisia agentteja, joita kutsutaan partikkeleiksi. Jokainen partikkeli edustaa mahdollista ratkaisua optimointiongelmaan ja liikkuu hakutilassa päivittämällä sijaintiaan ja nopeuttaan.

Keskeiset käsitteet

Jokaisen partikkelin liikettä ohjaavat kaksi päätekijää:

Henkilökohtainen paras: Paras tunnettu sijainti, jonka partikkeli itse on tähän mennessä löytänyt;
Globaali paras: Paras tunnettu sijainti, jonka koko parvi on milloinkin löytänyt haun aikana.

Tämä dynamiikka mahdollistaa parven tehokkaan ratkaisutilan tutkimisen, tasapainottaen etsinnän (uusien alueiden tutkiminen) ja hyödyntämisen (tunnettujen hyvien alueiden tarkentaminen), kun partikkelit viestivät ja oppivat toisiltaan.

PSO:n keskeiset käsitteet:

Partikkelit: agentit, jotka edustavat mahdollisia ratkaisuja;
Sijainti: partikkelin nykyinen paikka hakutilassa;
Nopeus: partikkelin liikkeen suunta ja nopeus;
Henkilökohtainen paras sijainti: paras sijainti, jonka kukin partikkeli on tähän mennessä löytänyt;
Globaali paras sijainti: paras sijainti, jonka mikä tahansa partikkeli parvessa on löytänyt.

Päivittämällä sijainteja ja nopeuksia iteratiivisesti näiden periaatteiden mukaisesti PSO mahdollistaa monimutkaisten optimointiongelmien ratkaisun joustavasti ja tehokkaasti.

Esimerkki: Perustason PSO-toteutus


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

Vaiheittainen ohje: Partikkelien sijainnin ja nopeuden päivitys PSO:ssa

Arvioi jokainen partikkeli: Laske tavoitefunktio jokaisen partikkelin nykyisessä sijainnissa;
Päivitä henkilökohtainen paras: Jos nykyinen sijainti tuottaa paremman arvon kuin mikään aiempi sijainti, tallenna se uudeksi henkilökohtaiseksi parhaaksi;
Päivitä globaali paras: Tunnista paras arvo kaikista henkilökohtaisista parhaista ja päivitä globaalin parhaan sijainti sen mukaisesti;
Päivitä nopeus: Laske jokaiselle partikkelille uusi nopeus käyttäen:
- Inertia-termiä (w * velocity), joka kannustaa partikkelia jatkamaan nykyiseen suuntaansa;
- Kognitiivista termiä (c1 * r1 * (personal_best - position)), joka vetää partikkelia kohti sen omaa parasta kokemusta;
- Sosiaalista termiä (c2 * r2 * (global_best - position)), joka vetää partikkelia kohti parasta, jonka parvi on löytänyt;
Päivitä sijainti: Lisää uusi nopeus nykyiseen sijaintiin saadaksesi partikkelin uuden sijainnin hakutilassa.

Partikkelit toistavat nämä vaiheet ennalta määrätyn määrän iteraatioita tai kunnes konvergenssikriteerit täyttyvät.

Esimerkki: Partikkelien reittien visualisointi


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

Parametrien analyysi

PSO-parametrien valinnalla on merkittävä vaikutus algoritmin käyttäytymiseen ja suorituskykyyn:

Inertia-kerroin (w): Määrittää, kuinka paljon edellistä nopeutta säilytetään;
- Suuremmat arvot edistävät tutkimista ja auttavat partikkeleita pakenemaan paikallisista minimeistä;
- Pienemmät arvot suosivat hyväksikäyttöä ja nopeuttavat konvergenssia.
Kognitiivinen kerroin (c1): Määrittää, kuinka voimakkaasti partikkelit vetäytyvät omiin parhaisiin sijainteihinsa;
- Tämän arvon kasvattaminen kannustaa itsenäiseen tutkimiseen ja ylläpitää parven monimuotoisuutta.
Sosiaalinen kerroin (c2): Säätelee vetovoimaa kohti globaalia parasta sijaintia;
- Tämän arvon kasvattaminen nopeuttaa konvergenssia edistämällä kollektiivista oppimista;
- Liian suuret arvot voivat aiheuttaa ennenaikaista pysähtymistä.

Näiden kertoimien huolellinen säätäminen on olennaista, jotta saavutetaan luotettava optimointisuoritus eri ongelma-alueilla. Säädä parametreja tasapainottaaksesi tutkimista ja hyväksikäyttöä, varmistaen että partikkelit etsivät tehokkaasti ilman että ne juuttuvat tai konvergoituvat liian nopeasti.

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 3. Luku 2

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

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

Pyyhkäise näyttääksesi valikon