6
$\begingroup$

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.

$\endgroup$
5
  • $\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 '16 at 17:58
  • $\begingroup$ This question does not contain nearly enough information to be answerable. $\endgroup$
    – Raphael
    Aug 17 '16 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 '16 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 '16 at 0:22
  • $\begingroup$ If the search space is truly unstructured then no algorithm will work besides brute force. $\endgroup$
    – user253751
    Aug 18 '16 at 0:36
9
$\begingroup$

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.

$\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.