7 ms·

The Genetic Algorithm Explained

58 points by GarethX 12y ago

Coding_Cat 12y ago
It's nice to see an article about GA, I've been working on them myself recently, fascinating stuff. However the definition of Tournament Selection[1] is a little bit off. With tournament selection you don't take the fittest "k" individuals but you take a subset of "k" individuals at random and then apply proportionate selection. [1] http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Tournament_selection
- zenogais 12y ago
  An important distinction. A lot of implementation bugs I saw when researching GA/GP were related to this slight misunderstanding.
  - randomsearch 12y ago
    Tournament Selection in Genetic Programming is predominantly: 1. Choose n individuals at random. 2. Return the individual with best fitness in that set. i.e. no proportional selection within that set.
MaastrichtTreat 12y ago
I have always heard that a focused gradient descent outperforms genetic algorithms in every application domain.
- deleted 12y ago
  [deleted]
- jimfleming 12y ago
  I'd love for someone who knows more to chime in but its my understanding that gradient descent does not perform well on non-differentiable functions and only finds local optima. Wikipedia seems to confirm this: http://en.wikipedia.org/wiki/Gradient_descent#Limitations http://en.wikipedia.org/wiki/Gradient_descent#Limitations
  - j2kun 12y ago
    I spoke with an optimization expert from Argonne National Lab and he gave me the same impression, that gradient descent techniques far outperform evolutionary ones. They're more specialized, make it easier to incorporate domain knowledge, and using stochasticity compensates for local optima.
    - irishtier 12y ago
      Technically combining stochasticity with gradient descent is not pure gradient descent. As for the domain knowledge - this is not specific to gradient descent either, genetic algorithms and their problem encoding can be adapted to a domain to minimise the search space considered - therefore improving performance of the algorithm.
      - j2kun 12y ago
        > Technically combining stochasticity with gradient descent is not pure gradient descent. Sounds like you're picking a nit. Stochastic gradient descent is included in "gradient descent techniques."
    - ppj606 12y ago
      Outperform on what? Can you give specific examples? There are a large number of Combinatorial Optimisation Problems. It is a very sweeping statement to say 'gradient descent techniques far outperform evolutionary ones'.
      - j2kun 12y ago
        He said something along the lines of "I have yet to see an application where evolutionary techniques outperform gradient descent approaches." His talk was about parameter optimization for costly experiments (e.g., manufacturing and testing a vehicle), so his emphasis was on optimization that minimizes the number of function applications. But he seemed to be an expert with a lot of experience.
    - randomsearch 12y ago
- SeanLuke 12y ago
  That is absurd. Gradient descent assumes you can compute the gradient of your objective function. For a great many functions you cannot define the gradient: indeed you can't even define the objective function well. Genetic algorithms belong to a family of metaheuristics, algorithms designed to tackle such ill-defined functions where gradient descent is simply impossible to use. My concern with this webpage is that it is a far too simplistic treatment of genetic algorithms, to the point of being misleading, and has quite a number of outright errors. I wouldn't use it.
  - irishtier 12y ago
    Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima. The point of evolutionary algorithms, or any naturally inspired algorithm for that matter, is that it does not tend to converge upon local optima and has the possibility of moving out of this space towards the global optima. The fact that most problems it is applied to are NP-Complete means that it is unlikely it will find the optimal solution in polynomial time.
    - SeanLuke 12y ago
      > Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima Well... just as evolutionary algorithms are essentially elaborate versions of hill-climbing which enable global search, likewise there are many well-established forms of gradient descent which are global searchers as well. I think the key distinguishing feature is that gradient descent makes strong assumptions about the nature of the space being searched; and metaheuristics make much more general assumptions.
      - GordyMD 12y ago
        Good point. This is key, as you say. Meta-heuristics have the flexibility of providing good performance on all Combinatorial Optimisation Problems. But meta-heuristics, can also be given domain knowledge. and/or be combined with a a heuristic. E.g. Ant Colony Optimisation techniques for Travelling Salesman Problems that combines ACO with Local Search.
- tlarkworthy 12y ago
  Yes. Gradient descent with random restarts is the pragmatists first optimizations technique. GA's often don't converge to anything useful and require tons of unsubstantiated unintuiative tuning.
- yid 12y ago
  Your statement contradicts the No Free Lunch theorem because of the word "every".
crazypyro 12y ago
I wrote a toy program that takes a source string and uses a genetic algorithm to transform it into a target string. It only took about an hour and was a fun process. I ended up adding in different types of crossover and trying to figure out which would solve it in the fewest generations on average. Fun stuff. Highly recommend it as a quick project for anyone.
guelo 12y ago
My favorite genetic algorithm implementation, http://boxcar2d.com/ http://boxcar2d.com/
sclangdon 12y ago
For those interested, here is Jori Liesenborgs' thesis, "Genetic algorithms for the non-parametric inversion of gravitational lenses". http://research.edm.uhasselt.be/jori/phd/phdthesis_jori_web.pdf http://research.edm.uhasselt.be/jori/phd/phdthesis_jori_web....
chinpokomon 12y ago
A couple more points. Depending on how diverse the population is, a high mutation rate may not help when selecting the fittest children. There is also a chance that you will find a local maxima, and not the best solution overall. Introducing a concept of multiple "species" to the population will sometimes help finding other solutions outside the local maxima, but then this complicates the crossover phase. If the "genes" are of equal length and therefore closely related species, you may be able to generate some offspring in the crossover phase, but then you are usually introducing another species at that time. Depending on the solution you are trying to find, this may or may not be appropriate.

