extremal optimization

Angol

Főnév

extremal optimization (tsz. extremal optimizations)

(informatika) Extremal Optimization (EO) egy természet-inspirált heurisztikus keresési algoritmus, amelyet nehezen megoldható optimalizálási problémák megoldására használnak. Az ötlet a Darwin-féle evolúciós szelekció elvén alapul, de a hagyományos evolúciós algoritmusoktól eltérően az EO mindig a legrosszabb teljesítményű komponenst cseréli ki egy megoldásban.

🧬 Alapötlet

Míg genetikus algoritmusok (GA) a populáció legjobb egyedeit tartják meg és kombinálják, az EO minden iterációban a leggyengébben teljesítő részegységet (pl. változót vagy döntést) választja ki, és azt random módon javítja vagy cseréli.

🧠 Elméleti alap

EO-t eredetileg a spinüvegek (spin glasses) fizikai modellje ihlette. Az algoritmus működése egy egyetlen megoldás lokális szerkezetét használja, és nem tart fenn populációt.

⚙️ Működési lépések

Kezdő megoldás létrehozása (véletlenszerűen vagy heurisztikusan).
Minden komponens (pl. egy változó vagy döntés) fitness értékének kiszámítása.
Rangsort készítünk a komponensek fitness alapján.
A legrosszabbakat (vagy egy rosszat) módosítjuk – gyakran power-law eloszlás alapján választva.
A módosított megoldásból új megoldás keletkezik.
Az új megoldás elfogadása (feltételesen vagy automatikusan).
Ismétlés adott számú lépésig vagy konvergenciáig.

📐 Matematikai séma

A komponensek egy ${\textstyle \lambda }$ paraméterrel szabályozott valószínűségi eloszlás alapján vannak rangsorolva:

$P(k)\sim k^{-\lambda }$

ahol:

${\textstyle k}$ = a komponens rangsorszáma (1 a legrosszabb),
${\textstyle \lambda }$ = vezérlőparaméter, ami meghatározza, hogy mennyire “extremális” legyen a kiválasztás (tipikusan ${\textstyle 1.5\leq \lambda \leq 2.5}$ ).

📊 Példa alkalmazási területek

NP-nehéz problémák: pl. gráf színezés, max-cut probléma, boole-függvény optimalizálás.
Combinatorikus optimalizálás: pl. utazóügynök probléma (TSP).
Gépi tanulásban: szelektív tanulási algoritmusok.

🔁 Példakód (egyszerűsített EO pseudokód)

init_solution()
while not stop:
    compute_fitness_per_component()
    rank_components()
    select_component_by_prob()
    modify_selected_component()
    update_solution()

🧾 Összehasonlítás

Algoritmus	Jellemző
Genetic Algorithm	Populáció, keresztezés, mutáció
Simulated Annealing	Egy megoldás, valószínűségi lépés elfogadás
Extremal Optimization	Egy megoldás, rossz komponens lecserélése

✅ Előnyök

Nem igényel deriváltat vagy gradiens-információt.
Nincs szükség globális keresésre (de mégis jól működik).
Könnyen implementálható.
Jól alkalmazható nem-szimmetrikus, diszkrét problémákra.

❌ Hátrányok

Nem biztosítja a globális optimumot.
Paraméter-érzékeny ( ${\textstyle \lambda }$ érték).
Lassú lehet komplex keresési terekben.

További információk

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