How to identify when to use Genetic Algorithm/Programming

Question

I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem.

TSP is basically a permutation/combination problem, and I can understand how GA helps to narrow down to the solution.

As far as I see GA is helpful in finding solution to

1. similar permutation/combination problems and
2. problems like pattern recognition.

Where/What are the other problem areas where GA could be applied and How(just provide a simple explanation) and What/Where GA can not be applied?

One case where I think GA can not applied are where there is no patterns, like Coin-Toss-Guess-Heads-Or-Tails Program, where outcome is purely luck.

Note: I am not looking for practical uses like printing circuit board or NLP. I am looking for what problems GA solves? or How to recognize that GA will help solve a certain problem instead of writing a complex algorithm.

Like TSP is a permutation/combination problem where possible solution could end up in 2.4 billion or more, and finding the right answer would be nearly impossible, Hence GA(or other optimization algorithm like simulated annealing) is useful in finding an optimal solution.

Answer 1

The key point in deciding whether or not to use genetic algorithms for a particular problem centers around the question:

what is the space to be searched?

If that space is well-understood and contains structure that can be exploited by special-purpose search techniques, the use of genetic algorithms is generally computationally less efficient. If the space to be searched is not so well understood and relatively unstructured, and if an effective GA representation of that space can be developed, then GAs provide a surprisingly powerful search heuristic for large, complex spaces.

(De Jong, Machine Learning, 1990 nr 5, pg. 351)

Here a key point is what is an effective GA representation.

GA initially detects biases in low-order schemas and converges on this part of the search space. Over time, biases in higher-order schemas are detected by combining information from low-order schemas (via crossover) and eventually GA converges (at least according to the building blocks hypothesis).

Situations in which lower-order schemas give misleading information to the GA about the probable fitness of higher-order schemas are said deceptive.

Most efforts at characterizing the difficulty of problems for GA have concentrated on deception, but there are other factors:

• the presence of multiple conflicting solutions or partial solutions
• the amount of information from lower-order building blocks (not how much this information is misleading)
• sampling error
• the number of local optima in the landscape ...

A general relation between a given problem's structure and the expected GA performance on that problem is a very open area of research (actually it's not even clear what is the relation between the degree of deception in a problem and the problem's difficulty for the GA).

In general GA is more suited to find good solutions quickly than to finding the absolute best solution to a problem.

Some references you could find interesting are:

• What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation by Stephanie Forrest and Melanie Mitchel (Machine Learning 1993)
• Fitness distance correlation as a Measure of Problem Difficulty for Genetic Algorithms by Terry Jones and Stephanie Forrest
• Dealings with Problem Hardness in Genetic Algorithms by Stjepan Picek and Marin Golub (2009)