8

From what I understand, genetic algorithms try out multiple variations and evaluate the fitness of each variation. Then they select the best variations, change them a bit and continue the process with the next generation.

But what if we have unlimited computation resources? Can we then just try out all possible variations and evaluate their fitness without resorting to the complex process of breeding new generations? In other words, are genetic algorithms only needed when computation is expensive and when a brute-force method is impossible? Or do they add other benefits as well?

Improve this question
2
  • 1
    I flagged this as belonging on Stackoverflow, but in my opinion it belongs on the Computer Science site (which there is not an option for in the flagging wizard). (But I still upvoted; interesting question!)
    – Patrick M
    Mar 20, 2014 at 16:10
  • 5
    If you have infinite memory and infinitely fast computation, you can just generate all possible states of the system, then evaluate every state and pick the ideal ones, or conclude that none of the possible states are satisfactory. "Infinite" makes the whole question kind of pointless IMO. Well, except if problem space is infinite too, but then we're quite far removed from anything a "programmer" might do.
    – hyde
    Mar 20, 2014 at 16:51

4 Answers 4

Reset to default
14

Genetic algorithms are basically a guided trial-and-error methodology. The only advantage I can think of for a GA over a exhaustive search is that since GA optimizes a fitness function in steps, you might get to an optimal solution faster, because the GA will favor solutions that are incrementally better. An exhaustive search that's guaranteed to find a solution might go the long way around.

  • If "computation resources" means CPU but not memory, then the GA gene pool might have a smaller memory footprint, requiring less memory.

  • On the other hand, because of hill climbing, a GA might get stuck on a local maximum & any mutations might not be sufficient to shake it loose.

  • Also, the search time for GA grows exponentially with the size of the input, so an exhaustive search may end up being faster after all, depending on the size of the space you're searching, and if you can constrain the size of the space by excluding possibilities.

...

Lately I've been thinking about GAs in terms of "entropy per second" and measuring the progress of my GA as a measure of how many distinct possibilities it runs through per second. Then I can compare that to the total entropy of the problem space. If a brute force search can beat that entropy per second with parallelization or fast processors, then a GA's "best score" isn't any better than a discovered "best score".

But I've just been noodling that over; I haven't actually instrumented a GA that way yet.

(Entropy is ln(N) for N possible states, or ln(N) - sum(n * ln(n) for all n) / N where n is the possible ways to achieve one result out of N possible outcomes.)

Interesting question :)

