6 ms·

Out of curiosity, does anyone know of examples where genetic algorithms are the "right choice"? I thought they were really nifty when I first heard of them, bu

Out of curiosity, does anyone know of examples where genetic algorithms are the "right choice"? I thought they were really nifty when I first heard of them, but thinking of them as an optimization procedure, they don't really stand up in my experience to basic gradient descent methods. Sure, you can e.g. train a neural network with genetic algorithms, but why would you? I'd love to be proven wrong though :)

jacques_chester 7y ago
American Fuzzy Loop[0] uses GAs to concentrate its fuzzing. But in general the "No Free Lunch Theorem"[1] shows that no optimisation algorithm is "better" than any other across the universe of all possible problems. So it's going to be some balance of your familiarity with GAs, having a problem domain that maps nicely to some simple input structure but which has a relatively gnarly surface to search and whether you could do it better in some other way. These days the clear winner is various kinds of neural nets, largely because they can be represented with matrix multiplication, which made them suitable first for GPUs and now for much more specialised hardware. I've had them in mind for searching autoscaler parameters, mostly because I feel it's easier to reason about a GA's optimisations than a series of matrix multiplications resulting in a cloud of floating point numbers. [0] http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/ [1] https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem
astazangasta 7y ago
I was thinking about this the other day when trying to imagine a way to produce texture shaders through some kind of optimization. The connections between various nodes in a shader might be modeled as mutations, since they can't easily be modeled as continuous values.
blarg1 7y ago
For a uni assignment we had to do a project that organised a bunch of people into 4-5 person groups based on * gender (try to get mixed gender groups and atleast have two of each gender in a group e.g. no 1 female + 4 males) * skill types and skill level (so correct combination of skills and skill levels) * bunch of other rules and stats At first I brute forced it, but didn't work very well, then with a few tweaks I used a simulated annealing algorithm which worked perfectly. I believe genetic algorithms can solve the same problems like that though.
dbcurtis 7y ago
I once saw an antenna design produced by GA that was very interesting. Met all the performance parameters in a very compact and easy to fabricate design. Extremely counter-intuitive design -- it looked like a mangled paper clip -- but it worked in simulation and in real life. People have also had good results using GA to optimize Yagi-Uda arrays. In that case, it is very easy to map design parameters onto a "gene vector" in a way that is well-understood and such that it yields an understandable result. But that is really just a search problem, so maybe other algorithms would do as well.
- bufferoverflow 7y ago
  It even has its own Wikipedia article https://en.wikipedia.org/wiki/Evolved_antenna https://en.wikipedia.org/wiki/Evolved_antenna
jrumbut 7y ago
Well one area where genetic algorithms are better than basic gradient descent is, naturally, nondifferentiable functions. But that is facile. I think the realistic strength is that there are some easy to use libraries that don't require the user to really know anything about optimisation or work too hard and can deal with very difficult optimization scenarios (and sometimes even deal with them well). Plus they're neat-o. That's gotta count for something. You ever try the island variant?
- geezerjay 7y ago
  > Well one area where genetic algorithms are better than basic gradient descent is, naturally, nondifferentiable functions. But that is facile. That's a poor assertion because even if detivative-free algorithms weren't already a thing, there are a myriad of smoothing techniques that enable nondifferentiable objective functions to be approximated by differentiable functions. > I think the realistic strength is that there are some easy to use libraries that don't require the user to really know anything about optimisation or work too hard and can deal with very difficult optimization scenarios (and sometimes even deal with them well). That's also not a reasonable assertion because there are also plenty software libraries for continuous and discrete optimization that are easy to use. GAs in general are explored in academia because they are a fad that's easily publishable. Other than that this class of methods is in general very computationally expensive and very inefficient, and don't provide any advantage over plain old adaptive sampling, or even dumb regular lattice sampling.
  - jmmcd 7y ago
    > GAs in general are explored in academia because they are a fad that's easily publishable. I would say 90% of GA papers are because of this. > Other than that this class of methods is in general very computationally expensive and very inefficient, and don't provide any advantage over plain old adaptive sampling, or even dumb regular lattice sampling. Definitely false. The vast majority of OR-type papers in good journals include comparison to weak baselines like those, and wouldn't be published (in those venues) if they didn't win.
