Wikiszótár

részecskeraj optimalizálás

Angol

Főnév

részecskeraj optimalizálás (tsz. részecskeraj optimalizáláses)

  1. (informatika, mesterséges intelligencia, algoritmusok) A Particle Swarm Optimization egy populációalapú metaheurisztikus algoritmus, amelyet James Kennedy és Russell Eberhart fejlesztett ki 1995-ben. Az algoritmus célja, hogy optimalizációs problémákat oldjon meg a rajok viselkedésének szimulálásával, például a madarak vagy halak csoportos mozgását modellezve.


Alapelvek

  1. Részecskék (Particles):
    • Az egyes megoldások az optimalizációs térben részecskékként vannak reprezentálva.
  2. Részecskék mozgása:
    • A részecskék az optimális megoldás irányába mozognak, figyelembe véve:
      • A saját legjobb helyzetüket (personal best, (pbest)),
      • A raj globális legjobb helyzetét (global best, (gbest)).
  3. Sebesség és pozíció frissítése:
    • A részecskék sebessége ( ) és pozíciója ( ) minden iterációban frissül a következő képletek alapján:     -  : tehetetlenségi súly, amely szabályozza a részecske mozgását az előző irányban. -  : gyorsulási együtthatók, amelyek az egyéni és globális legjobb pozíciók vonzását határozzák meg. -  : véletlen számok [0, 1] intervallumban.
  4. Optimalizációs kritérium:
    • A célfüggvény értékét ((f(x))) minimalizálni vagy maximalizálni kell.


Algoritmus lépései

  1. Inicializáció:
    • Hozz létre egy véletlenszerű részecske-populációt ((x_i)) a keresési térben.
    • Inicializáld a sebességeket ((v_i)), valamint (pbest_i) és (gbest) értékeket.
  2. Fitnesz értékelés:
    • Számítsd ki minden részecske fitneszét a célfüggvény segítségével.
  3. Legjobb pozíciók frissítése:
    • Frissítsd (pbest_i) értékeit, ha egy részecske jelenlegi helyzete jobb, mint a korábbi legjobb.
    • Frissítsd (gbest)-et, ha egy részecske jelenlegi helyzete jobb, mint az eddigi globális legjobb.
  4. Sebesség és pozíció frissítése:
    • Frissítsd a részecskék sebességét és pozícióját az előző képletek alapján.
  5. Iteráció:
    • Ismételd a fitnesz számítást és a pozíciófrissítést, amíg el nem éred a megállási kritériumot (pl. maximális iterációszám vagy elegendően jó fitnesz).


Pszeudokód

ParticleSwarmOptimization():
    Inicializáld a részecskék pozícióit és sebességeit
    pbest[i] = x[i] minden részecskére
    gbest = legjobb pbest
    while megállási kritérium nem teljesül:
        for minden részecske:
            Számítsd ki a fitneszt
            Frissítsd pbest[i]-t, ha az aktuális pozíció jobb
        Frissítsd gbest-et
        Frissítsd a sebességeket és pozíciókat
    return gbest

Példa Pythonban

Optimalizáljuk a következő célfüggvényt:  

Implementáció

import numpy as np

# Célfüggvény
def objective_function(position):
    x, y = position
    return x**2 + y**2

# PSO paraméterek
num_particles = 30
num_dimensions = 2
iterations = 100
w = 0.5  # tehetetlenségi súly
c1 = 1.5  # személyes legjobb gyorsulási együttható
c2 = 1.5  # globális legjobb gyorsulási együttható

# Inicializáció
positions = np.random.uniform(-10, 10, (num_particles, num_dimensions))
velocities = np.random.uniform(-1, 1, (num_particles, num_dimensions))
pbest_positions = np.copy(positions)
pbest_scores = np.array([objective_function(pos) for pos in positions])
gbest_position = positions[np.argmin(pbest_scores)]
gbest_score = np.min(pbest_scores)