58 points by GarethX 12y ago

It's nice to see an article about GA, I've been working on them myself recently, fascinating stuff. However the definition of Tournament Selection[1] is a little bit off. With tournament selection you don't take the fittest "k" individuals but you take a subset of "k" individuals at random and then apply proportionate selection. [1] http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Tournament_selection

zenogais 12y ago
An important distinction. A lot of implementation bugs I saw when researching GA/GP were related to this slight misunderstanding.
- randomsearch 12y ago
  Tournament Selection in Genetic Programming is predominantly: 1. Choose n individuals at random. 2. Return the individual with best fitness in that set. i.e. no proportional selection within that set.

MaastrichtTreat 12y ago

I have always heard that a focused gradient descent outperforms genetic algorithms in every application domain.

deleted 12y ago
[deleted]
jimfleming 12y ago
I'd love for someone who knows more to chime in but its my understanding that gradient descent does not perform well on non-differentiable functions and only finds local optima. Wikipedia seems to confirm this: http://en.wikipedia.org/wiki/Gradient_descent#Limitations http://en.wikipedia.org/wiki/Gradient_descent#Limitations
- j2kun 12y ago
  I spoke with an optimization expert from Argonne National Lab and he gave me the same impression, that gradient descent techniques far outperform evolutionary ones. They're more specialized, make it easier to incorporate domain knowledge, and using stochasticity compensates for local optima.
  - irishtier 12y ago
    Technically combining stochasticity with gradient descent is not pure gradient descent. As for the domain knowledge - this is not specific to gradient descent either, genetic algorithms and their problem encoding can be adapted to a domain to minimise the search space considered - therefore improving performance of the algorithm.
    - j2kun 12y ago
      > Technically combining stochasticity with gradient descent is not pure gradient descent. Sounds like you're picking a nit. Stochastic gradient descent is included in "gradient descent techniques."
  - ppj606 12y ago
    Outperform on what? Can you give specific examples? There are a large number of Combinatorial Optimisation Problems. It is a very sweeping statement to say 'gradient descent techniques far outperform evolutionary ones'.
    - j2kun 12y ago
      He said something along the lines of "I have yet to see an application where evolutionary techniques outperform gradient descent approaches." His talk was about parameter optimization for costly experiments (e.g., manufacturing and testing a vehicle), so his emphasis was on optimization that minimizes the number of function applications. But he seemed to be an expert with a lot of experience.
  - randomsearch 12y ago
SeanLuke 12y ago
That is absurd. Gradient descent assumes you can compute the gradient of your objective function. For a great many functions you cannot define the gradient: indeed you can't even define the objective function well. Genetic algorithms belong to a family of metaheuristics, algorithms designed to tackle such ill-defined functions where gradient descent is simply impossible to use. My concern with this webpage is that it is a far too simplistic treatment of genetic algorithms, to the point of being misleading, and has quite a number of outright errors. I wouldn't use it.
- irishtier 12y ago
  Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima. The point of evolutionary algorithms, or any naturally inspired algorithm for that matter, is that it does not tend to converge upon local optima and has the possibility of moving out of this space towards the global optima. The fact that most problems it is applied to are NP-Complete means that it is unlikely it will find the optimal solution in polynomial time.
  - SeanLuke 12y ago
    > Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima Well... just as evolutionary algorithms are essentially elaborate versions of hill-climbing which enable global search, likewise there are many well-established forms of gradient descent which are global searchers as well. I think the key distinguishing feature is that gradient descent makes strong assumptions about the nature of the space being searched; and metaheuristics make much more general assumptions.
    - GordyMD 12y ago
      Good point. This is key, as you say. Meta-heuristics have the flexibility of providing good performance on all Combinatorial Optimisation Problems. But meta-heuristics, can also be given domain knowledge. and/or be combined with a a heuristic. E.g. Ant Colony Optimisation techniques for Travelling Salesman Problems that combines ACO with Local Search.
tlarkworthy 12y ago
Yes. Gradient descent with random restarts is the pragmatists first optimizations technique. GA's often don't converge to anything useful and require tons of unsubstantiated unintuiative tuning.
yid 12y ago
Your statement contradicts the No Free Lunch theorem because of the word "every".

crazypyro 12y ago

I wrote a toy program that takes a source string and uses a genetic algorithm to transform it into a target string. It only took about an hour and was a fun process. I ended up adding in different types of crossover and trying to figure out which would solve it in the fewest generations on average. Fun stuff. Highly recommend it as a quick project for anyone.

guelo 12y ago

My favorite genetic algorithm implementation, http://boxcar2d.com/ http://boxcar2d.com/

sclangdon 12y ago

For those interested, here is Jori Liesenborgs' thesis, "Genetic algorithms for the non-parametric inversion of gravitational lenses". http://research.edm.uhasselt.be/jori/phd/phdthesis_jori_web.pdf http://research.edm.uhasselt.be/jori/phd/phdthesis_jori_web....

chinpokomon 12y ago

A couple more points. Depending on how diverse the population is, a high mutation rate may not help when selecting the fittest children. There is also a chance that you will find a local maxima, and not the best solution overall. Introducing a concept of multiple "species" to the population will sometimes help finding other solutions outside the local maxima, but then this complicates the crossover phase. If the "genes" are of equal length and therefore closely related species, you may be able to generate some offspring in the crossover phase, but then you are usually introducing another species at that time. Depending on the solution you are trying to find, this may or may not be appropriate.