4 ms·

How Do Genetic Algorithms Work? [video]

75 points by henning 11y ago

theatraine 11y ago
I'm curious to see what people have used genetic algorithms for in practice. Personally I've used them for feature selection when I was trying to reduce a high amount of features to smaller amount for a classification problem. Of course they're definitely great for evolving little cars, like this other example shows: http://rednuht.org/genetic_cars_2/ http://rednuht.org/genetic_cars_2/
- nickpsecurity 11y ago
  Google "applications of" genetic algoritms. I got results that way years ago. The abstracts of conference papers are also informative. I remember them used for scheduling/planning and optimization problems. One person even made one to find the optimal set of compiler arguments to get best performance for Haskell programs. Look up Humie Awards for Genetic Programming for a long list of human-equivalent achievements too.
- auxym 11y ago
  A grad-student-colleague of mine developped a control system for a robot using hyper-redundant binary-state actuators using GA's to search the solution space. See: http://dx.doi.org/10.1109/ICRA.2013.6630624 http://dx.doi.org/10.1109/ICRA.2013.6630624
- aheilbut 11y ago
  One interesting group of practical applications are the product design and optimization tools from Affinova http://www.affinova.com http://www.affinova.com
- Houshalter 11y ago
  You should see this fascinating stack overflow thread: https://stackoverflow.com/questions/1538235/what-are-good-examples-of-genetic-algorithms-genetic-programming-solutions https://stackoverflow.com/questions/1538235/what-are-good-ex... My favorite is the guy who got e-ink displays to work using them. Also see the Hummie awards, for the best use of genetic algorithms outperforming humans: http://www.genetic-programming.org/combined.php http://www.genetic-programming.org/combined.php
cmsmith 11y ago
My issue with GA is that they are definitely the sexiest/best known evolutionary algorithm in their class, so they get used for a lot of things that they're not really designed for. GA work best if you have lots of discrete parameters that combine in weird ways to determine fitness (you know, like DNA). I'm a structural engineer, and most search problems I run into have a smaller number of continuously valued parameters (like the locations of the joints in the car in the video). GA tends to try to swap parameters between the fittest of the previous generation, instead of looking in the area between those individuals.
- Lerc 11y ago
  The way I look at it is the selection/mutation mechanism is where the strength lies, the rest can be applied in all manner of ways. There's no reason why you can't generate the candidate generations in intelligent ways, in fact evolutionary models would be an excellent platform for error prone heuristics. Any cases where the heuristic fails are just discarded with the rest of the failures. I'm currently putting together a shader based polygon evolver and one of the things that I want to implement is smarter mutations where it weighs the relative importance of each gene and can more aggressively mutate genes that contribute the least.
- Houshalter 11y ago
  Yes, I believe there was a paper that hillclimbing with random restarts almost always did better than genetic algorithms. However does it really matter? It might save a little bit of time at best. But almost everyone has heard of genetic algorithms, so it's easier to talk about, than talking about particle swarm optimizations or whatever. Also genetic algorithms tend to excite people in a way that other metaheuristics just don't. People are fascinated with genetic algorithms, not so much with hillclimbing.
  - ai_maker 11y ago
    I would say that hill climbing with random restarts works better because you must first define a cost function in a precise (and concise) symbolic mathematical way. Very much similar to simulated annealing, stochastic gradient descent and the like. However, GA's can be applied regardless of the piece of knowledge that is required to build this cost function. GA is a universal optimisation technique: as long as you can encode features in a gene form (this is very convenient for binary attributes) and rate the fitting of that gene you are ready to search the optimum. My stab at explaining GA's: http://ai-maker.atrilla.net/the-%EF%BB%BFgenetic-algorithms/ http://ai-maker.atrilla.net/the-%EF%BB%BFgenetic-algorithms/
dyarosla 11y ago
How difficult of a problem is it to break out of local optimums several generations down in a genetic algorithm? If we prune the domain space from the get-go randomly, and then keep on creating sub-domains of the original large (or potentially non-finite) domain, wouldn't we generally only head towards local optimums, albeit, quickly?
lateguy 11y ago
What will be the difference between Reinforcement learning and Genetic Algorithm? The stackoverflow question here has mixed responses http://stackoverflow.com/questions/12411197/can-evolutionary-computation-be-a-method-of-reinforcement-learning http://stackoverflow.com/questions/12411197/can-evolutionary.... According to me I have implemented Reinforcement learning once http://somedeepthoughtsblog.tumblr.com/post/134793589864/maths-versus-computation http://somedeepthoughtsblog.tumblr.com/post/134793589864/mat..., they look same as both boils down to exploring and exploiting the environment for maximum reward.
- danielbarla 11y ago
  Reinforcement learning refers to the general problem of reward maximization where the agent must try solutions for itself and get feedback of the results via some kind of evaluation / fitness function. (As contrasted with supervised learning, where it the agent would be given examples, and would try to learn from that). Genetic algorithms are one specific class of optimization algorithms which accomplish this. Exploration and / vs exploitation is just a natural consequence of trying to make best sense of the unknown environment. Different algorithms have different strategies for this, and are generally suited for different classes of problems (generally, the issue would be matching the nature of the problem with the nature of the optimization algorithm - which brings up things like the no free lunch theorem).
razerw0lf 11y ago
On a side note, the item id of this post is a palindrome: "11066011", which you can often see in GA algorithms because of how sequence splits happen.

