5 ms·

Genetic algorithms aren't really that brilliant. They are simple, and that's what makes them popular among researchers. There's no formal science behind them.

Genetic algorithms aren't really that brilliant. They are simple, and that's what makes them popular among researchers. There's no formal science behind them. I bet that thinking about the problem more would allow you to find an algorithm that works better than genetic algorithms all the time. Just look at travelling salesman problem, or vehicle routing problem. Smart heuristics beat these hybrid-genetic-memetic-algorithms all the time.

adrianN 11y ago
It's wrong to say that there is no formal science behind them. It's true that practice is ahead of theory in the field of randomized search heuristics like evolutionary and genetic algorithms, but there are researchers working on it. For example it has been proven that crossover can be beneficial http://people.mpi-inf.mpg.de/~doerr/papers/gecco2008_1.pdf http://people.mpi-inf.mpg.de/~doerr/papers/gecco2008_1.pdf There is also a book on the topic that summarizes some of the current research http://www.worldscientific.com/worldscibooks/10.1142/7438 http://www.worldscientific.com/worldscibooks/10.1142/7438
sevensor 11y ago
> I bet that thinking about the problem more would allow you to find an algorithm that works better than genetic algorithms all the time. This is true. It's been formalized as the No Free Lunch theorem by Wolpert and Macready. > Genetic algorithms aren't really that brilliant. They are simple, and that's what makes them popular among researchers. There's no formal science behind them. There is a formal science behind them -- conferences, journals, the whole nine yards. The problem is, there's a dominant notion of genetic algorithms that's 25 years out of date, and nobody's been able (or tried too hard) to break through the noise. (Disclaimer: I work in the field.)
TelmoMenezes 11y ago
> There's no formal science behind them. I'm not sure what that means. Science is empiricism, and genetic algorithms are a wide field of research with a lot of experimentation behind them. There are many hypothesis about how they work, why they work and what their limitations are. These hypothesis are tested through experimentation, just like in other scientific fields. > Smart heuristics beat these hybrid-genetic-memetic-algorithms all the time. Sure, this is almost guaranteed by the "no free-lunch theorem": https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem There might be some exotic cases where genetic algorithms are actually the best solution, but nobody knows that. But that's not the point of genetic algorithms. The point is having a generic solution that can be applied with some success when you don't have the time or the resources to find those "smart heuristics". And there might be cases where we are just not smart enough to find them. Some of these cases might be related to the effort towards developing generic AI. You can also claim that it is always possible to write a more efficient computer program directly in machine code, if you ignore time and resources. Another interesting property of evolutionary computation is enabling some form of artificial creativity. Check out this antenna, created by NASA using evolutionary computation: https://en.wikipedia.org/wiki/Evolved_antenna https://en.wikipedia.org/wiki/Evolved_antenna Also, if you will forgive me a bit of self promotion, check out my own work on the discovery of complex network generators: http://www.nature.com/articles/srep06284 http://www.nature.com/articles/srep06284
- chriswarbo 11y ago
  >The point is having a generic solution that can be applied with some success when you don't have the time or the resources to find those "smart heuristics". And there might be cases where we are just not smart enough to find them. Indeed, the same could be said of any "smart heuristics" too: > Exact solutions beat these smart heuristics all the time. ;)
  - spooningtamarin 11y ago
    Most of the time, heuristics are faster than operators in genetic algorithms. Same goes for heuristics being faster than exact solutions for harder problems.
- howeman 11y ago
  > There might be some exotic cases where genetic algorithms are actually the best solution, but nobody knows that. Actually, No Free Lunch guarantees that such cases exist.
  - TelmoMenezes 11y ago
    Good point. What I had in mind was "problems that someone actually cares about". My bad.
