Memetic Algorithm (MA)

A Genetic Algorithm that locally improves every newborn child. Combines wide exploration with deep intensification.

Intuition

The big idea

Genetic algorithms cover a lot of ground but rarely polish any individual solution to a local optimum — they keep mixing and matching genes. Memetic algorithms add one step: after each crossover-and-mutation, take the new child and run local search on it until it's locally as good as it can be. Then put it back into the population. So you're evolving locally-optimized individuals.

Genetic Algorithm vs Memetic Algorithm

Step	GA	MA
1. Generate initial population	✓	✓
2. Selection	✓	✓
3. Crossover	✓	✓
4. Mutation	✓	✓
5. Local search on every offspring	✗	✓
6. Cull weakest	✓	✓
7. Repeat	✓	✓

The algorithm

MEMETIC_ALGORITHM():
    P ← random population
    repeat until stop:
        pairs ← random pairs from P
        offspring ← []
        for each (p1, p2) in pairs:
            (c1, c2) ← crossover(p1, p2)
            c1 ← mutate(c1);  c2 ← mutate(c2)
            c1 ← local_search(c1)      // ← the memetic step
            c2 ← local_search(c2)
            offspring.add(c1); offspring.add(c2)
        P ← keep_best_half( P ∪ offspring )

What local search looks like

Two simple versions used in your notes:

// Version 1 — one pass over all variables
for i = 1..K:
    try changing variable i's value
    if fitness increases: keep change

// Version 2 — repeat until no improvement
while (not stop):
    for i = 1..K:
        try changing variable i's value
        if fitness increases: keep change

Worked example (graph coloring, 2 colors)

Population size = 100, chromosome length K (e.g., 40 variables):

Individual 1: R B B R B R … R     fitness = 40 satisfied
Individual 2: B R R B R B … R     fitness = 35
…
Individual 100: R R B B R R … R   fitness = 56

Step 2: form 50 pairs at random:
    (1, 51), (3, 10), …, (13, 89)

Step 3: crossover each pair. Suppose pair (1, 51) produces:
    Child A: fitness 15 (worse than parents — that's fine)
    Child B: fitness 25

Step 4: apply LOCAL SEARCH to each child.
    Local search version 1 on Child A:
        For each variable i in 1..K:
            flip variable i's color
            if fitness improves, keep it; else revert
    Child A might end up with fitness 45 or higher after one local-search pass.

Step 5: cull. Keep the best 100 of (parents + improved offspring).

Exploration vs intensification

Why MA > GA in practice

Exploration — covering many parts of the search space. GA does this well: crossover combines genes from across the population.
Intensification — squeezing the most out of one region. Local search does this well: refine until no neighbor is better.
MA combines both. GA gives you the diverse population; local search polishes each individual.

Exam tips

Frequently asked

"State the difference between GA and MA in one step" — MA applies local search to each offspring; GA does not.
"What's the advantage?" — exploration (from GA) + intensification (from local search) = fewer generations to converge, better final solutions.
"Show an MA iteration on graph coloring" — generate parents, crossover, mutate, run local search per child, cull. Often the local-search step is the most important to show.
"What's the cost?" — each generation is more expensive than GA because of the local-search per offspring.