Memetic Algorithms: Evolve Tours with 2-opt

Introduction

Nature's evolutionary process is powerful but wasteful. Billions of organisms live and die, most of them barely adequate. What if each individual spent some time getting better before it reproduced?

That is the idea behind memetic algorithms (MAs), introduced by Pablo Moscato in 1989. The name is a nod to Richard Dawkins' concept of a meme — a unit of cultural information that organisms pass on through learning, not just genes. A memetic algorithm runs a standard evolutionary loop (selection, crossover, mutation) but adds a local-search phase after every offspring is born. Each individual refines itself before entering the competition.

The payoff is dramatic. Pure genetic algorithms explore broadly but slowly exploit good regions. Pure local search is fast but gets trapped in local optima. MAs get both: the population-level diversity of evolution and the solution-quality depth of local refinement. On benchmark problems like the Travelling Salesman Problem, memetic approaches hold most of the competition records.

The technique is not a fixed algorithm — it is a framework. Plug in any evolutionary engine and any local search, and you get a memetic algorithm suited to your problem. That flexibility, combined with its track record, has made it a staple of real-world optimization.

Try It: Evolve Tours with 2-opt

The demo below runs a tiny memetic algorithm on a 10-city Travelling Salesman Problem. A population of tours evolves across generations; after each crossover, every offspring is polished by 2-opt (swap pairs of edges until no swap improves the tour) before selection.

<div class="ma-header">
  <span id="gen-label">Generation: 0</span>
  <span id="best-label">Best: —</span>
  <label class="toggle-label">
    <input type="checkbox" id="ls-toggle" checked>
    Local search (2-opt)
  </label>
</div>
<canvas id="tour-canvas" width="340" height="220"></canvas>
<div class="ma-controls">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="ma-status" class="ma-status">Press Step or Run to start evolving.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #f8f9fa; }
.ma-header { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap;
             font-size: .85rem; font-weight: 600; margin-bottom: .4rem; }
#gen-label { color: #1d3557; }
#best-label { color: #0a7d33; }
.toggle-label { display: flex; align-items: center; gap: .35rem; cursor: pointer;
                font-weight: 500; margin-left: auto; }
canvas { display: block; background: #fff; border: 1px solid #cdd9e3;
         border-radius: 8px; width: 100%; max-width: 340px; height: auto; }
