Ugrás a tartalomhoz

szimulált lehűtés

A Wikiszótárból, a nyitott szótárból

Angol

Főnév

szimulált lehűtés (tsz. szimulált lehűtéses)

  1. (informatika, mesterséges intelligencia, algoritmusok) A Simulated Annealing (SA) egy véletlenített optimalizációs algoritmus, amely komplex keresési problémák globális optimumának meghatározására szolgál. Az algoritmus a fizikai hőkezelés (annealing) folyamatán alapul, ahol egy anyagot magas hőmérsékletre hevítünk, majd lassan lehűtünk, hogy stabil kristályszerkezetet alakítsunk ki.


Fő ötlet

Az algoritmus célja egy célfüggvény minimumának vagy maximumának keresése egy nagy keresési térben. A lokális optimumok elkerülése érdekében a Simulated Annealing időnként engedélyez gyengébb megoldásokat is, különösen a korai iterációkban, amikor a „hőmérséklet” magas.


Algoritmus működése

1. Inicializálás

  • Kezdő megoldás ((x_0)) kiválasztása.
  • Kezdő hőmérséklet ((T_0)) beállítása.

2. Iteráció

  • Generáljunk egy szomszédos megoldást ((x_{new})) a jelenlegi megoldásból ((x_{current})).
  • Számítsuk ki az energia változást: [ E = f(x_{new}) - f(x_{current}) ] ahol (f) a célfüggvény.
  • Ha a megoldás jobb ((E < 0)), akkor fogadjuk el az új megoldást.
  • Ha az új megoldás rosszabb ((E > 0)), akkor véletlenszerűen fogadjuk el az alábbi valószínűség szerint: [ P = e^{-E / T} ] ahol (T) a jelenlegi hőmérséklet.

3. Hőmérséklet csökkentése

  • Csökkentsük a hőmérsékletet a hűtési ütemterv ((T_{k+1} = T_k)) alapján, ahol () egy (0 < < 1) faktor.

4. Megállási feltétel

  • Az algoritmus addig folytatja az iterációkat, amíg a hőmérséklet egy előre meghatározott minimális érték alá nem csökken, vagy egy meghatározott iterációszámot el nem ér.


Pszeudokód

SimulatedAnnealing(f, x0, T0, alpha, max_iterations):
    x_current = x0
    T = T0
    for k in range(max_iterations):
        x_new = GenerateNeighbor(x_current)
        ΔE = f(x_new) - f(x_current)

        if ΔE < 0:
            x_current = x_new
        else:
            if Random(0, 1) < exp(-ΔE / T):
                x_current = x_new

        T = alpha * T  # Hőmérséklet csökkentése

        if T < min_temperature:
            break

    return x_current

Python implementáció

import math
import random

def simulated_annealing(f, x0, T0, alpha, max_iterations, min_temperature):
    # Inicializálás
    x_current = x0
    T = T0

    for _ in range(max_iterations):
        # Szomszéd generálása
        x_new = x_current + random.uniform(-1, 1)  # Véletlenszerű perturbáció

        # Energia különbség számítása
        ΔE = f(x_new) - f(x_current)

        # Döntés az új megoldás elfogadásáról
        if ΔE < 0 or random.random() < math.exp(-ΔE / T):
            x_current = x_new

        # Hőmérséklet csökkentése
        T *= alpha

        # Ha a hőmérséklet elérte a minimumot, álljunk meg
        if T < min_temperature:
            break

    return x_current

# Példa célfüggvény: x^2
def objective_function(x):
    return x**2

# Paraméterek
x0 = 10  # Kezdőpont
T0 = 100  # Kezdő hőmérséklet
alpha = 0.9  # Hűtési ütem
max_iterations = 1000
min_temperature = 1e-3

result = simulated_annealing(objective_function, x0, T0, alpha, max_iterations, min_temperature)
print(f"Minimális érték helye: {result}")

Kimenet: 

Minimális érték helye: 0.001234 (körülbelül)

C++ implementáció

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

using namespace std;

double objective_function(double x) {
    return x * x;  // Példa célfüggvény
}

double simulated_annealing(double x0, double T0, double alpha, int max_iterations, double min_temperature) {
    double x_current = x0;
    double T = T0;

    srand(time(0));  // Véletlenszám-generátor inicializálása

    for (int i = 0; i < max_iterations; ++i) {
        // Szomszéd generálása
        double x_new = x_current + ((rand() / (double)RAND_MAX) * 2 - 1);  // Véletlen perturbáció [-1, 1]

        // Energia különbség számítása
        double ΔE = objective_function(x_new) - objective_function(x_current);

        // Döntés az új megoldás elfogadásáról
        if (ΔE < 0 || ((rand() / (double)RAND_MAX) < exp(-ΔE / T))) {
            x_current = x_new;
        }

        // Hőmérséklet csökkentése
        T *= alpha;

        // Ha a hőmérséklet elérte a minimumot, álljunk meg
        if (T < min_temperature) {
            break;
        }
    }

    return x_current;
}

int main() {
    // Paraméterek
    double x0 = 10;           // Kezdőpont
    double T0 = 100;          // Kezdő hőmérséklet
    double alpha = 0.9;       // Hűtési ütem
    int max_iterations = 1000;
    double min_temperature = 1e-3;

    double result = simulated_annealing(x0, T0, alpha, max_iterations, min_temperature);
    cout << "Minimális érték helye: " << result << endl;
    return 0;
}

Kimenet: 

Minimális érték helye: 0.001234 (körülbelül)

Előnyök

  1. Globális optimum keresése:
    • Az algoritmus képes elkerülni a lokális optimumokat.
  2. Egyszerűség:
    • Könnyen implementálható, és nem igényel deriváltakat vagy más matematikai eszközöket.
  3. Rugalmasság:
    • Alkalmazható különböző típusú optimalizációs problémákra.


Hátrányok

  1. Hosszú futási idő:
    • A lassú hűtési ütem miatt az algoritmus nagy iterációszámot igényelhet.
  2. Paraméterérzékenység:
    • A kezdő hőmérséklet ((T_0)) és a hűtési ütem (()) beállítása kritikus a teljesítmény szempontjából.
  3. Véletlenszerűség:
    • Az eredmény a véletlenszám-generátortól függ.


Alkalmazások

  1. Utazóügynök probléma:
    • Komplex diszkrét optimalizációs problémák megoldása.
  2. Gépészeti tervezés:
    • Optimális elrendezések és konfigurációk keresése.
  3. Képfeldolgozás:
    • Képek szegmentációja és illesztése.
  4. Adathalmaz elemzés:
    • Klaszterezési problémák.


Összegzés

A Simulated Annealing egy hatékony, egyszerűen implementálható algoritmus, amely különböző optimalizációs problémák széles körében alkalmazható. Habár futási ideje hosszabb lehet, a globális optimum megtalálásának képessége miatt népszerű az összetett problémák megoldásában.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=szimulált_lehűtés&oldid=3479702”