horyzen 7y ago
Genetic algorithms works well when 0) there is not enough data for you to train a NN, and 1) you have a really huge solution space for the problem that you cannot brutal force, and 2) you can encode each solution into a simple ``string'' (chromosome), and 3) the problem you're trying to solve is not very time critical (GA can take seconds to minutes depending on your problem) Also, GA can actually utilize many CPU or even GPU cores to solve the problem much faster.
- richk449 7y ago
  > the problem you're trying to solve is not very time critical (GA can take seconds to minutes depending on your problem) Ha. Days or weeks is typical for complex problems.
  - horyzen 7y ago
    In the specific area I worked on, minutes are borderline tolerable so I didn't think twice before posting. But now that you said it, I totally see how it can go on for days.
    - richk449 7y ago
      Interesting. What is the application that need ga and can’t tolerate minutes of evaluation?
      - horyzen 7y ago
        Let's just say the "customers" are impatient for a good enough solution that is part of a iterative workflow :)
  - GordonS 7y ago
    Yep, I recently worked on an engineering project, where GAs were used to evolve new designs for large steel structures, with the aim of reducing weight (and, ergo, cost). There were a lot of constraints, and several applications were used at different points (e.g. specialised 3D CAD) - a single generation took around 1 hour, so we had to let it run for days at a time on a cluster to be useful.
dahart 7y ago
GA can be nice when you’re exploring a high dimensional space, and not optimizing. GA might be better than gradient descent when you can’t compute a gradient because the function you’re optimizing isn’t differentiable. GA is useful for interactive evolution, when the fitness function is a human.
- raverbashing 7y ago
  Good answers. I'd complement the "can't compute a gradient" also with the "gradient won't help you" cases (lots of local maxima/minima )
chrxr 7y ago
I wrote a GA for picking an optimal Fantasy Football (soccer, Brit here) team based on player scores from the previous season(1). The team did above average, even though it was hobbled by the fact that I didn't do any transfers after the initial pick. The knapsack problem(2), of which fantasy team picking is an example, is a classic use case for genetic algorithms. 1) https://github.com/chrxr/ga-prem-team/blob/master/scripts/ga_script.py https://github.com/chrxr/ga-prem-team/blob/master/scripts/ga... 2) https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem
- stevekemp 7y ago
  Funnily enough I did a similar thing - I was given a list of players with a "point score" and a "price", and I had to choose the best team I could get. One goal-keeper from a set of N, a couple of forwards, a couple of defenders, etc. The solution my program "evolved" was the best in the company. https://steve.fi/Software/Football/ https://steve.fi/Software/Football/
- pwbdecker 7y ago
  Wow that's funny I did the exact same thing! I was working at a web/mobile gaming company building a sports draft platform and I was tasked with building a bot player to fill in empty player slots. I used a GA and it worked really well even though I didn't know anything about sports.
