My search space is discrete and in the order of $10^{1360}$, with a probably very complex fitness surface. Is it hopeless to attempt to use GA for such a problem? One fitness evaluation could take 1-3 minutes per candidate solution.

  • $\begingroup$ Thanks for the comment. One fitness evaluation is for one solution, not a whole generation. I edited to make it clear. $\endgroup$
    – romanbird
    Aug 17, 2016 at 17:58
  • $\begingroup$ This question does not contain nearly enough information to be answerable. $\endgroup$
    – Raphael
    Aug 17, 2016 at 19:44
  • $\begingroup$ You are saying that computing the fitness function for a single element in a single generation run takes 1-3 minutes? I.e. a single generation takes a few hours? $\endgroup$
    – Bakuriu
    Aug 17, 2016 at 20:25
  • $\begingroup$ Not an answer to your question, but I hope still useful. There is a branch of search algorithms based on Bayesian methods. Some of these algorithms are targeted at search problems with long computation time and even may take the time necessary to evaluate a function into account when considering which parts of the space to explore to get best improvements quickly. See e.g. cs.ubc.ca/~hutter/nips2011workshop/papers_and_posters/… $\endgroup$
    – liori
    Aug 18, 2016 at 0:22
  • $\begingroup$ If the search space is truly unstructured then no algorithm will work besides brute force. $\endgroup$ Aug 18, 2016 at 0:36

1 Answer 1


No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on.

There is no good theory to know whether GA will work or not. Ultimately, all you can do is try it and see.

As a side note: Generally speaking, for most problems, other approaches tend to do better than GA. This is not a theorem; it's just experience / a rule of thumb that seems to often hold.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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