Improve this answer
5
  • 1
    Doesn't this entropy question basically boil down to "GAs often repeat states and brute force never does"? The way I tend to think about it as that a search algorithm defines and is defined by a permutation over the solution space. In short, a search algorithm is nothing more than the order in which it visits the points (modulo some overhead due to repeated evalutions). The NFL theorems make perfect sense then -- I can always construct a problem for which my algorithm will encounter the optimum sooner than yours and vice versa.
    – deong
    Mar 20, 2014 at 9:15
  • 1
    @deong In many cases, better states, or even optimum states, may be rejected occasionally (e.g. non-deterministic systems), so it may be necessary to search cases repeatedly.
    – resgh
    Mar 20, 2014 at 10:44
  • 1
    I'd say there's a bit more to it than just this; firstly, while the question presupposes "unlimited computation resources", GAs are typically used where exhaustive search is completely infeasible (we're talking "wait for the universe to end" infeasible here, which you approach rapidly with any interesting problems). Secondly, GAs have a crossover operator, in addition to plain old mutation; for certain types of problems (NFL holding), this is a very good heuristic, and far better than exhaustive search. The rest, I'd largely agree with.
    – Daniel B
    Mar 20, 2014 at 12:38
  • 4
    GA's are generally not used for finding optimal solutions. They're for finding reasonable solutions given some limited amount of time.
    – Cruncher
    Mar 20, 2014 at 13:26
  • 1
    Simulated Annealing is a variation of Genetic Algorithm which addresses the local maxima/minima problem very effectively.
    – recursion.ninja
    Mar 20, 2014 at 14:35
6

Yes, if computation were free, then you wouldn't need genetic algorithms at all. But remember that this is a huge, huge "if" that none of us will ever live to see!

Still, since you're asking... if computation were infinitely fast, there would be no reason whatsoever not to apply the simplest brute-force combinatorial generate-and-test sledgehammer to a problem. Every question that can be answered with a finite set of information (i.e. a constraint satisfaction problem in the loosest possible sense of that term, which is quite loose indeed) would be instantly solvable; hill climbing, heuristics and all the clever simplifications that we now use to build e.g. a world-class chess engine would simply not be necessary.

Put another way, if computation approaches infinite speed, the decision which approach to use becomes founded on how hard it is to write the computer program to be executed, not how long it takes to actually execute; and that means that it simply isn't worthwhile to invent a more complicated algorithm when the simplest possible will also work and run in the same time.

Arguably, computation has indeed been moving in this direction, but again, remember, that we aren't quite there yet, and probably never will be. (Unless the quantum computer is perfected, of course.)

Improve this answer
2
  • 3
    Even if quantum computers are perfected, we suspect (but don't yet know for sure) that NP-Complete is not a subset of BQP. If true, this means that the class of problems solvable by a quantum computer with high probability in polynomial time does not include the NP-hard optimization problems that one would generally use a GA for.
    – deong
    Mar 20, 2014 at 9:11
  • 1
    There's much bigger consequence with infinite computation speed... For example, all recognizable problems now become decidable. Yay for the halting problem!
    – Cruncher
    Mar 20, 2014 at 13:30
3

The problem with infinitely fast computations is that they infinitely fast cover a state space which is larger than the information limit of our known universe. You mentioned "brute force", however consider that brute forcing chess for example, can produce an output that exceeds in size the number of atoms in the universe.

Taking the example of chess further, as you brute force chess, you have to whittle down the number of chess board combinations you consider and you will have to make a decision which states to keep, and which states to discard - so indeed selective algorithms, such as genetic algorithms, will forever be necessary.

Improve this answer
3
  • 1
    Well, unless weird physics like closed timelike curves (near the end) turn out to work and can be exploited for general-purpose computation.
    – user7043
    Mar 20, 2014 at 12:26
  • Actually GA is not good at all for chess. Heuristic pruning, yes
    – Konrad Morawski
    Mar 20, 2014 at 14:25
  • Reminds me of this story... The first time I read it, I was confused why writing a search routine took a long time -- it took me a while to realize that the "search" aspect was different from the "simulation" aspect.
    – Pandu
    Mar 20, 2014 at 15:54
2

If by "unlimited computation resources" you mean that your algorithm would take 0 time and that memory is unlimited and electricity is of no concern, I would say the only algorithm to use would be a brute force algorithm that tries every possible input and is guaranteed to find the very best one. If you are referring to unlimited memory but a possible difference in time required, then a genetic algorithm might be preferable because it might come to a solution faster than a brute force algorithm. But the genetic algorithm's solution might not be optimal, so depending on the context and your requirements you might still prefer the brute force method.

Given that unlimited computation resources is not possible, the question at first seemed like idle speculation. But as we get more and more computational power, the question becomes more relevant because we may not need genetic algorithms in an age of enormous supercomputers. However, I have noticed that even as computers become more powerful, we keep asking them to do harder and harder computations with more and more data. So in the end, I think genetic algorithms will be with us for the foreseeable future and will be used even when a lot of computing power is available.

However, if truly unlimited computation resources ever became available, a lot more would change than whether or not to use genetic algorithms.

Improve this answer
1
  • Along the lines of "not needing better algorithms" or what have you in the future because our machines are so powerful: I often think of tiny optimizations that were made in early CPUs like pipelining. It would seem trivial for us to gain a few extra clock cycles nowadays, but those cycles add up. I think that it's crucial to keep making these little optimizations to help propel us towards super-fast computers in the future. Without them, we'd only have kinda-fast computers.
    – DLeh
    Mar 20, 2014 at 17:46

Your Answer

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

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