salty_biscuits 7y ago
All these meta heuristic type things (simulated annealing, GAs,...) are really just fancy dress on MCMC adapted for mode seeking (usually via importance sampling by scaling). Specifically in this case the evolution bit is a sampler and evaluation function is the log likelihood. Nothing wrong with that, MCMC is awesome. But you need to put in the features of your particular problem if you want good performance. i.e. if your input to cost surface mapping is continuous and you can efficiently calculate a gradient then you would be silly not to use it. Your sampler will be much more efficient.
jvanderbot 7y ago
If you need a GA, you haven't decomposed your problem well enough. Which is to say, if you need a quick example of an optimizer for a high dimensional space and you just want to tinker with a few cost functions, then GA is the right choice.
mightybyte 7y ago
I used a genetic algorithm to evolve the evaluation function that I used to win this programming contest: http://dinsights.com/POTM/LOAPS/finals.php http://dinsights.com/POTM/LOAPS/finals.php The game's scoring system was based on Lines of Action but added an alternative goal which was to win by points. So in order to play this game well a bot had to balance progress towards one of the goals with the need to make sure the opponent didn't get too far ahead in the other goal. My program was the output of a genetic algorithm that learned a remarkably good balance between these two sometimes competing goals. Before I used the genetic algorithm I spent a lot of time hand tuning the evaluation function and actually came up with a quite good result that I was unable to improve on. When I ran the genetic algorithm I was thrilled to discover that the genetic algorithm's output totally crushed my hand tuned output. After my program won the contest with an undefeated 74-0-0 record the author of one of the best Lines of Action computer programs in the world played his program against mine. If the organizer of the programming contest had chosen just a slightly different scoring system that was biased a little more towards the Lines of Action goal, then my program would probably lose against the Lines of Action program. The author played two games of his program against my program. Both games ended with his program thinking it won by Lines of Action rules and my program thinking it won by the tweaked contest rules! This suggests that the organizer of the contest had done a particularly good job of balancing the different goals of the game. (No, this paragraph is about the organizer's game design and has nothing to do with the question of genetic algorithms. I just thought it was an interesting side note.) I really have no idea of whether gradient descent optimization methods would have been better or not. But this was an area where genetic algorithms worked very well.
mostafab 7y ago
yes,they are better than GAN and reinforcement learning for generating new molecules https://medium.com/the-ai-lab/you-didnt-need-deep-learning-to-generate-new-molecules-4c784747b2cc https://medium.com/the-ai-lab/you-didnt-need-deep-learning-t...
Ragib_Zaman 7y ago
You shouldn't view GA as a competitor to gradient descent. Whenever gradient descent applies to a problem, it'll probably be better than GA. But GAs are flexible and applicable to more problems, and can be used in conjunction with other optimisation methods. A few days ago I used GA to perform feature selection (binary encoding with 0 indicating a feature is excluded, 1 if included, fitness function was the accuracy of a NN taking the included features as inputs and trained with gradient descent for x epochs). This made my final network smaller, train faster, etc.

jacques_chester 7y ago

American Fuzzy Loop[0] uses GAs to concentrate its fuzzing. But in general the "No Free Lunch Theorem"[1] shows that no optimisation algorithm is "better" than any other across the universe of all possible problems. So it's going to be some balance of your familiarity with GAs, having a problem domain that maps nicely to some simple input structure but which has a relatively gnarly surface to search and whether you could do it better in some other way. These days the clear winner is various kinds of neural nets, largely because they can be represented with matrix multiplication, which made them suitable first for GPUs and now for much more specialised hardware. I've had them in mind for searching autoscaler parameters, mostly because I feel it's easier to reason about a GA's optimisations than a series of matrix multiplications resulting in a cloud of floating point numbers. [0] http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/ [1] https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem

astazangasta 7y ago

I was thinking about this the other day when trying to imagine a way to produce texture shaders through some kind of optimization. The connections between various nodes in a shader might be modeled as mutations, since they can't easily be modeled as continuous values.

blarg1 7y ago

For a uni assignment we had to do a project that organised a bunch of people into 4-5 person groups based on * gender (try to get mixed gender groups and atleast have two of each gender in a group e.g. no 1 female + 4 males) * skill types and skill level (so correct combination of skills and skill levels) * bunch of other rules and stats At first I brute forced it, but didn't work very well, then with a few tweaks I used a simulated annealing algorithm which worked perfectly. I believe genetic algorithms can solve the same problems like that though.

dbcurtis 7y ago

I once saw an antenna design produced by GA that was very interesting. Met all the performance parameters in a very compact and easy to fabricate design. Extremely counter-intuitive design -- it looked like a mangled paper clip -- but it worked in simulation and in real life. People have also had good results using GA to optimize Yagi-Uda arrays. In that case, it is very easy to map design parameters onto a "gene vector" in a way that is well-understood and such that it yields an understandable result. But that is really just a search problem, so maybe other algorithms would do as well.