.ma-controls { display: flex; gap: .5rem; margin-top: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.ma-status { font-size: .88rem; color: #555; margin-top: .35rem; min-height: 1.3em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Memetic Algorithm on a 10-city TSP ────────────────────────────────────────
// Each generation: tournament-select parents → order-crossover (OX) → 2-opt
// local search on every offspring (if enabled) → replace worst in population.

const CITIES = [
  [50,40],[270,30],[310,100],[290,190],[200,210],
  [100,200],[30,150],[80,80],[170,110],[220,160]
];
const N = CITIES.length;
const POP = 14;        // population size
const TOURNEY = 3;     // tournament size

// ── distance helpers ──────────────────────────────────────────────────────────
const dist = (a, b) => Math.hypot(CITIES[a][0]-CITIES[b][0], CITIES[a][1]-CITIES[b][1]);
function tourLen(t) {
  let s = 0;
  for (let i = 0; i < N; i++) s += dist(t[i], t[(i+1)%N]);
  return s;
}

// ── 2-opt local search ────────────────────────────────────────────────────────
function twoOpt(t) {
  t = t.slice();
  let improved = true;
  while (improved) {
    improved = false;
    for (let i = 0; i < N-1; i++) {
      for (let j = i+2; j < N; j++) {
        if (i === 0 && j === N-1) continue;
        const delta = dist(t[i],t[j]) + dist(t[i+1],t[(j+1)%N])
                    - dist(t[i],t[i+1]) - dist(t[j],t[(j+1)%N]);
        if (delta < -1e-9) {
          // reverse segment [i+1 .. j]
          let l = i+1, r = j;
          while (l < r) { [t[l],t[r]] = [t[r],t[l]]; l++; r--; }
          improved = true;
        }
      }
    }
  }
  return t;
}

// ── Order Crossover (OX) ──────────────────────────────────────────────────────
function ox(p1, p2) {
  const a = Math.floor(Math.random()*N);
  const b = a + 1 + Math.floor(Math.random()*(N-1));
  const child = new Array(N).fill(-1);
  // copy segment [a, b) from p1
  for (let i = a; i < b; i++) child[i % N] = p1[i % N];
  // fill rest from p2 in order
  let ci = b % N;
  for (let k = 0; k < N; k++) {
    const v = p2[(b+k)%N];
    if (!child.includes(v)) { child[ci] = v; ci = (ci+1)%N; }
  }
  return child;
}

// ── tournament selection ──────────────────────────────────────────────────────
function select(pop, fitArr) {
  let best = Math.floor(Math.random()*pop.length);
  for (let i = 1; i < TOURNEY; i++) {
    const c = Math.floor(Math.random()*pop.length);
    if (fitArr[c] < fitArr[best]) best = c;
  }
  return pop[best];
}

// ── random tour ───────────────────────────────────────────────────────────────
function randTour() {
  const t = Array.from({length:N},(_,i)=>i);
  for (let i = N-1; i > 0; i--) {
    const j = Math.floor(Math.random()*(i+1));
    [t[i],t[j]] = [t[j],t[i]];
  }
  return t;
}

// ── state ─────────────────────────────────────────────────────────────────────
let pop, fits, generation, bestLen, bestTour, running, timer;

function initPop() {
  const useLS = document.getElementById('ls-toggle').checked;
  pop = Array.from({length:POP}, () => {
    let t = randTour();
    return useLS ? twoOpt(t) : t;
  });
  fits = pop.map(tourLen);
  const bi = fits.indexOf(Math.min(...fits));
  bestLen = fits[bi]; bestTour = pop[bi].slice();
  generation = 0;
}

// ── one generation ────────────────────────────────────────────────────────────
function step() {
  const useLS = document.getElementById('ls-toggle').checked;
  // generate POP offspring
  const newPop = pop.slice();
  const newFits = fits.slice();
  for (let k = 0; k < POP; k++) {
    let child = ox(select(pop, fits), select(pop, fits));
    if (useLS) child = twoOpt(child);
    const cLen = tourLen(child);
    // replace worst
    const wi = newFits.indexOf(Math.max(...newFits));
    if (cLen < newFits[wi]) { newPop[wi] = child; newFits[wi] = cLen; }
  }
  pop = newPop; fits = newFits;
  generation++;
  const bi = fits.indexOf(Math.min(...fits));
  if (fits[bi] < bestLen) { bestLen = fits[bi]; bestTour = pop[bi].slice(); }
  updateUI();
  draw();
}

// ── drawing ───────────────────────────────────────────────────────────────────
function draw() {
  const canvas = document.getElementById('tour-canvas');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0,0,W,H);
  // draw all tours faintly
  ctx.strokeStyle = '#d0dce8';
  ctx.lineWidth = 0.7;
  for (const t of pop) {
    ctx.beginPath();
    for (let i = 0; i <= N; i++) { const [x,y] = CITIES[t[i%N]]; i===0?ctx.moveTo(x,y):ctx.lineTo(x,y); }
    ctx.stroke();
  }
  // draw best tour
  if (bestTour) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2;
    ctx.beginPath();
    for (let i = 0; i <= N; i++) { const [x,y] = CITIES[bestTour[i%N]]; i===0?ctx.moveTo(x,y):ctx.lineTo(x,y); }
    ctx.stroke();
  }
  // draw city dots
  for (let i = 0; i < N; i++) {
    const [x,y] = CITIES[i];
    ctx.beginPath(); ctx.arc(x,y,5,0,Math.PI*2);
    ctx.fillStyle = '#1d3557'; ctx.fill();
    ctx.fillStyle = '#fff'; ctx.font = 'bold 8px system-ui';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(i+1, x, y);
  }
}

function updateUI() {
  document.getElementById('gen-label').textContent = fmt('Generation: %generation%', { generation: generation });
  document.getElementById('best-label').textContent = fmt('Best: %round%', { round: Math.round(bestLen) });
  const ls = document.getElementById('ls-toggle').checked;
  document.getElementById('ma-status').textContent =
    fmt('Gen %generation% | Best tour: %round% | Mode: %v%', { generation: generation, round: Math.round(bestLen), v: ls?'Memetic (GA + 2-opt)':'Genetic only' });
}

function reset() {
  stopRun();
  initPop();
  updateUI();
  draw();
  document.getElementById('ma-status').textContent = 'Population reset. Press Step or Run.';
}

