14 ms·

Genetic Algorithm 2D Car Thingy

162 points by sconxu 11y ago

ColinWright 11y ago
This is brilliantly cool, and utterly hypnotic. I still always wonder about implementations of genetic algorithms, though. In real life, from which inspiration has been taken, the phenotype is often radically affected by small changes in the genotype. In computer implementation of the concept this is rarely the case. The computer versions are small, clean, spare, and nowhere near as messy as the real life version. I wonder if the messiness actually matters. I wonder if "optimization by genetic algorithm" would be significantly improved by using a more faithful algorithm. ======== Anyway, here's a previous discussion of this particular toy: https://news.ycombinator.com/item?id=5942757 https://news.ycombinator.com/item?id=5942757 (169 comments) Other submissions: https://news.ycombinator.com/item?id=10596079 https://news.ycombinator.com/item?id=10596079 https://news.ycombinator.com/item?id=10134390 https://news.ycombinator.com/item?id=10134390 https://news.ycombinator.com/item?id=5952145 https://news.ycombinator.com/item?id=5952145 https://news.ycombinator.com/item?id=2226137 https://news.ycombinator.com/item?id=2226137 Also, genetic development of walkers: https://news.ycombinator.com/item?id=8911719 https://news.ycombinator.com/item?id=8911719 (74 comments)
- spooningtamarin 11y ago
  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.
  - 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...
- sconxu 11y ago
  Didn't know about the walkers version. Thanks!