bufferoverflow 7y ago
It even has its own Wikipedia article https://en.wikipedia.org/wiki/Evolved_antenna https://en.wikipedia.org/wiki/Evolved_antenna

jrumbut 7y ago

Well one area where genetic algorithms are better than basic gradient descent is, naturally, nondifferentiable functions. But that is facile. I think the realistic strength is that there are some easy to use libraries that don't require the user to really know anything about optimisation or work too hard and can deal with very difficult optimization scenarios (and sometimes even deal with them well). Plus they're neat-o. That's gotta count for something. You ever try the island variant?

geezerjay 7y ago
> Well one area where genetic algorithms are better than basic gradient descent is, naturally, nondifferentiable functions. But that is facile. That's a poor assertion because even if detivative-free algorithms weren't already a thing, there are a myriad of smoothing techniques that enable nondifferentiable objective functions to be approximated by differentiable functions. > I think the realistic strength is that there are some easy to use libraries that don't require the user to really know anything about optimisation or work too hard and can deal with very difficult optimization scenarios (and sometimes even deal with them well). That's also not a reasonable assertion because there are also plenty software libraries for continuous and discrete optimization that are easy to use. GAs in general are explored in academia because they are a fad that's easily publishable. Other than that this class of methods is in general very computationally expensive and very inefficient, and don't provide any advantage over plain old adaptive sampling, or even dumb regular lattice sampling.
- jmmcd 7y ago
  > GAs in general are explored in academia because they are a fad that's easily publishable. I would say 90% of GA papers are because of this. > Other than that this class of methods is in general very computationally expensive and very inefficient, and don't provide any advantage over plain old adaptive sampling, or even dumb regular lattice sampling. Definitely false. The vast majority of OR-type papers in good journals include comparison to weak baselines like those, and wouldn't be published (in those venues) if they didn't win.

horyzen 7y ago

Genetic algorithms works well when 0) there is not enough data for you to train a NN, and 1) you have a really huge solution space for the problem that you cannot brutal force, and 2) you can encode each solution into a simple ``string'' (chromosome), and 3) the problem you're trying to solve is not very time critical (GA can take seconds to minutes depending on your problem) Also, GA can actually utilize many CPU or even GPU cores to solve the problem much faster.

richk449 7y ago
> the problem you're trying to solve is not very time critical (GA can take seconds to minutes depending on your problem) Ha. Days or weeks is typical for complex problems.
- horyzen 7y ago
  In the specific area I worked on, minutes are borderline tolerable so I didn't think twice before posting. But now that you said it, I totally see how it can go on for days.
  - richk449 7y ago
    Interesting. What is the application that need ga and can’t tolerate minutes of evaluation?
    - horyzen 7y ago
      Let's just say the "customers" are impatient for a good enough solution that is part of a iterative workflow :)
- GordonS 7y ago
  Yep, I recently worked on an engineering project, where GAs were used to evolve new designs for large steel structures, with the aim of reducing weight (and, ergo, cost). There were a lot of constraints, and several applications were used at different points (e.g. specialised 3D CAD) - a single generation took around 1 hour, so we had to let it run for days at a time on a cluster to be useful.

dahart 7y ago

GA can be nice when you’re exploring a high dimensional space, and not optimizing. GA might be better than gradient descent when you can’t compute a gradient because the function you’re optimizing isn’t differentiable. GA is useful for interactive evolution, when the fitness function is a human.

raverbashing 7y ago
Good answers. I'd complement the "can't compute a gradient" also with the "gradient won't help you" cases (lots of local maxima/minima )

chrxr 7y ago

