7
$\begingroup$

In the field of Optimization and Operations Research : Are there "Types" any Problems where Evolutionary Algorithms (significantly) Outperform Non-Evolutionary Algorithms?

For instance:

  • Advancements in Machine Learning has shown us that problems that have differentiable "objective functions" (i.e. the function being optimized) - even in instances where these "objective functions" are high dimensional, non-convex, complex and noisy - they are generally best handled using some variant of the Gradient Descent Algorithm.

  • However, there are still some cases that even when the "objective function" is differentiable - if for some reason evaluating derivatives of the "objective function" are quite time consuming (e.g. high dimensional functions), Evolutionary Algorithms (e.g. Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing) offer advantages in such instances.

  • Advancements in Machine Learning has also shown us that Evolutionary Algorithms are sometimes preferred for certain types problems such as "games", in which optimal strategies are developed by mutating and combining random strategies according to their performance with respect to some target (e.g. https://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies , https://www.youtube.com/watch?v=OGHA-elMrxI)

  • In the case of discrete combinatorial optimization problems (where the "objective function" is non-differentiable), Evolutionary Algorithms still offer strong advantages.

My Question: With all this being said, are there any particular "types" of problems where Evolutionary Algorithms are considered the "gold standard" for optimizing? Or in general, are there no such "types" of problems where Evolutionary Algorithms present clear advantages?

$\endgroup$

2 Answers 2

9
$\begingroup$

I don't think that there are any particular problem types where evolutionary algorithms are known to outperform all other metaheuristics or problem-specific heuristics. Looking specifically at genetic algorithms, I seem to recall reading a paper by David Goldberg in the 1980s (when GAs were fairly new) in which he stressed the importance of defining chromosomes in a way that makes it likely that crossover operations on pairs of good solutions will retain a significant amount of what makes them good. (I'm paraphrasing here, so any sloppiness is my fault, not his.) That may make GAs poor choices for some problems, either because there is no good way to express solutions as chromosomes (which I suspect would be difficult to prove) or because there is no obvious good way to do it (meaning the user is likely to use a representation that more or less reduces the GA to random search).

$\endgroup$
6
$\begingroup$

They are currently used where "the best" is still under debate.

This paper about detecting blood vessels in the eye is a good example. I'm heavily simplifying but there are multiple fitness functions used since there is no agreement on what "the best" is. Of all the algorithms you mentioned, genetic algorithms would likely be the easiest to adapt to use multiple fitness functions.

As for it being the "gold standard" anywhere - problems that are fuzzy generally don't have gold-standards. It'll always be - good enough until we understand more. If you can articulate "the best" then there are much faster ways of finding a good functional fit. As you point out, game AI tends to be a popular choice - likely because luck plays some role in almost all games.

They also are a black box, and there is no certainty they found the best or even the right answer. From a business perspective people in charge like to have better answers than "the computer said it was right."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.