Memetic Algorithm
Also known as: Hybrid Evolutionary Algorithm, Cultural Algorithm (local-search variant), Genetic Local Search, Memetik Algoritma
A Memetic Algorithm (MA) is a population-based metaheuristic that combines the global exploration of an evolutionary algorithm with the local exploitation of individual learning procedures. Introduced by Pablo Moscato in 1989 at Caltech, MAs draw on Richard Dawkins' concept of the meme — a unit of cultural transmission — to model the idea that solutions can improve not only through crossover and mutation but also through individual refinement within each generation.
Key highlights
- Combines global search breadth of evolutionary algorithms with local search depth, often outperforming both in isolation
- Highly modular: the local search component can be swapped for any neighbourhood-based method suited to the problem
- Robust to rugged, multimodal fitness landscapes where gradient-based methods fail
- Empirically faster convergence than standard genetic algorithms on many combinatorial benchmarks
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Memetic algorithms are best suited to combinatorial and continuous optimisation problems where the fitness landscape contains many local optima and pure evolutionary search converges too slowly. They are particularly effective for NP-hard problems such as the travelling salesman problem, vehicle routing, protein structure prediction, and timetabling. Prerequisites include a well-defined neighbourhood structure for the local search phase. MAs are less appropriate when local search itself is prohibitively expensive, when the problem is fully continuous and smooth (gradient methods are faster), or when extremely large populations are required and computation time is limited.
Strengths & limitations
- Combines global search breadth of evolutionary algorithms with local search depth, often outperforming both in isolation
- Highly modular: the local search component can be swapped for any neighbourhood-based method suited to the problem
- Robust to rugged, multimodal fitness landscapes where gradient-based methods fail
- Empirically faster convergence than standard genetic algorithms on many combinatorial benchmarks
- Computational cost per generation is higher than pure evolutionary algorithms because each individual undergoes local refinement
- Performance is sensitive to the choice and intensity of the local search operator — poor choices can cause premature convergence
- Requires careful balance between exploration (evolutionary) and exploitation (local search) to avoid population collapse
- Problem-specific design of the neighbourhood structure is often needed, reducing out-of-the-box applicability
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How is a memetic algorithm different from a genetic algorithm?
A genetic algorithm relies solely on population-level operators (selection, crossover, mutation) and does not refine individual solutions between generations. A memetic algorithm adds a local search step after the evolutionary operators, so each individual is improved within its local neighbourhood before contributing to the next generation. This individual learning phase is the defining difference and typically yields faster, higher-quality convergence on hard combinatorial problems.
What local search methods are commonly used inside memetic algorithms?
Any neighbourhood-based procedure can serve as the local search component. Common choices include hill-climbing (steepest descent), 2-opt and 3-opt moves for routing problems, simulated annealing for problems with many local optima, and tabu search when cycling is a concern. The choice depends on the problem's structure: the neighbourhood must be small enough to search quickly yet rich enough to escape poor solutions efficiently.
Should the genotype be updated after local search (Lamarckian) or left unchanged (Baldwinian)?
In the Lamarckian scheme, the locally improved solution replaces the original in the population, accelerating convergence but risking premature loss of diversity. In the Baldwinian scheme, only the fitness score is updated while the genotype is unchanged, preserving diversity at the cost of slower progress. Empirical evidence suggests Lamarckian updating generally converges faster, but the best choice depends on the problem landscape and population size.
Sources
- 1.Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program Report 826.
- 2.Neri, F., & Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2, 1–14.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 2). Memetic Algorithm. ScholarGate. https://scholargate.app/optimization/memetic-algorithm