function stopRun() {
  running = false;
  if (timer) { clearTimeout(timer); timer = null; }
  document.getElementById('btn-run').textContent = 'Run';
}

function runLoop() {
  if (!running) return;
  step();
  timer = setTimeout(runLoop, 60);
}

document.getElementById('btn-step').addEventListener('click', () => { stopRun(); step(); });
document.getElementById('btn-run').addEventListener('click', () => {
  running = !running;
  document.getElementById('btn-run').textContent = running ? 'Pause' : 'Run';
  if (running) runLoop();
});
document.getElementById('btn-reset').addEventListener('click', reset);
document.getElementById('ls-toggle').addEventListener('change', reset);

reset();
console.assert(N === 10, 'CITIES count must be 10');
console.assert(POP > 0, 'population must be positive');
// verify twoOpt never increases tour length
const t0 = randTour();
const t1 = twoOpt(t0);
console.assert(tourLen(t1) <= tourLen(t0) + 1e-6, '2-opt must not increase tour length');
console.log('Memetic demo loaded. Cities:', N, '| Pop:', POP, '| 2-opt verified.');

<div class="ma-header">
  <span id="gen-label">Generation: 0</span>
  <span id="best-label">Best: —</span>
  <label class="toggle-label">
    <input type="checkbox" id="ls-toggle" checked>
    Local search (2-opt)
  </label>
</div>
<canvas id="tour-canvas" width="340" height="220"></canvas>
<div class="ma-controls">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="ma-status" class="ma-status">Press Step or Run to start evolving.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #f8f9fa; }
.ma-header { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap;
             font-size: .85rem; font-weight: 600; margin-bottom: .4rem; }
#gen-label { color: #1d3557; }
#best-label { color: #0a7d33; }
.toggle-label { display: flex; align-items: center; gap: .35rem; cursor: pointer;
                font-weight: 500; margin-left: auto; }
canvas { display: block; background: #fff; border: 1px solid #cdd9e3;
         border-radius: 8px; width: 100%; max-width: 340px; height: auto; }