- randomsearch 11y ago
  > the phenotype is often radically affected by small changes in the genotype This is not true. If it were true, then the small mutations caused during reproduction of humans (for example) would result in huge changes to the phenotype. Typically, the genotype is fairly robust, for obvious reasons. OTOH, in genetic algorithms there is usually much less redundancy and neutrality in their genomes, because they are designed to solve problems, rather than simply survive.
  - ColinWright 11y ago
    Do you speak from direct knowledge, or is this a deduction you're making? I can't find any clues in your profile or other contributions, so I don't know whether this is your area of expertise - in which case I would bow to it - or if it's something you've deduced from other reading. The reason I ask is because your assertion is at odds with my understanding. My understanding is that most small mutations lead to no apparent change at all, hence the robustness. Some small mutations lead to catastrophic changes, as do almost all large mutations. But some small mutations lead to noticeable changes in the phenotype, and those are the ones that then get selected against. Some of them are beneficial in the existing circumstances, some are not. But the point is that it's small mutations that lead to a comparatively large change in the phenotype. And that's my point, which you echo: > ... in genetic algorithms there is usually > much less redundancy and neutrality in their > genomes, because they are designed to solve > problems, rather than simply survive. Yes. Current "genetic algorithms" don't actually do anything like the systems they have been inspired by. I wonder if real progress would be better if the implementations were more faithful.
    - raverbashing 11y ago
      Here's the difference between GA and GP In this case it's GA, so your genome directly maps to characteristics. So (let's say) chassis density is N bits. Mutate the MSB of that and the change will be big GP on the other hand would "build a car". And what usually happens during evolution is that some aspects gain resistance to mutation through some form of redundancy. So instead of Chassis density being a number it might be a crazy math expression that is not affected by small changes. Also a lot of "genes" have no effect on the final product. But having a bigger genome (in this way) effectively lowers mutation rates. It is "junk DNA" but actually has a purpose
- sklogic 11y ago
  I played a bit with the "more faithful" genetic algorithms, got some promising results (getting out of the local minima better). The key is to use hierarchical encoding in your chromosome: instead of directly encoding traits/functions/properties/whatever, encode a program (maybe even in a Turing-complete representation) which in turn generates those traits/functions/properties/whatever, or even generates a next level of code. This is closer to how the biological systems work, and allows for much higher sensitivity to small changes.
  - ionforce 11y ago
    Do you have more information about this approach? I've never heard about it until now.
    - sklogic 11y ago
      I tried to dig out the references from my mess of bibliography (I worked on this topic long before Mendeley and alike appeared), unsuccessfully. I remember that I ran into this technique independently first (in a context of encoding expression trees) and then found a number of other examples in the literature (e.g., encoding the neural network topology, etc.).
542458 11y ago
Bizarrely, I seem to get much better performance in safari than in chrome with this, which runs contrary to my expectations. I wonder why that is.
deleted 11y ago
[deleted]
pjs_ 11y ago
Here's my version from a decade ago: http://peteshadbolt.co.uk/ga/ http://peteshadbolt.co.uk/ga/ It's so old that it's written in Flash! One of these days I will port it to canvas, I swear...
- hliyan 11y ago
  I remember this when it came out! I was so fascinated I wanted to write my own, but I didn't have the programming skills back then...
- krallja 11y ago
  If you're going to port to JavaScript, it looks like it would be much better suited for SVG rather than canvas.
bentpins 11y ago
It's a little dead, but there's a few more similar natural selection simulators over at https://www.reddit.com/r/NSIP/top/?sort=top&t=all https://www.reddit.com/r/NSIP/top/?sort=top&t=all
sevensor 11y ago
This is a very beautiful illustration of a woefully outdated algorithm. Its proportional selection operator was superseded in 1994 (at the latest) when Bäck published his comparison of selection operators. Its approach to crossover looks like an ad-hoc extension of binary crossover, which Deb improved on in the same year. It's using uniform mutation, although better options have been demonstrated by Evolution Strategies since the '70s, if not earlier. But it's really fun to watch. I'll give it that.
- Gravityloss 11y ago
  Could we have a metagame sourced from all the games played by various people, where the selection algorithms etc evolved?
  - randomsearch 11y ago
    You're looking for "hyperheuristics."
- LoSboccacc 11y ago
  something I didn't get from the code/description: are the car generated only from mutations of the winners? because it seems those are generated by their own previous seed.
- mdda 11y ago
  I researched GAs / GPs back in the mid-90s (but then went in a different direction). Is there a paper/presentation that embodies the current best practices/thinking that you could recommend? I'm not trying to be lazy, it's just that there is clearly a lot of retro thinking among the top search results on the net, and it's difficult to separate the wheat from the chaff...
  - sevensor 11y ago
    With the disclaimer that there are different schools of thought, I can give a basic outline, and provide some references. This pertains mainly to optimizing engineering models, which tend to be continuous or mixed integer. GAs are just OK at combinatorial optimization (although GP is pretty nifty, from what I hear about it). * Steady-state: pioneered to the best of my knowledge by Deb's epsilon-MOEA, steady-state algorithms use function evaluations as soon as they are received, rather than waiting for a whole generation to complete. [1] * Multi-objective: Pareto ranking as dominance relation lets us have multiple objectives [2]. This is good because it gives us a whole bunch of solutions at once and lets us decide which one we want, instead of tweaking objectives and constraints to get an idea of the tradeoffs involved. * Epsilon resolution: comes from an idea by Laumanns et al. [3]. We can have more objectives if we don't care about differences below a certain threshold. Otherwise the Pareto front explodes in size. * Restarting: Proposed by Coello-Coello [4] and demonstrated by his micro-GA, restarting helps you get out of local optima. * Better search operators: Binary crossover doesn't work so well, especially for real-valued decision variables. It took some fancy theoretical footwork involving schema theory and domino convergence to support it. There were a lot of new search operators proposed in the late '90s, the best of which seem to be simulated binary crossover (SBX), and polynomial mutation (PM). [5] * Alternatively, the Differential Evolution search operator [6] works really well too. * Better selection operator: tournament selection beats the pants off of the alternatives [7]. Resources: * Dave Hadka's MOEAFramework [8], which includes open-source multi-objective evolutionary algorithm implementations. * Dave Hadka's dissertation [9], which describes a (regrettably patented) MOEA that's kind of a greatest-hits of good MOEA ideas. * Deb's website [10], which includes questionably-licensed algorithm implementations, as well as a number of technical reports. Links. I'm posting raw bibtex because I'm lazy. [1] @article{deb_2005_emoea, author = { Deb, K. and Mohan, M. and Mishra, S}, year = {2005}, title = {Evaluating the $\varepsilon$-domination based multiobjective evolutionary algorithm for a quick computation of Pareto-optimal solutions.}, journal = {Evolutionary Computation Journal}, volume= {13}, number = {4}, pages ={501--525} } [2] @book{goldberg_1989_book, title={Genetic algorithms in search, optimization, and machine learning}, author={Goldberg, D.E.}, year={1989}, publisher={Addison-Wesley Professional} } [3] @article{laumanns_2002_combining, title={Combining convergence and diversity in evolutionary multiobjective optimization}, author={Laumanns, M. and Thiele, L. and Deb, K. and Zitzler, E.}, journal={Evolutionary computation}, volume={10}, number={3}, pages={263--282}, year={2002}, publisher={MIT Press} } [4] @inproceedings{coello_2001_uga, author = {Carlos A Coello Coello and Gregorio Toscano Pulido}, title = {Multi-Objective Optimization Using a Micro-Genetic Algorithm}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001)}, pages = {274--282}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {2001} } [5] @techreport{deb_1994_sbx, author = {Deb, K. and Agrawal, R. B.}, year = 1994, title = {Simulated binary crossover for continuous search space}, number = { Technical Report IITK/ME/SMD-94027}, institution = {Indian Institute of Technology, Kanpur}, address = {Kanpur, UP, India} } [6] @article{storn_1997_de, author = {Storn, R. and Price, K.}, year = 1997, title = {Differential evolution --- a simple and efficient heuristic for global optimization over continuous spaces}, journal = { Journal of Global Optimization}, volume = 11, number = 4, pages = {341--359} } [7] @inproceedings{back_1994_selection, title={Selective pressure in evolutionary algorithms: A characterization of selection mechanisms}, author={B{\"a}ck, Thomas}, booktitle={Proceedings of the First IEEE Conference on Evolutionary Computation}, pages={57--62}, year={1994}, organization={IEEE} } [8] http://moeaframework.org/ http://moeaframework.org/ [9] https://etda.libraries.psu.edu/ https://etda.libraries.psu.edu/ You'll have to search for it, I'm afraid. The site's not responding for me right now. But his dissertation is publicly available on Penn State's ETD site. [10] http://www.iitk.ac.in/kangal/deb.shtml http://www.iitk.ac.in/kangal/deb.shtml edit: formatting
nmc 11y ago
OP, please append "(2012)" to the title.
deleted 11y ago
[deleted]
scottmcdot 11y ago
Does the best one look like a Strandbeest?
sanoli 11y ago
I keep looking for the version of this simulator where you get to draw your own car, and then you run it and see how well it handles the terrain. played with it many years ago, never found it again. maybe someone here can help?
raldi 11y ago
What does "Floor: [fixed / mutable]" mean?
- ChicagoBoy11 11y ago
  You can have each generation always run on the exact same terrain, or the terrain can be randomly generated on each iteration.
IanDrake 11y ago
It would be cool if someone added a car designer to this. I wonder if I could design a car based on intuition that would perform better than the algo could generate.
- sevensor 11y ago
  This is a frequent request. It can be very interesting to see how professional designs stack up against algorithmically generated ones. I'm a proponent of multi-objective algorithms, so it tends to be the case that professional designs are at least close to Pareto-optimal. Pros are pros for a reason. But they are often unaware of nondominated alternatives. For really hard problems, problems that evolutionary algorithms are bad at, experts can still come up with better alternatives than algorithms.
ixtli 11y ago
So how long do I have to leave it running before the cars create art or try to figure out who I am?
shostack 11y ago
Would be cool to display the current world seed somewhere if it isn't explicitly entered. I was going to paste an example track I came across that seemed literally impossible to conquer within the constraints of the mutations, but I can't grab the seed. In any event, would love more depth to the mutations. Longer/taller cars, etc. Maybe even other things like randomly firing after burners, wings to let it glide, etc. Nice work!

162 points by sconxu 11y ago

This is brilliantly cool, and utterly hypnotic. I still always wonder about implementations of genetic algorithms, though. In real life, from which inspiration has been taken, the phenotype is often radically affected by small changes in the genotype. In computer implementation of the concept this is rarely the case. The computer versions are small, clean, spare, and nowhere near as messy as the real life version. I wonder if the messiness actually matters. I wonder if "optimization by genetic algorithm" would be significantly improved by using a more faithful algorithm. ======== Anyway, here's a previous discussion of this particular toy: https://news.ycombinator.com/item?id=5942757 https://news.ycombinator.com/item?id=5942757 (169 comments) Other submissions: https://news.ycombinator.com/item?id=10596079 https://news.ycombinator.com/item?id=10596079 https://news.ycombinator.com/item?id=10134390 https://news.ycombinator.com/item?id=10134390 https://news.ycombinator.com/item?id=5952145 https://news.ycombinator.com/item?id=5952145 https://news.ycombinator.com/item?id=2226137 https://news.ycombinator.com/item?id=2226137 Also, genetic development of walkers: https://news.ycombinator.com/item?id=8911719 https://news.ycombinator.com/item?id=8911719 (74 comments)

spooningtamarin 11y ago
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.
- 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...
sconxu 11y ago
Didn't know about the walkers version. Thanks!
randomsearch 11y ago
> the phenotype is often radically affected by small changes in the genotype This is not true. If it were true, then the small mutations caused during reproduction of humans (for example) would result in huge changes to the phenotype. Typically, the genotype is fairly robust, for obvious reasons. OTOH, in genetic algorithms there is usually much less redundancy and neutrality in their genomes, because they are designed to solve problems, rather than simply survive.
- ColinWright 11y ago
  Do you speak from direct knowledge, or is this a deduction you're making? I can't find any clues in your profile or other contributions, so I don't know whether this is your area of expertise - in which case I would bow to it - or if it's something you've deduced from other reading. The reason I ask is because your assertion is at odds with my understanding. My understanding is that most small mutations lead to no apparent change at all, hence the robustness. Some small mutations lead to catastrophic changes, as do almost all large mutations. But some small mutations lead to noticeable changes in the phenotype, and those are the ones that then get selected against. Some of them are beneficial in the existing circumstances, some are not. But the point is that it's small mutations that lead to a comparatively large change in the phenotype. And that's my point, which you echo: > ... in genetic algorithms there is usually > much less redundancy and neutrality in their > genomes, because they are designed to solve > problems, rather than simply survive. Yes. Current "genetic algorithms" don't actually do anything like the systems they have been inspired by. I wonder if real progress would be better if the implementations were more faithful.
  - raverbashing 11y ago
    Here's the difference between GA and GP In this case it's GA, so your genome directly maps to characteristics. So (let's say) chassis density is N bits. Mutate the MSB of that and the change will be big GP on the other hand would "build a car". And what usually happens during evolution is that some aspects gain resistance to mutation through some form of redundancy. So instead of Chassis density being a number it might be a crazy math expression that is not affected by small changes. Also a lot of "genes" have no effect on the final product. But having a bigger genome (in this way) effectively lowers mutation rates. It is "junk DNA" but actually has a purpose
sklogic 11y ago
I played a bit with the "more faithful" genetic algorithms, got some promising results (getting out of the local minima better). The key is to use hierarchical encoding in your chromosome: instead of directly encoding traits/functions/properties/whatever, encode a program (maybe even in a Turing-complete representation) which in turn generates those traits/functions/properties/whatever, or even generates a next level of code. This is closer to how the biological systems work, and allows for much higher sensitivity to small changes.
- ionforce 11y ago
  Do you have more information about this approach? I've never heard about it until now.
  - sklogic 11y ago
    I tried to dig out the references from my mess of bibliography (I worked on this topic long before Mendeley and alike appeared), unsuccessfully. I remember that I ran into this technique independently first (in a context of encoding expression trees) and then found a number of other examples in the literature (e.g., encoding the neural network topology, etc.).

542458 11y ago

Bizarrely, I seem to get much better performance in safari than in chrome with this, which runs contrary to my expectations. I wonder why that is.

deleted 11y ago

[deleted]

pjs_ 11y ago

Here's my version from a decade ago: http://peteshadbolt.co.uk/ga/ http://peteshadbolt.co.uk/ga/ It's so old that it's written in Flash! One of these days I will port it to canvas, I swear...

hliyan 11y ago
I remember this when it came out! I was so fascinated I wanted to write my own, but I didn't have the programming skills back then...
krallja 11y ago
If you're going to port to JavaScript, it looks like it would be much better suited for SVG rather than canvas.

bentpins 11y ago

It's a little dead, but there's a few more similar natural selection simulators over at https://www.reddit.com/r/NSIP/top/?sort=top&t=all https://www.reddit.com/r/NSIP/top/?sort=top&t=all

sevensor 11y ago

This is a very beautiful illustration of a woefully outdated algorithm. Its proportional selection operator was superseded in 1994 (at the latest) when Bäck published his comparison of selection operators. Its approach to crossover looks like an ad-hoc extension of binary crossover, which Deb improved on in the same year. It's using uniform mutation, although better options have been demonstrated by Evolution Strategies since the '70s, if not earlier. But it's really fun to watch. I'll give it that.

Gravityloss 11y ago
Could we have a metagame sourced from all the games played by various people, where the selection algorithms etc evolved?
- randomsearch 11y ago
  You're looking for "hyperheuristics."
LoSboccacc 11y ago
something I didn't get from the code/description: are the car generated only from mutations of the winners? because it seems those are generated by their own previous seed.
mdda 11y ago
I researched GAs / GPs back in the mid-90s (but then went in a different direction). Is there a paper/presentation that embodies the current best practices/thinking that you could recommend? I'm not trying to be lazy, it's just that there is clearly a lot of retro thinking among the top search results on the net, and it's difficult to separate the wheat from the chaff...
- sevensor 11y ago
  With the disclaimer that there are different schools of thought, I can give a basic outline, and provide some references. This pertains mainly to optimizing engineering models, which tend to be continuous or mixed integer. GAs are just OK at combinatorial optimization (although GP is pretty nifty, from what I hear about it). * Steady-state: pioneered to the best of my knowledge by Deb's epsilon-MOEA, steady-state algorithms use function evaluations as soon as they are received, rather than waiting for a whole generation to complete. [1] * Multi-objective: Pareto ranking as dominance relation lets us have multiple objectives [2]. This is good because it gives us a whole bunch of solutions at once and lets us decide which one we want, instead of tweaking objectives and constraints to get an idea of the tradeoffs involved. * Epsilon resolution: comes from an idea by Laumanns et al. [3]. We can have more objectives if we don't care about differences below a certain threshold. Otherwise the Pareto front explodes in size. * Restarting: Proposed by Coello-Coello [4] and demonstrated by his micro-GA, restarting helps you get out of local optima. * Better search operators: Binary crossover doesn't work so well, especially for real-valued decision variables. It took some fancy theoretical footwork involving schema theory and domino convergence to support it. There were a lot of new search operators proposed in the late '90s, the best of which seem to be simulated binary crossover (SBX), and polynomial mutation (PM). [5] * Alternatively, the Differential Evolution search operator [6] works really well too. * Better selection operator: tournament selection beats the pants off of the alternatives [7]. Resources: * Dave Hadka's MOEAFramework [8], which includes open-source multi-objective evolutionary algorithm implementations. * Dave Hadka's dissertation [9], which describes a (regrettably patented) MOEA that's kind of a greatest-hits of good MOEA ideas. * Deb's website [10], which includes questionably-licensed algorithm implementations, as well as a number of technical reports. Links. I'm posting raw bibtex because I'm lazy. [1] @article{deb_2005_emoea, author = { Deb, K. and Mohan, M. and Mishra, S}, year = {2005}, title = {Evaluating the $\varepsilon$-domination based multiobjective evolutionary algorithm for a quick computation of Pareto-optimal solutions.}, journal = {Evolutionary Computation Journal}, volume= {13}, number = {4}, pages ={501--525} } [2] @book{goldberg_1989_book, title={Genetic algorithms in search, optimization, and machine learning}, author={Goldberg, D.E.}, year={1989}, publisher={Addison-Wesley Professional} } [3] @article{laumanns_2002_combining, title={Combining convergence and diversity in evolutionary multiobjective optimization}, author={Laumanns, M. and Thiele, L. and Deb, K. and Zitzler, E.}, journal={Evolutionary computation}, volume={10}, number={3}, pages={263--282}, year={2002}, publisher={MIT Press} } [4] @inproceedings{coello_2001_uga, author = {Carlos A Coello Coello and Gregorio Toscano Pulido}, title = {Multi-Objective Optimization Using a Micro-Genetic Algorithm}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001)}, pages = {274--282}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {2001} } [5] @techreport{deb_1994_sbx, author = {Deb, K. and Agrawal, R. B.}, year = 1994, title = {Simulated binary crossover for continuous search space}, number = { Technical Report IITK/ME/SMD-94027}, institution = {Indian Institute of Technology, Kanpur}, address = {Kanpur, UP, India} } [6] @article{storn_1997_de, author = {Storn, R. and Price, K.}, year = 1997, title = {Differential evolution --- a simple and efficient heuristic for global optimization over continuous spaces}, journal = { Journal of Global Optimization}, volume = 11, number = 4, pages = {341--359} } [7] @inproceedings{back_1994_selection, title={Selective pressure in evolutionary algorithms: A characterization of selection mechanisms}, author={B{\"a}ck, Thomas}, booktitle={Proceedings of the First IEEE Conference on Evolutionary Computation}, pages={57--62}, year={1994}, organization={IEEE} } [8] http://moeaframework.org/ http://moeaframework.org/ [9] https://etda.libraries.psu.edu/ https://etda.libraries.psu.edu/ You'll have to search for it, I'm afraid. The site's not responding for me right now. But his dissertation is publicly available on Penn State's ETD site. [10] http://www.iitk.ac.in/kangal/deb.shtml http://www.iitk.ac.in/kangal/deb.shtml edit: formatting

nmc 11y ago

OP, please append "(2012)" to the title.

deleted 11y ago

[deleted]

scottmcdot 11y ago

Does the best one look like a Strandbeest?

sanoli 11y ago

I keep looking for the version of this simulator where you get to draw your own car, and then you run it and see how well it handles the terrain. played with it many years ago, never found it again. maybe someone here can help?

raldi 11y ago

What does "Floor: [fixed / mutable]" mean?

ChicagoBoy11 11y ago
You can have each generation always run on the exact same terrain, or the terrain can be randomly generated on each iteration.

IanDrake 11y ago

It would be cool if someone added a car designer to this. I wonder if I could design a car based on intuition that would perform better than the algo could generate.

sevensor 11y ago
This is a frequent request. It can be very interesting to see how professional designs stack up against algorithmically generated ones. I'm a proponent of multi-objective algorithms, so it tends to be the case that professional designs are at least close to Pareto-optimal. Pros are pros for a reason. But they are often unaware of nondominated alternatives. For really hard problems, problems that evolutionary algorithms are bad at, experts can still come up with better alternatives than algorithms.

ixtli 11y ago

So how long do I have to leave it running before the cars create art or try to figure out who I am?

shostack 11y ago

Would be cool to display the current world seed somewhere if it isn't explicitly entered. I was going to paste an example track I came across that seemed literally impossible to conquer within the constraints of the mutations, but I can't grab the seed. In any event, would love more depth to the mutations. Longer/taller cars, etc. Maybe even other things like randomly firing after burners, wings to let it glide, etc. Nice work!