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.
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.
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.
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 = * n
path =
visited = True
total_cost = 0
for _ in range(n - 1):
last = path
next_city = np.argmin( if not visited else float('inf') for j in range(n)])
path.append(next_city)
visited = True
total_cost += distance_matrix
total_cost += distance_matrix]] # 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([
,
,
,
])
path, cost = greedy_tsp(distance_matrix)
print("Útvonal:", path)
print("Teljes költség:", cost)
import math
import random
def simulated_annealing(function, bounds, temp=1000, cooling_rate=0.99, max_iter=1000):
current_solution = random.uniform(bounds, bounds)
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 <= new_solution <= bounds:
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 tartományban
result = simulated_annealing(lambda x: (x - 3)**2, bounds=(0, 10))
print("Legjobb megoldás:", result)
import random
def genetic_algorithm(function, bounds, population_size=50, generations=100, mutation_rate=0.1):
def generate_individual():
return random.uniform(bounds, bounds)
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 =
for _ in range(generations):
population = sorted(population, key=function)
next_generation = population # Elitizmus
while len(next_generation) < population_size:
parent1, parent2 = random.sample(population, 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 tartományban
result = genetic_algorithm(lambda x: (x - 5)**2, bounds=(0, 10))
print("Legjobb megoldás:", result)
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.