A memetic algorithm (MA) combines a population-based global search — typically a genetic algorithm — with one or more fast local search procedures that polish each individual after it is created. The term was coined by Pablo Moscato in his 1989 technical report, drawing an analogy to Richard Dawkins’ concept of “memes” (cultural units that evolve): where genes are passed through biological reproduction, memes are refined through individual learning before being transmitted. In optimization terms, the “meme” is a local search operator that improves each candidate solution before it re-enters the population.
More broadly, hybrid metaheuristics combine any metaheuristic with other optimization approaches — mathematical programming (LP/MIP relaxations), constraint programming, machine learning surrogates, or domain-specific heuristics. The core insight is that global search methods (GA, ACO, PSO) are good at exploration but poor at fine-grained exploitation, while local search methods (hill climbing, 2-opt, tabu search) are excellent at exploitation but get trapped in local optima. Combining them yields solvers that are dramatically better than either component alone.
This is not a theoretical curiosity — it is the dominant pattern in high-performance optimization. Virtually every competition-winning solver for vehicle routing, scheduling, bin-packing, and TSP is a hybrid. The celebrated LKH-3 solver for TSP uses an evolutionary framework wrapped around the Lin-Kernighan local search. Google OR-Tools’ routing solver combines metaheuristic search with constraint propagation. Understanding how to design effective hybrids is arguably the most practically valuable skill in the metaheuristic toolkit.
The canonical MA follows a simple structure:
def memetic_algorithm(problem, pop_size, generations, local_search):
# 1. Initialize population randomly
population = [random_solution(problem) for _ in range(pop_size)]
# 2. Improve each individual with local search
population = [local_search(ind) for ind in population]
for gen in range(generations):
# 3. Selection (e.g., tournament)
parents = select(population)
# 4. Crossover → offspring
offspring = [crossover(p1, p2) for p1, p2 in pairs(parents)]
# 5. Mutation
offspring = [mutate(child) for child in offspring]
# 6. Local search on each offspring (the "memetic" step)
offspring = [local_search(child) for child in offspring]
# 7. Replacement (e.g., elitist)
population = replace(population, offspring)
return best(population)Steps 1–5 and 7 are standard GA. Step 6 is what makes it memetic: every offspring is locally optimized before competing for survival. This ensures the population consists of local optima (solutions that cannot be improved by small moves), so crossover operates on high-quality building blocks rather than random noise.
In Lamarckian MAs, the locally improved solution replaces the original genotype — the “learned” improvement is inherited. In Baldwinian MAs, the local search determines the fitness value but the original (unimproved) genotype is stored in the population. Lamarckian is the default and usually performs better because it maintains a population of already-optimized solutions. Baldwinian preserves genetic diversity (the genotype hasn’t been overwritten) at the cost of re-doing local search each generation.
The local search is the most critical design decision. Common choices by problem type:
Standard GA crossover operators (single-point, uniform) often produce infeasible or very poor offspring for combinatorial problems. MAs typically use problem-specific recombination designed to combine structural features of two good solutions:
Because local search pushes all individuals to local optima, MA populations converge faster than pure GA populations. Managing diversity is critical. Techniques include: (1) distance-based replacement — only replace an individual if the offspring is both better and sufficiently different (measured by Hamming distance, edit distance, or broken-pairs distance); (2) diverse initialization — use different construction heuristics; (3) adaptive local search intensity — apply more local search to diverse offspring, less to similar ones.
The memetic algorithm is the most common hybrid pattern, but not the only one:
Thibaut Vidal’s Hybrid Genetic Search for the Capacitated VRP (HGS-CVRP) is the gold standard for vehicle routing. It combines: (1) a genetic algorithm with population diversity management based on broken-pairs distance, (2) an education procedure (local search) using relocate, swap, 2-opt*, and or-opt moves, and (3) penalty-based handling of capacity and duration constraints. HGS-CVRP holds the best-known solutions for most CVRPLIB benchmark instances and runs in seconds to minutes. The algorithm is open-source and integrated into Google OR-Tools.
Keld Helsgott’s LKH-3 solver wraps the Lin-Kernighan variable-depth local search in an evolutionary framework. The population maintains a set of locally optimal tours; Edge Assembly Crossover (EAX) combines edges from two parent tours to produce offspring that inherit good sub-structures from both. LKH-3 routinely finds optimal or near-optimal solutions for TSP instances with millions of cities and has been extended to handle multiple variants including TSP with time windows and pickup-and-delivery.
Evolutionary NAS methods like Google’s AmoebaNet and NSGA-Net are memetic in spirit: a genetic algorithm evolves network architectures (the global search), and each candidate architecture is trained for a fixed number of epochs (the “local search” — gradient descent on the weights). The fitness is validation accuracy after training. The MA framework naturally handles the mixed discrete (topology) + continuous (weights) search space.
Optimizing LLM prompt templates and retrieval-augmented generation (RAG) pipelines involves discrete, non-differentiable search spaces. A memetic approach might evolve a population of prompt variants using crossover (combine segments from two prompts), apply local search (single-word substitutions, rephrasing), and evaluate fitness on a benchmark. DSPy’s optimization module uses similar principles.