részecskeraj optimalizálás

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.

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 (${\textstyle v_{i}}$) és pozíciója (${\textstyle x_{i}}$) minden iterációban frissül a következő képletek alapján: $${\displaystyle v_{i}(t+1)=w\cdot v_{i}(t)+c_{1}\cdot r_{1}\cdot (pbest_{i}-x_{i}(t))+c_{2}\cdot r_{2}\cdot (gbest-x_{i}(t))}$$ $${\displaystyle x_{i}(t+1)=x_{i}(t)+v_{i}(t+1)}$$ - ${\textstyle w}$: tehetetlenségi súly, amely szabályozza a részecske mozgását az előző irányban. - ${\textstyle c_{1},c_{2}}$: gyorsulási együtthatók, amelyek az egyéni és globális legjobb pozíciók vonzását határozzák meg. - ${\textstyle r_{1},r_{2}}$: véletlen számok intervallumban.
4. Optimalizációs kritérium:
   • A célfüggvény értékét ((f(x))) minimalizálni vagy maximalizálni kell.

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

ParticleSwarmOptimization():
    Inicializáld a részecskék pozícióit és sebességeit
    pbest = x 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-t, ha az aktuális pozíció jobb
        Frissítsd gbest-et
        Frissítsd a sebességeket és pozíciókat
    return gbest

Optimalizáljuk a következő célfüggvényt: $${\displaystyle f(x,y)=x^{2}+y^{2}}$$

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()
gbest_position = positions
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)
        if score < pbest_scores:
            pbest_scores = score
            pbest_positions = positions
        if score < gbest_score:
            gbest_score = score
            gbest_position = positions

    # 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: , Célfüggvény értéke: 0.000005

#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 = random_double(-10, 10);
        positions = random_double(-10, 10);
        velocities = random_double(-1, 1);
        velocities = random_double(-1, 1);

        double score = objective_function(positions, positions);
        pbest_scores = score;
        pbest_positions = positions;
        if (score < gbest_score) {
            gbest_score = score;
            gbest_position = positions;
        }
    }

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

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

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

    return 0;
}

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ó.

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.

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.

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.

• részecskeraj optimalizálás - Szótár.net (en-hu)
• részecskeraj optimalizálás - Sztaki (en-hu)
• részecskeraj optimalizálás - Merriam–Webster
• részecskeraj optimalizálás - Cambridge
• részecskeraj optimalizálás - WordNet
• részecskeraj optimalizálás - Яндекс (en-ru)
• részecskeraj optimalizálás - Google (en-hu)
• részecskeraj optimalizálás - Wikidata
• részecskeraj optimalizálás - Wikipédia (angol)