75 points by henning 11y ago

I'm curious to see what people have used genetic algorithms for in practice. Personally I've used them for feature selection when I was trying to reduce a high amount of features to smaller amount for a classification problem. Of course they're definitely great for evolving little cars, like this other example shows: http://rednuht.org/genetic_cars_2/ http://rednuht.org/genetic_cars_2/

nickpsecurity 11y ago
Google "applications of" genetic algoritms. I got results that way years ago. The abstracts of conference papers are also informative. I remember them used for scheduling/planning and optimization problems. One person even made one to find the optimal set of compiler arguments to get best performance for Haskell programs. Look up Humie Awards for Genetic Programming for a long list of human-equivalent achievements too.
auxym 11y ago
A grad-student-colleague of mine developped a control system for a robot using hyper-redundant binary-state actuators using GA's to search the solution space. See: http://dx.doi.org/10.1109/ICRA.2013.6630624 http://dx.doi.org/10.1109/ICRA.2013.6630624
aheilbut 11y ago
One interesting group of practical applications are the product design and optimization tools from Affinova http://www.affinova.com http://www.affinova.com
Houshalter 11y ago
You should see this fascinating stack overflow thread: https://stackoverflow.com/questions/1538235/what-are-good-examples-of-genetic-algorithms-genetic-programming-solutions https://stackoverflow.com/questions/1538235/what-are-good-ex... My favorite is the guy who got e-ink displays to work using them. Also see the Hummie awards, for the best use of genetic algorithms outperforming humans: http://www.genetic-programming.org/combined.php http://www.genetic-programming.org/combined.php

cmsmith 11y ago

My issue with GA is that they are definitely the sexiest/best known evolutionary algorithm in their class, so they get used for a lot of things that they're not really designed for. GA work best if you have lots of discrete parameters that combine in weird ways to determine fitness (you know, like DNA). I'm a structural engineer, and most search problems I run into have a smaller number of continuously valued parameters (like the locations of the joints in the car in the video). GA tends to try to swap parameters between the fittest of the previous generation, instead of looking in the area between those individuals.

Lerc 11y ago
The way I look at it is the selection/mutation mechanism is where the strength lies, the rest can be applied in all manner of ways. There's no reason why you can't generate the candidate generations in intelligent ways, in fact evolutionary models would be an excellent platform for error prone heuristics. Any cases where the heuristic fails are just discarded with the rest of the failures. I'm currently putting together a shader based polygon evolver and one of the things that I want to implement is smarter mutations where it weighs the relative importance of each gene and can more aggressively mutate genes that contribute the least.
Houshalter 11y ago
Yes, I believe there was a paper that hillclimbing with random restarts almost always did better than genetic algorithms. However does it really matter? It might save a little bit of time at best. But almost everyone has heard of genetic algorithms, so it's easier to talk about, than talking about particle swarm optimizations or whatever. Also genetic algorithms tend to excite people in a way that other metaheuristics just don't. People are fascinated with genetic algorithms, not so much with hillclimbing.
- ai_maker 11y ago
  I would say that hill climbing with random restarts works better because you must first define a cost function in a precise (and concise) symbolic mathematical way. Very much similar to simulated annealing, stochastic gradient descent and the like. However, GA's can be applied regardless of the piece of knowledge that is required to build this cost function. GA is a universal optimisation technique: as long as you can encode features in a gene form (this is very convenient for binary attributes) and rate the fitting of that gene you are ready to search the optimum. My stab at explaining GA's: http://ai-maker.atrilla.net/the-%EF%BB%BFgenetic-algorithms/ http://ai-maker.atrilla.net/the-%EF%BB%BFgenetic-algorithms/

dyarosla 11y ago

How difficult of a problem is it to break out of local optimums several generations down in a genetic algorithm? If we prune the domain space from the get-go randomly, and then keep on creating sub-domains of the original large (or potentially non-finite) domain, wouldn't we generally only head towards local optimums, albeit, quickly?

lateguy 11y ago

What will be the difference between Reinforcement learning and Genetic Algorithm? The stackoverflow question here has mixed responses http://stackoverflow.com/questions/12411197/can-evolutionary-computation-be-a-method-of-reinforcement-learning http://stackoverflow.com/questions/12411197/can-evolutionary.... According to me I have implemented Reinforcement learning once http://somedeepthoughtsblog.tumblr.com/post/134793589864/maths-versus-computation http://somedeepthoughtsblog.tumblr.com/post/134793589864/mat..., they look same as both boils down to exploring and exploiting the environment for maximum reward.

danielbarla 11y ago
Reinforcement learning refers to the general problem of reward maximization where the agent must try solutions for itself and get feedback of the results via some kind of evaluation / fitness function. (As contrasted with supervised learning, where it the agent would be given examples, and would try to learn from that). Genetic algorithms are one specific class of optimization algorithms which accomplish this. Exploration and / vs exploitation is just a natural consequence of trying to make best sense of the unknown environment. Different algorithms have different strategies for this, and are generally suited for different classes of problems (generally, the issue would be matching the nature of the problem with the nature of the optimization algorithm - which brings up things like the no free lunch theorem).

razerw0lf 11y ago

On a side note, the item id of this post is a palindrome: "11066011", which you can often see in GA algorithms because of how sequence splits happen.