Beginner Explanation
Imagine you are trying to find the best route to your friend’s house, but there are many ways to get there, and you don’t know which is the fastest. A metaheuristic is like a smart map that gives you tips on how to explore different paths efficiently. Instead of trying every possible route (which would take forever), it helps you make good guesses and adjust your route based on traffic or road conditions. So, you can reach your friend’s house in the best time possible without getting lost in all the choices.Technical Explanation
Metaheuristics are high-level procedures that guide the search process in optimization problems. They do not guarantee an optimal solution but aim to find a good enough solution in a reasonable time. Common examples include Genetic Algorithms, Simulated Annealing, and Particle Swarm Optimization. For instance, in Python, a Genetic Algorithm can be implemented using the DEAP library. Here’s a simple example: “`python from deap import base, creator, tools, algorithms import random # Define the problem creator.create(“FitnessMax”, base.Fitness, weights=(1.0,)) creator.create(“Individual”, list, fitness=creator.FitnessMax) # Initialize population population = [creator.Individual([random.random() for _ in range(10)]) for _ in range(100)] # Define evaluation function def evaluate(ind): return sum(ind), # Register functions toolbox = base.Toolbox() toolbox.register(“evaluate”, evaluate) toolbox.register(“mate”, tools.cxTwoPoint) toolbox.register(“mutate”, tools.mutGaussian, mu=0, sigma=1, indpb=0.2) toolbox.register(“select”, tools.selTournament, tournsize=3) # Run the algorithm for gen in range(50): offspring = toolbox.select(population, len(population)) offspring = list(map(toolbox.clone, offspring)) for child1, child2 in zip(offspring[::2], offspring[1::2]): if random.random() < 0.5: toolbox.mate(child1, child2) del child1.fitness.values for mutant in offspring: if random.random() < 0.2: toolbox.mutate(mutant) del mutant.fitness.values population[:] = offspring ``` This code sets up a simple Genetic Algorithm to optimize a function by evolving a population of solutions.Academic Context
Metaheuristics have been extensively studied in operations research and computer science. They provide a flexible framework for solving complex optimization problems where traditional methods may fail. Key papers include “A Survey of Metaheuristics for the Traveling Salesman Problem” by Gendreau et al., which discusses various metaheuristic approaches to a classic optimization problem. The mathematical foundations often involve combinatorial optimization and stochastic processes, emphasizing the balance between exploration (searching new areas) and exploitation (refining known good areas).Code Examples
Example 1:
from deap import base, creator, tools, algorithms
import random
# Define the problem
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
# Initialize population
population = [creator.Individual([random.random() for _ in range(10)]) for _ in range(100)]
# Define evaluation function
def evaluate(ind):
return sum(ind),
# Register functions
toolbox = base.Toolbox()
toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
# Run the algorithm
for gen in range(50):
offspring = toolbox.select(population, len(population))
offspring = list(map(toolbox.clone, offspring))
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < 0.5:
toolbox.mate(child1, child2)
del child1.fitness.values
for mutant in offspring:
if random.random() < 0.2:
toolbox.mutate(mutant)
del mutant.fitness.values
population[:] = offspringExample 2:
offspring = toolbox.select(population, len(population))
offspring = list(map(toolbox.clone, offspring))
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < 0.5:
toolbox.mate(child1, child2)
del child1.fitness.values
for mutant in offspring:
if random.random() < 0.2:
toolbox.mutate(mutant)
del mutant.fitness.values
population[:] = offspringExample 3:
from deap import base, creator, tools, algorithms
import random
# Define the problem
creator.create("FitnessMax", base.Fitness, weights=(1.0,))Example 4:
import random
# Define the problem
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)Example 5:
def evaluate(ind):
return sum(ind),
# Register functions
toolbox = base.Toolbox()View Source: https://arxiv.org/abs/2511.16201v1