I'm not an expert but I believe the use case is if you're in an environment where you have no gradient to learn from, or even, without the hope of approximating a gradient to learn from.

I think genetic fuzzy trees are being considered for unmanned aerial combat.

I believe genetic algorithms would find its uses in optimisation of emergence behaviour - in biological analogy, if NN is akin to evolving a brain, then GA would be like evolving a colony / society.

It's not dead, but gradient-based optimization is more popular right now because it works so well for neural networks.

But you can't always use gradient descent. Backprop requires access to the inner workings of the function, and requires that it be smoothly differentiable. Even if you can use it, it may not find a good solution if your loss landscape has a lot of bad local minima.

Evolution is widely used in combinatorial optimization problems, where you're trying to determine the best order of a fixed number of elements.

>But you can't always use gradient descent. Backprop requires access to the inner workings of the function

Backprop and gradient descent are not the same thing. When you don't have access to the inner workings of the function, you can still use stochastic approximation methods for getting gradient estimates, e.g. SPSA. In fact, there are close ties between genetic algorithms and stochastic gradient estimation.

Not genetic, but you might find cool this paper https://arxiv.org/abs/2302.06675 Program search inspired by evolution

Is this type of math optimization?

For me an always interesting and alluring idea was to use GA to search for a combination of elementary information processing stuff (probably Boolean gates) and memory which would result in some novel ML architecture. Maybe much more effective than NN as it would be possible to directly implement via electronics without the overhead.

Oh brings back a lot of memories. I remember using it in the early 2000s to optimize neural networks. Back when only Matlab was there and we couldn't afford it and had to build NN from scratch.... using Visual Basic 😢

Back to your question, I don't think they're dead. Probably their use in NN is. Edit:spelling

No. See this recent pub in Nature.

This is really interesting. Do you know of any approaches similar to this for learning hyperparameters layer structure, or complications such as inception networks or resnet?

I've never directly worked with either, but isn't RL agent-competitions approaches (i.e. simulating games between agents with different parameter values and iterating on this agents) a form of genetic algorithms?

It's also worth noting that this is exactly the type of problem that genetic algorithms were made for: no gradients, highly multimodal.

I use GA optimization for non-convex problems, mainly hyperparameter optimization. Sometimes it’s very effective but I’ve not found a way to know ahead of time if it will outperform other algorithms.

I think genetic algorithms may have a new role to play in problems involving inference / text generation / prompting with language models, even if they aren't used to train the models themselves.

For example, in our recent work on natural-language prompting, we use a genetic algorithm to generate prompts that are semantically coherent -- the genetic algorithm lets us make use of suggestions by a language model, for which gradients would be hard to obtain.

One of my friend use genetic algorithms to do acoustic material research.

The fundamental problem with evolutionary strategies is that they are a freakin nightmare to evaluate. It's basically impossible to reason about their mathematical properties, experiments are noisy as hell, and how representative are the benchmark objective functions anyway? It's just really hard to do good science with those, which means it's hard to make concrete improvement. Sure, once upon a time they were the only choice for noisy, gradient free global optimization problems. But now we have Bayesian optimization.

I still see papers written on them occasionally. I have always wanted to implement one, but I've never had a use case. I think there are certain categories of problems where they excel, but in the real world, most of the time, there seems to be a better approach.

One real-world use case I saw was using genetic algorithms to design an automobile brake rotor to reduce heat (or increase heat dissipation). From what I remember of the presentation... Basically, they had a very large number of mathematical definable designs with many input variables. The interactions between these different variables were not necessarily clear. Elements of one of these designs might combine well with elements from a totally separate design. And the model to test them was computationally expensive.

