Ugrás a tartalomhoz

heurisztikus algoritmus

A Wikiszótárból, a nyitott szótárból

Magyar

Kiejtés

  • IPA: [ ˈhɛuristikuʃɒlɡoritmuʃ]

Főnév

heurisztikus algoritmus

  1. (matematika, algoritmusok)

Heurisztikus algoritmusok

Definíció

A heurisztikus algoritmusok olyan problémamegoldó módszerek, amelyek célja, hogy gyors és jó közelítő megoldásokat találjanak komplex optimalizálási problémákra, amikor a pontos megoldás megtalálása túl időigényes vagy számításigényes. Ezek az algoritmusok nem garantálnak optimális megoldást, de gyakran jó eredményeket nyújtanak rövid idő alatt.


Főbb Jellemzők

  1. Gyors megoldás: Gyors közelítéseket nyújt, különösen nagy állapottérrel rendelkező problémáknál.
  2. Nem garantált optimalitás: Az eredmények lehetnek optimálisak, de erre nincs garancia.
  3. Korlátos erőforrások: Akkor hasznos, ha idő- vagy számítási erőforrások korlátozottak.
  4. Problémaspecifikus megközelítés: A heurisztikus algoritmusokat gyakran az adott probléma tulajdonságaihoz igazítják.


Heurisztikus Algoritmusok Típusai

Egyszerű Heurisztikák

Ezek az algoritmusok egy adott szabályt vagy egyszerű stratégiát követnek. - Greedy algoritmus (Mohó algoritmus): - Minden lépésben a pillanatnyilag legjobb megoldást választja. - Példa: Kruskal-algoritmus a minimális feszítőfa megtalálására.

Metaheurisztikák

Ezek általános keretrendszerek, amelyek különféle problémákra alkalmazhatók. - Szimulált lehűlés (Simulated Annealing): Inspirációja a hűtött fém kristályszerkezete. - Genetikus algoritmusok: Az evolúciós biológiát utánozza. - Hangya kolónia optimalizáció (Ant Colony Optimization, ACO): A hangyák útvonalkereséséből származik. - Részecskeraj optimalizáció (Particle Swarm Optimization, PSO): A madarak és halrajok viselkedésén alapul.


Példa Algoritmusok és Implementációk

1. Greedy Algoritmus

Példa: Utazó ügynök problémája (TSP)

Egy egyszerű greedy megközelítés a legközelebbi szomszéd kiválasztása: 

import numpy as np

def greedy_tsp(distance_matrix):
    n = len(distance_matrix)
    visited = [False] * n
    path = [0]
    visited[0] = True
    total_cost = 0

    for _ in range(n - 1):
        last = path[-1]
        next_city = np.argmin([distance_matrix[last][j] if not visited[j] else float('inf') for j in range(n)])
        path.append(next_city)
        visited[next_city] = True
        total_cost += distance_matrix[last][next_city]

    total_cost += distance_matrix[path[-1]][path[0]]  # Visszatérés az indulási városba
    path.append(0)

    return path, total_cost

# Példa távolságmátrix
distance_matrix = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
])

path, cost = greedy_tsp(distance_matrix)
print("Útvonal:", path)
print("Teljes költség:", cost)

2. Szimulált Lehűlés

Példa: Optimalizációs Probléma
import math
import random

def simulated_annealing(function, bounds, temp=1000, cooling_rate=0.99, max_iter=1000):
    current_solution = random.uniform(bounds[0], bounds[1])
    current_value = function(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 = function(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 az [0, 10] tartományban
result = simulated_annealing(lambda x: (x - 3)**2, bounds=(0, 10))
print("Legjobb megoldás:", result)

3. Genetikus Algoritmus

Példa: Egyszerű Függvény Optimalizálás
import random

def genetic_algorithm(function, 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(-1, 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=function)
        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=function)
    return best_solution, function(best_solution)

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

Alkalmazások

  1. Logisztika és ütemezés:
    • Utazó ügynök probléma (TSP).
    • Jármű útvonaltervezési probléma (VRP).
  2. Mesterséges intelligencia és gépi tanulás:
    • Paraméteroptimalizálás.
    • Neurális hálózatok súlyozásának finomítása.
  3. Operációkutatás:
    • Hálózatoptimalizálási problémák (pl. minimális feszítőfa, Max-Cut probléma).
  4. Biológia és bioinformatika:
    • Fehérjeszerkezet-elemzés.
    • DNS szekvenciaillesztés.


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

Előnyök

  • Gyors és hatékony: Nagy méretű problémák esetén is jól működnek.
  • Rugalmasság: Széles körben alkalmazható különféle problémákra.
  • Egyszerű implementáció: Számos heurisztika könnyen kódolható.

Hátrányok

  • Nem garantált optimalitás: Az algoritmusok nem mindig találják meg a legjobb megoldást.
  • Problémafüggő teljesítmény: Egy adott algoritmus nem biztos, hogy minden problémára megfelelő.


Összegzés

A heurisztikus algoritmusok kulcsszerepet játszanak a komplex optimalizálási problémák megoldásában. Bár nem garantálják az optimális megoldást, gyakran megfelelő kompromisszumot nyújtanak a megoldás minősége és a számítási idő között. Az egyszerű heurisztikák és a metaheurisztikák kombinációja számos ipari és tudományos alkalmazásban hatékony megoldásokat kínál.

Fordítások

Tartalom

További információk

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