6
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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:

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! I hope you like it here. We have plenty of other unanswered questions about genetic algorithms which might benefit from yoru knowledge. $\endgroup$ – David Richerby Apr 22 '16 at 17:08
  • $\begingroup$ @DavidRicherby Thank you. I'll take a look for sure, perhaps there's something I'm able to answer. $\endgroup$ – manlio Apr 23 '16 at 10:03

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.