.ma-controls { display: flex; gap: .5rem; margin-top: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.ma-status { font-size: .88rem; color: #555; margin-top: .35rem; min-height: 1.3em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Memetic Algorithm on a 10-city TSP ────────────────────────────────────────
// Each generation: tournament-select parents → order-crossover (OX) → 2-opt
// local search on every offspring (if enabled) → replace worst in population.

const CITIES = [
  [50,40],[270,30],[310,100],[290,190],[200,210],
  [100,200],[30,150],[80,80],[170,110],[220,160]
];
const N = CITIES.length;
const POP = 14;        // population size
const TOURNEY = 3;     // tournament size

// ── distance helpers ──────────────────────────────────────────────────────────
const dist = (a, b) => Math.hypot(CITIES[a][0]-CITIES[b][0], CITIES[a][1]-CITIES[b][1]);
function tourLen(t) {
  let s = 0;
  for (let i = 0; i < N; i++) s += dist(t[i], t[(i+1)%N]);
  return s;
}

// ── 2-opt local search ────────────────────────────────────────────────────────
function twoOpt(t) {
  t = t.slice();
  let improved = true;
  while (improved) {
    improved = false;
    for (let i = 0; i < N-1; i++) {
      for (let j = i+2; j < N; j++) {
        if (i === 0 && j === N-1) continue;
        const delta = dist(t[i],t[j]) + dist(t[i+1],t[(j+1)%N])
                    - dist(t[i],t[i+1]) - dist(t[j],t[(j+1)%N]);
        if (delta < -1e-9) {
          // reverse segment [i+1 .. j]
          let l = i+1, r = j;
          while (l < r) { [t[l],t[r]] = [t[r],t[l]]; l++; r--; }
          improved = true;
        }
      }
    }
  }
  return t;
}

// ── Order Crossover (OX) ──────────────────────────────────────────────────────
function ox(p1, p2) {
  const a = Math.floor(Math.random()*N);
  const b = a + 1 + Math.floor(Math.random()*(N-1));
  const child = new Array(N).fill(-1);
  // copy segment [a, b) from p1
  for (let i = a; i < b; i++) child[i % N] = p1[i % N];
  // fill rest from p2 in order
  let ci = b % N;
  for (let k = 0; k < N; k++) {
    const v = p2[(b+k)%N];
    if (!child.includes(v)) { child[ci] = v; ci = (ci+1)%N; }
  }
  return child;
}

// ── tournament selection ──────────────────────────────────────────────────────
function select(pop, fitArr) {
  let best = Math.floor(Math.random()*pop.length);
  for (let i = 1; i < TOURNEY; i++) {
    const c = Math.floor(Math.random()*pop.length);
    if (fitArr[c] < fitArr[best]) best = c;
  }
  return pop[best];
}

// ── random tour ───────────────────────────────────────────────────────────────
function randTour() {
  const t = Array.from({length:N},(_,i)=>i);
  for (let i = N-1; i > 0; i--) {
    const j = Math.floor(Math.random()*(i+1));
    [t[i],t[j]] = [t[j],t[i]];
  }
  return t;
}

// ── state ─────────────────────────────────────────────────────────────────────
let pop, fits, generation, bestLen, bestTour, running, timer;

function initPop() {
  const useLS = document.getElementById('ls-toggle').checked;
  pop = Array.from({length:POP}, () => {
    let t = randTour();
    return useLS ? twoOpt(t) : t;
  });
  fits = pop.map(tourLen);
  const bi = fits.indexOf(Math.min(...fits));
  bestLen = fits[bi]; bestTour = pop[bi].slice();
  generation = 0;
}

// ── one generation ────────────────────────────────────────────────────────────
function step() {
  const useLS = document.getElementById('ls-toggle').checked;
  // generate POP offspring
  const newPop = pop.slice();
  const newFits = fits.slice();
  for (let k = 0; k < POP; k++) {
    let child = ox(select(pop, fits), select(pop, fits));
    if (useLS) child = twoOpt(child);
    const cLen = tourLen(child);
    // replace worst
    const wi = newFits.indexOf(Math.max(...newFits));
    if (cLen < newFits[wi]) { newPop[wi] = child; newFits[wi] = cLen; }
  }
  pop = newPop; fits = newFits;
  generation++;
  const bi = fits.indexOf(Math.min(...fits));
  if (fits[bi] < bestLen) { bestLen = fits[bi]; bestTour = pop[bi].slice(); }
  updateUI();
  draw();
}

// ── drawing ───────────────────────────────────────────────────────────────────
function draw() {
  const canvas = document.getElementById('tour-canvas');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0,0,W,H);
  // draw all tours faintly
  ctx.strokeStyle = '#d0dce8';
  ctx.lineWidth = 0.7;
  for (const t of pop) {
    ctx.beginPath();
    for (let i = 0; i <= N; i++) { const [x,y] = CITIES[t[i%N]]; i===0?ctx.moveTo(x,y):ctx.lineTo(x,y); }
    ctx.stroke();
  }
  // draw best tour
  if (bestTour) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2;
    ctx.beginPath();
    for (let i = 0; i <= N; i++) { const [x,y] = CITIES[bestTour[i%N]]; i===0?ctx.moveTo(x,y):ctx.lineTo(x,y); }
    ctx.stroke();
  }
  // draw city dots
  for (let i = 0; i < N; i++) {
    const [x,y] = CITIES[i];
    ctx.beginPath(); ctx.arc(x,y,5,0,Math.PI*2);
    ctx.fillStyle = '#1d3557'; ctx.fill();
    ctx.fillStyle = '#fff'; ctx.font = 'bold 8px system-ui';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(i+1, x, y);
  }
}

function updateUI() {
  document.getElementById('gen-label').textContent = fmt('Generation: %generation%', { generation: generation });
  document.getElementById('best-label').textContent = fmt('Best: %round%', { round: Math.round(bestLen) });
  const ls = document.getElementById('ls-toggle').checked;
  document.getElementById('ma-status').textContent =
    fmt('Gen %generation% | Best tour: %round% | Mode: %v%', { generation: generation, round: Math.round(bestLen), v: ls?'Memetic (GA + 2-opt)':'Genetic only' });
}

function reset() {
  stopRun();
  initPop();
  updateUI();
  draw();
  document.getElementById('ma-status').textContent = 'Population reset. Press Step or Run.';
}

function stopRun() {
  running = false;
  if (timer) { clearTimeout(timer); timer = null; }
  document.getElementById('btn-run').textContent = 'Run';
}

function runLoop() {
  if (!running) return;
  step();
  timer = setTimeout(runLoop, 60);
}