They were able to use this genetic algorithm to design a rotor that, at least on the computer, was meaningfully better than their companies (and likely the industry's) state of the art.

GAs are not great for expensive-to-evaluate functions. And those have become kind of relevant lately.

My fave has always been the radio antenna designed by a GA

Evolved antenna

>In radio communications, an evolved antenna is an antenna designed fully or substantially by an automatic computer design program that uses an evolutionary algorithm that mimics Darwinian evolution. This procedure has been used in recent years to design a few antennas for mission-critical applications involving stringent, conflicting, or unusual design requirements, such as unusual radiation patterns, for which none of the many existing antenna types are adequate.

^([ )^(F.A.Q)^( | )^(Opt Out)^( | )^(Opt Out Of Subreddit)^( | )^(GitHub)^( ] Downvote to remove | v1.5)

Genetic algorithms require you to create a population where the genetic operators are applied (mutation, crossover and selection).

Creating a population of neural networks implies having multiple slightly different copies of the neural network to be optimized (i.e.: the population).

This can be more computationally expensive than other techniques which will do all the learning "in-place".

[deleted]

I recently used a genetic algorithm in a supply chain application. Not the fastest algo but we made it work for our purpose

Have you seen this paper?

Evolution through Large Models

https://arxiv.org/abs/2206.08896

You don't always need a population of neural networks, it could be a population of prompts or even a population of problem solutions.

If you're using GA to solve specific coding problems, then there is one paper where they use LLM to generate diffs for code. The LLM was the mutation operator, and they even fine-tune it iteratively.

Genetic optimization might be dead in most cases. I think a lot of the ideas aside from optimization algorithms are still relevant.

I've found GP techniques can yield parsimonious models. A lot of the big research these days is on big models, but GP seems good for small, parsimonious, and elegant models. Good for low data regimes, specialized problems, and problems where you have expert knowledge you can encode. Generally speaking I like working with GP becuase you end up with a parsimonious and interpretable model (opposite of a lot of NN research).

In practice I've found importance sampling methods to work about as good as genetic optimization for optimizing GP trees/grammars for the small amount of work I did with them. I haven't found either method to edge out by much, but it could depend on the problem.

I don't know if this is considered GP (or GA) without a genetic optimization method. However I think we can say that the notion of optimizing a symbolic tree or grammar was heavily developed within GP, even if today you may use some monte carlo optimization method in practice.

Plus also there needs to be a learnable, nontrivial 'strategy' to take advantage of, otherwise it's not going to beat simulated annealing except on speed. The couple of times I've used it in practice, SA was about as good as we could get performance-wise.

The notable diffrence between GA and other random searches is cross-over operator, and in it's theory "building blocks" hypothesis. Neither were confirmed during years (dozens of years) of attemted use of GA.

I think, my professor summarized it very well: "Genetic algorithms is what you do when everything else fails."

What he meant by that is, that they are very inefficient optimizers. You need to evaluate lots and lots of configurations because you are stepping around more of less blindly in the parameter space and you are only relying on luck and a few heuristics to improve your fitness. But their advantage is that they will always work as long as you can define some sort of fitness function.

If you can get a gradient, you are immediately more efficient because you already know in which direction you need to step to get a better solution.

But of course there is room for all algorithms. Even when you can do gradient descent, there are problems where it quickly gets stuck in a local optimum. There are approaches how to "restart" the algorithm to find a better local optimum. I'm not that familiar with that kind of optimization but it is not inconceivable that genetic algorithms might have a role to play in such a scenario.

[deleted]

[removed]

Hyperparam optimization?

Genetic algorithms are still useful for strange objective functions that defy analytical approaches, such as anything based on complex simulations. But it somehow has always been this way.

Nowadays things have changed by generative models for code generation. A few years ago Genetic Programming (and it's many variants) was the only approach to do this, now some problem can just be solved by asking a language model to write the code for xyz.

Yes, there is a whole field https://arxiv.org/abs/2008.10937

This is actually a very cool approach, if more narrow in application. Other domains that have these linear representations like the Morgan fingerprint might also benefit.

It wasn't as bad as it sounds. The fun part was that you had to understand how every little piece of the algorithm works, and the nightmare was implementing all of this with 512mb of RAM. We didn't have the luxury of trying different solutions.

Genetic algorithms are good, as you said, when you really understand the space and can come up with a really good candidate generation system. They’re okayish (or, the same as everything else) when you have no understanding of the space at all, and you’re just totally guessing. They can’t latch onto a curve in design space as well as things that look at a simpler gradient can. So maybe they’re best used for really complex spaces where gradient based methods don’t do well. The kind of places you’d use Gibbs sampling, or general optimization algorithms.

So, basically, they’re useful when you have good feature engineering already done, like many methods that have fallen out of vogue in the age of letting algorithms and data do your feature engineering for you. And they’re as good a shot in the dark as any when standard methods fail and you’ve got no clue how to proceed.

So, yeah, the number of times genetic algorithms are the “right” choice is pretty limited these days.

Don't Bayesian approaches generally work better in gradient-free optimization?

This is a reasonable question but I believe you are misunderstanding. The randomization of parameters in a neural network (I assume you are talking about initialization?) is certainly not the same as a mutation in a GA. Mutation occurs randomly, sure, but is selected for and crossed over, whereas hill-climbing and gradient descent simply move on the gradient and do not use either random mutations or cross-over so are not genetic.

Can you give a few examples of how genetic algorithms and stochastic gradient estimation are related?

It turned out that other models have superior genes.

We recently published an evolutionary method to sample from the latent space of a variational autoencoder. It is still alive and well. Just a bit niche.

[removed]

In one of our recent work https://arxiv.org/abs/2012.14956, we used Genetic Algorithm to attack NLP models in a hard label black box setting, where we do not have access to the confidence scores of the model.

You can say they have gone extinct in the ecosystem of completion from superior approaches 😂

I don't think they are dead. Their popularity for NNs is much lower for sure.

In general, GAs can theoretically solve any problem (if you can formulate a fitness function), given long enough time. Because of that, I think they will always have some use cases.

Yeah it's used for automatic hyperparameter tuning.

Better than a grid or just intuition.

Exactly due to the computational demands I don't think genetic algorithms have ever really been "alive", but with compute getting cheaper I could see it seeing success similar to the rise of Deep Learning.

Evolution Strategies as stabilizers without the genetic component are already being deployed quite well e.g. AlphaStar.

Jeff Clune was quite active in that area of research and he recently joined DeepMind.

https://twitter.com/jeffclune/status/1629132544255070209

Sorry to be that person, but that's not Nature, that's Scientific Reports, which is a tier 3 journal in the Nature portfolio. If Nature would be compared to a top conference, Scientific reports would be less than a workshop paper.

No, good on you for being that person. I just looked at the prefix of the URL. Thx!

They are certainly still used for RL (and other cases where you don’t have a gradient), but even in those contexts there have been modern advancements that cause the preferred algorithms to diverge from old-school genetic algorithms. For instance, things like Particle Swarm Optimization and the Cross Entropy Method have their conceptual origins in the similar sampling regimes as MCMC approaches, but they’ve become their own entities at this point, outperforming genetic algorithms, and really being unique and broad enough to get their own categories.

I think they're still useful for "no information at all" scenarios where attempting a solution is just too time consuming or not possible using other methods (e.g. traveling salesman problem).

As a practical matter, I think they're best integrated with other methods as "first cut" solutions that get you closer to something you can work out with a neural net or rule based system.

That said, I'm unaware of any NN or rule based solution better than a GA for solving the traveling salesman problem even now. So, maybe some P-NP problems will always be best attacked with GAs.

It sounds very interesting. Is it available to read? Thanks

[deleted]

They might see a resurgence in dynamic multi-agent environments.

Not necessarily. Bayesian methods work great when you have expensive objective function evaluations that can only be evaluated in serial (or limited parallel evaluations). Bayesian methods aren't ideal in massively parallelizable evaluations (evaluating >100 points at a time) or when evaluations are relatively cheap. It depends on the cost of optimizing the acquisition function. I've actually played around with combining BO with evolutionary algorithms to extend BO towards massively parallelizable evaluations and have seen some promising results.

I think there are few problems were a couple extra assumptions that could make much more efficient methods work (not NNs necessarily of course) don't hold. I'm not sure there exist problems where genetic algos outperform other methods, disregarding problems where only genetic algos work.

It was. Dumb too. Because of the limitations of memory and computing power at the time you had to constantly tweak parameters to optimize learning speed, avoid overfitting, avoid local optimums, etc. Only to find that the best performing model was the one generated by your 2 AM code with the fundamental flaw and the random parameters you chose while high.

I use CMA-ES (a type of evolutionary algorithm) for training neural networks for finance stuff. The neural networks involved are not superhuge so it works out (IIRC the number of parameters is around ~500-1000).

The fitness function is pretty complicated and written in Rust and I put a lot of effort to making it fast because these algorithms need to evaluate it many many times. I feel using evolutionary algorithms makes coding simpler because you do not need to care that whatever you are writing is differentiable or that some backprop/gradient descent library needs to be able to "see" inside your function.

I do think my use case is a bit more niche. I live in hope that some breakthrough happened that made evolutionary algorithms practically usable for large neural networks.

[deleted]

Who says genetic algorithms are dead? They're pretty much dead for training neural nets absolutely, but there are tons of other more general optimization problems that GAs (or more generally evolutionary algorithms) are well suited for.

Not to mention they still have plenty of utility as a search algorithm for hyperparameters so they aren't even dead for neural applications.

This comment make me wonder if the same rules about using one-hot encoding instead of ordinal encoding for classifiers still apply to a neural net trained with a gradient-less search algorithm like a GA instead of backprop.

Appears to be here: https://openreview.net/forum?id=ibNr25jJrf

edit: actually after reading it, I don't think this is the referenced publication, but it's still interesting

I can't disagree.

Fun story! How you have chosen hyper-parameters for models? Have you turn them over in for-loops?

Mostly. Other times I would interrupt the code when it wasn't converging and start over after changing a parameter or two. I feel si spoiled with Tensorflow now!

The trick with genetic algorithms is you have to tune your approach very specifically to the kinds of things you're modelling. Different animals mate and evolve differently, in the analogical view.

It's not enough to just do the textbook "1D chromosome" approach. You have to design your "chromosome", as well as your "crossover" and "mutation" operators specifically to your problem. In my experience, the crossover implementation is the most important one to focus on.

Aren't people working on ways to implement NN in hardware?

My thoughts too. Simulated annealing and similar strategies seem to intuitively be better is most cases where traditional gradient methods aren't applicable. I can imagine a handful of cases where genetic algorithms MIGHT be better, but even then I am not fully convinced and it just feels gimmicky.

Cool idea, thanks for sharing!

Seems like those algorithms sunk in a global minimum

> isn't RL agent-competitions approaches (i.e. simulating games between agents with different parameter values and iterating on this agents) a form of genetic algorithms?

Hmm, I hadn't thought about RL like that. I guess the signal from a reward function based on competition could be considered "fitness", and then perhaps some form of cross-over is done in the way we iterate on and update the agents. Interesting thought.

Absolutely, lots of great work is being done in this domain right as we speak. Neuromorphic computing and analog computing I personally think are some of the most exciting things to look out for in the next 10 or so years.

Agreed. That being said, I think the prior is that you still need to have enough understanding of the state space to be able to design good mutations, cross-over, and fitness. This can easily add a lot of overhead. In contrast, I think that other cool methods like swarm optimization and ant colony optimization are also promising and in some ways simpler.

Cool! I'd never heard of the building block hypothesis before, thanks for sharing.

> In my experience, the crossover implementation is the most important one to focus on

I've heard this as well

Hmm. Hadn't thought of that, but that's probably true. I'm less familiar with the mechanics of these but I bet they'll be similarly good for low or no-information scenarios or P-NP problems.

Interesting, thanks for sharing your thoughts! I'm a bit curious about why genetic algorithms might be better for these strange objective functions, as compared to something like simulated annealing. I can understand that a pure gradient method could easily be insufficient, but do the underlying components of genetic algorithms (like cross-over, etc.) really provide a distinct advantage here? Especially when the fitness is probably directly related to the gradient anyways

I think GA is still fairly popular in operations management to e.g. produce solutions for delivery scheduling problems.

Our lab made a python package that combines simulated annealing and genetic algorithms for helping to solve really gnarly inverse problems in chemistry modeling. The package is on GH, and here is the link to the paper where it was primarily used.

I love it! Great to see these kind of applications

Thanks

[removed]

Hey, this is it actually! We are optimizing a discrete variational autoencoder with no gumbel-softmax trick.

Of course we require no encoding model, so the notion of a latent space only holds up until closer inspection.

The latest version is here: https://2022.ecmlpkdd.org/wp-content/uploads/2022/09/sub_1229.pdf

Thanks

I was kinda excited, I had hoped to find an evolutionary algorithm to find things in a latent space, I've been having a hell of a time trying to optimize text encodings for diffusion models.

https://www.nature.com/articles/s41467-021-26568-2

Try this article

No way. They're still one of the best bets out there for high-dimensional discrete optimization.

You just need a notion of a fitness function and then you can apply permutations to the tokens.

Cheers

In my experience, if you are "stepping around more or less blindly" then the problem & EA have not been properly formulated. In general of course, if a gradient is available then gradient descent will do a better job >99% of the time.

Though with a bit of domain knowledge, and/or some careful design of the objective function(s), variation operators etc., an EA can be a pretty efficient explorer of the space. It's nichely-applicable, but when done properly it's far from blind.

I think the best approach for this is thinking about the search space and the fitness landscape. If different components of the solution vector can independently improve the fitness crossover operators will have a positive impact.

Another aspect is the search space itself. Is it real-valued, is it binary, is it a tree-like structure,..?

Traditionally genetic algorithms are operating on binary encodings, and they often work ok problem which have binary solutions (a fixed-size vector of bits). These problem do not have gradient to start with. However one should investigate beforehand if there are combinatorial approaches to solve the problem.

For real-valued problems with no gradient: evolution strategies with a smart mutation operation like CMA (covariance matrix adaption) would be a good choice.

I'm not sure whether you mean genetic algorithms or evolutionary algorithms or if those terms are interchangeable for you (often, they are not). Anyway, a field that heavily relies on them is Quality-Diversity (https://quality-diversity.github.io/, there is a nice list of papers there). Also, I would recommend that you have a look at the proceedings from the GECCO conference (e.g. https://dl.acm.org/doi/proceedings/10.1145/3512290 , the conference is much smaller than neurips/ICML/etc, and the research quality tends to be a bit more variable, but you'll see that evo algortihms, and in particular genetic ones are far from being dead).

The idea that "designing an experiment for a genetic algorithm requires sufficient prior" doesn't sound correct to me, generally you turn to them when you don't have any reliable priors on the search space (as other comments have pointed out, see CMA-ES as an example. I'll add ES https://arxiv.org/abs/1703.03864 as another useful example that I've personally often used to simplify meta-learning problems).

Metaheuristic algorithms like GA and simulated annealing are almost identical to Bayesian methods/MCMC. Metaheuristic algorithms are Bayesian methods if you can pretend that your objective function is proportional to a probability distribution that you want to maximize. They just take unique approaches to exploring the posterior distribution. But conceptually they’re identical