8 ms·

I wrote my MSc on improving certain Genetic Algorithms by incorporating biologists' ideas of "exaptation," or having features that were evolved for use in one c

by SamBam 5y ago

I wrote my MSc on improving certain Genetic Algorithms by incorporating biologists' ideas of "exaptation," or having features that were evolved for use in one context providing a jump in another context. For example, it's quite difficult to imagine how wings evolved, since 1% of a wing seems to offer no fitness advantage, and yet you can't evolve 10% of a wing without evolving 1%. One idea from biology is that feathers probably evolved first as thermoregulators (basically good fur for dinosaurs), and small wing flaps may have evolved similarly to keep animals warm, and only once they had evolved large enough could they be used in a "flying squirrel" way to get from tree to tree, and at that point you're in a different fitness landscape and can start evolving for wings proper. It turns out such an idea may be useful for evolving hard-to-evolve neural networks and the like. (Although this was 15 years ago, and genetic algorithms have fallen out of fashion.)

ailef 5y ago
I've always loved genetic algorithms and similar ideas. Unfortunately, as you said, they are not that common now unless maybe in some niche use cases. It's very fun to use them for a weekend project, though.
tomrod 5y ago
> genetic algorithms have fallen out of fashion. I fully anticipate they will come back in fashion. NN were out of fashion for a long time.
- fivea 5y ago
  >>I fully anticipate they will come back in fashion. It's not possible to predict fashions, but I seriously doubt that the whole evolutionary algorithms field will see a resurgence based on anything other than buzzword-driven fads. In general evolutionary algorithms perform terribly poorly in any optimization problem, and at best are effective (but not efficient) in exploring problems involving the arbitrary addition/removal of dimensions/parameters, including high-dimensional discrete optimization problems. Given there are already techniques to convert discrete optimization problems to non-discrete ones and to add/remove arbitrary parameters, and there are already global optimization techniques which are far more efficient and, more importantly, deterministic, genetic algorithms don't really offer any relevant advantage over even brute-force techniques.
  - nicoco 5y ago
    I usually use CMA-ES as a 'very easy to set and up and better than brute force' approach. Am I dumb to do that? (genuine question, no irony, optimization is not my field at all)
    - randomsearch 5y ago
      You are correct about CMA-ES.
  - rusticpenn 5y ago
    I have used swarm optimization methods that have consistently provided better solutions than alternatives for optimizations of solution spaces in alterst 3 different domains. I am not sure what you are talking about.
    - fivea 5y ago
      > I have used swarm optimization methods that have consistently provided better solutions than alternatives for optimizations of solution spaces in alterst 3 different domains. Benchmark your PSO implementation against a) a naive Monte Carlo implementation with an uniform distribution, b) low-discrepancy sequence, c) a global optimization algorithm such as DIRECT, and compare convergence rates. I'd be surprised if your PSO implementation did not competed for the last place in terms of function evaluations.
      - rusticpenn 5y ago
        Unfortunately I don’t currently have access to this data. I can tell you that it’s leagues better than any Monte Carlo implementation as I have done this comparison as a litmus test for several population based algorithms in the past. I I’ll look into making a comparison with DIRECT when I have time (not anytime this month)
  - tomrod 5y ago
    To my understanding, they are coming back in vogue with neural architecture search. But hey, it's newish, so maybe you're one of today's lucky 10,000. https://xkcd.com/1053 https://xkcd.com/1053
