Wikiszótár

genetikus algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɡɛnɛtikuʃɒlɡoritmuʃ]

Főnév

genetikus algoritmus

  1. (matematika, algoritmusok, informatika) A genetikus algoritmus (GA) egy evolúciós optimalizációs technika, amelyet John Holland fejlesztett ki az 1970-es években. A módszer az evolúció biológiai folyamatain alapul, mint például a szelekció, keresztezés és mutáció, hogy egy probléma közelítő megoldását megtalálja.


Alapvető működés

A genetikus algoritmus egy populációalapú keresési eljárás, amely iteratívan javítja a megoldások halmazát. Az alábbi lépéseken alapul:

  1. Inicializáció:
    • Kezdeti populáció generálása véletlenszerűen vagy heurisztikusan.
  2. Fitnesz értékelés:
    • Minden egyedhez rendelünk egy fitnesz értéket, amely azt méri, hogy az adott megoldás mennyire jó a probléma szempontjából.
  3. Szelekció:
    • A legjobbnak ítélt egyedeket választjuk ki a következő generáció szülőinek.
  4. Keresztezés (Crossover):
    • A szülők kombinációjával új egyedeket hozunk létre.
  5. Mutáció:
    • Véletlenszerű változtatások alkalmazása az egyedek egy részén, hogy a genetikai sokféleséget fenntartsuk.
  6. Reprodukció:
    • Az új egyedek (utódok) alkotják a következő generáció populációját.
  7. Megállási feltétel ellenőrzése:
    • Az algoritmus megáll, ha elér egy előre meghatározott kritériumot (pl. maximális iterációk száma, vagy a fitnesz egy bizonyos szintje).


Algoritmus lépései (Pszeudokód)

GeneticAlgorithm():
    Inicializáld a populációt véletlenszerű megoldásokkal.
    Ciklus amíg a megállási feltétel nem teljesül:
        Értékeld ki a populáció egyedeinek fitneszét.
        Szelektálj szülőket a fitnesz alapján.
        Alkalmazz keresztezést a szülőkre, hogy utódokat hozz létre.
        Alkalmazz mutációt az utódokra.
        Hozd létre az új populációt az utódokból.
    Visszatérési érték: a legjobb megoldás.

Fontos fogalmak

  1. Kromoszóma:
    • Egy lehetséges megoldást kódol, általában bináris, numerikus vagy szimbolikus reprezentációban.
  2. Fitnesz függvény:
    • Az egyedek minőségét értékelő függvény, amely irányítja az evolúciót.
  3. Szelekciós stratégiák:
    • Rulettkerék szelekció: A fitnesz arányában történik a kiválasztás.
    • Tornament szelekció: Véletlenszerű csoportokból választjuk ki a legjobbakat.
    • Elitizmus: A legjobb egyedek automatikusan átkerülnek a következő generációba.
  4. Keresztezési operátorok:
    • Egypontos keresztezés: A kromoszómákat egy adott pontnál felosztva cseréljük ki.
    • Többpontos keresztezés: Több szakasz cseréjével állítunk elő utódokat.
    • Egységes keresztezés: Véletlenszerűen választjuk ki, hogy melyik gén származik melyik szülőtől.
  5. Mutációs operátorok:
    • Bitflip mutáció: Egy bináris kromoszóma egy bitjének megfordítása.
    • Numerikus mutáció: Egy érték kis mértékű véletlen megváltoztatása.


Példa Pythonban

Probléma: Maximumkeresés ( f(x) = x^2 ) függvényen (( x )).

import random

# Fitnesz függvény
def fitness(x):
    return x**2

# Bináris kromoszóma dekódolása
def decode_chromosome(chromosome):
    return int("".join(map(str, chromosome)), 2)

# Inicializáció
def initialize_population(pop_size, chromosome_length):
    return [[random.randint(0, 1) for _ in range(chromosome_length)] for _ in range(pop_size)]

# Szelekció (rulettkerék)
def select_parents(population, fitness_values):
    total_fitness = sum(fitness_values)
    probabilities = [f / total_fitness for f in fitness_values]
    return random.choices(population, probabilities, k=2)

# Keresztezés (egypontos)
def crossover(parent1, parent2):
    point = random.randint(1, len(parent1) - 1)
    return parent1[:point] + parent2[point:], parent2[:point] + parent1[point:]

# Mutáció
def mutate(chromosome, mutation_rate):
    return [gene if random.random() > mutation_rate else 1 - gene for gene in chromosome]

# Genetikus algoritmus
def genetic_algorithm(pop_size, chromosome_length, generations, mutation_rate):
    population = initialize_population(pop_size, chromosome_length)

    for generation in range(generations):
        fitness_values = [fitness(decode_chromosome(ind)) for ind in population]
        new_population = []

        for _ in range(pop_size // 2):
            parent1, parent2 = select_parents(population, fitness_values)
            offspring1, offspring2 = crossover(parent1, parent2)
            new_population.append(mutate(offspring1, mutation_rate))
            new_population.append(mutate(offspring2, mutation_rate))

        population = new_population

    # Legjobb megoldás
    best_individual = max(population, key=lambda ind: fitness(decode_chromosome(ind)))
    return decode_chromosome(best_individual), fitness(decode_chromosome(best_individual))

# Paraméterek
pop_size = 10
chromosome_length = 5
generations = 20
mutation_rate = 0.1

best_solution, best_fitness = genetic_algorithm(pop_size, chromosome_length, generations, mutation_rate)
print(f"Legjobb megoldás: {best_solution}, Fitnesz: {best_fitness}")

Kimenet: 

Legjobb megoldás: 31, Fitnesz: 961

Előnyök

  1. Rugalmas:
    • Alkalmazható különböző típusú optimalizációs problémákra.
  2. Globális keresés:
    • Nem szorul lokális optimumokra, mint sok más módszer.
  3. Párhuzamosítás:
    • Az algoritmus természeténél fogva jól párhuzamosítható.


Hátrányok

  1. Számításigényes:
    • Nagy populáció és generációk esetén a futási idő nő.
  2. Paraméterérzékenység:
    • A populáció mérete, a mutációs ráta és más paraméterek jelentősen befolyásolják a teljesítményt.
  3. Konvergencia:
    • Előfordulhat, hogy nem találja meg a globális optimumot.


Alkalmazások

  1. Mesterséges intelligencia:
    • Gépi tanulási modellek hiperparaméter-tuningja.
  2. Ütemezési problémák:
    • Feladatok és erőforrások optimális elosztása.
  3. Robotika:
    • Mozgástervezés és optimalizáció.
  4. Kombinatorikus optimalizáció:
    • Utazóügynök probléma, hátizsák probléma.


Összegzés

A genetikus algoritmus egy erőteljes és rugalmas heurisztikus optimalizációs technika, amely széles körben alkalmazható. Bár számításigényes, hatékonyan kezeli a komplex problémákat, különösen azokat, amelyeknél a keresési tér nagy vagy nemlineáris. Fejlesztett változatai, mint például az evolúciós stratégiák és a differenciális evolúció, tovább növelik a gyakorlati alkalmazhatóságát.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=genetikus_algoritmus&oldid=3479710”