#evolutionary algorithms #programming #debugging #evolutionary algorithms #c++

Programming before and after ChatGPT

Learning algorithms are notoriously hard to debug, and evolutionary algorithms are even worse.

You may have already experienced it if you have implemented a simple genetic algorithm (e.g. GAs are fault-tolerant by their very nature...).

The main issue is that when an evolutionary algorithm fails to learn, it's unclear whether this is due to a bug, the learning problem being too difficult, excessive noise, or some other factor.

Moreover, sometimes bugs cause learning algorithms to perform better than they should — these are particularly hard to catch and always a bit disappointing when you do.

Common debugging steps

In general, when debugging machine learning models, you should examine the following stages: data collection, choosing training data, training model, evaluating on test data.

At any of these steps, things can go wrong.

Is the problem with generalization to the test data?

It's unrealistic to expect better performance on test data than on training data. Can your system at least fit the training data well?

If yes, then the issue is likely generalization — perhaps the model is too complex, there are too many features, or you don't have enough data.

If no, then the problem is in representation (you probably need better features / function set or better data).

Do you have train/test mismatch?

If your model fits the training data but fails to generalize, the test data may differ in some way. Try shuffling the training and test sets together and randomly selecting a new test set.

If performance improves, then your original test set has distributional differences.

If it doesn't help, then you have deeper generalization issues.

Is your algorithm implemented correctly?

Ask yourself: is it actually optimizing what you think it’s optimizing? Instead of just measuring accuracy, check whether the algorithm minimizes the intended objective function (e.g. log loss or hinge loss). In other terms you can often prefer fitness over other model measurements.

To verify correctness:

  • handcraft simple datasets where you know the expected behavior;
  • run a symbolic regression genetic program on an easy linear function;
  • compare against a reference implementation if available.

Do you have an adequate representation?

If your model can't even fit the training data, your function set may not be expressive enough.

One trick to test this is adding a DummyInput feature: assign +1 if the example is positive, 0 if negative; this feature is a perfect class indicator.

If adding DummyInput doesn't drive training error near 0%, you likely have a bug.

If it does reach near 0% error, then your function set may need improvement.

Do you have enough data?

Try training on only 80% of your training data and see how much performance degrades: if it drops significantly, getting more data will likely help; otherwise your model may already be data-saturated.

The Cardinal Rule of Machine Learning

Never touch your test data. Ever.

If that’s not clear enough:

Never ever touch your test data!

Evolutionary algorithms-specific debugging steps

Visualise the population

Print out or plot some individuals from the population at different generations. Check if they diversify over time or if they converge too early.

If individuals look too similar early on, your mutation or crossover might not be working correctly.

Track fitness over time

Plot fitness over generations to see if the population is improving. If fitness plateaus too early, you may have:

  • premature convergence;
  • poor mutation/crossover rates;
  • a bad fitness function.

Check mutation & crossover operators

Print out before/after snapshots of mutation and crossover operations and ensure that children resemble parents but still introduce meaningful diversity.

If offspring are identical to parents, mutation may be too weak. If offspring are nonsensical or too random, mutation/crossover may be too strong.

Watch for premature convergence

Monitor diversity in the population. If all individuals become identical early, you may need:

  • higher mutation rates;
  • stronger selection pressure adjustments (e.g. tournament size, elitism, fitness sharing);
  • diversity-preserving techniques like crowding, speciation, or novelty search.

Hand-test the fitness function

Manually evaluate a few individuals to check if the fitness score makes sense. If the best solutions aren't making progress, the fitness function might be:

  • rewarding the wrong behaviour;
  • too noisy or sparse.

Use a minimal reproducible example

Start with the simplest possible problem where you know the optimal solution (e.g. evolving $\(y = x^2\)$).

Ensure your GA/GP can solve it before tackling harder problems. If it fails on simple cases, debug before scaling up.

Verify Selection Pressure

Print out the fitness values of selected individuals. If selection always picks the same individuals, you may need:

  • lower elitism;
  • more diversity in selection (e.g. roulette wheel vs. tournament selection).

Overfit Deliberately

Try overfitting by making your model too powerful (e.g. increasing population size, mutation rate, or function set complexity).

If it still fails, your representation or fitness function is likely flawed.

Check for bloat in genetic programming

In GP, solutions tend to grow excessively (code "bloat"). If trees/programs get huge without improving fitness:

  • use parsimony pressure (penalise large solutions);
  • implement lexicographic selection (prefer simpler solutions with similar fitness);
  • try node deletion mutations to reduce size.

Compare against a baseline

Implement a random search or hill climber and compare its performance. If your GA doesn't outperform a simpler approach, something is likely wrong.

Debugging evolutionary algorithms (EAs) in C++

Code doesn't work - code works

This can be even more challenging due to memory management, performance concerns, and the complexity of tracking population changes.

Enable AddressSanitizer & Valgrind (memory debugging)

Evolutionary algorithms heavily use dynamic memory (vectors, trees, graphs...), making them prone to memory leaks, dangling pointers, and buffer overflows.

Use AddressSanitizer when compiling with GCC or Clang:

clang++ -g -fsanitize=address -o my_ea my_ea.cc
./my_ea

Use Valgrind to check for memory issues:

valgrind --leak-check=full ./my_ea

If using Eigen or STL containers, double-check out-of-bounds access in selection, crossover, or mutation.

Log key evolutionary events (without slowing performance)

Printing population states at every generation is useful but slows down execution. Instead, use conditional logging:

#if !defined(NDEBUG)
std::cout << "Generation " << gen << " | best fitness: " << best_fitness << '\n';
#endif

Write logs to a file for post-run analysis:

std::ofstream log_file("evolution.log", std::ios::app);

log_file << "Generation " << gen << " | best fitness: " << best_fitness << '\n';

Debug selection, crossover, and mutation

  • Print indices of selected parents to ensure selection isn't biased: if selection always picks the same individuals, lower elitism or adjust tournament size.
  • Check mutation logs. If mutations don't change the individual, check random number generation.

Profile performance (GAs can be slow!)

Use gprof or perf to identify bottlenecks in fitness evaluation or genetic operators:

g++ -pg -o my_ea my_ea.cc
./my_ea
gprof my_ea gmon.out > profile.txt

If fitness evaluation is slow, consider:

  • multithreading (OpenMP, std::thread);
  • lazy evaluations (only re-evaluate modified individuals).

References