- api 5y ago
  IMHO genetic algorithms are waiting for their AlexNet paper: https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6... The approach is clearly valid but I feel like there's some missing pieces in making it work effectively in a digital context. I played around with this stuff a lot in college and my take was that the evolvable encoding problem (a form of representation problem) is fairly major and not really solved. There are also some unsolved issues around evolutionary dynamics and evolutionary game theory, which means how to structure the population and the "game" for best results. Not sure how much progress has been made since then on these, but my impression is not much. The main area where GAs have seen use in the field so far is optimization problems with a lot of parameters related in unknown or hard to model ways or where a closed form solution is unknown or computationally too expensive (NP). These include shipping and air travel routing (traveling salesman with multiple optimization goals like distance + time + fuel + depreciation), circuit board and IC layout, antenna design for exotic RF modulations, drug discovery, materials science, etc. Problems like these are fairly easy to map to a GA, and current GAs are pretty good at finding local maxima in these functions. Still those are a far cry from "design ex nihilo," which is really the promise that evolutionary computation carries. Those applications are using GAs as a bigger brother to things like Monte Carlo and simulated annealing. One area that I'd look into if I were doing this now would be a hybrid approach where a GA is used to design deep learning architectures and their associated parameters. Seems like it could be very powerful but damn would that ever take a lot of computing power. The fitness function of the GA would consist of N deep learning runs for each candidate. Luckily GAs are parallelizable to an almost unlimited degree.
  - randomsearch 5y ago
    Speculative comments: evolving neural network architectures may be where EAs prove their worth. Plenty of work on it but it’s early days and we need massive, massive, compute power.
    - apl 5y ago
      Neural architecture search (NAS) is a thing! But it's almost exclusively based on meta-gradients. Again, wouldn't put my money on GAs ever outperforming gradient-based methods again.
amelius 5y ago
How did wings evolve in insects?
- Teever 5y ago
  I would imagine that the lift to mass ratio of a small animal like an insect would be more forgiving, allowing an organism that evolved those '1%' wings through random mutation to see sufficient benefit that a selective pressure could then produce larger and more articulatable '2%' and then '3%' wings and so on...
  - amelius 5y ago
    Wouldn't it make sense that bird-wings started also with small animals in evolution?
    - Teever 5y ago
      Yes but I don't think the smallest birds are all that comparable in size to the smallest insects. Keep in mind that for many insects their terminal velocity isn't sufficient to kill them on landing. So an ant can be dropped from an airplane, fall for thousands of feet, hit the ground, and the walk on like nothing happened.
lukas099 5y ago
> For example, it's quite difficult to imagine how wings evolved, since 1% of a wing seems to offer no fitness advantage Not to nitpick, and I agree with your overall point, but couldn't 1% of a wing be useful for any tree-climbing animal that falls/jumps occasionally? It would allow them to fall/jump a little further without injury by acting as a little bit of a parachute or glider.

by SamBam 5y ago

ailef 5y ago

I've always loved genetic algorithms and similar ideas. Unfortunately, as you said, they are not that common now unless maybe in some niche use cases. It's very fun to use them for a weekend project, though.

tomrod 5y ago

> genetic algorithms have fallen out of fashion. I fully anticipate they will come back in fashion. NN were out of fashion for a long time.

fivea 5y ago
>>I fully anticipate they will come back in fashion. It's not possible to predict fashions, but I seriously doubt that the whole evolutionary algorithms field will see a resurgence based on anything other than buzzword-driven fads. In general evolutionary algorithms perform terribly poorly in any optimization problem, and at best are effective (but not efficient) in exploring problems involving the arbitrary addition/removal of dimensions/parameters, including high-dimensional discrete optimization problems. Given there are already techniques to convert discrete optimization problems to non-discrete ones and to add/remove arbitrary parameters, and there are already global optimization techniques which are far more efficient and, more importantly, deterministic, genetic algorithms don't really offer any relevant advantage over even brute-force techniques.
- nicoco 5y ago
  I usually use CMA-ES as a 'very easy to set and up and better than brute force' approach. Am I dumb to do that? (genuine question, no irony, optimization is not my field at all)
  - randomsearch 5y ago
    You are correct about CMA-ES.