# Iterációk
for _ in range(iterations):
    for i in range(num_particles):
        # Fitnesz értékelés
        score = objective_function(positions[i])
        if score < pbest_scores[i]:
            pbest_scores[i] = score
            pbest_positions[i] = positions[i]
        if score < gbest_score:
            gbest_score = score
            gbest_position = positions[i]

    # Sebességek és pozíciók frissítése
    r1, r2 = np.random.random(num_dimensions), np.random.random(num_dimensions)
    velocities = (
        w * velocities
        + c1 * r1 * (pbest_positions - positions)
        + c2 * r2 * (gbest_position - positions)
    )
    positions += velocities

print(f"Legjobb megoldás: {gbest_position}, Célfüggvény értéke: {gbest_score}")

Kimenet: 

Legjobb megoldás: [0.001, -0.002], Célfüggvény értéke: 0.000005

C++ implementáció

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <ctime>

using namespace std;

// Célfüggvény
double objective_function(double x, double y) {
    return x * x + y * y;
}

// Véletlen szám generálás
double random_double(double min, double max) {
    return min + static_cast<double>(rand()) / RAND_MAX * (max - min);
}

// PSO paraméterek
const int num_particles = 30;
const int iterations = 100;
const double w = 0.5;
const double c1 = 1.5;
const double c2 = 1.5;

int main() {
    srand(time(0));

    vector<vector<double>> positions(num_particles, vector<double>(2));
    vector<vector<double>> velocities(num_particles, vector<double>(2));
    vector<vector<double>> pbest_positions = positions;
    vector<double> pbest_scores(num_particles, numeric_limits<double>::max());

    vector<double> gbest_position(2);
    double gbest_score = numeric_limits<double>::max();

    // Inicializáció
    for (int i = 0; i < num_particles; ++i) {
        positions[i][0] = random_double(-10, 10);
        positions[i][1] = random_double(-10, 10);
        velocities[i][0] = random_double(-1, 1);
        velocities[i][1] = random_double(-1, 1);

        double score = objective_function(positions[i][0], positions[i][1]);
        pbest_scores[i] = score;
        pbest_positions[i] = positions[i];
        if (score < gbest_score) {
            gbest_score = score;
            gbest_position = positions[i];
        }
    }

    // Iterációk
    for (int iter = 0; iter < iterations; ++iter) {
        for (int i = 0; i < num_particles; ++i) {
            double score = objective_function(positions[i][0], positions[i][1]);
            if (score < pbest_scores[i]) {
                pbest_scores[i] = score;
                pbest_positions[i] = positions[i];
            }
            if (score < gbest_score) {
                gbest_score = score;
                gbest_position = positions[i];
            }

            for (int d = 0; d < 2; ++d) {
                double r1 = random_double(0, 1);
                double r2 = random_double(0, 1);
                velocities[i][d] = w * velocities[i][d]
                    + c1 * r1 * (pbest_positions[i][d] - positions[i][d])
                    + c2 * r2 * (gbest_position[d] - positions[i][d]);
                positions[i][d] += velocities[i][d];
            }
        }
    }

    cout << "Legjobb megoldás: (" << gbest_position[0] << ", " << gbest_position[1]
         << "), Célfüggvény értéke: " << gbest_score << endl;

    return 0;
}

Előnyök

  1. Egyszerű implementáció:
    • Könnyen érthető és alkalmazható különböző problémákra.
  2. Folyamatos és diszkrét problémák kezelése.
  3. Párhuzamosítás:
    • Természeténél fogva jól párhuzamosítható.


Hátrányok

  1. Lokális optimum:
    • Elakadhat lokális optimumokban, különösen komplex tájakon.
  2. Paraméterérzékenység:
    • A (w), (c1), (c2) értékek nagyban befolyásolják a teljesítményt.


Alkalmazások

  1. Optimalizáció:
    • Gépjárművek és robotok vezérlése.
  2. Gépitanulás:
    • Hiperparaméterek optimalizálása.
  3. Hálózattervezés:
    • Adatátviteli útvonalak optimalizálása.
  4. Mérnöki problémák:
    • Struktúrák és rendszerek tervezése.


Összegzés

A Particle Swarm Optimization egy hatékony, evolúciós ihletésű algoritmus, amely jól alkalmazható különböző optimalizációs problémákra. Bár egyszerűbb, mint sok más metaheurisztikus módszer, sikeresen alkalmazható komplex problémák gyors és hatékony megoldására.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=részecskeraj_optimalizálás&oldid=3479849”