Memetic 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.

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.

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.