11. tétel - Optimalizálás alapfogalmai

Mit értünk optimalizálási feladat alatt? Ismertesse az optimalizálás alapvető fogalmait (célfüggvény, megszorítás, fitnesz,keresési/probléma tér, optimum, genotípus, fenotípus)! Mutasson gyakorlati példákat ezekre! Milyen módon lehet csoportosítani az optimalizálási módszereket?

Optimalizálási feladat

• Olyan feladat, melynek célja, hogy valamilyen problémára megtalálja az optimális megoldást.
• Lehetnek
  • matematikai hátterűek (pl. függvény minimumának megkeresése)
  • való világból érkező gyakorlati problémák (pl. az optimális termeléi ütemezés meghatározása)
  • természetiek (pl. evolúció is egy optimalizálás)
• Informatikai szempontból az optimalizálást általában egy vagy több függvény minimumának megkereséseként értelmezzük, erre sok gyakorlatorientált probléma visszavezethető.

Fogalmak

1. Problématér (\(ℙ\))

Egy halmaz, ami tartalmazza a feladat megoldásjelöltjeit (összes lehetséges megoldás)

Például:

• függvényközelítés esetén: elemei a lehetséges függvényparaméterek
• utazó ügynöknél: lehetséges útvonalak

2. Célfüggvény (\( g: ℙ → ℝ\))

• Az optimalizálás során számszerűsítenünk kell a problématérban található megoldások jóságát.
• A célfüggvény minden problématérbeli elemhez egy számot rendel.

Például:

• függvényközelítésnél: a referenciafüggvény és a megoldásjelölt függvény különbsége
• utazó ügynöknél: a városok adott permutációjához tartozó útvonal hossza

3. Globális optimum:

A problématér azon elemei, amelyeknél nincs "jobb" elem. Általában a legkisebb értéket keressük, de fordítva is lehet.

Például:

• utazó ügynöknél: a legrövidebb útvonalak

4. Lokális optimum:

A problématér azon elemei, amelyeknél egy adott környezetben nincs "jobb" elem. Általában a legkisebb értéket keressük, de fordítva is lehet.

Fontos, hogy ez nem "majdnem jó" érték. Lehet nagyon messze van a megoldástól, csak a problématér olyan részén van, ahol a környezetében nincsen nála jobb elem.

5. Megszorítások:

Gyakran van, hogy a leendő megoldásoknak különféle megszorításoknak is meg kell felelniük, amikből több lehet.

Például: gyártási folyamat tervezése → egyik műveletnek meg kell előznie a másikat

A megszorításokat függvényekként értelmezzük, halmazukat \(ℂ\)-vel jelöljük. Egy megoldásjelölt akkor elégít ki egy megszorítást, ha a függvény értéke a megoldásjelöltre legalább 0.

\[ \forall c \in ℂ: c(x) \geq 0 \]

6. Keresési tér (\(𝕊\))

• A problématérből kell választani megoldásjelölteket
• Ezek közül egyet vagy többet kiválasztunk
• Az optimalizáló algoritmusunk ebben fog működni
• Miben más, mint a problématér?
  1. Más szerkezetű
     • Pl. utazú ügynöknél a problématér az útvonalak, a keresési tér a városokat jelölő számok tömbje
  2. A problématér kisebb szelete
     • Pl. ki tudjuk zárni a reménytelen megoldásjelölteket
  3. A problématér leegyszerűsítése
     • Pl. a gyártási folyamat optimalizálásánál annak csak bizonyos részeivel foglalkozunk

Nem muszáj megkülönböztetni a problémateret és a keresési teret.

7. Fenotípus, Genotípus

A problématér és a keresési tér közötti leképezéshez használjuk ezeket.

1. Fenotípus: a problématér elemei
2. Genotípus: a keresési tér elemei

Genotype-phenotype mapping: függvény, ami a keresési térből a problématérbe képezi le az elemeket.

\[gpm: 𝕊 → ℙ \]

A leképezésnek legalább az egyik irányba teljeskörűnek kell lennie.

• Tehát a keresési tér összes eleméhez tudjunk rendelni elemet a problématérből.

8. Fitnesz függvény

A keresési térben értelmezett függvény, ami minden elemhez hozzárendel egy jóságot.

\[f: 𝕊 → ℝ\]

• Lehet a célfüggvény egyszerűsítése, vagy több célfüggvény összevonása.
• Tartalmazhatja a megszorításokat is.
• Felhasználható arra is, ha több megoldásból az egymástól legtávolabbiakat akarjuk választani

Összehasonlító táblázat

Optimalizálási módszerek csoportosítása

flowchart TB
O["`**Optimalizálási módszerek**`"]
A["`**Analitikus módszerek**
*(matematikai eszközökkel levezethető megoldások)*
`"]
N["`**Numerikus módszerek**
*(lineáris programozás, nemlineáris programozás, dinamikus programozás, visszalépéses keresés, stb.)*`"]
H["`**Heurisztikus módszerek**
*(hegymászó módszer, genetikus algoritmusok, raj alapú módszerek, stb.)*
`"]
O --> A & N & H