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.
import random
def genetic_algorithm(fitness_func, 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(-0.1, 0.1)
return individual
def crossover(parent1, parent2):
return (parent1 + parent2) / 2
population =
for _ in range(generations):
population = sorted(population, key=fitness_func)
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=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)
print("Legjobb érték:", result)
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.
import math
import random
def simulated_annealing(f, bounds, temp=1000, cooling_rate=0.99, max_iter=1000):
current_solution = random.uniform(bounds, bounds)
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 <= new_solution <= bounds:
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)
print("Legjobb érték:", result)
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.
Egy egyszerű ACO példaként alkalmazható az Utazó Ügynök Problémában (TSP).
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.
import random
def particle_swarm_optimization(f, bounds, num_particles=30, iterations=100):
dim = 1
particles = , bounds) for _ in range(num_particles)]
velocities =
personal_best = particles
personal_best_values =
global_best = personal_best
for _ in range(iterations):
for i in range(num_particles):
velocities = 0.5 * velocities + 0.5 * random.random() * (personal_best - particles) + 0.5 * random.random() * (global_best - particles)
particles += velocities
particles = max(min(particles, bounds), bounds)
if f(particles) < f(personal_best):
personal_best = particles
global_best = 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)
print("Legjobb érték:", result)
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.