Wikiszótár

metaheurisztikus algoritmus

Magyar

Kiejtés

  • IPA: [ ˈmɛtɒɦɛuristikuʃɒlɡoritmuʃ]

Főnév

metaheurisztikus algoritmus

  1. (matematika) A metaheurisztikus algoritmusok olyan általános módszerek, amelyek különféle optimalizációs problémák közelítő megoldásait keresik. Ezeket a módszereket gyakran használják komplex problémák esetén, amelyek megoldása hagyományos algoritmusokkal nehézkes vagy időigényes lenne. A metaheurisztikák célja a globális optimum megtalálása anélkül, hogy teljes mértékben bejárnák a keresési teret.


Jellemzők

  1. Keresési stratégia:
    • Heurisztikus szabályokkal vezérelt keresési folyamat.
  2. Problémafüggetlenség:
    • Különféle típusú optimalizációs problémákra alkalmazhatók.
  3. Globális és lokális keresés:
    • Egyensúlyt próbálnak találni a keresési tér feltárása (exploration) és a legjobb megoldás finomítása (exploitation) között.
  4. Nem garantált optimalitás:
    • A megtalált megoldás nem mindig optimális, de közel optimális lehet.


Fő Metaheurisztikus Algoritmusok

1. Genetikus algoritmus (Genetic Algorithm, GA)

Az evolúciós biológián alapul, és a populációt iteratívan fejleszti: - Kezdeti populáció: Random módon generált megoldások. - Szelekció: Az adott populáció legjobb egyedeinek kiválasztása. - Keresztezés: Az egyedek kombinálása új megoldások létrehozására. - Mutáció: Véletlenszerű módosítások a sokszínűség fenntartása érdekében.

Python Implementáció:
import random

def genetic_algorithm(fitness_func, bounds, population_size=50, generations=100, mutation_rate=0.1):
    def generate_individual():
        return random.uniform(bounds[0], bounds[1])

    def mutate(individual):
        if random.random() < mutation_rate:
            return individual + random.uniform(-0.1, 0.1)
        return individual

    def crossover(parent1, parent2):
        return (parent1 + parent2) / 2

    population = [generate_individual() for _ in range(population_size)]
    for _ in range(generations):
        population = sorted(population, key=fitness_func)
        next_generation = population[:10]  # Elitizmus
        while len(next_generation) < population_size:
            parent1, parent2 = random.sample(population[:20], 2)
            child = crossover(parent1, parent2)
            child = mutate(child)
            next_generation.append(child)
        population = next_generation

    best_solution = min(population, key=fitness_func)
    return best_solution, fitness_func(best_solution)

# Példa: Minimalizáljuk az f(x) = (x - 5)^2 függvényt
result = genetic_algorithm(lambda x: (x - 5)**2, bounds=(0, 10))
print("Legjobb pont:", result[0])
print("Legjobb érték:", result[1])

2. Szimulált lehűlés (Simulated Annealing, SA)

Fizikai folyamatokon alapul, különösen a kristályok hűtésének modellezésén: - Kezdeti hőmérséklet: Magas érték, ami lehetővé teszi, hogy a keresés a távoli régiókat is bejárja. - Hőmérséklet csökkentése: A hőmérséklet fokozatos csökkentésével a keresés egyre finomabbá válik.

Python Implementáció:
import math
import random

def simulated_annealing(f, bounds, temp=1000, cooling_rate=0.99, max_iter=1000):
    current_solution = random.uniform(bounds[0], bounds[1])
    current_value = f(current_solution)
    best_solution = current_solution
    best_value = current_value

    for _ in range(max_iter):
        new_solution = current_solution + random.uniform(-1, 1)
        if bounds[0] <= new_solution <= bounds[1]:
            new_value = f(new_solution)
            delta = new_value - current_value
            if delta < 0 or math.exp(-delta / temp) > random.random():
                current_solution = new_solution
                current_value = new_value
                if new_value < best_value:
                    best_solution = new_solution
                    best_value = new_value
        temp *= cooling_rate

    return best_solution, best_value

# Példa: Minimalizáljuk az f(x) = (x - 3)^2 függvényt
result = simulated_annealing(lambda x: (x - 3)**2, bounds=(0, 10))
print("Legjobb pont:", result[0])
print("Legjobb érték:", result[1])

3. Hangya kolónia optimalizáció (Ant Colony Optimization, ACO)

A hangyák útvonalkeresési viselkedését modellezi: - Feromonok: A lehetséges megoldások közötti utak népszerűségének jelölésére. - Keresés: A hangyák kezdetben véletlenszerűen keresnek, majd a jobb utak erősödnek.

Python Implementáció:

Egy egyszerű ACO példaként alkalmazható az Utazó Ügynök Problémában (TSP).


4. Részecskeraj optimalizáció (Particle Swarm Optimization, PSO)

A rajok, például halrajok és madárrajok viselkedésén alapul: - Részecskék: A keresési tér különböző pontjain helyezkednek el. - Mozgás: A részecskék a legjobb ismert megoldások felé mozognak.

Python Implementáció:
import random

def particle_swarm_optimization(f, bounds, num_particles=30, iterations=100):
    dim = 1
    particles = [random.uniform(bounds[0], bounds[1]) for _ in range(num_particles)]
    velocities = [random.uniform(-1, 1) for _ in range(num_particles)]
    personal_best = particles[:]
    personal_best_values = [f(p) for p in particles]
    global_best = personal_best[personal_best_values.index(min(personal_best_values))]

    for _ in range(iterations):
        for i in range(num_particles):
            velocities[i] = 0.5 * velocities[i] + 0.5 * random.random() * (personal_best[i] - particles[i]) + 0.5 * random.random() * (global_best - particles[i])
            particles[i] += velocities[i]
            particles[i] = max(min(particles[i], bounds[1]), bounds[0])
            if f(particles[i]) < f(personal_best[i]):
                personal_best[i] = particles[i]
        global_best = personal_best[personal_best_values.index(min([f(p) for p in personal_best]))]

    return global_best, f(global_best)

# Példa: Minimalizáljuk az f(x) = (x - 2)^2 függvényt
result = particle_swarm_optimization(lambda x: (x - 2)**2, bounds=(0, 10))
print("Legjobb pont:", result[0])
print("Legjobb érték:", result[1])

Alkalmazások

  1. Logisztikai problémák:
    • Jármű útvonaltervezés.
    • Ütemezési problémák.
  2. Mesterséges intelligencia:
    • Paraméterek optimalizálása gépi tanulási modellekben.
  3. Kémiai tervezés és biológia:
    • Fehérjeszerkezet elemzés.
    • Gyógyszerkutatás.
  4. Gazdaság és pénzügy:
    • Befektetési portfólió optimalizálás.


Előnyök és Hátrányok

Előnyök

  • Problémafüggetlenség: Sokféle probléma esetén alkalmazható.
  • Rugalmasság: Alkalmazkodik a komplex korlátokhoz.
  • Egyszerű implementáció: Kisebb technikai háttérrel is használható.

Hátrányok

  • Nem garantált optimalitás: Nem mindig találja meg a legjobb megoldást.
  • Időigényes lehet: Nagy problémák esetén.


Összegzés

A metaheurisztikus algoritmusok hatékony és rugalmas megoldást kínálnak a komplex optimalizációs problémákra. Pythonban egyszerűen implementálhatók, és számos tudományos és ipari alkalmazásban bizonyították hatékonyságukat. Bár nem garantálják az optimális megoldást, gyakran jó közelítést nyújtanak rövid idő alatt.

Fordítások

Tartalom

További információk

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