- rusticpenn 5y ago
  I have used swarm optimization methods that have consistently provided better solutions than alternatives for optimizations of solution spaces in alterst 3 different domains. I am not sure what you are talking about.
  - fivea 5y ago
    > I have used swarm optimization methods that have consistently provided better solutions than alternatives for optimizations of solution spaces in alterst 3 different domains. Benchmark your PSO implementation against a) a naive Monte Carlo implementation with an uniform distribution, b) low-discrepancy sequence, c) a global optimization algorithm such as DIRECT, and compare convergence rates. I'd be surprised if your PSO implementation did not competed for the last place in terms of function evaluations.
    - rusticpenn 5y ago
      Unfortunately I don’t currently have access to this data. I can tell you that it’s leagues better than any Monte Carlo implementation as I have done this comparison as a litmus test for several population based algorithms in the past. I I’ll look into making a comparison with DIRECT when I have time (not anytime this month)
- tomrod 5y ago
  To my understanding, they are coming back in vogue with neural architecture search. But hey, it's newish, so maybe you're one of today's lucky 10,000. https://xkcd.com/1053 https://xkcd.com/1053
api 5y ago
IMHO genetic algorithms are waiting for their AlexNet paper: https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6... The approach is clearly valid but I feel like there's some missing pieces in making it work effectively in a digital context. I played around with this stuff a lot in college and my take was that the evolvable encoding problem (a form of representation problem) is fairly major and not really solved. There are also some unsolved issues around evolutionary dynamics and evolutionary game theory, which means how to structure the population and the "game" for best results. Not sure how much progress has been made since then on these, but my impression is not much. The main area where GAs have seen use in the field so far is optimization problems with a lot of parameters related in unknown or hard to model ways or where a closed form solution is unknown or computationally too expensive (NP). These include shipping and air travel routing (traveling salesman with multiple optimization goals like distance + time + fuel + depreciation), circuit board and IC layout, antenna design for exotic RF modulations, drug discovery, materials science, etc. Problems like these are fairly easy to map to a GA, and current GAs are pretty good at finding local maxima in these functions. Still those are a far cry from "design ex nihilo," which is really the promise that evolutionary computation carries. Those applications are using GAs as a bigger brother to things like Monte Carlo and simulated annealing. One area that I'd look into if I were doing this now would be a hybrid approach where a GA is used to design deep learning architectures and their associated parameters. Seems like it could be very powerful but damn would that ever take a lot of computing power. The fitness function of the GA would consist of N deep learning runs for each candidate. Luckily GAs are parallelizable to an almost unlimited degree.
- randomsearch 5y ago
  Speculative comments: evolving neural network architectures may be where EAs prove their worth. Plenty of work on it but it’s early days and we need massive, massive, compute power.
  - apl 5y ago
    Neural architecture search (NAS) is a thing! But it's almost exclusively based on meta-gradients. Again, wouldn't put my money on GAs ever outperforming gradient-based methods again.

amelius 5y ago

How did wings evolve in insects?

Teever 5y ago
I would imagine that the lift to mass ratio of a small animal like an insect would be more forgiving, allowing an organism that evolved those '1%' wings through random mutation to see sufficient benefit that a selective pressure could then produce larger and more articulatable '2%' and then '3%' wings and so on...
- amelius 5y ago
  Wouldn't it make sense that bird-wings started also with small animals in evolution?
  - Teever 5y ago
    Yes but I don't think the smallest birds are all that comparable in size to the smallest insects. Keep in mind that for many insects their terminal velocity isn't sufficient to kill them on landing. So an ant can be dropped from an airplane, fall for thousands of feet, hit the ground, and the walk on like nothing happened.

lukas099 5y ago

> For example, it's quite difficult to imagine how wings evolved, since 1% of a wing seems to offer no fitness advantage Not to nitpick, and I agree with your overall point, but couldn't 1% of a wing be useful for any tree-climbing animal that falls/jumps occasionally? It would allow them to fall/jump a little further without injury by acting as a little bit of a parachute or glider.