I thought they were really nifty when I first heard of them, but thinking of them as an optimization procedure, they don't really stand up in my experience to basic gradient descent methods. Sure, you can e.g. train a neural network with genetic algorithms, but why would you?
I'd love to be proven wrong though :)
http://dinsights.com/POTM/LOAPS/finals.php
The game's scoring system was based on Lines of Action but added an alternative goal which was to win by points. So in order to play this game well a bot had to balance progress towards one of the goals with the need to make sure the opponent didn't get too far ahead in the other goal. My program was the output of a genetic algorithm that learned a remarkably good balance between these two sometimes competing goals. Before I used the genetic algorithm I spent a lot of time hand tuning the evaluation function and actually came up with a quite good result that I was unable to improve on. When I ran the genetic algorithm I was thrilled to discover that the genetic algorithm's output totally crushed my hand tuned output.
After my program won the contest with an undefeated 74-0-0 record the author of one of the best Lines of Action computer programs in the world played his program against mine. If the organizer of the programming contest had chosen just a slightly different scoring system that was biased a little more towards the Lines of Action goal, then my program would probably lose against the Lines of Action program. The author played two games of his program against my program. Both games ended with his program thinking it won by Lines of Action rules and my program thinking it won by the tweaked contest rules! This suggests that the organizer of the contest had done a particularly good job of balancing the different goals of the game. (No, this paragraph is about the organizer's game design and has nothing to do with the question of genetic algorithms. I just thought it was an interesting side note.)
I really have no idea of whether gradient descent optimization methods would have been better or not. But this was an area where genetic algorithms worked very well.
GA might be better than gradient descent when you can’t compute a gradient because the function you’re optimizing isn’t differentiable.
GA is useful for interactive evolution, when the fitness function is a human.
I'd complement the "can't compute a gradient" also with the "gradient won't help you" cases (lots of local maxima/minima )
But in general the "No Free Lunch Theorem"[1] shows that no optimisation algorithm is "better" than any other across the universe of all possible problems.
So it's going to be some balance of your familiarity with GAs, having a problem domain that maps nicely to some simple input structure but which has a relatively gnarly surface to search and whether you could do it better in some other way.
These days the clear winner is various kinds of neural nets, largely because they can be represented with matrix multiplication, which made them suitable first for GPUs and now for much more specialised hardware.
I've had them in mind for searching autoscaler parameters, mostly because I feel it's easier to reason about a GA's optimisations than a series of matrix multiplications resulting in a cloud of floating point numbers.
People have also had good results using GA to optimize Yagi-Uda arrays. In that case, it is very easy to map design parameters onto a "gene vector" in a way that is well-understood and such that it yields an understandable result. But that is really just a search problem, so maybe other algorithms would do as well.
0) there is not enough data for you to train a NN, and
1) you have a really huge solution space for the problem that you cannot brutal force, and
2) you can encode each solution into a simple ``string'' (chromosome), and
3) the problem you're trying to solve is not very time critical (GA can take seconds to minutes depending on your problem)
Also, GA can actually utilize many CPU or even GPU cores to solve the problem much faster.
Ha. Days or weeks is typical for complex problems.
There were a lot of constraints, and several applications were used at different points (e.g. specialised 3D CAD) - a single generation took around 1 hour, so we had to let it run for days at a time on a cluster to be useful.
I actually kind of surprised, because I didn't realise people still used GAs any more, let alone such a standard implementation.
I think the realistic strength is that there are some easy to use libraries that don't require the user to really know anything about optimisation or work too hard and can deal with very difficult optimization scenarios (and sometimes even deal with them well).
Plus they're neat-o. That's gotta count for something. You ever try the island variant?
That's a poor assertion because even if detivative-free algorithms weren't already a thing, there are a myriad of smoothing techniques that enable nondifferentiable objective functions to be approximated by differentiable functions.
> I think the realistic strength is that there are some easy to use libraries that don't require the user to really know anything about optimisation or work too hard and can deal with very difficult optimization scenarios (and sometimes even deal with them well).
That's also not a reasonable assertion because there are also plenty software libraries for continuous and discrete optimization that are easy to use.
GAs in general are explored in academia because they are a fad that's easily publishable. Other than that this class of methods is in general very computationally expensive and very inefficient, and don't provide any advantage over plain old adaptive sampling, or even dumb regular lattice sampling.
I would say 90% of GA papers are because of this.
> Other than that this class of methods is in general very computationally expensive and very inefficient, and don't provide any advantage over plain old adaptive sampling, or even dumb regular lattice sampling.
Definitely false. The vast majority of OR-type papers in good journals include comparison to weak baselines like those, and wouldn't be published (in those venues) if they didn't win.
That statement is not correct. Although it's customary to accompany papers with benchmarks, these benchmarks focus practically exclusively on popular evolutionary algorithms. Worse, the "no free lunch" theorem grants authors the freedom to cherry-pick which benchmark problems are used.
About NFL, I agree that a lot of authors misuse it in that way. But again, in most papers in good journals, what we see is either a comprehensive experiment with a wide enough range of instances, or a real industry problem, not cherry-picking.
Those methods are invariably other evolutionary methods, and benchmarks are cherry-picked to show only encouraging results under the convenient guise of the "no free lunch" theorem. That' pretty much the norm, such as the repetitive recipe for inventing a metaheuristic algorithm of a) coming up with a clever nature-inspired metaphor with a catchy name, b) put together an algorithm that is arguably inspired on the metaphor, c) come up with a benchmark that arguably portrays the algorithm as being any improvement, even if only on a fortuitous corner case.
I agree that many papers of that recipe type exist -- Sorensen and Weyland have skewered them effectively -- they are just froth, to be ignored in a discussion of the true merits of evolutionary computation.
The function you wish to optimise may be non differentiable because the domain is discrete. E.g. to perform feature selection one can binary encode which features are included and which are excluded, with the fitness function being the accuracy of a model using the included features as inputs and trained for X iterations.
The knapsack problem(2), of which fantasy team picking is an example, is a classic use case for genetic algorithms.
1) https://github.com/chrxr/ga-prem-team/blob/master/scripts/ga... 2) https://en.wikipedia.org/wiki/Knapsack_problem
The solution my program "evolved" was the best in the company.
A few days ago I used GA to perform feature selection (binary encoding with 0 indicating a feature is excluded, 1 if included, fitness function was the accuracy of a NN taking the included features as inputs and trained with gradient descent for x epochs). This made my final network smaller, train faster, etc.
* gender (try to get mixed gender groups and atleast have two of each gender in a group e.g. no 1 female + 4 males)
* skill types and skill level (so correct combination of skills and skill levels)
* bunch of other rules and stats
At first I brute forced it, but didn't work very well, then with a few tweaks I used a simulated annealing algorithm which worked perfectly. I believe genetic algorithms can solve the same problems like that though.