Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 36 ยท Applications and Tuning

Fitness Caching and Parallel Evaluation

Make genetic algorithms faster. Cache repeated fitness evaluations, vectorize with NumPy, evaluate in parallel with multiprocessing, and use cheap surrogate models.

In most real applications, the genetic operators cost almost nothing and the fitness function costs almost everything: a simulation, a model training run, a physics solver. A GA with 100 individuals and 200 generations makes 20,000 evaluations. If one takes a second, that is more than five hours. This lesson shows four ways to cut that cost: caching, vectorizing, parallel evaluation and surrogates.

Always profile first. If fitness takes 5 microseconds, none of this matters. If it takes 50 milliseconds or more, everything here pays off.

Caching: never evaluate the same thing twice

GAs create duplicates all the time. Elites are copied unchanged. Crossover between two similar parents returns something like a parent. As a population converges, a large share of individuals are identical to one already seen. Evaluating each again wastes time.

A fitness cache is a dictionary from genotype to fitness. For bit strings or integer lists, convert the chromosome to a tuple (or bytes) to use as the key.

Python Count how many evaluations a cache saves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The saving typically grows as the run goes on and the population converges, often reaching 30 to 70 percent. Two cautions:

  • Memory: an unbounded cache can grow forever. Use an LRU cache (for example functools.lru_cache(maxsize=100000)) or clear it periodically.
  • Noisy fitness: if the fitness is random (a simulation with random events), caching freezes the first lucky or unlucky value. Cache only deterministic functions, or average several runs.

For real-valued genes, exact duplicates are rare, so caching helps little. Round the genes to a grid (for example 6 decimals) if the problem tolerates that.

Vectorizing: let NumPy evaluate the whole population

A Python loop calling a function 100 times is slow. If you can write the fitness as array math over a (pop_size, genes) matrix, NumPy does all individuals in one call, often 20 to 200 times faster. All the examples in this course use that style when possible.

Python Loop versus vectorized fitness

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Vectorizing works only when the fitness is simple array math. A fitness that trains a model or runs a simulator cannot be vectorized, and parallelism is the next tool.

Parallel evaluation

Fitness evaluations of different individuals are independent, so this part of a GA is "embarrassingly parallel". With 8 cores you can approach an 8x speed-up. In normal Python, use a process pool:

Python
from multiprocessing import Pool

def fitness(individual):
    ...   # must be a top-level function so it can be pickled

if __name__ == "__main__":
    with Pool(processes=8) as pool:
        for generation in range(100):
            scores = pool.map(fitness, population)   # evaluates in parallel
            ...

Notes for real projects:

  • Use processes, not threads, for CPU-bound Python (the GIL blocks threads). Threads are fine if the fitness mostly waits for I/O or a C library that releases the GIL.
  • Chunking: use pool.map(f, pop, chunksize=...) so tiny tasks do not drown in messaging cost.
  • Libraries: DEAP lets you register pool.map as the evaluation mapper; joblib.Parallel, concurrent.futures.ProcessPoolExecutor and Ray work too.
  • Clusters: the same pattern scales to many machines with Dask, Ray or a job queue. A GA's synchronous generation is a natural barrier.
  • Seeds: give every worker its own random seed so they do not produce identical results.

The in-browser Python on this site runs in a single thread, so the pool example above is shown read-only. The ideas are identical, and the next example measures what parallelism can give you using a simple model.

Amdahl's law: how much can you gain?

If a fraction s of the run is serial (selection, crossover, bookkeeping), the best possible speed-up on p workers is 1 / (s + (1 - s) / p). If fitness is 95 percent of the time, 8 workers give about 1 / (0.05 + 0.95 / 8) = 5.9x, not 8x.

Python Estimate the parallel speed-up

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Asynchronous (steady-state) evaluation

A normal generational GA waits for the slowest individual in the generation. If evaluation times vary a lot (some simulations take 10 times longer), cores sit idle. A steady-state or asynchronous GA creates a new child whenever a worker is free and inserts it into the population when its result arrives, so all workers stay busy.

Surrogate-assisted evolution

When each evaluation is truly expensive (a CFD simulation taking hours), even parallelism is not enough. A surrogate is a cheap model (a neural network, a Gaussian process, a random forest) trained on the evaluations you already have. The GA uses the surrogate to screen candidates, and only the most promising few per generation are sent to the real function, which also provides new training data. This can reduce true evaluations by a factor of 10 or more. The risk is that the surrogate is wrong in unexplored areas, so keep evaluating some random and some best-predicted individuals for real.

Other speed-ups

  • Early termination: stop evaluating an individual as soon as it is clearly bad (for example, abort a simulation that crashes in the first second).
  • Smaller test problems: evaluate with a subsample of the data early in the run and the full data later.
  • Incremental evaluation: when a mutation changes one gene, update the fitness from the difference (very effective for TSP and scheduling).
  • Cheaper arithmetic: float32, compiled code (Numba, Cython) or GPU arrays.

Common mistakes

  • Optimizing before profiling. Measure where the time goes.
  • Caching noisy functions.
  • Giving every worker the same seed.
  • Sending huge objects to workers on every call. Send indices or small genomes and load big data once per worker.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a fitness cache usually save more work later in the run?

    As diversity falls, more individuals repeat earlier genotypes.
  2. 2. Why shouldn't you cache a noisy (random) fitness function?

    A cache assumes the same input always gives the same output.
  3. 3. For CPU-bound Python fitness functions, which is usually the right parallel tool?

    The GIL stops threads from running Python code in parallel; separate processes avoid it.
  4. 4. If fitness evaluation is 95 percent of the run time, what limits the speed-up on many cores?

    The serial part caps the speed-up at 1 / 0.05 = 20x no matter how many workers you add.

Summary

  • Fitness evaluation usually dominates the run time; profile before optimizing.
  • Cache deterministic fitness by genotype, with a bounded cache.
  • Vectorize with NumPy when the fitness is array math.
  • Evaluate individuals in parallel with processes; mind Amdahl's law and per-worker seeds.
  • Asynchronous GAs and surrogate models help when evaluations are slow or very expensive.

Next: Feature Selection with a Genetic Algorithm