- spooningtamarin 11y ago
  I wouldn't say genetic algorithms are generic solutions. I have to try really hard to implement efficient operators that would allow me fast optimization. Scientific contributions are mostly in operators, I guess. I can't think what else can someone working with genetic algorithms contribute because adding elitism, or 3-way crossover isn't really the solution to a problem, it's just metaheuristics jibber-jabber.
  - TelmoMenezes 11y ago
    I find the situation a bit similar to neural networks. It's a bio-inspired model, and we know from nature that it can work spectacularly well. The actual algorithms that became popular (both in neural networks and evolutionary computation) are extreme simplifications of the biological reality. So a lot of the research goes in the direction of finding the "missing ingredients". On the evolutionary computation front, one of the topics I find the most interesting is the genotype-phenotype mapping. Naive genetic algorithms have genotypes that map directly to phenotypes (e.g you are evolving some vector which is a direct solution to a problem). More complex mapping (like what we see in nature) encode a generator for a solution. On this note, exciting stuff happens on the genetic programming front (where you are evolving computer programs, commonly Lisp-like trees). It really is a vast field, ranging from direct engineering applications to artificial life simulations aimed at theoretical biology. Like everything else, you have to be familiar with the literature.
loopbit 11y ago
Genetic algorithms are not brilliant, but their results sometimes can be. I remember reading and article[0] about a researcher using genetic algorithms on FPGAs. One paragraph stuck with me through all these years: "Dr. Thompson peered inside his perfect offspring to gain insight into its methods, but what he found inside was baffling. The plucky chip was utilizing only thirty-seven of its one hundred logic gates, and most of them were arranged in a curious collection of feedback loops. Five individual logic cells were functionally disconnected from the rest— with no pathways that would allow them to influence the output— yet when the researcher disabled any one of them the chip lost its ability to discriminate the tones. Furthermore, the final program did not work reliably when it was loaded onto other FPGAs of the same type." Now, I agree with you that, even for a problem as simple as that one (or specially because it's a simple problem, maybe) a "normal" algorithm would perform better. But the fact that the genetic algorithm was able to find the effects of magnetic flux (those five disconnected logic cells) in that specific FPGA is nothing short of brilliant. The problem I've always seen (not an expert, by any means, but I've played around with them a bit) with genetic algorithms is that they require a weird balance. For simple problems, a normal algorithm will probably work better. As the complexity of the problem increases, the scoring and evaluating rules' complexity increases as well (I've got no hard data, of course, but my feeling is that the complexity of the scoring process increases much faster than the complexity of the problem), making a well thought algorithm a better/easier solution. This, and that any mistake in the scoring process might throw away thousands and thousands of generations. [0]http://www.damninteresting.com/on-the-origin-of-circuits/ http://www.damninteresting.com/on-the-origin-of-circuits/
- ionforce 11y ago
  This story is like the poster child of success with genetic algorithms.
segmondy 11y ago
Why would you use a genetic algorithm to solve a traveling salesman problem or vehicle routing problem? Get real. That's a very bad mapping. Genetic algorithm thrives when you have a lot of variables that can be optimized to gain a favorable behavior and those optimizations are unknown. Saying it's not brilliant because it's simple is like saying that binary search or merge sort is not brilliant because they are simple.
- spooningtamarin 11y ago
  Checkout latest research in Vehicle Routing Problem, its filled with GA/Ants and similar nonsense. On the other hand you have TSP which murdered all those GA algorithms with a proper Lin-Kernighan heuristic implementation. I'm not sure if we are talking about same problems. > Saying it's not brilliant I said they were simple and that's why people like them.
vidarh 11y ago
Computational resources are steadily getting cheaper. Peoples time is not. Which is why GA/GP matters: It's part of a growing toolbox to allow us to find interesting candidate algorithms for certain classes of problems without spending as much human time to figure out cleaner solutions. If you wish you can then have humans figure out why the solution works and use that knowledge to come up with something better.
verdverm 11y ago
I agree! I spent a few years with Genetic Programming for Symbolic Regression. After understanding the nature of the problem, I came up with a dynamic programming based heuristic that beats the pants off of GP. I called it Prioritized Grammar Enumeration. http://github.com/verdverm/pypge http://github.com/verdverm/pypge http://www.math.binghamton.edu/dept/ComboSem/worm-chiu.pge_gecco2013.pdf http://www.math.binghamton.edu/dept/ComboSem/worm-chiu.pge_g...

adrianN 11y ago

It's wrong to say that there is no formal science behind them. It's true that practice is ahead of theory in the field of randomized search heuristics like evolutionary and genetic algorithms, but there are researchers working on it. For example it has been proven that crossover can be beneficial http://people.mpi-inf.mpg.de/~doerr/papers/gecco2008_1.pdf http://people.mpi-inf.mpg.de/~doerr/papers/gecco2008_1.pdf There is also a book on the topic that summarizes some of the current research http://www.worldscientific.com/worldscibooks/10.1142/7438 http://www.worldscientific.com/worldscibooks/10.1142/7438

sevensor 11y ago

> I bet that thinking about the problem more would allow you to find an algorithm that works better than genetic algorithms all the time. This is true. It's been formalized as the No Free Lunch theorem by Wolpert and Macready. > Genetic algorithms aren't really that brilliant. They are simple, and that's what makes them popular among researchers. There's no formal science behind them. There is a formal science behind them -- conferences, journals, the whole nine yards. The problem is, there's a dominant notion of genetic algorithms that's 25 years out of date, and nobody's been able (or tried too hard) to break through the noise. (Disclaimer: I work in the field.)

TelmoMenezes 11y ago

> There's no formal science behind them. I'm not sure what that means. Science is empiricism, and genetic algorithms are a wide field of research with a lot of experimentation behind them. There are many hypothesis about how they work, why they work and what their limitations are. These hypothesis are tested through experimentation, just like in other scientific fields. > Smart heuristics beat these hybrid-genetic-memetic-algorithms all the time. Sure, this is almost guaranteed by the "no free-lunch theorem": https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem There might be some exotic cases where genetic algorithms are actually the best solution, but nobody knows that. But that's not the point of genetic algorithms. The point is having a generic solution that can be applied with some success when you don't have the time or the resources to find those "smart heuristics". And there might be cases where we are just not smart enough to find them. Some of these cases might be related to the effort towards developing generic AI. You can also claim that it is always possible to write a more efficient computer program directly in machine code, if you ignore time and resources. Another interesting property of evolutionary computation is enabling some form of artificial creativity. Check out this antenna, created by NASA using evolutionary computation: https://en.wikipedia.org/wiki/Evolved_antenna https://en.wikipedia.org/wiki/Evolved_antenna Also, if you will forgive me a bit of self promotion, check out my own work on the discovery of complex network generators: http://www.nature.com/articles/srep06284 http://www.nature.com/articles/srep06284

chriswarbo 11y ago
>The point is having a generic solution that can be applied with some success when you don't have the time or the resources to find those "smart heuristics". And there might be cases where we are just not smart enough to find them. Indeed, the same could be said of any "smart heuristics" too: > Exact solutions beat these smart heuristics all the time. ;)
- spooningtamarin 11y ago
  Most of the time, heuristics are faster than operators in genetic algorithms. Same goes for heuristics being faster than exact solutions for harder problems.
howeman 11y ago
> There might be some exotic cases where genetic algorithms are actually the best solution, but nobody knows that. Actually, No Free Lunch guarantees that such cases exist.
- TelmoMenezes 11y ago
  Good point. What I had in mind was "problems that someone actually cares about". My bad.
spooningtamarin 11y ago
I wouldn't say genetic algorithms are generic solutions. I have to try really hard to implement efficient operators that would allow me fast optimization. Scientific contributions are mostly in operators, I guess. I can't think what else can someone working with genetic algorithms contribute because adding elitism, or 3-way crossover isn't really the solution to a problem, it's just metaheuristics jibber-jabber.
- TelmoMenezes 11y ago
  I find the situation a bit similar to neural networks. It's a bio-inspired model, and we know from nature that it can work spectacularly well. The actual algorithms that became popular (both in neural networks and evolutionary computation) are extreme simplifications of the biological reality. So a lot of the research goes in the direction of finding the "missing ingredients". On the evolutionary computation front, one of the topics I find the most interesting is the genotype-phenotype mapping. Naive genetic algorithms have genotypes that map directly to phenotypes (e.g you are evolving some vector which is a direct solution to a problem). More complex mapping (like what we see in nature) encode a generator for a solution. On this note, exciting stuff happens on the genetic programming front (where you are evolving computer programs, commonly Lisp-like trees). It really is a vast field, ranging from direct engineering applications to artificial life simulations aimed at theoretical biology. Like everything else, you have to be familiar with the literature.

loopbit 11y ago

Genetic algorithms are not brilliant, but their results sometimes can be. I remember reading and article[0] about a researcher using genetic algorithms on FPGAs. One paragraph stuck with me through all these years: "Dr. Thompson peered inside his perfect offspring to gain insight into its methods, but what he found inside was baffling. The plucky chip was utilizing only thirty-seven of its one hundred logic gates, and most of them were arranged in a curious collection of feedback loops. Five individual logic cells were functionally disconnected from the rest— with no pathways that would allow them to influence the output— yet when the researcher disabled any one of them the chip lost its ability to discriminate the tones. Furthermore, the final program did not work reliably when it was loaded onto other FPGAs of the same type." Now, I agree with you that, even for a problem as simple as that one (or specially because it's a simple problem, maybe) a "normal" algorithm would perform better. But the fact that the genetic algorithm was able to find the effects of magnetic flux (those five disconnected logic cells) in that specific FPGA is nothing short of brilliant. The problem I've always seen (not an expert, by any means, but I've played around with them a bit) with genetic algorithms is that they require a weird balance. For simple problems, a normal algorithm will probably work better. As the complexity of the problem increases, the scoring and evaluating rules' complexity increases as well (I've got no hard data, of course, but my feeling is that the complexity of the scoring process increases much faster than the complexity of the problem), making a well thought algorithm a better/easier solution. This, and that any mistake in the scoring process might throw away thousands and thousands of generations. [0]http://www.damninteresting.com/on-the-origin-of-circuits/ http://www.damninteresting.com/on-the-origin-of-circuits/

ionforce 11y ago
This story is like the poster child of success with genetic algorithms.

segmondy 11y ago

Why would you use a genetic algorithm to solve a traveling salesman problem or vehicle routing problem? Get real. That's a very bad mapping. Genetic algorithm thrives when you have a lot of variables that can be optimized to gain a favorable behavior and those optimizations are unknown. Saying it's not brilliant because it's simple is like saying that binary search or merge sort is not brilliant because they are simple.

spooningtamarin 11y ago
Checkout latest research in Vehicle Routing Problem, its filled with GA/Ants and similar nonsense. On the other hand you have TSP which murdered all those GA algorithms with a proper Lin-Kernighan heuristic implementation. I'm not sure if we are talking about same problems. > Saying it's not brilliant I said they were simple and that's why people like them.

vidarh 11y ago

Computational resources are steadily getting cheaper. Peoples time is not. Which is why GA/GP matters: It's part of a growing toolbox to allow us to find interesting candidate algorithms for certain classes of problems without spending as much human time to figure out cleaner solutions. If you wish you can then have humans figure out why the solution works and use that knowledge to come up with something better.

verdverm 11y ago

I agree! I spent a few years with Genetic Programming for Symbolic Regression. After understanding the nature of the problem, I came up with a dynamic programming based heuristic that beats the pants off of GP. I called it Prioritized Grammar Enumeration. http://github.com/verdverm/pypge http://github.com/verdverm/pypge http://www.math.binghamton.edu/dept/ComboSem/worm-chiu.pge_gecco2013.pdf http://www.math.binghamton.edu/dept/ComboSem/worm-chiu.pge_g...