document.getElementById('btn-step').addEventListener('click', () => { stopRun(); step(); });
document.getElementById('btn-run').addEventListener('click', () => {
  running = !running;
  document.getElementById('btn-run').textContent = running ? 'Pause' : 'Run';
  if (running) runLoop();
});
document.getElementById('btn-reset').addEventListener('click', reset);
document.getElementById('ls-toggle').addEventListener('change', reset);

reset();
console.assert(N === 10, 'CITIES count must be 10');
console.assert(POP > 0, 'population must be positive');
// verify twoOpt never increases tour length
const t0 = randTour();
const t1 = twoOpt(t0);
console.assert(tourLen(t1) <= tourLen(t0) + 1e-6, '2-opt must not increase tour length');
console.log('Memetic demo loaded. Cities:', N, '| Pop:', POP, '| 2-opt verified.');

Result

Console

Press Step to advance one generation at a time and watch the best tour length drop. Press Run to let it evolve continuously. Toggle Local search on/off to compare pure genetic evolution against the memetic version — the difference in solution quality is stark.

The Real Complexity

Memetic algorithms sit in fascinating theoretical territory.

No worst-case guarantee. Like all metaheuristics, MAs cannot promise optimality. For NP-hard problems like TSP or graph coloring, no polynomial algorithm is known to find the true optimum, and MAs are no exception.
No-free-lunch theorem. Averaged over all possible problems, every search algorithm performs identically. MAs win only when the problem structure — smooth fitness landscapes with good crossover operators — suits the design. The art is in matching the local searcher to the problem.
Why they still win in practice. The local-search phase dramatically reduces the effective search space: offspring arrive already near a local optimum, so the genetic operators work in a landscape of locally optimal individuals rather than random noise. This is called Lamarckian learning (offspring inherit the improved genotype) versus Baldwinian learning (offspring use the improved phenotype for fitness but revert to original genotype for reproduction). Both variants work; Lamarckian is more common.
Per-generation cost. Running 2-opt on every offspring adds $O(n^{2})$ work per individual per generation (n = problem size). For large instances this is significant. Adaptive MAs run local search only on promising individuals or only for a few steps — a budget-constrained variant that scales better.
Relation to other problems. MAs are most powerful on problems where checking a solution is easy but finding a good one is hard — the NP landscape. They have broken records on Travelling Salesman, graph coloring, scheduling, and protein-structure prediction. They are essentially a practical assault on NP-hard instances where exact solvers give up.

Where It Matters

Memetic algorithms shine wherever the search space is large, the problem is NP-hard, and a good local-search operator can be designed:

Logistics and routing: TSP, vehicle routing, and delivery scheduling — memetic approaches hold many of the best-known solution records on standard benchmarks.
Protein structure prediction: the energy landscape of a folding protein is a notoriously rugged optimization surface; MAs with fragment-based local search are among the top performers.
VLSI design and circuit layout: placing millions of components to minimize wire length and heat is a combinatorial nightmare; MAs automate it in hours rather than human-weeks.
Timetabling and scheduling: university timetables, nurse rosters, and airline crew scheduling all combine hard constraints with soft preferences — exactly where memetic frameworks excel.
Drug and material design: a molecular structure is a combinatorial object; local moves (bond rotations, atom substitutions) pair naturally with evolutionary search to explore chemical space.

The common thread is structured search spaces where domain knowledge can be baked into a local-search operator — that knowledge is exactly what pure genetic algorithms discard and what MAs preserve. See also non-convex optimization for the landscape theory that explains why local search helps so much.

Conclusion

Memetic algorithms offer a simple but powerful insight: don't just breed — learn first. By coupling evolutionary global search with local refinement on every individual, they achieve solution quality that neither approach reaches alone.

They carry no theoretical guarantee of optimality — the No-Free-Lunch theorem ensures that. But on the structured, NP-hard problems that matter most in the real world, memetic algorithms consistently outperform both pure genetic search and pure local search. That track record, built across logistics, biology, engineering, and scheduling, makes them one of the most useful tools in the computational toolkit.

The next time you face an optimization problem too large for exact methods, consider letting your candidates evolve and learn. The combination might be exactly what P vs NP leaves room for.

Comments

Loading comments...

https://www.kipuhub.com/en/article/memetic-algorithms/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Memetic Algorithms

When every individual polishes itself before the next generation