What happened to genetic algorithms?

Eight years ago in March of 2017, evolutionary algorithms seemed on track to become the AI paradigm, before being supplanted by the LLMs that we all know and love (tolerate?). OpenAI proposed that evolutionary strategies could replace–or at least supplement–reinforcement learning: they are simple to implement and scale well. Since these optimizers are population-based, they’re parallelizable and make minimal assumptions. Three months later, however, Google released “Attention is All You Need” and the transformer was born. It took OpenAI roughly a year to then develop GPT1 (and we know the rest).

For those unfamiliar, genetic algorithms fall within a category of optimization procedures called metaheuristics. Acting analogously to evolution, they simulate populations of candidate solutions, select and retain the best, and modify the survivors for the next generation. By design, these algorithms lack closed-form solutions and strong guarantees. That’s their whole gimmick, and it’s a double-edged sword. They can solve black-box problems with practically no assumptions, but guarantees for finding optimal solutions are limited, and convergence speeds are slow and only known in specific contexts. 

Also, the true umbrella term is not actually genetic algorithms but “evolutionary computation” (EC), comprising four historically distinct subfields (though the schools have blended together in recent years):

  1. Genetic algorithms (the most commonly known), 
  2. Evolutionary strategies,
  3. Evolutionary programming, and
  4. Genetic programming. 

Given this is an applied statistics blog, what’s the relevance? It turns out that model selection (or as ML practitioners call it, hyperparameter tuning), can be framed as an optimization problem. Instead of doing grid search, LASSO, or old-fashioned forward selection, we can also search the space of models using evolutionary algorithms. In difficult-to-traverse, discrete model spaces, that could mean the difference between success and no attempt at all. 

What about beyond model selection? From the perspective of expanding models continuously, any unmodeled selection event (even if done with clever metaheuristics) still artificially shrinks posterior intervals and inflates confidence. Not an issue since evolutionary algorithms can also be used for general model estimation! That opens the door to optimizing model parameters over complicated non-differentiable geometries. Technically, we could even try EC instead of OLS for linear models (although I don’t know why we would want to).

So why is it that they have fallen in disfavor? Are they in disfavor?

Thomas Bäck, a prominent researcher in EC, (and collaborators) reviewed the last thirty years of developments. They claim the main issues that have prevented adoption are:

  1. A “bestiary” of nature-inspired algorithms lacking fundamental grounding has made the field incohesive, and practitioners confused
  2. There is no unifying paradigm for designing algorithms, and benchmarks only apply to specific problems, making specific implementations idiosyncratic and hard to evaluate

On the other hand, we shouldn’t undersell developments like CMA-ES (covariance matrix adaptation evolutionary strategy–a bit of a mouthful). In simple terms, you adapt a shared covariance matrix to shape, scale, and correlate your Gaussian perturbations based on current best candidates and past generations. This shared strategy is in contrast to previous algorithms where each individual updated its own parameters. It represents the current state of the art, ranks highly on numerical benchmarks, and has had success in combustion feedback control, multi-cellular migration, and ultrasound imaging. But then again, the core algorithm hasn’t changed in the thirty years since its inception, at least according to Bäck.

So, there may be a more fundamental issue, for which we can speculate. Evolving things takes lots of computation, and when I say lots, I truly mean lots.

A paper by Yampolskiy called “Why We Do Not Evolve Software” has made a compelling case for why evolutionary algorithms aren’t a cure all. The following are incredibly rough estimates and make various assumptions about total global biomass, cell replication rates, and what constitutes biological computation, but essentially: the biosphere that evolved us can compute ~10^40+ FLOPS (floating point operations) per second. It also took that biosphere billions of years to evolve us. All our supercomputers on Earth combined can only compute ~10^22 FLOPS per second. This would seem to imply that the cleverness of an efficient genetic search has to cut through ten to thirty orders of magnitude! That’s a hefty requirement. Not impossible, but probably impractical in many cases.

What does this mean about the future of genetic algorithms? It seems that solutions will somehow need to bypass the combinatorial explosion of the solution space, since getting the compute required without that would take hundreds of years, even with an ever-constant Moore’s law. One direction may be to continue exploring the interplay between local and global solutions (like in CMA-ES and particle swarm optimization). The most concrete step forward would be improving benchmarks and validation. Maybe a unifying paradigm for automatically designing evolutionary algorithms could then develop, similar to what we have in probabilistic modeling.