I wrote a GA for picking an optimal Fantasy Football (soccer, Brit here) team based on player scores from the previous season(1). The team did above average, even though it was hobbled by the fact that I didn't do any transfers after the initial pick. The knapsack problem(2), of which fantasy team picking is an example, is a classic use case for genetic algorithms. 1) https://github.com/chrxr/ga-prem-team/blob/master/scripts/ga_script.py https://github.com/chrxr/ga-prem-team/blob/master/scripts/ga... 2) https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem

stevekemp 7y ago
Funnily enough I did a similar thing - I was given a list of players with a "point score" and a "price", and I had to choose the best team I could get. One goal-keeper from a set of N, a couple of forwards, a couple of defenders, etc. The solution my program "evolved" was the best in the company. https://steve.fi/Software/Football/ https://steve.fi/Software/Football/
pwbdecker 7y ago
Wow that's funny I did the exact same thing! I was working at a web/mobile gaming company building a sports draft platform and I was tasked with building a bot player to fill in empty player slots. I used a GA and it worked really well even though I didn't know anything about sports.

salty_biscuits 7y ago

All these meta heuristic type things (simulated annealing, GAs,...) are really just fancy dress on MCMC adapted for mode seeking (usually via importance sampling by scaling). Specifically in this case the evolution bit is a sampler and evaluation function is the log likelihood. Nothing wrong with that, MCMC is awesome. But you need to put in the features of your particular problem if you want good performance. i.e. if your input to cost surface mapping is continuous and you can efficiently calculate a gradient then you would be silly not to use it. Your sampler will be much more efficient.

jvanderbot 7y ago

If you need a GA, you haven't decomposed your problem well enough. Which is to say, if you need a quick example of an optimizer for a high dimensional space and you just want to tinker with a few cost functions, then GA is the right choice.

mightybyte 7y ago

I used a genetic algorithm to evolve the evaluation function that I used to win this programming contest: http://dinsights.com/POTM/LOAPS/finals.php http://dinsights.com/POTM/LOAPS/finals.php The game's scoring system was based on Lines of Action but added an alternative goal which was to win by points. So in order to play this game well a bot had to balance progress towards one of the goals with the need to make sure the opponent didn't get too far ahead in the other goal. My program was the output of a genetic algorithm that learned a remarkably good balance between these two sometimes competing goals. Before I used the genetic algorithm I spent a lot of time hand tuning the evaluation function and actually came up with a quite good result that I was unable to improve on. When I ran the genetic algorithm I was thrilled to discover that the genetic algorithm's output totally crushed my hand tuned output. After my program won the contest with an undefeated 74-0-0 record the author of one of the best Lines of Action computer programs in the world played his program against mine. If the organizer of the programming contest had chosen just a slightly different scoring system that was biased a little more towards the Lines of Action goal, then my program would probably lose against the Lines of Action program. The author played two games of his program against my program. Both games ended with his program thinking it won by Lines of Action rules and my program thinking it won by the tweaked contest rules! This suggests that the organizer of the contest had done a particularly good job of balancing the different goals of the game. (No, this paragraph is about the organizer's game design and has nothing to do with the question of genetic algorithms. I just thought it was an interesting side note.) I really have no idea of whether gradient descent optimization methods would have been better or not. But this was an area where genetic algorithms worked very well.

mostafab 7y ago

yes,they are better than GAN and reinforcement learning for generating new molecules https://medium.com/the-ai-lab/you-didnt-need-deep-learning-to-generate-new-molecules-4c784747b2cc https://medium.com/the-ai-lab/you-didnt-need-deep-learning-t...

Ragib_Zaman 7y ago

You shouldn't view GA as a competitor to gradient descent. Whenever gradient descent applies to a problem, it'll probably be better than GA. But GAs are flexible and applicable to more problems, and can be used in conjunction with other optimisation methods. A few days ago I used GA to perform feature selection (binary encoding with 0 indicating a feature is excluded, 1 if included, fitness function was the accuracy of a NN taking the included features as inputs and trained with gradient descent for x epochs). This made my final network smaller, train faster, etc.