genetic algorithm (tsz. genetic algorithms)
A genetikus algoritmus (angolul: genetic algorithm, GA) egy evolúció-alapú kereső és optimalizáló eljárás, amely a természetes kiválasztódás és a genetikai öröklődés elvein alapul. A cél: jó megoldást találni egy bonyolult problémára, még akkor is, ha nincs analitikus vagy hatékony módszer a pontos megoldásra.
A genetikus algoritmus a darwini evolúciót utánozza:
| Fogalom | Jelentés |
|---|---|
| Egyed (individual) | Egy lehetséges megoldás (pl. bitstring, vektor) |
| Populáció | Egyedek halmaza, amin a GA dolgozik |
| Fitness függvény | Kiértékeli, mennyire jó egy megoldás |
| Szelekció | A legjobb egyedek kiválasztása reprodukcióhoz |
| Keresztezés (crossover) | Két egyedből új egyed létrehozása |
| Mutáció | Véletlenszerű módosítás egy egyedben |
| Generáció | Egy evolúciós ciklus (egy új populáció létrehozása) |
Keressük meg azt a 10 bites bináris számot, amely a legnagyobb értéket képviseli (fitness = bináris érték). A GA megtanulja „kikódolni” az ideális 1111111111 kromoszómát.
A megoldást gyakran bitstringként, valós szám vektorként, karakterláncként vagy permutációként ábrázoljuk – a feladat típusától függően.
Példák:
1011001010
A genetikus algoritmusok kulcseleme, amely meghatározza, hogy egy egyed „mennyire jó”:
f(x) = -x² + 5
Két szülőből egy vagy két utódot hozunk létre.
Egy pontú keresztezés:
Szülő1: 101|011
Szülő2: 110|101
Utód : 101101
Két pontú keresztezés, uniform crossover is létezik.
Véletlenszerű módosítás kis valószínűséggel, pl. 0 → 1, 1 → 0.
| Paraméter | Jelentés |
|---|---|
| Populáció mérete | Hány egyed van egyszerre |
| Mutációs ráta | Mekkora az esélye egy mutáció bekövetkeztének |
| Keresztezési ráta | Mekkora arányban használjuk a keresztezést |
| Generációk száma | Hány iteráción keresztül fusson az algoritmus |
| Elitizmus | A legjobbak automatikusan bekerülnek a következő körbe |
import random
def fitness(x): return int(x, 2)
def mutate(gene): return ''.join(c if random.random() > 0.1 else str(1 - int(c)) for c in gene)
def crossover(a, b):
point = random.randint(1, len(a) - 1)
return a + b
pop =
for generation in range(100):
pop.sort(key=fitness, reverse=True)
print(f"Gen {generation}: Best = {pop} ({fitness(pop)})")
next_gen = pop # elitizmus
while len(next_gen) < len(pop):
parents = random.choices(pop, k=2)
child = mutate(crossover(*parents))
next_gen.append(child)
pop = next_gen
| Korlát | Magyarázat |
|---|---|
| 🐢 Lassú lehet | Sok generáció, nagy populáció kell |
| 🧮 Paraméter-érzékeny | Mutációs ráta, szelekciós módszer nagyban befolyásolja |
| 🎯 Nem garantáltan optimális | Jó, de nem tökéletes megoldás |
| 🔁 Reprodukciós variancia | Néhány futtatás jobb, másik rosszabb lehet ugyanarra a problémára |
| Terület | Példa |
|---|---|
| Műszaki tervezés | Formaoptimalizálás (pl. aerodinamika) |
| AI játékokban | Stratégiák fejlesztése (pl. játékos AI) |
| Bioinformatika | Fehérjeszerkezet keresése |
| Pénzügy | Portfólió optimalizálás |
| Utazó ügynök probléma (TSP) | Útvonal optimalizálása |
| Jellemző | Leírás |
|---|---|
| Definíció | Evolúciót utánzó optimalizációs algoritmus |
| Bemenet | Egy populáció megoldásokkal |
| Kimenet | A legjobb megtalált megoldás |
| Kulcslépések | Szelekció, keresztezés, mutáció, értékelés |
| Alkalmazás | Optimalizálás, vezérlés, tervezés, AI |
| Előny | Általános, nem igényel deriváltat |
| Hátrány | Lassú, paraméterhangolás-igényes |