4 ms·

Are there theoretical reasons people use genetic algorithms for problems like this? It seems like you lose any local knowledge that something like annealing or

Are there theoretical reasons people use genetic algorithms for problems like this? It seems like you lose any local knowledge that something like annealing or stochastic gradient descent type algorithms use, but it's not clear to me that there are many advantages of using it versus some sort of random sampling. I guess in the case where your merit function is decomposable as, for example, the product or sum of a number of lower dimensional functions then it makes sense - but if that's true then I would think there would also be other approaches that would work even better.That is, if genetic algorithms work better than random search then your problem has some structure that would make it amenable to techniques that explicitly take advantage of that structure, thus performing even better.

sago 11y ago
You don't lose local knowledge, no. You're basically doing a bunch of parallel stochastic hill-climbings that can share information. In fact, with suitable parameters, a GA can reduce to a stochastic hill climber. You're right that the problem structure is key. There's a key theorem called the No Free Lunch Theorem for Search which says that will always be the case. But on search problems with many related local maxima, evolution will often outperform a series of stochastic gradient ascents, because the information in one hill can be applied to another. Of course, search and knowledge are always two sides of the same coin. The less knowledge you encode, the more search you'll have to do. But GAs allow you to encode knowledge too, in their operators, particularly. There's been quite a bit of work done on the kinds of fitness landscapes that evolutionary algorithms are better suited for. [NB: Used 'ascent' terminology to avoid confusion - it's a convention only, of course, energy minimization or fitness maximization]
- TTPrograms 11y ago
  Thank you, very good points! If you have the time to suggest some references I'd greatly appreciate it :)

sago 11y ago

You don't lose local knowledge, no. You're basically doing a bunch of parallel stochastic hill-climbings that can share information. In fact, with suitable parameters, a GA can reduce to a stochastic hill climber. You're right that the problem structure is key. There's a key theorem called the No Free Lunch Theorem for Search which says that will always be the case. But on search problems with many related local maxima, evolution will often outperform a series of stochastic gradient ascents, because the information in one hill can be applied to another. Of course, search and knowledge are always two sides of the same coin. The less knowledge you encode, the more search you'll have to do. But GAs allow you to encode knowledge too, in their operators, particularly. There's been quite a bit of work done on the kinds of fitness landscapes that evolutionary algorithms are better suited for. [NB: Used 'ascent' terminology to avoid confusion - it's a convention only, of course, energy minimization or fitness maximization]

TTPrograms 11y ago
Thank you, very good points! If you have the time to suggest some references I'd greatly appreciate it :)